计算机科学 ›› 2020, Vol. 47 ›› Issue (7): 166-170.doi: 10.11896/jsjkx.190500014
侯改, 何朗, 黄樟灿, 王占占, 谈庆
HOU Gai, HE Lang, HUANG Zhang-can, WANG Zhan-zhan, TAN Qing
摘要： 一维下料问题是组合优化中一类经典的NP-hard问题,被广泛用于机械制造及工程应用等领域。针对传统群智能算法在求解该类问题时难以平衡种群内部个体及种群之间开采与探索、竞争与协作矛盾的问题,在金字塔演化策略(Pyramid Evolution Strategy,PES)的基础上,提出了求解一维下料问题的基于差分进化的PES算法。该算法充分利用PES算法的优势,很好地解决了以上两个矛盾;但是由于PES算法未考虑种群当前个体与最优个体之间的协作关系,因此其收敛速度较慢。为此,在PES算法的加速过程中引入差分进化的变异、交叉操作,并对产生的不可行试验个体进行修复,使得算法能够充分利用种群个体间的差异信息,这一方面有利于加快算法的收敛速度,另一方面可以实现对新个体附近区域的局部开采,有利于提高算法的求解精度。将提出的算法应用于6组一维下料算例,实验结果表明,与其他8种算法相比,所提算法在求解精度和收敛速度上均有更好的性能表现,验证了该算法求解一维下料问题的可行性和有效性。
中图分类号:
| [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] | 刘宝宝, 杨菁菁, 陶露, 王贺应. 基于DE-LSTM模型的教育统计数据预测研究 Study on Prediction of Educational Statistical Data Based on DE-LSTM Model 计算机科学, 2022, 49(6A): 261-266. https://doi.org/10.11896/jsjkx.220300120 |
| [2] | 徐汝利, 黄樟灿, 谢秦秦, 李华峰, 湛航. 基于金字塔演化策略的彩色图像多阈值分割 Multi-threshold Segmentation for Color Image Based on Pyramid Evolution Strategy 计算机科学, 2022, 49(6): 231-237. https://doi.org/10.11896/jsjkx.210300096 |
| [3] | 张蔷, 黄樟灿, 谈庆, 李华峰, 湛航. 基于动态近邻套索算子的金字塔演化策略 Pyramid Evolution Strategy Based on Dynamic Neighbor Lasso 计算机科学, 2021, 48(6): 215-221. https://doi.org/10.11896/jsjkx.200400115 |
| [4] | 俞家珊, 吴雷. 双领导者樽海鞘群算法 Two Types of Leaders Salp Swarm Algorithm 计算机科学, 2021, 48(4): 254-260. https://doi.org/10.11896/jsjkx.200600181 |
| [5] | 张志强, 鲁晓锋, 隋连升, 李军怀. 集成随机惯性权重和差分变异操作的樽海鞘群算法 Salp Swarm Algorithm with Random Inertia Weight and Differential Mutation Operator 计算机科学, 2020, 47(8): 297-301. https://doi.org/10.11896/jsjkx.190700063 |
| [6] | 李章维,王柳静. 基于群体分布的自适应差分进化算法 Population Distribution-based Self-adaptive Differential Evolution Algorithm 计算机科学, 2020, 47(2): 180-185. https://doi.org/10.11896/jsjkx.181202356 |
| [7] | 王瑄, 毛莺池, 谢在鹏, 黄倩. 基于差分进化的推断任务卸载策略 Inference Task Offloading Strategy Based on Differential Evolution 计算机科学, 2020, 47(10): 256-262. https://doi.org/10.11896/jsjkx.190800159 |
| [8] | 董明刚,刘宝,敬超. 模糊自适应排序变异多目标差分进化算法 Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation 计算机科学, 2019, 46(7): 224-232. https://doi.org/10.11896/j.issn.1002-137X.2019.07.034 |
| [9] | 肖鹏, 邹德旋, 张强. 一种高效动态自适应差分进化算法 Efficient Dynamic Self-adaptive Differential Evolution Algorithm 计算机科学, 2019, 46(6A): 124-132. |
| [10] | 倪洪杰, 彭春祥, 周晓根, 俞立. 一种阶段性策略自适应差分进化算法 Differential Evolution Algorithm with Stage-based Strategy Adaption 计算机科学, 2019, 46(6A): 106-110. |
| [11] | 张煜培, 赵知劲, 郑仕链. 融合学习差分进化和粒子群优化算法的认知决策引擎 Cognitive Decision Engine of Hybrid Learning Differential Evolution and Particle Swarm Optimization 计算机科学, 2019, 46(6): 95-101. https://doi.org/10.11896/j.issn.1002-137X.2019.06.013 |
| [12] | 赵云涛, 谌竟成, 李维刚. 融合自适应差分进化机制的多目标灰狼优化算法 Multi-objective Grey Wolf Optimization Hybrid Adaptive Differential Evolution Mechanism 计算机科学, 2019, 46(11A): 83-88. |
| [13] | 杨晓花, 高海云. 基于改进贝叶斯的书目自动分类算法 Improved Bayesian Algorithm Based Automatic Classification Method for Bibliography 计算机科学, 2018, 45(8): 203-207. https://doi.org/10.11896/j.issn.1002-137X.2018.08.036 |
| [14] | 余伟伟,谢承旺. 一种多策略混合的粒子群优化算法 Hybrid Particle Swarm Optimization with Multiply Strategies 计算机科学, 2018, 45(6A): 120-123. |
| [15] | 邹华福,谢承旺,周杨萍,王立平. 应用反向学习和差分进化的群搜索优化算法 Group Search Optimization with Opposition-based Learning and Differential Evolution 计算机科学, 2018, 45(6A): 124-129. |
|
||
首页