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

张梦　陈仕军　李嘉宾　刘朝阳

摘 要： 模拟退火算法是求解一维下料问题的有效方法之一。但传统模拟退火算法具有易于陷入局部最优解的缺点，其性能好坏除了与一些参数设置有关外，特别依赖于邻域结构设计和编码机制的效率。为设计高效的求解一维下料问题的模拟退火算法，提出了新的基于一维下料问题特征的变异算子和解码策略。通过实验计算，与文献中的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必须满足：

上述模型⑵的目标函数是最小化所使用的原材料根数。为了考虑后续切割的方便，有时在考虑最小化总切割根数的条件下最大化最后一根原材料的余料长度。此时，目标函数为：endprint

其中，为最后一根被切割原材料的余料长度。

为求解模型⑵，需要给出所有的下料模式。由于下料模式数量是所有坯料的整系数线性组合数，对于大规模问题，精确列出所有下料模式是及其困难的。为了求解该模型，利用模拟退火算法在只考虑部分合理高效的下料模式子集下，可以得到原问题的满意（或最优）解。

2 模拟退火算求解一维下料问题

2.1 传统的模拟退火算法求解

⑴ 模拟退火算法流程

模拟退火算法[2]是一种常用于求解NP难组合优化问题的智能算法，来源于模拟固体退火原理的过程。温度升高，固体内部粒子随温升变为无序状，内能增大；随着温度逐渐降低分子逐步趋于稳态，内能减为最小。模拟退火算法的主要特点在于搜寻解的过程中，它采用Boltzmann接受准则接收新解，能以一定概率接受比当前最优解劣的解，克服了爬山算法只接受好解而陷入局部最优解的缺点。而且，模拟退火算法具有易于实现的优点，其基本算法框架如图1。

图1 求解一维下料的模拟退火算法

上述算法流程图1中，Δf=f（β'）-f（β）用于计算新解β'和当前解β之间目标函数的差值，从而判断是否接受用新解β'取代原解β。记当前的退火温度为T，则接受新解β'的概率：

⑸

上述模拟退火算法具有如下特点：当新解与当前参照解的目标值差Δf一定时，在模拟退火算法前期，退火温度T较高，接受概率P相对比较大，容易接受比当前解差很多的解，使得搜索算法加强全局搜索能力；在模拟退火算法后期，退火温度T逐步降低，算法倾向于在当前已得到较好解的邻域内做细搜索，渐渐使得算法收敛到满意解（或最优解）。模拟退火算法的终止条件为：当内循环次数达到上限或者概率选择次数达到上限时结束内循环；当达到凝固温度或达到外循环次数上限时，模拟退火算法结束。

⑵ 一维下料问题的编码与解码

利用智能算法求解最优化问题时，需设计合理的编码与解码方法。对任意给定的编码序，通过解码得到原问题的可行解，从而对相应编码序进行评价。智能算法求解的目标在于不断搜索最优的编码序，即对应原问题的最优解。

针对一维下料问题，常用编码与解码方法[4]如下：以坯料类型序号的自然排列作为编码，解码时基于坯料类型序号排列，从原材料上依次进行切割小坯料，当某根原材料被切完或不够切下一个坯料（原材料的余料长小于当前要切割的坯料）时，在新的原材料上继续切割，如此循环，直到所有那些小坯料切割完毕。例如，对于序号排列为{2，3，1，5，4}的5种坯料，切割坯料时，先切割2，接着依次切割3、1、5，最后切割4。为了得到新解，常采用基于“随机两点交换”的邻域结构。例如，交换两个坯料序号3、5的位置，即可得到新解{2，5，1，3，4}。以坯料类型序号的自然排列作为编码时，n种坯料的排列数为n！，因此难以枚举所有排列组合，需要利用模拟退火算法来优化编码序。

2.2 改进的局部搜索与启发式解码策略

利用2.1节的模拟退火算法求解一维下料问题时，邻域结构和解码策略对算法效率有着重要影响。邻域结构设计，能够使当前解在邻域算子作用下形成新的可行解。当需要切割的某类型坯料需求数较多时，常用的基于“随机两点交叉”的邻域结构，有很大概率出现无效操作的情况，即当前解在邻域操作算子之后仍然不变。因此，该方法具有较大的局限性。其次，在智能算法中，解码的目的是将编码序转化成原问题的可行解，并进行解评价，从而比较解的优劣。对给定的编码序，解码策略不同，得到相应原问题的解质量也不同。显然，高效的解码方法能得到更高质量的原问题解。同时，对于任何新解都需要评价，智能算法需要数千万（甚至更多）的次数来调用解码过程。因而，解码也不能过于复杂，否则计算复杂性太高，直接影响整个算法的运行效率。

为了克服上述缺点，采用两种改进方法：①首先，设计分组跳变的邻域结构，即对随机的编码序进行分组（例如10个一组），每组组内随机选取两个元素交换位置，得到新解，克服了常用“随机两点交叉”得到解可能不变的局限性。②其次，基于一维下料问题特征，提出改进的解码方法。在基本不影响算法时间复杂度的条件下，提高解码效率生成更高质量的问题解。改进的解码方法如下：以坯料类型序号的自然排列作为编码，即每次基于坯料类型序号排列，从原材料上依次进行切割小坯料，当某根原材料被切完或不够切下一个坯料时，进行一次回溯比较——即先记录下当前原材料的剩余余料长，同时取消最后一次加入的坯料，從编码序中该坯料的后续坯料中逐次进行切割，直到当前余料无法利用，重新计算对应原材料的剩余余料长，即得到回溯后的余料长。若回溯结果优于原结果（回溯得到余料长小于回溯前的余料长），则利用回溯后的解替换回溯前的解。在新的原材料上继续切割，如此循环，直到所有所需求的小坯料切割完毕。

3 算例分析

利用文献中的3组算例，测试所提算法的有效性。在实现模拟退火算法时，相关参数如初始温度、温度衰减率、内循环次数、外循环次数，通过多次试验方法确定。

案例1 原材料长3m，需切割的零件坯料分别为长2.2m的3件、长1.8m的3件、长1.2m的4件、长0.5m的6件、长0.3m的6件。求最优下料方案（不考虑切口损失）。案例1的计算结果见表1。

通过计算，使用原材料总数8根，总利用率为97.30%。最后一根的原材料剩余余料为1.8，其余的原材料余料均小于0.3。求得结果和祝胜兰[1]所提启发式算法的结果相同，优于贾志新等[4]提出的遗传算法。

案例2 已知40段网线的长度分别为4 m、6 m、10 m、13 m、14 m、19 m、20 m、21 m、22 m、28 m、32 m、33 m、36 m、38 m、38 m、40 m、41 m、42 m、48 m、48 m、50 m、55 m、57 m、60 m、64 m、66 m、67 m、72 m、76 m、77 m、83 m、84 m、85 m、86 m、91 m、91 m、94 m、94 m、99 m、100 m，求所需每箱长度为305m的网线箱数及分割方案。案例2的计算结果见表2。

通过计算，所需原材料总数为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-1466endprint