摘要
带平衡约束圆形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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2012年第9期1899-1909,共11页
Journal of Computer Research and Development
基金
国家自然科学基金项目(61272294
51005034
61040009
61070088)
国家科技支撑计划基金项目(2012BAF10B04)
湖南省自然科学基金项目(11JJ6050)
湖南省教育厅重点科学研究项目(11A120)
湖南省重点学科建设基金项目(湘教发[2012]1号)
辽宁省和湘潭大学博士启动基金项目(20101019
09QDZ18)
关键词
平衡约束
圆形PACKING问题
蚁群算法
物理模型
启发式方法
并行算法
equilibrium constraint
circles packing problem
ant colony algorithm
physical model
heuristic method
parallel algorithm
