Computer Science ›› 2020, Vol. 47 ›› Issue (7): 166-170.doi: 10.11896/jsjkx.190500014

• Artificial Intelligence • Previous Articles     Next Articles

Pyramid Evolution Strategy Based on Differential Evolution for Solving One-dimensional Cutting Stock Problem

HOU Gai, HE Lang, HUANG Zhang-can, WANG Zhan-zhan, TAN Qing   

  1. School of Science,Wuhan University of Technology,Wuhan 430070,China
  • Received:2019-05-05 Online:2020-07-15 Published:2020-07-16
  • About author:HOU Gai,born in 1993,postgraduate.Her main research interests include swarm intelligent computation and so on.
    HE Lang,born in 1974,Ph.D,associate professor.His main research interests include evolutionary computation and so on.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61672391)

Abstract: One-dimensional cutting stock problem is a classic NP-hard problem in combinatorial optimization,which is widely used in mechanical manufacturing and engineering applications.It is difficult for traditional swarm intelligence algorithm to ba-lance the contradictions of mining and exploration,competition and cooperation between individuals and populations with in a po-pulation when solving one-dimensional cutting stock problem.On the basis of pyramid evolution strategy,an algorithm based on pyramid evolution strategy and differential evolution is proposed in this paper.The algorithm makes full use of the advantages of the PES algorithm and solves these two contradictions well,but the PES algorithm does not consider the cooperative relationship between the current individual and the optimal individual,it may lead the convergence speed of the algorithm to be slowly.To this end,the mutation and crossover operations of differential evolution are introduced into the accelerating process of PES algorithm,and the invalid individuals are corrected by the repair operator.On the one hand,it is conducive to speed up the convergence speed of the algorithm,on the other hand,it can utilize the differences among individuals and realize the local mining of the area near the individuals in the population,which is beneficial to improve the accuracy of the algorithm.The proposed algorithm is applied to six examples.The experimental results show that the algorithm has high optimization accuracy and convergence speed compared with other eight algorithms,which verifies the feasibility and effectiveness of the algorithm for solving the one-dimensional cutting stock problem.

Key words: Differential evolution, One-dimensional cutting stock problem, Pyramid evolution strategy, Swarm intelligent algorithm

CLC Number: 

  • TP301.6
