改进的模拟退火算法及其在装填问题中的应用

罗娜

摘要：NP难度问题一直是计算机科学研究的一个重要问题，具有很高的理论和实用价值。这篇文章主要研究利用模拟退火算法解决具有NP难度的装填问题，它的求解目标是寻求多个圆在一个矩形内的优良布局，使得这些圆两两互不嵌入地放置。通过将模拟退火算法与梯度法相结合，并且融入一些启发式的格局更新策略，提出了改进的模拟退火算法。计算结果显示，该算法对于解决圆形装填问题具有很高的效率。

关键词：模拟退火算法；装填问题；NP难度；梯度法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）06-0181-03

1 概述

装填问题研究的是一组小物体在大区域内互相不重叠的布局方式，要求尽可能地提高空间或物体的利用率，并达到某些最优指标[1-3]，从而减少浪费。在物体堆放、运输以及原材料下料等领域有着广泛的应用，有效地解决这个问题可以增加资源的利用率，从而带来不可估量的经济效益。由于装填问题通常是NP难度的问题，所以目前学术界没有算法能保证在有效时间内求出其精确解，顺着应用行业的迫切要求，出现了很多有效的搜索策略来解决这一问题。

本文在模拟退火算法的基础上，提出了一个改进的模拟退火算法，它是在模拟退火算法能够有效地逃离局部最小值陷阱策略的基础上，又结合了梯度算法和空白点放置策略，有效地提高了算法的效率。

2 问题的描述

2.1 NP问题和NP完全问题介绍

首先我们来看下NP问题的定义，所谓N也就是Non-Deterministic，即不确定性，P则是多项式算法问题，所以NP就叫做非确定性多项式算法问题，有些多项式问题没有一套完整的求解公式，只能使用确定性的猜测的方法和验证的方法来求解，对于这一类求解的问题我们都可以叫它NP问题，如果来求解NP问题，我们一般使用一个合理的算法来对NP问题进行猜测和验证

如果以上的NP问题可以用一个多项式算法得到这个NP问题的最优解，就叫做NP完全问题的解，但是这个难度是很大的，也是目前世界数学界的难题。本文研究的是对于NP问题的相对最优解，采用改进模拟退火算法来对布局进行优化，从而得到优质的计算结果。

2.2 装填问题介绍

装填问题所探讨的是一组小物体放在一个大区域内并且让它们互相不重叠的布局方案，要求尽可能地提高空间和物体的利用率，并达到某些最优指标，从而减少浪费。下面来看下本文研究的装填问题的说明。

给定一个矩形区域和N个不同规格的圆，圆形装填问题就是问能否将这些圆互不重叠地放到矩形容器中，此问题更形式化的描述如下：

将二维笛卡尔坐标的原点取在矩形区域的左下角，如图1所示：

记矩形容器的长宽分别为L与W，圆i的圆心坐标为（xi， yi），半径为Ri，圆j的圆心坐标为（xj，yj） ， 半径为Rj，问是否存在2n个实数x1，y1，…，xn，yn满足以下两个约束条件：

[Ri≤xi≤L-Ri， Ri≤yi≤W-Ri（xi-xj）2+（yi-yj）2≥Ri+Rj]

如果存在，则给出一组合乎条件的解（x1，y1，…，xn，yn），这里i， j=1，2，…，N， and i≠j。

3 问题的转化

根据上面的问题描述，我们按照拟物方法[10， 11]，假设这N个圆为有弹性的光滑的圆形物体，将它们随机的放入这个矩形容器内，若物体间两两无挤压，则得到问题的解，否则根据弹性力学，受挤压的圆间将产生积压弹性力，并在此力的作用下产生一系列恢复原本形状的运动，直到物体间没有挤压则得到此问题的解，这样通过拟物的方法可以转化为一个势能函数的优化问题，根据弹性力学原理就可以得出势能函数。以下是势能函数的求得过程：

第一种情况，第i个圆和第j个圆相互嵌入时，这时嵌入深度的是它们半径之和减去圆心的距离；当两圆不嵌入时，则[dij]为0，见图2所示：

因此圆i与圆j的挤压深度为：

5 改进的模拟退火算法

5.1 挑圆策略

当模拟退火算法陷入局部最小值陷阱后，我们需要挑出一个圆重新放置来使算法跳出陷阱从而继续寻求最优解，那么选择挑出哪一个圆将是一个待解决的问题。我们借鉴黄文奇等人的拟人策略来解决这一问题，在热闹拥挤的公交车中，受挤压最甚者总能设法改变自己的位置，而处境宽松者往往也会让出一部分空间给予别人。所以当陷入局部最小值陷阱时，我们可以挑出受挤压最严重的圆饼，将它重新放置到矩形容器的某个地方去，也可以跳出那个挤压最宽松的圆放到矩形容器的某个地方去，挤压的严重程度我们可以用圆的势能与其半径比来表示，我们可以将挑出势能半径比最大的圆的策略称之为压力解除策略，将挑出势能半径比最小的圆的策略称之为资源让与策略。此两个策略统称为挑圆策略。

