摘要
二维矩形Strip Packing问题的约束条件及目标函数与基本型二维矩形Packing问题类似,都是在有限的矩形容器中,有效地摆放各个矩形块,以最大化容器利用率为目标。为了解决这一NP-hard问题,该文在邓见凯、王磊提出的拟人型全局优化算法的基础上进行了深入的算法研究与改进。针对Strip Packing问题特点,提出了QHG(Quasi-Human Group)算法,其核心改进涵盖了多个方面,包括扩充初始点集合、删除和替换评价标准以及扩大邻域空间搜索范围。和单个局部极小值点的迭代相比,对局部极小值点集合进行迭代所生成布局优度更高,跳坑策略用于跳出局部极小值点,将搜索引向有希望的区域,优美度枚举有望进一步提高布局优度。通过这些措施,QHG算法更好地模拟人类决策过程,提高了全局搜索的效率。为评估QHG算法性能,对8组标准问题实例(C组、N组、NT组、CX组、NP组、ZDF组、2sp组、bwmv组)进行了大量实验。实验结果表明,QHG算法生成的布局优度优于当前国际文献中的几种较先进算法,展现了其在Strip Packing问题上的卓越性能。
The constraints and objective function of the two-dimensional rectangular Strip Packing problem are similar to those of the basic two-dimensional rectangular Packing problem in that each rectangular block is effectively placed in a limited rectangular container with the goal of maximizing container utilization.To tackle this famous NP-hard problem,we conduct in-depth algorithm research and achieve significant improvements based on the quasi-human global optimization algorithm proposed by Deng Jiankai and Wang Lei.According to the characteristics of the Strip Packing problem,we propose the QHG(Quasi-Human Group)algorithm,incorporating key enhancements such as enlarging the set of the initial points,deleting and replacing evaluation criteria and expanding the search scope of neighborhood space.Compared with the iteration of a single local minimum point,iterating on a set of local minimum points can generate better configurations.Off-trap procedure is used to jump out of the local minimum point and lead the search into the promising areas.Tree-search procedure is expected to further improve the area usage ratios of the configurations.Through these measures,the QHG algorithm better simulates human decision-making processes so as to generate better configurations.To evaluate the performance of the QHG algorithm,extensive experiments are conducted on 8 sets of standard problem instances(C,N,NT,CX,NP,ZDF,2sp,and bwmv).The experimental results demonstrate that the quality of the configurations generated by the QHG algorithm surpasses several advanced algorithms in the current international literature,highlighting its outstanding performance in addressing the Strip Packing problem.
作者
蔡家尧
王磊
CAI Jia-yao;WANG Lei(School of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China)
出处
《计算机技术与发展》
2024年第7期138-146,共9页
Computer Technology and Development
基金
国家自然科学基金(62271359)。
