求解平衡约束圆形Packing问题的快速启发式并行蚁群算法  

A Fast Heuristic Parallel Ant Colony Algorithm for Circles Packing Problem with the Equilibrium Constraints

作　　者：黎自强[1] 田茁君[1] 王奕首[2] 岳本贤[3] 

机构地区：[1]教育部智能计算与信息处理重点实验室(湘潭大学),湖南湘潭411105 [2]工业装备结构分析国家重点实验室(大连理工大学),辽宁大连116024 [3]大连理工大学计算机科学与技术学院,辽宁大连116024

出　　处：《计算机研究与发展》2012年第9期1899-1909,共11页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61272294;51005034;61040009;61070088);国家科技支撑计划基金项目(2012BAF10B04);湖南省自然科学基金项目(11JJ6050);湖南省教育厅重点科学研究项目(11A120);湖南省重点学科建设基金项目(湘教发[2012]1号);辽宁省和湘潭大学博士启动基金项目(20101019;09QDZ18)

摘　　要：带平衡约束圆形Packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆数不超过3的布局方案).然后将蚁群优化与并行搜索相结合,使种群个体快速收敛到最优解或迭代出存在少量干涉的近似最优解(1～3个相交圆).若为后者,则基于物理模型用最速下降法将其快速调整成最优解.所采用的启发式方法、并行蚁群搜索机制和快速调整策略有机结合提高了算法的搜索精度和效率.数值实验表明该算法在性能指标上优于已存在的算法.Circles packing problem with equilibrium constraints is difficult to solve due to its NP-hard nature. A fast heuristic parallel ant colony algorithm is proposed for this problem. Both circular radius and mass are taken as the probability factors of the roulette selection and the circles are located by arranging round existing circles in peripheral with counter-clockwise movement. Its diverse population individuals （no more than 3 circles are overlapped in each one） are constructed through the proposed heuristic method. The ant colony optimization combined with parallel search mechanism is adopted to obtain an optimal solution or an approximate optimal solution with 1-3 overlapping circles. The steepest descent method based on physical model is used to adjust the approximate optimal solution into the optimal one without overlapping. The combination of heuristic strategy, ant colony search mechanism in parallel, and fast adjustment strategy can improve the computational precision and efficiency of the proposed algorithm. The experiment results show that the proposed algorithm is superior to the existing algorithms in performance.

关 键 词：平衡约束 圆形PACKING问题 蚁群算法 物理模型 启发式方法 并行算法 

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