利用改进的微分进化算法求解带平衡约束的圆形packing问题  

A Modified Differential Evolution Algorithm for Solving Circles Packing Problem with Constraints of Equilibrium

作　　者：刘建[1] 黄文奇[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《信息与控制》2006年第1期103-107,113,共6页Information and Control

基　　金：国家自然科学基金资助项目(10471051);国家973计划资助项目(2004CB318000)

摘　　要：提出了一种改进的微分进化算法(DE)求解二维带平衡约束的圆形pack ing问题.首先,构造出等价的物理模型,定义系统的能量函数,再对能量函数进行全局优化,从而间接得到问题的近似解.其中引入的参数动态调整策略在计算初期维持个体的多样性,后期加快算法的收敛速度,提高了DE算法的性能.最后,对两个算例进行了数值计算,实验结果证明了算法的有效性.此算法思路可推广应用于求解其它类型布局问题.A modified differential evolution algorithm （DE） is presented for solving circles packing problem with constraints of equilibrium in 2-D space. Firstly, the method constructs an equivalent physical model and defines the energy function of the system. Then the DE optimizes the energy function globally and the approximate solution is obtained indirectly. Strategy of adjusting parameters dynamically maintains diversity of the individuals at early stages and expedites convergence speed of the algorithm at latter stages, thus the performance of DE algorithm is improved. Finally, .two examples are computed numerically, and the experiment results show that the algorithm is effective. The strategy in this paper can be applied to solve other layout problems.

关 键 词：微分进化算法 NP难问题 约束布局问题 能量模型 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]