一维下料的基于贪心策略的多目标自适应 粒子群算法优化

来源:用户上传      作者:

　　摘  要： 针对一维下料问题，提出一种基于贪心策略的多目标自适应粒子群算法，在余料率最低和下料方式数量最少两个目标上进行优化。通过将贪心策略应用于粒子群算法，把一维下料问题分割成多个子问题，对每个子问题依次求全局最优解，有效缩小单次处理问题的规模，由所有子问题的最优解取得原问题的近似最优解。为解决种群过早收敛而因此陷入局部最优，设计一种自适应策略。此外，考虑到切换下料方式会产生一定成本，通过最大化当前下料方式使用次数优化下料方式数量。仿真实验结果表明，该算法收敛速度快，取得的下料方案利用率高且下料方式数量较少，具备较好的实用性，并能够为企业带来显著的经济效益。
　　关键词： 一维下料; 粒子群算法; 算法优化; 贪心策略; 自适应策略; 仿真实验
　　中图分类号： TN911?34; TP391.9                 文献标识码： A                      文章编号： 1004?373X（2020）14?0086?04
　　Multi?objective adaptive particle swarm algorithm optimization based on greedy strategy for one?dimension cutting stock problem
　　JIA Lu1， YANG Le2， TANG Jiyue2， LI Youhuang2
　　（1. School of Architecture and Engineering， Nanchang University， Nanchang 330031， China;
　　2. School of Software， Nanchang University， Nanchang 330047， China）
　　Abstract： The multi?objective adaptive particle swarm algorithm optimization based on greedy strategy is proposed for the one?dimension cutting stock problem， which is optimized in the two aspects of the lowest surplus rate and the minimum number of cutting stock ways. By applying the greedy strategy into the particle swarm algorithm， the one?dimension cutting stock problem is divided into multiple sub?problems， the global optimal solution of each sub?problem are found in turn （which can effectively reduce the scale of single processed problem）， and the approximate optimal solution of the original problem is obtained from the optimal solution of all sub?problems. An adaptive strategy is designed to prevent the population is trapped into local optimum due to the premature convergence. In consideration of the cost of switching cutting stock ways， the quantity of cutting stock way is optimized by maximizing the number of times that the current cutting stock way is used. The simulation experimental results show this algorithm has fast convergence speed， the utilization rate of the obtained cutting stock plan is high， and the used cutting stock ways are fewer. It has a certain practicability and can bring significant economic benefits to enterprises.
　　Keywords： one?dimension cutting stock; particle swarm algorithm; algorithm optimization; greedy strategy; adaptive strategy; simulation experiment
　　0  引  言
　　粒子群優化算法（Particle Swarm Optimization，PSO）是由Eberhart和Kennedy于1995年提出的群智能算法[1]。相比传统优化算法，粒子群算法具备并行、信息共享等特性，能够更快逼近最优解。因此，目前已普遍应用于函数优化、神经网络优化[2]、图像分割[3]以及提高工业生产效率[4]等方面。相比遗传算法（GA），粒子群算法（PSO）无需进行交叉和变异操作，原理更简单，无需调整众多参数，实现更容易。与GA的信息共享机制不同的是，PSO种群在搜索中朝着当前最优解的方向更新。因此大多数情况，种群所有粒子会更早收敛于最优解。贪心算法是解决最优化及近似最优化问题的经典算法[5]，与全局优化算法不同，并非从整体最优考虑，而是只关注当前子问题的最优解，广泛用于优化路径选择[6]和调度问题[7]。本文针对一维下料问题，将贪心策略应用于粒子群算法，加入自适应策略和下料方式优化方法，提出一种基于贪心策略的多目标自适应粒子群算法（GSMAPSO）。仿真实验结果表明，该算法收敛速度快，求解精度高，且下料方式较少。 　　由于一维下料问题的普遍存在，大量学者对其进行了研究，并提出各自的优化算法[8]。针对一维下料问题，结合分支定界法的整数线性规划[9]，理论上可以得到最优解。然而该方法必须首先列出所有的下料方式，再进行线性规划。在数据规模较大时，有效的下料方式数量巨大，全部遍历并不现实，因此只适合小规模下料优化问题。文献[10]提出一种贪心算法优化方法，试图利用子集和思想寻找一组近似于最佳的下料组合方式。该算法虽然在一定程度上减少了下料方式数，但是问题规模较大时，寻找余料率低的下料方式耗时长，且由于贪心算法在求解局部最优时只是逐步从一个方向逼近理想最优值，不能并行比较，导致求解精度较低。进化算法如遗传算法也被用于一维下料优化[11]，但遗传算法需要对问题编码和解码，编程实现复杂，不能及时利用种群网络的反馈信息。因此得出较优的下料方案需要较多训练时间，且算子的实现依赖于多个参数[12]，参数的选择较大程度上决定了解的品质。目前对于这些参数的选择大多凭借经验，仍未有较为成熟的研究。
　　3  仿真实验对比与分析
　　本文仿真实验共2个算例，运行在Windows 10系统、i5?7200U CPU环境下的Matlab R2018a，设定粒子群大小为50，最大迭代次数为300，独立运行15次，，所有算例单次运行时间均小于50 s。其中，大部分时间用于前面的下料方式计算，后续下料方式的运算速度将随着问题规模的缩小进一步加快。表1中，次数均表示该下料方式的使用次数。
　　算例1：实验数据来自文献[11，19]。文献[11]采用改进的自适应遗传算法，最佳下料方案共需要原材料24根，总利用率97.41%，下料方式为24种，前23根总余料为2 436，末根余料长度为5 032。文献[19]采用自适应广义粒子群优化算法得到的最佳下料方案共需要原材料24根，下料方式24种，前23根总余料长度为764，末根余料长度为6 704。本文采用GSMAPSO算法得出的下料方案共需原材料24根，下料方式20种，前23根总余料长度为88，末根余料长度为7 380，前23根原材料利用率高达99.97%，各项数据均优于上述两个文献。
　　算例2：实验数据源自文献[10，20]。文献[20]通过建立一种多目标的优化模型，提高了利用率并改进了下料方式。在不优化下料方式数量的情况下，得出的下料方案共需原材料809根，下料方式为71种，废料总长度为32 274;在使用加权求解减小下料方式后，共需原材料811根，下料方式66种，废料总长度为38 239。本文采用GSMAPSO算法计算后，得出的下料过程原材料余料率变化折线图如图1所示。共需原材料795根，下料方式60种，总余料10 012，总利用率达99.58%，各项数据均更优，且十分接近该问题的理论最优解792。文献[10]利用贪心算法优化，虽然在下料过程中加入了切割损耗，但在计算利用率时并未将切割损耗纳入废料当中。在将切缝损耗计入废料后，共需原材料807根，下料方式为51种，废料总长度46 012，总利用率98.1%。本文的GSMAPSO算法，在考虑下料时的切割损耗后，得出的下料过程原材料余料率变化折线图如图2所示。共需原材料800根，下料方式为55种，总余料长度25 012，总利用率为98.96%。除下料方式偏多外，其余数据均优于贪心算法。
　　4  结  语
　　针对一维下料问题，本文提出一种基于贪心策略的多目标自适应粒子群算法。通过仿真实验对比现有多种优化算法表明，该算法收敛速度快，求解精度高，下料方式切换次数较少，适用于中大规模一维下料。
　　参考文献
　　[1] KENNEDY J， EBERHART R C. Particle swarm optimization [C]// Proceedings of IEEE International Conference on Neural Networks. Perth： IEEE， 1995： 1942?1948.
　　[2] LIN C H， CHANG K T. SCRIM drive system using adaptive backstepping control and mended recurrent Romanovski polynomials neural network with reformed particle swarm optimization [J]. International journal of adaptive control and signal processing， 2019， 33（5）： 802?828.
　　[3] SAEED Mirghasemi， PETER Andreae， ZHANG Mengjie. Domain?independent severely noisy image segmentation via adaptive wavelet shrinkage using particle swarm optimization and fuzzy C?means [J]. Expert systems with applications， 2019， 133（6）： 542?558.
　　[4] ZOU Jing， CHANG Qing， OU Xinyan， et al. Resilient adaptive control based on renewal particle swarm optimization to improve production system energy efficiency [J]. Journal of manufacturing systems， 2019（50）： 650?667.
　　[5] TSAMARDINOS Ioannis， BORBOUDAKIS Giorgos， KATSOG?RIDAKIS Pavlos， et al. A greedy feature selection algorithm for Big Data of high dimensionality [J]. Machine learning， 2019（2）： 338?347. 　　[6] SAMUEL Nucamendi?Guillén， FRANCISCO Angel?Bello， IRIS Martínez?Salazar， et al. The cumulative capacitated vehicle routing problem： new formulations and iterated greedy algorithms [J]. Expert systems with applications， 2018， 11（7）： 36?43.
　　[7] WU Chin?Chia， YANG Tzu?Hsuan， ZHANG Xingong， et al. Using heuristic and iterative greedy algorithms for the total weighted completion time order scheduling with release times [J]. Swarm and evolutionary computation， 2018（6）： 456?468.
　　[8] 漏家俊.基于MATLAB的钢筋下料优化算法[J].建筑施工，2018，40（2）：292?294.
　　[9] 鲁强，周新.基于在线检测动态一维下料问题的GPU并行蚁群算法[J].仪器仪表学报，2015，36（8）：1774?1782.
　　[10] 寿周翔，王琦晖，王李冬，等.一维下料的改进遗传算法优化[J].计算机时代，2014（1）：36?37.
　　[11] 刘在良，翁旭辉，王静，等.基于遗传算法的多规格管材或型材的优化下料[J].计算机时代，2018（12）：71?74.
　　[12] YAN Chun， LI Meixuan， WEI Liu， et al. Improved adaptive genetic algorithm for the vehicle insurance fraud identification model based on a BP neural network [J]. Theoretical computer science， 2019（7）： 783?792.
　　[13] 苗振华，孙旭东，邵诚.一种并行变异自适应遗传算法及其性能分析[J].信息与控制，2016，45（2）：142?150.
　　[14] SHI Y H， EBERHART R. A modified particle swarm optimizer [C]// 1998 IEEE International Conference on Evolutionary Computation Proceedings. Anchorage： IEEE， 1998： 69?73.
　　[15] 王耀雷，周步祥.基于自适应粒子群算法的直流微网能量优化管理[J].现代电力，2017，34（1）：37?43.
　　[16] MANIKANDAN Subramaniyan， SASITHARAN Subramaniyan， MOORTHY Veeraswamy， et al. Optimal reconfiguration/distributed generation integration in distribution system using adaptive weighted improved discrete particle swarm optimization [J]. Compel， 2019， 38（1）： 226?249.
　　[17] ATEFEH N， MOHAMMAD H M. Missing value imputation for breast cancer diagnosis data using tensor factorization improved by enhanced reduced adaptive particle swarm optimization [J]. Journal of King Saud University， 2018（9）： 89?96.
　　[18] 姜栋瀚，林海涛.基于布谷鸟搜索的虚拟机放置算法[J].电信科学，2017（10）：96?104.
　　[19] 文笑雨，罗国富，李浩，等.基于广义粒子群优化模型的工艺规划方法研究[J].郑州大学学报（工学版），2018，39（6）：65?69.
　　[20] 程浩.复杂下料问题的优化模型及求解方法研究[D].合肥：合肥工业大学，2015.
转载注明来源:https://www.xzbu.com/8/view-15283735.htm