宋真真，王金敏（天津职业技术师范大学机械工程学院，天津　300222）

一种解决三维矩形布局问题的蚁群算法

宋真真，王金敏
（天津职业技术师范大学机械工程学院，天津300222）

摘要：针对三维矩形布局问题，提出一种布局蚁群算法，该算法通过赋定值与随机产生2种方式给出蚂蚁的初始信息素并求得布局初始解。在迭代过程中选择不同的信息素挥发系数，使更新后的信息素值随机性更强，从而提高了算法的寻优性能。通过算例的计算并与已有文献结果进行比较，表明本文提出的算法可得到更优的布局结果。关键词：布局问题；蚁群算法；挥发系数

现代生活中的许多实际问题，例如集装箱货物摆放、仪器舱内仪器布局、车间布局设计、集成电路的设计等都涉及三维布局问题[1]，因此研究三维布局问题的有效解法具有重要的实际意义。随着布局问题研究的不断深入，求解算法越来越复杂，各种智能算法也随之应用到布局问题中，如蚁群算法、遗传算法、模拟退火算法、粒子群算法等。鲁强等[2]使用蚁群优化算法来优化平面布局问题，利用蚁群变异特征加快了解的收敛速度。DANIEL等[3]根据应用在容器装载布局问题的砌墙法并结合一维箱体装载布局的求解方法，提出了一种直接的启发式算法用来求解到二维、三维箱体布局。张德富等[4]根据砌墙工人长期积累的经验，提出砌墙式算法用以求解三维矩形布局问题。WANG等[5]提出一种基于动态空间分解的三叉树启发式算法，用来解决三维装箱问题。蚁群算法[6]具有通用性、鲁棒性、自组织性、正反馈、并行分布式计算等特点，因此能够更好地应用于组合优化问题。本文将蚁群算法应用到三维矩形布局问题中，力求得到更好的布局结果。

1　三维矩形布局问题

1.1布局模型

三维矩形布局问题是指将形状为长方体的布局物体（矩形块）互不干涉地放入长方体的布局容器中，且矩形块的各表面分别平行于布局容器的各表面；布局所追求的目标是使布局容器利用率最高。布局模型描述如下：

式中：Fit为布局容器的利用率，也称布局适应度值函数；n表示布入容器的矩形块的个数；li、wi、hi分别表示第i个已布入矩形块的长、宽、高；L、W、H分别表示容器的长、宽、高；（xi、yi、zi）和（xj、yj、zj）分别表示第i个和第j个已布入矩形块的中心点坐标；li、wi、hi分别表示第i个已布入矩形块的长、宽、高。这里令布局容器的左下前角点的坐标为（0，0，0）。式（2）确保矩形块完全布入容器中，而式（3）则保证了矩形块互不干涉。

1.2定位规则

本文采用吸引子法作为矩形块的定位方式，它通过在布局容器设置一些吸引子，用来吸引待布局矩形块，以实现待布局矩形块的定位。吸引子法描述如下：

在布局容器中设置m个吸引子，吸引子t的位置表示为（x0t，y0t，z0t）。待布矩形块i在点（xi，yi，zi）处的定位函数为：

本文采用4个吸引子用于解决三维矩形布局问题。吸引子分别布置在布局容器下面的4个角点，即左下前、左上前、左上后、左下后，其定位函数为：

当系数ωt、αt、βt、γt确定后，定位函数也随之确定。G（xi，yi，zi）取最小值的坐标点，即为此矩形块的布入点。

2　布局蚁群算法

20世纪90年代初期，意大利学者Dorigo等[8-9]通过模拟自然界中蚂蚁集体寻径的行为而提出了蚁群算法（ant colony algorithm），它是一种基于种群的启发式仿生类并行智能进化算法。蚁群算法包含适应阶段和协作阶段2个基本阶段。在适应阶段，蚂蚁个体根据自身信息素浓度的大小进行自身调整；而在协作阶段，各蚂蚁通过信息交换，进行个体调整，以获得更好的解。

蚁群算法相对于其他算法，对初始解的要求不高，在搜索的过程中不需要进行人工调整。利用正反馈原理，在一定程度上可以加快寻找到最优解的速度；利用并行分布式计算的特征，不同蚂蚁个体之间只能进行信息交流和传递，从而能够相互协作，避免算法的早熟性收敛，有利于发现近似最优解。

2.1信息素初始化及更新规则

蚁群算法是一种新兴的智能优化算法，自身存在易陷入局部最优解的问题，容易出现停滞的现象。所以本文将蚁群信息素初始值的确定分为赋定值与随机产生2种方式。

（1）依前人经验，根据占角顺序策略、下台阶法等[7]吸引子参数的特点，赋予其中一部分蚂蚁[0，1]之间特定的值，以期得到较好的布局结果。

