利用改进的差分进化算法求解等圆Packing问题

Solving Congruent Circle Packing Problem Based on Improved Differential Evolution Algorithm

等圆Packing问题属于强约束的复杂组合优化问题之一,针对其强约束特点及难点,通过改进传统的差分进化算法,提出一种等圆Packing问题的求解方法。该改进算法特点是将有效解空间加入差分进化的变异约束中,并采用随机排序机制改进差分进化的选择机制。通过多次实验,表明此算法在求解小规模等圆Packing问题上取得的效果与目前所能找到的最优值相差不到0.6%,从而验证了演化计算在求解等圆Packing问题的可行性;与此同时,演化算法具有很好的收敛性,因此在其他强约束的复杂优化问题上将有很好的应用。

Congruent circle packing problem is one of the complex combination optimization problems with strong constraint. Ai- ming at the characteristics and difficulties of strong constraints, this paper proposes a method to solve the problem by improving the traditional differential evolution algorithm. The improved algorithm uses the effective solution space to improve the mutation of differential evolution, and uses the stochastic ranking mechanism to improve the selection of differential evolution. A lot of experi- ments have been done and prove that the result of the proposed algorithm is about less than 1% with the current optimal value, so the evolutionary computation is feasible in solving the congruent circle packing problem. At the same time, evolution algorithm is of good convergence, thus there will be a very good application in other strong constraint complex optimization problems.