矩形布局优化问题的局部搜索蜂群算法

Artificial bee colony algorithm with local search for rectangle layout optimization

带平衡约束的矩形布局问题属于组合优化问题,当问题规模增大时求解困难。为提高求解效率,设计了一个蜂群算法,通过分析解的分布,提供了基于贪心策略的群体初始化方案,选择了有效的变异算子,将蜂群算法的搜索空间聚焦于最优解可能的区域。另外设计了一个二次局部搜索算法,对解的质量进行进一步提升。在10个公开的案例上与目前性能最好的算法进行了对照,提出的蜂群算法在其中9个较大规模的案例上超过了现有算法。理论分析和实验结果表明,相对于现有算法,所提蜂群算法能明显提高求解效率。

The rectangular layout problem with balance constraints is a combinatorial optimization problem,which is difficult to solve when the problem scale increases.To improve the performance,this paper designed a bee colony algorithm.By analyzing the distribution of solutions,it provided a greedy initialization scheme for the population,selected an effective mutation operator,and limited the search space around the optimal solution.In addition,it designed a local search module to further improve the quality of the solution.On 10 open test cases,the algorithm was compared with the best known existing algorithms,and the performance of the proposed algorithm exceeded the existing algorithms on 9 large-scale cases.The theoretical analysis and experimental results show that the proposed algorithm can significantly improve the efficiency of solution.