Design and implementation of parallel genetic algorithm for cutting stock of circular parts

doi:10.11772/j.issn.1001-9081.2019081397

Abstract

Abstract:

For the cutting stock problem of circular parts which is widely existed in many manufacturing industries， a new parallel genetic algorithm for cutting stock was proposed to maximize the material utilization within a reasonable computing time， namely Parallel Genetic Blanking Algorithm （PGBA）. In PGBA， the material utilization rate of cutting plan was used as the optimization objective function， and the multithread was used to perform the genetic manipulation on multiple subpopulations in parallel. Firstly， a specific individual coding method was designed based on the parallel genetic algorithm， and a heuristic method was used to generate the individuals of population to improve the search ability and efficiency of the algorithm and avoid the premature phenomena. Then， an approximate optimal cutting plan was searched out by adaptive genetic operations with better performance. Finally， the effectiveness of the algorithm was verified by various experiments. The results show that compared with the heuristic algorithm proposed in literature， PGBA takes longer computing time， but has the material utilization rate greatly improved， which can effectively improve the economic benefits of enterprises.

Key words: cutting stock of circular parts, genetic algorithm, parallel computing, heuristic method, dynamic programming method

摘要：

针对制造行业中的圆片下料问题，为了在合理的计算时间内使材料的利用率尽可能高，提出并行遗传下料算法（PGBA），以下料方案的材料利用率作为优化目标函数，将下料方案作为个体，采用多线程的方式对多个子种群并行进行遗传操作。首先，在并行遗传算法的基础上设计特定的个体编码方式，采用启发式方法生成种群的个体，以提高算法的搜索能力和效率，避免早熟现象的发生；然后，采用性能较好的遗传算子进行自适应的遗传操作，搜索出一种近似最优的下料方案；最后，通过多种实验验证算法的有效性。结果表明，与启发式算法相比，PGBA的计算时间有所增加，但材料利用率得到了较大的提高，能有效提高企业的经济效益。

关键词: 圆片下料, 遗传算法, 并行计算, 启发式方法, 动态规划方法

CLC Number:

TP391

Zhiyang ZENG, Yan CHEN, Ke WANG. Design and implementation of parallel genetic algorithm for cutting stock of circular parts[J]. Journal of Computer Applications, 2020, 40(2): 392-397.