（2）为减小算法陷入局部最优解的几率，其余蚂蚁的信息素赋值为[0，1]之间的随机数。

蚂蚁在不断活动的同时，伴随着信息素的释放与挥发，在不同情况下信息素的更新方式会有所不同，如式（6）和式（7）。

若更新后的信息素值不在[0，1]范围内，则将其在[0，1]之间随机赋值；若τCbestj为0，强制τCbestj=0.001，即取接近0的极小值。

p0为蚂蚁转移概率的临界值。p0值越小，则说明越靠近最优解。取（0.1，0.2）之间的随机数，当pij

ρ表示信息素挥发系数，其值越小，表明残留信息素越多。ρ=c*ROU，ROU为与ρ相关的常数；c为变量系数。为使更新后的信息素值随机性更强，取值范围更广，使变量系数c随着迭代次数的改变而改变，c取值为：

式中：K为迭代次数。

2.2布局蚁群算法

本文利用蚁群算法优化吸引子参数，提出了布局蚁群算法（PACA），算法步骤如下。

步骤1设置蚂蚁个数N、迭代次数K。

步骤2初始化：产生N个蚂蚁的初始信息素τij，计算每只蚂蚁的适应度Fi（ti），从中选择适应度最大的蚂蚁，记录其序号Cbest，适应度值记为Fi（tCbes）t，携带的信息素值为τCbestj。

步骤3迭代次数k=k+ 1，蚂蚁序号i=0。

步骤4 i=i+ 1。

步骤6计算更新后每个蚂蚁的适应度Fit′（i），若Fit′（i）>Fi（tCbes）t，则Fi（tCbes）t=Fit′（i），Cbest=C′best，记录对应Fi（tCbes）t及Cbest。若当前循环中还有未执行上述操作的蚂蚁，即i

步骤7若k>K，转至步骤8；否则，转至步骤3。

步骤8输出蚂蚁Cbest的信息、布局方案及Fit （Cbes）t，算法结束。

3　算例及分析

本文在1.73 GHz、0.99 GB内存的计算机上，利用C++语言编写程序实现布局蚁群算法，采用文献[10]中的后6组算例（BR算例）进行运算。BR算例共有15组。每组100个算例。本文选取的BR10~BR15属于强异构问题，而且异构性逐渐增强。蚁群算法初始参数选择N=40、K=20、ROU=0.1。计算中，容器利用率是算例计算10次后得到的平均值。

选取BR10的部分算例（21~30），采用5种方式进行计算，得到布局结果如表1所示。5种方式主要用于研究算法中初始信息素、挥发系数的选择对布局结果的影响。表1中：方式1的初始信息素随机选取，挥发系数取0.2；方式2的初始信息素是由赋定值与随机产生2种方式结合得到的，挥发系数取为0.2；方式3的初始信息素随机选取，挥发系数取0.1；方式4的初始信息素随机选取，挥发系数取0.3；方式5的初始信息素由赋定值与随机产生2种方式结合得到，挥发系数取0.1。

表1　5种方式的布局利用率%

从表1中可以看出，方式3和方式5得到的利用率相对较高，两者区别在于初始信息素的选取方式，相同之处为挥发系数均选取0.1。经过比较可知，初始信息素由2种方式结合给出、挥发系数取为0.1时，布局结果最好。

为研究挥发系数选取方式对布局结果的影响，选取BR10的部分算例（21~30）进行计算，得到布局结果如表2所示。表2中：I的挥发系数选取恒定值0.1；II的挥发系数在（ρmin，ρmax）之间取随机值，ρmin=0.02，ρmax=0.1；III中的挥发系数取（0，0.1）之间的随机值；IV中的挥发系数取（0，0.1）之间的值。

表2　4种情况的容器利用率%

从表2可以看出，IV的利用率最高，即挥发系数采用分段选取的方式较好。

根据表1和表2的分析结果，选取2种方式结合得到信息素初始值，挥发系数由分段方式得到，计算BR10~BR15这6组算例的容器利用率，具体计算结果及比较如表3所示。

表3　布局结果比较%

由表3可以看出，从BR10到BR15，随着布局块种类的增加，容器利用率呈不断上升趋势，说明本算法在强异构布局问题上更有优势。此外，BR14和BR15均得到了当前最优值，分别比文献中的最优值提高0.3%和0.16%；BR10~BR13平均值计算结果没有得到当前最优值，但是利用率高于上述大部分算法。虽然文献[14]中的BR10~BR13的利用率高于本文算法的利用率，矩形块在每个待布局点有3个方向可以放置，经计算后选择使剩余空间最小的方式，但本文中体积递减的方式在待布局点是确定的放置方向，所以本文算法的复杂度比文献[14]算法的复杂度低。

