[1]蔡家尧,王磊.二维矩形Strip Packing问题的算法研究与改进[J].计算机技术与发展,2024,34(07):138-146.[doi:10.20165/j.cnki.ISSN1673-629X.2024.0096]
　CAI Jia-yao,WANG Lei.Algorithm Research and Improvement for Optimizing 2D Rectangle Strip Packing Problem[J].,2024,34(07):138-146.[doi:10.20165/j.cnki.ISSN1673-629X.2024.0096]
点击复制

二维矩形Strip Packing问题的算法研究与改进

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
34
期数:
2024年07期
页码:
138-146
栏目:
人工智能
出版日期:
2024-07-10

文章信息/Info

Title:
Algorithm Research and Improvement for Optimizing 2D Rectangle Strip Packing Problem
文章编号:
1673-629X(2024)07-0138-09
作者:
蔡家尧; 王磊
武汉科技大学 计算机科学与技术学院,湖北 武汉 430065
Author(s):
CAI Jia-yao; WANG Lei
School of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China
关键词:
Strip Packing问题; 组合优化; 全局优化; 算法; 拟人
Keywords:
Strip Packing problem; combinatorial optimization; global optimization; algorithm; quasi-human
分类号:
TP301
DOI:
10.20165/j.cnki.ISSN1673-629X.2024.0096
摘要:
二维矩形 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 问题上的卓越性能。
Abstract:
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. Ac-cording 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 ad-vanced algorithms in the current international literature,highlighting its outstanding performance in addressing the Strip Packing problem.

相似文献/References:

[1]鲍娜 张德贤 孙傲冰 王飞.基于改进蚁群算法的网格组合拍卖资源分配[J].计算机技术与发展,2009,(10):149.
　BAO Na,ZHANG De-xian,SUN Ao-bing,et al.Research on Resource Allocation of Combinatorial Auction in Grid Based on Improved Ant Colony Algorithm[J].,2009,(07):149.
[2]光熠 刘心报 程浩.求解车间作业调度问题的一种改进遗传算法[J].计算机技术与发展,2007,(11):171.
　GUANG Yi,LIU Xin-bao,CHENG Hao.An Improved Genetic Algorithm in Job - Shop Scheduling Problem[J].,2007,(07):171.
[3]李林菲 马苗.基于ABC算法的逻辑推理题快速求解方法[J].计算机技术与发展,2011,(06):125.
　LI Lin-fei,MA Miao.Artificial Bee Colony Algorithm Based Solution Method for Logic Reasoning[J].,2011,(07):125.
[4]焉为家 郭雨珍.改进的粒子群算法求解蛋白质结构预测问题[J].计算机技术与发展,2011,(12):109.
　YAN Wei-jia,GUO Yu-zhen.Modified Particle Swarm Optimization Algorithm for Protein Structure Prediction Problem[J].,2011,(07):109.
[5]秦军[],翟钊[]. 基于Hadoop MapReduce的组合服务性能优化研究[J].计算机技术与发展,2016,26(05):61.
　QIN Jun[],ZHAI Zhao[]. Research on Composite Service Performance Optimization Based on Hadoop MapReduce[J].,2016,26(07):61.
[6]颜腾威[],王丽侠[],周杰[],等. 求解CVRP问题的改进和声算法[J].计算机技术与发展,2016,26(09):187.
　YAN Teng-wei[],WANG Li-xia[],ZHOU Jie[],et al. An Improved Harmony Search Algorithm for CVRP[J].,2016,26(07):187.
[7]王建辉,郑光勇,徐雨明.混合人工化学反应优化算法求解 0-1 背包问题[J].计算机技术与发展,2020,30(07):71.[doi:10. 3969 / j. issn. 1673-629X. 2020. 07. 016]
　WANG Jian-hui,ZHENG Guang-yong,XU Yu-ming.Artificial Chemical Reaction Optimization Algorithm for 0-1 Knapsack Problem[J].,2020,30(07):71.[doi:10. 3969 / j. issn. 1673-629X. 2020. 07. 016]
[8]吕成瑶,邵可南,张帅帅,等.生鲜食品冷链物流配送路径优化[J].计算机技术与发展,2020,30(11):168.[doi:10. 3969 / j. issn. 1673-629X. 2020. 11. 031]
　LYU Cheng-yao,SHAO Ke-nan,ZHANG Shuai-shuai,et al.Optimization of Fresh Food Cold Chain Logistics Distribution Route[J].,2020,30(07):168.[doi:10. 3969 / j. issn. 1673-629X. 2020. 11. 031]
[9]邵可南,吕成瑶,张帅帅,等.一种基于冷链低碳物流路径的混合优化算法[J].计算机技术与发展,2021,31(02):27.[doi:10. 3969 / j. issn. 1673-629X. 2021. 02. 005]
　SHAO Ke-nan,LYU Cheng-yao,ZHANG Shuai-shuai,et al.A Hybrid Optimization Algorithm Based on Low-carbon Cold Chain Logistic Route[J].,2021,31(07):27.[doi:10. 3969 / j. issn. 1673-629X. 2021. 02. 005]

更新日期/Last Update: 2024-07-10