曾志阳, 陈燕, 王珂. 圆片下料并行遗传算法的设计与实现[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 392-397.

Figures/Tables 11

Fig. 1 Layout diagrams of X and Y directions

Fig. 2 Crossover of two points and two directions

Fig. 3 Mutation of two points and two directions

Tab. 1 Relevant parameters for random examples

参数	范围	参数	范围	参数	范围
$d i$	100~500	$m$	3~6	$b i$	500~3 000

Tab. 1 Relevant parameters for random examples

参数	范围	参数	范围	参数	范围
$d i$	100~500	$m$	3~6	$b i$	500~3 000

Fig. 4 Average utilization rate of different evolutionary generations

Fig. 5 Average utilization rate of different population sizes

Tab. 2 Parameters setting for examples with different scales

算例	$d i$	$m$	$b i$
1	$100 ~ 500$	$3 ~ 6$	$500 ~ 3 000$
2	$100 ~ 500$	$6 ~ 8$	$1 000 ~ 3 000$
3	$100 ~ 500$	$8 ~ 10$	$3 000 ~ 5 000$
4	$100 ~ 500$	$10 ~ 12$	$5 000 ~ 7 000$

Tab. 2 Parameters setting for examples with different scales

算例	$d i$	$m$	$b i$
1	$100 ~ 500$	$3 ~ 6$	$500 ~ 3 000$
2	$100 ~ 500$	$6 ~ 8$	$1 000 ~ 3 000$
3	$100 ~ 500$	$8 ~ 10$	$3 000 ~ 5 000$
4	$100 ~ 500$	$10 ~ 12$	$5 000 ~ 7 000$

Tab. 3 Running results comparison of examples with different scales

算例	平均利用率/%		并行后平均利用率的变化/%	运行时间/s		并行后缩短的运行时间/s
算例	并行	串行	并行后平均利用率的变化/%	并行	串行	并行后缩短的运行时间/s
1	67.30	67.19	0.11	19.30	32.11	12.81
2	69.91	69.87	0.04	34.82	62.03	27.21
3	68.70	68.64	0.06	56.24	100.78	44.54
4	70.04	69.92	0.12	85.75	160.04	74.29

Tab. 4 Comparison of cutting results of two algorithms

算法	$S$ /m²	$U L$ /%	$T$ /s
$Δ$	1 738	+3.21	+30.43
本文算法	33 650	65.24	36.55
文献［6］算法	35 388	62.03	6.12

Tab. 4 Comparison of cutting results of two algorithms

算法	$S$ /m²	$U L$ /%	$T$ /s
$Δ$	1 738	+3.21	+30.43
本文算法	33 650	65.24	36.55
文献［6］算法	35 388	62.03	6.12

Tab. 5 Relevant parameters of random examples

参数	范围	参数	范围	参数	范围
$d i$	100~500	$m$	8~10	$b i$	3 000~5 000

Tab. 5 Relevant parameters of random examples

参数	范围	参数	范围	参数	范围
$d i$	100~500	$m$	8~10	$b i$	3 000~5 000

Tab. 6 Comparison of cutting results of two algorithms for large-scale examples

算法	$S$ /m²	$U L$ /%	$T$ /s
$Δ$	1 045	+1.25	+40.43
本文算法	56 313	69.04	57.55
文献［6］算法	57 358	67.79	14.50

Tab. 6 Comparison of cutting results of two algorithms for large-scale examples

算法	$S$ /m²	$U L$ /%	$T$ /s
$Δ$	1 045	+1.25	+40.43
本文算法	56 313	69.04	57.55
文献［6］算法	57 358	67.79	14.50

References 14

1	崔耀东.计算机排样技术及其应用［M］.北京：机械工业出版社，2004： 7-9. 10.7763/ijke.2015.v1.17
	CUI Y D. Computer Layout Technology and Its Application［M］. Beijing： China Machine Press， 2004： 7-9. 10.7763/ijke.2015.v1.17
2	秦旭辉.圆形件剪切下料的排样研究［D］.长春：吉林大学， 2014：1-3.
	QIN X H. Layout research of circular piece under the way of blanking［D］. Changchun： Jiling University， 2014： 1-3.
3	杨萌. 布局问题NP难性质的传递路线研究［D］.北京：北京交通大学， 2016： 3-5. 10.18552/2016/scmt4s312
	YANG M. Research on proof transmit path about NP-hardness of cutting and packing problems［D］. Beijing： Beijing Jiaotong University， 2016： 3-5. 10.18552/2016/scmt4s312
4	侯桂玉，崔耀东，黄少丽，等.一种求解圆形件下料问题的启发式算法［J］.计算机工程，2010，36（13）：227-229. 10.3969/j.issn.1000-3428.2010.13.081
	HOU G Y， CUI Y D， HUANG S L， et al. Heuristic algorithm for cutting stock problem of circular item［J］. Computer Engineering， 2010， 36（13）： 227-229. 10.3969/j.issn.1000-3428.2010.13.081
5	陈燕，谢琪琦，刘咏，等.圆形件下料顺序分组启发式算法的设计与实现［J］.图学学报，2017，38（1）：5-9. 10.11996/JG.j.2095-302X.2017010005
	CHEN Y， XIE Q Q， LIU Y， et al. The cutting stock problem of circular items based on sequential grouping heuristic algorithm［J］. Journal of Graphics， 2017， 38（1）： 5-9. 10.11996/JG.j.2095-302X.2017010005
6	王婷婷，崔耀东，陈燕，等.考虑余料生成及利用的圆片下料算法［J］.锻压技术，2019，44（4）：40-47. 10.13330/j.issn.1000-3940.2019.04.007
	WANG T T， CUI Y D， CHEN Y， et al. An algorithm of circular piece cutting stock considering generation and utilization of margin［J］. Forging and Stamping Technology， 2019， 44（4）： 40-47. 10.13330/j.issn.1000-3940.2019.04.007
7	吴阳. 并行遗传退火算法的圆形件下料问题求解［D］. 南宁：广西大学， 2018： 18-26， 30-35.
	WU Y. Parallel genetic annealing algorithm for solving circle piece blanking problems［D］. Nanning：Guangxi University，2018： 18-26， 30-35.
8	许华杰，檀洪森，胡小明.基于自适应遗传算法和多条带策略的排样方法研究［J］.计算机科学，2016，43（4）：274-278， 317. 10.11896/j.issn.1002-137X.2016.4.056
	XU H J， TAN H S， HU X M. Research of packing method based on adaptive genetic algorithm and multi-strip strategy［J］. Computer Science， 2016， 43（4）： 274-278， 317. 10.11896/j.issn.1002-137X.2016.4.056
9	孙佳正，郭骏. 改进的双种群遗传算法在矩形件排样中的应用［J］. 计算机工程与应用， 2018， 54（15）： 139-146. 10.3778/j.issn.1002-8331.1704-0360
	SUN J Z， GUO J. Improved dual population genetic algorithm for rectangle packing［J］. Computer Engineering and Applications， 2018， 54（15）： 139-146. 10.3778/j.issn.1002-8331.1704-0360
10	孟子暄. 基于遗传算法的钣金件下料问题优化研究［J］. 现代工业经济和信息化， 2018 （15）： 24-25. 10.16525/j.cnki.14-1362/n.2018.15.10
	MENG Z X. Research on optimization of sheet metal cutting problem based on genetic algorithm［J］. Modern Industrial Economy and Informationzation， 2018 （15）： 24-25. 10.16525/j.cnki.14-1362/n.2018.15.10
11	李岩，袁弘宇，于佳乔，等. 遗传算法在优化问题中的应用综述［J］. 山东工业技术， 2019（12）： 242-243， 180.
	LI Y， YUAN H Y， YU J Q， et al. Review of genetic algorithm on optimization problems［J］. Shandong Industrial Technology， 2019（12）： 242-243， 180.
12	张立，陈燕，陈秋莲，等. 条带上圆形件的优化排样［J］. 锻压技术， 2018， 43（10）：179-184.
	ZHANG L， CHEN Y， CHEN Q L， et al. Optimized layout of circular pieces on strip［J］. Forging and Stamping Technology， 2018， 43（10）： 179-184.
13	李小莲. 动态规划法的应用分析［J］. 计算机时代， 2019（6）： 53-55. 10.1016/j.comcom.2019.05.023
	LI X L. Analysis of the application of dynamic programming method［J］. Computer Era， 2019（6）： 53-55. 10.1016/j.comcom.2019.05.023
14	CUI Y， TANG T. Parallelized sequential value correction procedure for the one-dimensional cutting stock problem with multiple stock lengths［J］. Engineering Optimization， 2014， 46（10）：1352-1368. 10.1080/0305215x.2013.841903

[1]	Dong LIU, Chenhang LI, Changmao WU, Faxin RU, Yuanyuan XIA. Automatic design of optical systems based on correctable reinforced search genetic algorithm [J]. Journal of Computer Applications, 2024, 44(9): 2838-2847.
[2]	Runlian ZHANG, Mi ZHANG, Xiaonian WU, Rui SHU. Differential property evaluation method based on GPU for large-state cryptographic S-boxes [J]. Journal of Computer Applications, 2024, 44(9): 2785-2790.
[3]	Xuanfeng LI, Shengcai LIU, Ke TANG. Novel genetic algorithm for solving chance-constrained multiple-choice Knapsack problems [J]. Journal of Computer Applications, 2024, 44(5): 1378-1385.
[4]	Lin GAO, Yu ZHOU, Tak Wu KWONG. Evolutionary bi-level adaptive local feature selection [J]. Journal of Computer Applications, 2024, 44(5): 1408-1414.
[5]	Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery [J]. Journal of Computer Applications, 2024, 44(4): 1187-1194.
[6]	Wei SHE, Yang LI, Lihong ZHONG, Defeng KONG, Zhao TIAN. Hyperparameter optimization for neural network based on improved real coding genetic algorithm [J]. Journal of Computer Applications, 2024, 44(3): 671-676.
[7]	Jun LIANG, Zehong HONG, Songsen YU. Image segmentation model based on improved particle swarm optimization algorithm and genetic mutation [J]. Journal of Computer Applications, 2023, 43(6): 1743-1749.
[8]	Bin WANG, Tian XIANG, Yidong LYU, Xiaofan WANG. Adaptive multi-scale feature channel grouping optimization algorithm based on NSGA‑Ⅱ [J]. Journal of Computer Applications, 2023, 43(5): 1401-1408.
[9]	Hairong XUE, Xiaolong HAN. Integrated scheduling considering automated guided vehicle charging strategy based on improved NSGA-Ⅱ [J]. Journal of Computer Applications, 2023, 43(12): 3848-3855.
[10]	Fuqin DENG, Huanzhao HUANG, Chaoen TAN, Lanhui FU, Jianmin ZHANG, Tinlun LAM. Multi-robot task allocation algorithm combining genetic algorithm and rolling scheduling [J]. Journal of Computer Applications, 2023, 43(12): 3833-3839.
[11]	Qian LIU, Yangming ZHANG, Dingsheng WAN. Parallel computing algorithm of grid-based distributed Xin’anjiang hydrological model [J]. Journal of Computer Applications, 2023, 43(11): 3327-3333.
[12]	JIANG Songyan, LIAO Xiaojuan, CHEN Guangzhu. Optimal task scheduling method based on satisfiability modulo theory for multiple processors with communication delay [J]. Journal of Computer Applications, 2023, 43(1): 185-191.
[13]	Jingwen CAI, Yongzhuang WEI, Zhenghong LIU. GPU-based method for evaluating algebraic properties of cryptographic S-boxes [J]. Journal of Computer Applications, 2022, 42(9): 2750-2756.
[14]	Houming FAN, Shuang MU, Lijun YUE. Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion [J]. Journal of Computer Applications, 2022, 42(7): 2281-2291.
[15]	Yanfei LIU, Zheng PENG, Yihui WANG, Zhong WANG. PID parameter tuning of brushed direct-current motor based on improved genetic algorithm [J]. Journal of Computer Applications, 2022, 42(5): 1634-1641.