5.2 空白点放置策略

通过上面介绍的挑圆策略可以确定应该重新放置的圆，那么将这个圆放置在矩形容器的什么位置就成了新的问题，原来的策略往往是将这个圆随机的放置在矩形容器内的一个位置从而获得一个新的格局，可是这种方法来寻求全局最优解效率是很低的，空白点放置就是将所挑出的圆放入一个空白位置，并且得到多个空白位置，再从这些空白点中选择一个放入后使系统势能最小值的空白点来放置。

下面是空白点放置策略描述：

（1） 在矩形容器内随机产生一个点，判断该点是否是空白点，即要满足在矩形的内部，也要满足不在其他小圆的内部，如果是空白点，则记录下其位置，然后继续寻找空白点，直到找到100个空白点。

（2） 将选择的圆分别放入选择出的100个空白点中，分别计算它们的系统势能。

（3） 选出系统势能最小的空白点放置圆，即设置为该圆的坐标。

（4） 如果循环需找500次也没能找到100个空白点，为了避免陷入死循环则结束空白点的搜索。

5.3 局部最优判断策略

上文已经多次提到，当算法运行时，可能陷入局部最小值而无法自拔，挑圆策略与空白点放置策略用来解决这一问题，但是前提是怎么样判断系统已经陷入局部最小值，我们知道算法陷入局部最小值时，系统的势能的变化已经非常小了，我们可以用新格局势能值比上新的格局势能值与原来格局势能值的差的绝对值来判断系统是否处于局部最小值状态，如果比值大于10000，我们可以认为处于局部最小值状态，然后就使用挑圆策略与空白点放置策略。

5.4 改进的模拟退火算法步骤

改进的模拟退火算法步骤如下：

在矩形容器中随机生成N个圆的圆心坐标，得到初始格局解X=（x1，y1，…，xi，yi，…，xn，yn），设置初始温度T为10N（N为小圆数量），温度下降系数k设置为0.92。

计算所有小圆的势能半径比，记下势能半径比最大的小圆的序号，记下此时的势能U（X1）。最后备份当前格局X1。

使用空白点放置策略把势能半径比最大的圆放入空白点中，从而得到新的格局X。

用梯度法进行计算，令每个圆按其梯度方向进行移动，得到新的格局X2，记下此时的势能U（X2），如果U（X2） <10-10则接受X2格局，算法成功停机，否则继续进行第5步。

判断是否是局部最优解。

如果是局部最优解，则使用挑圆策略挑出一个势能半径比最小的圆利用空白点放置策略放入空白点中转第4步，如果不是则转（2）。

如果不是局部最优解，则使用梯度法前的格局势能U（X1）与使用梯度法后的格局势能U（X2）来比较，取它们的差△E=U（X1）-U（X2）；如果势能有所下降，那么我们接受这个格局，令X1=X2；如果势能增加了，那么我们以一定的概率exp（-△E）/T）去接受产生的新解，如果没有接受恶化解则还原第2步骤中备份的格局。

如果在温度T下系统的势能没有达到稳定，则转第2步骤，否则转7。

进行模拟退火算法的退温操作，T=T*k。

如果温度T<0.01，算法失败停机。

6 结论

大规模组合优化问题和NP难度问题是现代计算机科学的难点问题， 并且这类问题的有效解决将会带来计算机科学上的巨大理论突破，同时也会带来巨大的经济效益，因此，也是现代计算机科学的热点问题，本文的圆形Packing问题的研究涉及物理、数学、哲学、计算机科学、计算智能、优化理论等多个学科领域，并且在布局优化和运筹学等方面有着十分重要的应用。预计在未来的若干年内，将带来巨大的经济实用价值。

参考文献：

[1] 王大志，汪定伟，闫杨.一类多旅行商问题的计算及仿真分析[J].系统仿真学报，2009（20）.

[2] 邢文训.现代优化计算方法[M].2版.北京：清华大学出版社，2006.

[3] 王万森.人工智能原理及其应用[M].2版 .北京：电子工业出版社，2007.

[4] 梁艳春.群智能优化算法理论与应用[M]，北京：科学出版社，2009.

[5] Ingber L，Rosen B.Genetic algorithms and fast simulated annealing：A comparison.Mathematic Computer Modeling.1992，16（Ⅱ）：87-100

[6] A Lodi，S Martello，M Monaci.Tow-dimensional packing problems：A survey[J].European Journal of Operational Research.2002，141（2）：241-252

[7] J Leung，T Tam，C S Wong，et al.Packing squares into square[J].Journal of Parallel and Distributed Computing.1990，10（3）：271-275

[8] 黄文奇，詹叔浩.求解Packing问题的拟物方法[J].应用数学学报，1979，2（2）：176-180.

[9] 康立山，谢云，罗祖华.非数值并行算法——模拟退火算法[M].北京：科学出版社，1997.

[10] 康燕 黄文奇.基于禁忌搜索的启发式算法求解圆形packing问题[J].计算机研究与发展学报，2004，（9）：1555-1558.