一种求解等圆装箱问题的种群算法  

A Population Algorithm for Solving the Equal Circle Packing Problem

作　　者：朱哲彤 向垚 赖向京 ZHU Zhetong;XIANG Yao;LAI Xiangjing(Advanced Technology Research Institute of Nanjing University of Posts and Telecommunications,Nanjing 210023)

机构地区：[1]南京邮电大学先进技术研究院,南京210023

出　　处：《计算机与数字工程》2024年第3期641-645,652,共6页Computer & Digital Engineering

基　　金：国家自然科学基金项目(编号:61703213)资助。

摘　　要：针对等圆装箱问题,基于圆之间的连接表,论文为基于种群的盆地跳跃算法(Population Basin Hopping)提出了一个新的变种。基于连接表的概念,论文为等圆装箱问题提出了一种解之间的距离函数,并根据该距离函数提出了一种新的种群更新策略。通过在规模小于等于100的标准算例上进行优化实验,对所提算法的性能进行了评估。实验结果表明,该算法在解质量和计算速度方面均胜过了文献中已有的最好算法。To solve the equal circles packing problem(ECPP),this paper proposes a new variant of population basin hopping(PBH)algorithm based on the connectivity table.In the paper,the connectivity table between circles is used to define the distance function between two packing configurations and then a population updating strategy is designed for the proposed algorithm.The per-formance of the proposed algorithm is assessed on the 100 benchmark instances with N£100,and the experimental results show that the proposed algorithm outperforms the state-of-the-art algorithms in the literature both in terms of solution quality and compu-tational efficiency.

关 键 词：等圆装箱问题 连接表 自适应搜索 种群算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]