为探寻容器利用率与迭代次数和蚂蚁个数之间的关系，经部分算例（81~90）计算后，得到趋势图，如图1和图2所示。

图1　利用率与迭代次数的关系（算例81~90）

图2　利用率与蚂蚁个数的关系（算例81~90）

从图1中可以看出，容器利用率在迭代次数为40时，曲线趋于平稳。在寻找容器利用率与蚂蚁个数的关系时，得到了图2的“W”型曲线，说明容器利用率不一定随着蚂蚁个数的增多而增大；在迭代次数为40、60、80时出现利用率高值点，迭代次数为50、70时出现利用率低值点，说明在迭代次数为偶数时，容器利用率较高。

4　结束语

本文针对三维矩形布局问题，将赋定值与随机生成2种方式作为初始信息素的来源，在更新方式的信息素挥发系数选取上提出分段选取的思想，经过算例计算及分析，本文算法取得了良好的计算结果。此外，算法还有一些问题有待进一步研究解决，如怎样通过改变信息素更新方式提高算法的搜索能力，如何去探究容器利用率与蚂蚁个数的关系等，这些将是今后研究的内容与方向。

参考文献：

［1］COLORNI A，DORIGO M，MANIEZZO V，et al. Distributed optimizationbyantcolonies［C］//Proceedingsof European Conference on Artificial Life. Paris：Elsevin Publishing，1991：134-142.

［2］鲁强，陈明.平面布局的蚁群算法［J］.计算机应用，2005，25（5）：1019-1021.

［3］DANIEL M，ANDREAS B. A heuristic for solving large bin packing problems in two and three dimensions［J］. CEJOR，2012，20：337-354.

［4］张德富，韩水华，叶卫围.求解矩形Packing问题的砌墙式启发式算法［J］.计算机学报，2008，31（3）：509-515.

［5］WANG Z J，KEVIN W L，JASON K L. A heuristic for the container loading problem：A tertiary -tree -based dynamic space decomposition approach［J］. European Journal of Operational Research，2008，191：86-99.

［6］朱丽萍，王金敏.基于空间分割的求解布局几何可行域的算法［J］.天津职业技术师范大学学报，2012，22（2）：30-33.

［7］王金敏，杨维嘉.动态吸引子在布局求解中的应用［J］.计算机辅助设计与图形学学报，2005，17（8）：1725-1720.

［8］LODI A，DORIGO M，MANIEZZO V，et al. Distributed optimization by ant colonies［C］//Proceedings of European Conference on Artificial Life. Paris：Elsevin Publishing，1991：134-142.

［9］BONABEAU E，DORIGO M，THERAULAZ G. Inspiration for optimization from social insect behaviour［J］. Nature，2000，406（6）：39-42.

［10］BISCHOFF E E，RATCLIFFB S W. Issues in the development of approaches to container loading［J］. Omega，1995，23（3）：377-390.

［11］GEHRING H，BORTFELDTA. A genetic algorithm for solving the container loading problem［J］. International Transactions in Operational Research，1997，4（6）：401-418.

［12］BORTFELD T A，GEHRING H. A tabu search algorithm for weakly heterogeneous container loading problems［J］. OR Spectrum，1998，20（4）：237-250.

［13］GEHRING H，BORTFELD T A. A parallel genetic algorithm for solving the container loading problem［J］. International Trasactions in Operational Research，2002，9（4）：497-511.

［14］MOURA A，OLIVEIRA J F. A GRASP approach to the container loading problem［J］. IEEE Intelligent Systems，2005，20（4）：50-57.

［15］王金敏，朱丽苹，甄士刚.一种基于蜜蜂进化选择算子的布局遗传算法［J］.图形学学报，2014，35（5）：690-696.

Ant-colony algorithm for 3D rectangular packing problem

SONG Zhen-zhen，WANG Jin-min
（School of Mechanical Engineering，Tianjin University of Technology and Education，Tianjin 300222，China）

Abstract：A packing ant-colony algorithm is proposed for the 3D rectangular packing problem.The algorithm obtains initial information and packing initial solution of ants by two ways，specific values and random values. And the article takes different pheromone evaporation coefficients in the iterative process，making the random of update information values stronger，which improves the searching optimization of the algorithm.Through the calculation of some cases，it indicates that the packing results are better than the existing literature by the algorithm of the article.

Key words：packing problem；ant-colony algorithm；volatile coefficient

作者简介：宋真真（1989—），女，硕士研究生；王金敏（1963—），男，教授，硕士生导师，研究方向为智能布局、计算机辅助设计与图形学.

基金项目：天津职业技术师范大学科研发展基金资助项目（KJ14-64）.

收稿日期：2015-07-09

中图分类号：TP301.6

文献标识码：A

文章编号：2095－0926（2015）03－0025－04