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

作者：黎自强; 田茁君; 王奕首; 岳本贤

来源：Z201209013, 2012, (09): 1899-1909.

• 平衡约束
• 圆形Packing问题
• 蚁群算法
• 物理模型
• 启发式方法
• 并行算法 equilibrium constraint
• circles packing problem
• ant colony algorithm
• physical model
• heuristic method
• parallel algorithm

带平衡约束圆形Packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆数不超过3的布局方案).然后将蚁群优化与并行搜索相结合,使种群个体快速收敛到最优解或迭代出存在少量干涉的近似最优解(1～3个相交圆).若为后者,则基于物理模型用最速下降法将其快速调整成最优解.所采用的启发式方法、并行蚁群搜索机制和快速调整策略有机结合提高了算法的搜索精度和效率.数值实验表明该算法在性能指标上优于已存在的算法.

• 出版日期2012
• 单位工业装备结构分析国家重点实验室; 湘潭大学; 大连理工大学