高级检索

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

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

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

       

      Abstract: 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.

       

    /

    返回文章
    返回