一种求解等圆装箱问题的种群算法
A Population Algorithm for Solving the Equal Circle Packing Problem
朱哲彤 1向垚 1赖向京1
作者信息
- 1. 南京邮电大学先进技术研究院 南京 210023
- 折叠
摘要
针对等圆装箱问题,基于圆之间的连接表,论文为基于种群的盆地跳跃算法(Population Basin Hopping)提出了一个新的变种.基于连接表的概念,论文为等圆装箱问题提出了一种解之间的距离函数,并根据该距离函数提出了一种新的种群更新策略.通过在规模小于等于100的标准算例上进行优化实验,对所提算法的性能进行了评估.实验结果表明,该算法在解质量和计算速度方面均胜过了文献中已有的最好算法.
Abstract
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.
关键词
等圆装箱问题/连接表/自适应搜索/种群算法Key words
equal circle packing problem/connectivity table/adaptive search/population algorithm引用本文复制引用
出版年
2024
国家科技期刊平台
NSTL
万方数据