星论文网欢迎您的来访,本中致力于各类论文代写,论文发表,代写代发论文服务

想快速发表职称论文找星论文网
当前位置:星论文网论文资料->理工论文->计算机论文

基于模拟退火算法的一维下料研究

分享到:
作者:原作原创  来源:网络转载  发布时间:2017-12-27 09:41:00

  摘 要: 模拟退火算法是求解一维下料问题的有效方法之一。但传统模拟退火算法具有易于陷入局部最优解的缺点,其性能好坏除了与一些参数设置有关外,特别依赖于邻域结构设计和编码机制的效率。为设计高效的求解一维下料问题的模拟退火算法,提出了新的基于一维下料问题特征的变异算子和解码策略。通过实验计算,与文献中的3组案例进行比较,结果优于部分既有文献的结果,验证了所提算法的有效性。 
  关键词: 一维下料; 模拟退火; 解码; 改进策略 
  中图分类号:TP301.6 文献标志码:A 文章编号:1006-8228(2017)12-01-04 
  Research on one-dimensional cutting stock problem based on 
  simulated annealing algorithm 
  Zhang Meng, Chen Shijun, Li Jiabin, Liu Zhaoyang 
  (School of Mathematics & Computer Science, Hubei University of Arts and Science, Hubei, Xiangyang 441053, China) 
  Abstract: Simulated annealing is one of the most efficient algorithms to solve one-dimensional cutting stock problem. However, traditional simulated annealing algorithms have the weakness of obtaining local optimal solutions. In addition to some parameters, its performance relies on neighborhood structure and decoding strategy. Based on the problem-knowledge, the new mutation operator and decoding strategy are presented to improve simulated annealing algorithm. By computational experiments with three instances, some better results comparing to those of in literatures are obtained, and the efficiency of presented algorithm is verified. 
  Key words: one-dimensional cutting stock; simulated annealing; decoding; improvement strategy 
  0 引言 
  在实际生产生活中,经常会遇到一维下料问题[1],即将单一规格或者多种规格、数量若干的线性原材料,切割成满足多种需求规格和数量的零件(即坯料)。一维下料问题的目标就是,要找到最优的可行下料方案,使得废料尽可能少,以提高原材料的利用率,对建设资源节约型社会具有重要实际意义。 
  一维下料优化问题是组合优化领域著名的NP-hard问题,目前还不存在求最优解的多项式时间算法。因此目前大多数的方法都基于启发式或元启发式算法,例如贪婪算法、模拟退火算法[2-3]、遗传算法[4-6]、粒子群算法[7]、蚁群算法[8]等。这些算法虽然都取得了一定效果,但对于大规模的下料问题,仍然有很大的优化空间。其中,模拟退火算法具有算法通俗易懂、易于实现的优点。同时,模拟退火算法的性能除了依赖于初始解、退火温度、局部搜索次数、劣解接受概率等因素外,特别依赖于编码与解码效率。在应用模拟退火算法求解问题时,现有文献对模拟退火算法的结构和参数研究较多,而关于编码和解码的影响因素易于被忽略。 
  为此,本论文基于一维下料的问题特征,拟设计一种改进的模拟退火算法,一方面提高解码效率,即尽可能地在不影響解码时间复杂度的前提下,生成具有更高质量的解;另一方面,加强模拟退火算法的局部搜索能力,设计新的变异算子,使得算法生成的解群体具有更好的多样性。 
  1 一维下料的数学模型 
  一维下料问题可以描述如下:设有足够多的某种线型原材料数量为n,单个原材料的长度为L,现需要从原材料上切割出m种小坯料,小坯料的长度和数量分别为和di(i=1,2,…,m),目标是寻找可行的下料方案,并且使得原材料的利用率最大(或使用原材料的根数最少)。记xji表示第j根原材料上切割第i个坯料的数量,yj表示是否使用第j根原材料即:,则一维下料问题的数学模型为: 
  由于模型⑴是非线性整数规划模型,利用传统的优化软件(如lingo)难于求解大规模问题;而利用智能优化方法,非线性约束使得编码和解码难以有效设计。因此,考虑将该模型转化成一种易于编码和解码的线性规划模型。应注意到,虽然原材料很多,但每种原材料的长度相同,故只需要考虑每种原材料的下料方式。若已知原材料的所有下料方式,则模型可以写成更易于求解的线性规划模型。记下料模式数为p,aij表示第j种下料模式下切割的第i种坯料的次数,zj表示使用第j种下料模式的使用次数。则一维下料的数学模型为: 
  由于模型⑵中的下料模式必须可行,因此aij必须满足: 
  上述模型⑵的目标函数是最小化所使用的原材料根数。为了考虑后续切割的方便,有时在考虑最小化总切割根数的条件下最大化最后一根原材料的余料长度。此时,目标函数为:

 其中,为最后一根被切割原材料的余料长度。 
  为求解模型⑵,需要给出所有的下料模式。由于下料模式数量是所有坯料的整系数线性组合数,对于大规模问题,精确列出所有下料模式是及其困难的。为了求解该模型,利用模拟退火算法在只考虑部分合理高效的下料模式子集下,可以得到原问题的满意(或最优)解。 
  2 模拟退火算求解一维下料问题 
  2.1 传统的模拟退火算法求解 
  ⑴ 模拟退火算法流程 
  模拟退火算法[2]是一种常用于求解NP难组合优化问题的智能算法,来源于模拟固体退火原理的过程。温度升高,固体内部粒子随温升变为无序状,内能增大;随着温度逐渐降低分子逐步趋于稳态,内能减为最小。模拟退火算法的主要特点在于搜寻解的过程中,它采用Boltzmann接受准则接收新解,能以一定概率接受比当前最优解劣的解,克服了爬山算法只接受好解而陷入局部最优解的缺点。而且,模拟退火算法具有易于实现的优点,其基本算法框架如图1。 
  

 通过计算,所需原材料总数为7,与王晓伟等提出的蜂群遗传算法[6]的结果相同。最后一根余料长为10,略差于其结果,但总利用率为99.01%,也基本达到了最优解。 
  案例3 已知原材料长度 L=1000m,需切割的零件坯料分别为长512m的5件、长321m的12件、长128m的8件、长247m的22件、长290m的6件。案例3的计算结果见表3。 
  通过计算,得到所需要的原材料总数16,优于林建良[9]所提AB分类法得到的17根。所需原材料的根数与祝胜兰所提的启发式算法[1]相同,但本文的原材料利用率为92.38%,略高于祝胜兰所提启发式算法[1]得到的91.3%。 
  4 结论 
  针对一维下料问题,提出一种改进模拟退火算法,并基于一维下料问题特征提出改进的解码方法、变异算子等。通过对文献中的案例进行计算,并与既有相关算法进行比较,证实了所提算法的有效性。此外,本文算法主要针对一维下料问题,还无法直接应用求解二维下料问题。对于如何將算法进行调整和改进应用于求解二维甚至更高维的下料问题,还需要进一步研究。 
  参考文献(References): 
  [1] 祝胜兰,饶运清.一维下料问题的启发式方法[J]. 机械制造与 
  自动化,2014.43(1):52-55 
  [2] 陈华根,吴健生,王家林等.模拟退火算法机理研究[J].同济大 
  学学报(自然科学版),2004.32(6):802-805 
  [3] 郑晓军,杨光辉,滕弘飞.多规格一维下料问题基于满意度模 
  拟退火算法[J].大连理工大学学报,2009.49(6):865-871 
  [4] 贾志新,殷富强,胡晓兵等.一维下料方案的遗传算法优化[J]. 
  西安交通大学学报,2002.36(9):967-970 
  [5] 寿周翔,王琦晖,王李冬等.一维下料的改进遗传算法优化[J]. 
  计算机时代,2014.1:36-41 
  [6] 王晓伟,刘林,周谧.蜂群遗传算法在一维下料问题中的应用[J]. 
  微型机与应用,2012.31(6):66-71 
  [7] 张建科,刘三阳,张晓清.改进的粒子群算法[J].计算机工程与 
  设计,2007.28(17):4215-4216 
  [8] 段海滨,王道波,于秀芬.蚁群算法的研究现状及其展望[J].中 
  国工程科学,2007.9(2):98-102 
  [9] 林建良.一维下料问题的AB分类法[J].计算机应用,2009.29(5): 
  1461-1466


本文TAGS:
如您需要代写代发表论文请联系QQ:800054855