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

Solving Congruent Circle Packing Problem Based on Improved Differential Evolution Algorithm

作　　者：路有兵[1,2] 耿焕同[1] 张明[1,2] 刘景发[1] 

机构地区：[1]南京信息工程大学江苏省网络监控中心,江苏南京210044 [2]南京信息工程大学计算机与软件学院,江苏南京210044

出　　处：《计算机与现代化》2012年第6期1-4,22,共5页Computer and Modernization

基　　金：灾害天气国家重点实验室2010年开放课题(2010LASW-A02);江苏省博士后基金资助项目(1001030B)

摘　　要：等圆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.

关 键 词：改进差分进化 等圆PACKING问题 强约束 随机排序选择 有效解空间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]