[1]CHERRI A C,ARENALES M N,YANASSE H H,et al.The one-dimensional cutting stock problem with usable leftovers-A survey [J].European Journal of Operational Research,2014,236(2):395-402.
[2]DELORME M,IORI M,MARTELLO S.Bin packing and cutting stock problems:Mathematical models and exact algorithms [J].European Journal of Operational Research,2016,255(1):1-20.
[3]ALIANO F A,MORETTI A C,PATO M V.A comparativestudy of exact methods for the bi-objective integer one-dimensional cutting stock problem [J].Journal of the Operational Research Society,2018,69(1):91-107.
[4]CUI Y,SONG X,CHEN Y,et al.New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers [J].Journal of the Operational Research Society,2017,68(3):269-280.
[5]ZHU S L.The research on optimization algorithms for one-dimensional cutting stock problems [D].Wuhan:Huazhong University of Science and Technology,2013.
[6]GRADISˇARM,CESAR M,TOMAT L.One-dimensional cutting stock optimisation by suborders [J].Tehnicˇki Vjesnik-Tehnical Gazette,2018,25(2):474-480.
[7]POLDI K,ARENALES M.Heuristics for the one-dimensionalcutting stock problem with limited multiple stock lengths [J].Computers & Operations Research,2009,36(6):2074-2081.
[8]GUAN W L,GONG J,XUE H T.A hybrid heuristic algorithm
for one-dimensional cutting stock problem[J].Machinery Design &Manufacture,2018(8):237-239.
[9]TIEN N D.A genetic algorithm approach for large-scale cutting stock problem[M]//Advances in Intelligent Systems and Computing.Singapore:Springer,2018:796-805.
[10]EVTIMOV G,FIDANOVA S.Ant colony optimization algo-rithm for 1D cutting stock problem[M]//Advanced Computing in Industrial Mathematics.Cham:Springer,2017:25-31.
[11]ASVANY T,AMUDHAVEL J,SUJATHA P.One-dimensional cutting stock problem with single and multiple stock lengthsusing DPSO[J].Advances and Applications in Mathematical Sciences,2017,17(1):147-163.
[12]CHENG C,BAO L.An improved artificial fish swarm algorithm to solve the cutting stock problem[C]//International Symposiumon Neural Networks.Cham:Springer,2018:165-172.
[13]SHEN X J,YANG J C,YING W Q,et al.Adaptive general particle swarm optimization for one-dimension cutting stock problem[J].Journal of South China University of Technology(Natural Science Edition),2007,35(9):113-117.
[14]LI B,HE F.Improved hybrid genetic algorithm for solving one-dimensional cutting stock problem [J].Journal of Inner Mongolia University (Natural Science Edition),2014,45(3):245-250.
[15]TAN Q.Swarm intelligent evolution strategy based on pyramid structure [D].Wuhan:Wuhan University of Technology,2018.
[16]TANG H H,PENG S J,WANG Z Z.Swarm intelligent evolution strategy based on pyramid structure for solving mixed integer programming problems [J].Application Research of Computers,2020,37(5).
[17]LI H,JIANG D Y,HUANG Z C,et al.Method for solving color images quantization problem [J].Journal of Computer Applications,2019,39(9):2646-2651.
[18]LI X,MA S,HU J.Multi-search differential evolution algorithm[J].Applied Intelligence,2017,47(1):231-256.
[19]ZOU H F,XIE C W,ZHOU Y P,et al.Group search optimization with opposition-based learning and differential evolution [J].Computer Science,2018,45(S1):124-129.
[20]AL-BETAR M A,AWADALLAH M A,FARIS H,et al.Bat-inspired Algorithms with Natural Selection mechanisms for Global optimization[J].Neurocomputing,2018,273:448-465.
[1] LI Dan-dan, WU Yu-xiang, ZHU Cong-cong, LI Zhong-kang. Improved Sparrow Search Algorithm Based on A Variety of Improved Strategies [J]. Computer Science, 2022, 49(6A): 217-222.
[2] LIU Bao-bao, YANG Jing-jing, TAO Lu, WANG He-ying. Study on Prediction of Educational Statistical Data Based on DE-LSTM Model [J]. Computer Science, 2022, 49(6A): 261-266.
[3] XU Ru-li, HUANG Zhang-can, XIE Qin-qin, LI Hua-feng, ZHAN Hang. Multi-threshold Segmentation for Color Image Based on Pyramid Evolution Strategy [J]. Computer Science, 2022, 49(6): 231-237.
[4] ZHANG Qiang, HUANG Zhang-can, TAN Qing, LI Hua-feng, ZHAN Hang. Pyramid Evolution Strategy Based on Dynamic Neighbor Lasso [J]. Computer Science, 2021, 48(6): 215-221.
[5] YU Jia-shan, WU Lei. Two Types of Leaders Salp Swarm Algorithm [J]. Computer Science, 2021, 48(4): 254-260.
[6] ZHANG Zhi-qiang, LU Xiao-feng, SUI Lian-sheng, LI Jun-huai. Salp Swarm Algorithm with Random Inertia Weight and Differential Mutation Operator [J]. Computer Science, 2020, 47(8): 297-301.
[7] LI Zhang-wei,WANG Liu-jing. Population Distribution-based Self-adaptive Differential Evolution Algorithm [J]. Computer Science, 2020, 47(2): 180-185.
[8] WANG Xuan, MAO Ying-chi, XIE Zai-peng, HUANG Qian. Inference Task Offloading Strategy Based on Differential Evolution [J]. Computer Science, 2020, 47(10): 256-262.
[9] DONG Ming-gang,LIU Bao,JING Chao. Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation [J]. Computer Science, 2019, 46(7): 224-232.
[10] XIAO Peng, ZOU De-xuan, ZHANG Qiang. Efficient Dynamic Self-adaptive Differential Evolution Algorithm [J]. Computer Science, 2019, 46(6A): 124-132.
[11] NI Hong-jie, PENG Chun-xiang, ZHOU Xiao-gen, YU Li. Differential Evolution Algorithm with Stage-based Strategy Adaption [J]. Computer Science, 2019, 46(6A): 106-110.
[12] ZHANG Yu-pei, ZHAO Zhi-jin, ZHENG Shi-lian. Cognitive Decision Engine of Hybrid Learning Differential Evolution and Particle Swarm Optimization [J]. Computer Science, 2019, 46(6): 95-101.
[13] ZHAO Yun-tao, CHEN Jing-cheng, LI Wei-gang. Multi-objective Grey Wolf Optimization Hybrid Adaptive Differential Evolution Mechanism [J]. Computer Science, 2019, 46(11A): 83-88.
[14] YANG Xiao-hua, GAO Hai-yun. Improved Bayesian Algorithm Based Automatic Classification Method for Bibliography [J]. Computer Science, 2018, 45(8): 203-207.
[15] YU Wei-wei,XIE Cheng-wang. Hybrid Particle Swarm Optimization with Multiply Strategies [J]. Computer Science, 2018, 45(6A): 120-123.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!