一种求解排样问题的遗传算法收敛性分析

Convergence Analysis of Genetic Algorithm to Solve the Cutting Problem

遗传算法已经被广泛用于求解排样问题,但是在算法不收敛的情况下,很难有效地找到满意解.因此,在用遗传算法求解排样问题时,有必要研究其算法的收敛性.对求解圆形件排样问题的混合遗传算法,采用概率论的方法,证明了该遗传算法理论上完全收敛于全局最优解.该结论可以进一步应用到其它形状零件的排样问题,并给出了遗传算法求解排样问题的收敛性条件.

Genetic algorithm is widely used to solve the cutting problems.However,it is very difficult to find the satisfactory solution if the algorithm does not converge.Thus it is necessary to study algorithm convergence when we use genetic algorithm.For our previous work on using hybird genetic algorithm to solve circular cutting problems,this paper proves that the algorithm converges completely at the global optimal solution by using the concept of probability.The algorithm convergence is also employed in other cutting problems,and the convergence condition of genetic algorithm is given to solve the cutting problems.