英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
带填充问题的混合蚁群算法求解：排列顺序是可学习的
Dhananjay R. Thiruvady Bernd Meyer Andreas T. Ernst
摘要：本文通过混合基本元启发算法和蚁群算法来解决带填充问题。在带填充问题中，一些固定长宽的矩形件要求被放置在一个宽度一定，但高度没有限制的带子中，并且矩形件不可重叠放置，目标是使填充带的所用的高度最小。我们分析了一种被广泛使用的基本元启发算法和一些混合蚁群算法。并比较了混合蚁群算法的四个不同的模式：只有的序列学习模式、只有矩形件旋转方向学习模式、两种指令都有但彼此独立、旋旋转方向学习模式受狗关键排列位置影响。我们的研究表明：混合蚁群算法相比基本元启发算法有极大的优势。实验进一步证明即使是在只有序列学习模式下，混合蚁群算法也表现了可观的性能提升。有趣的是，矩形件旋转方向学习模式下，混合蚁群算法表现了最佳的边际优势。本文提出的最佳混合蚁群算法的性能显著优于先前文献中的带填充元启发算法。
1.介绍
带填充问题是与将固定长宽的工件不重叠的放置在宽度一定，高度不限的填充带有关的问题[15]。这个问题与矩形件的放置有关，具体来说：一些长宽一定的矩形工件被放置在填充带中，目的是使填充带的高度最小。矩形件可以被旋转90°以达到更加紧凑的填充。工件的切割不必一定要一刀切[8]。带填充问题已被证明是NP-complete问题[9],，所以元启发算法是一个明智的解决方式。
像很多运筹学的NP-hard问题一样，简单的元启发算法就可以令人惊奇的将SSP问题可很好的解决。对于SSP问题，通常使用左下侧位置解码(BL[12],[14])和左下侧填充解码(BLF[10])这两种元启发算法是。基本BL解码[12]会根据给出的序列和工件旋转方向挑选出工件，并连续的将它们放置在填充带上。工件开始位于填充带右上方，然后尽可能的向左下滑动。这一过程将一直重复直至工件再也不能向左或者向右滑动。显而易见的是BL元启发算法在布置工件过程中会造成很大的空隙。而BLF算法可以改善这一情况，它对左下角的所有间隙添加候选点，以使BL算法可以产生并选择出下方最左侧点。图a显示了BL算法产生的候选点，图b给出了BLF产生的可能放置点。标记位于工件1和工件4之间的角落中的点。下一个工件将总是被放置在下部最左的位置，所以工件5将放置在工件4的上方，然后BLF算法将工件6放置到由此产生的间隙中。然而BF算法将不会利用这个间隙，反而将工件6放置到工件3上方。
Fig.1.BLand BLF placement heuristics;(a)a partial layout with BL placement points,the small circles show candidate locations for the next item;(b)the same partial layout with BLF placement points;(c-d)subsequent items are placed as far bottom-left as possible.
即便工件的顺序是随机产生的（详见图二，通过BLF算法和随机搜索解决的197个工件问题），BLF算法自身也表现出令人满意的性能。这就产生了一个问题，可学习的元启发算法是否可以提高BLF算法的基本性能？Hopperamp;Turton在文献11中研究了关于SSP问题的算法，其中元启发算法包括基因算法，模拟退火算法和自然进化算法。在他们的研究中，这些元启发算法被用来产生一个工件序列，这个序列随后被BF/BLF编码以产生完整的布置。Hopperamp;Turton推断BLF启发式布置算法完成了最主要的工作，而元启发算法的序列学习仅能在小数量规模问题下产生重要的贡献。
于此相比，我们在本文中表明良好设计的元启发算法可以使BLF算法的性能大大的提升。因为这是一个排序问题，所以蚁群算法(ACO[6])是一个合适的选择。我们的蚁群—BLF混合算法相比于BLF算法实现了更好的填充效果。并且与文献[11]中最好的混合算法相比，平均减少了68.8%的空置空间。在大数量规模问题上，我们发现蚁群-BLF算法有显著的性能提升。
本文结构如下：在第二部分我们简单的回顾了蚁群算法和我们蚁群算法关于SSP问题的细节处理。第三部分展示了我们的实验和结果。在第四部分，我们讨论了我们的发现和其他文献中的报告。第五部分总结对未来工作的建议。
Fig.2.Results from the problem instance c7-2;(a)A packing obtained with RR(b)A packing obtained with ACS4
2.蚁群优化算法
文献7首次提出蚁群优化算法，该算法是受大规模的蚁群觅食行为所启发得出的。当蚂蚁在食物源和巢穴往返时，它们会沿途释放信息素。新离开巢穴的蚂蚁会通过环境中信息素的浓度梯度来概率性获取食物，并且信息素会随着时间而衰变减少。由此，一个自限制的正反馈回路得以创立，并且通往食物源道路上的信息素越来越多。由于信息素的释放量往往直接受食物源质量的影响，或者间接受食物源与蚁穴的距离调控，所以大多数的流通更加倾向于减少路程长度来获得更得满意的食物源[4]。
蚁群算法利用这一原理来解决组合优化问题。基本的算法框架是随机搜索，并通过单独的解的组件逐步构建出候选解。理论上讲，算法中每一代中的每一只蚂蚁都会构建出一个候选解。在每一步中，蚂蚁会通过新的解的组件来扩展它的潜在候选解，直至获得一个完整的解。通过一个启发式的偏好因子——信息素，下一个解的组件会被概率性的选择。在排序问题中，这个信息素模型喜欢根据刚刚被选择的解的组件来挑选下一个解的组件。在构建解时，每只蚂蚁都会通过增加相应的信息素的值来强化它们先前做过去的选择，而此过程是会是解的质量(客观价值)所调控。通过一正反馈过程，大多数搜索将越来越多的关注优秀的解。
蚁群算法首次被应用是在旅行商问题，而且自此被成功的应用在各种各样的组合优化问题中[6]。文献13阐述了ACO算法应用于二维装箱问题，一系列工件被放置在尺寸一定的箱子中，目标是使被使用的箱子最少。
A.蚁群算法对于装箱问题
这这个研究中，我们使用了精英升级模式的标准蚁群变异算法，也就是说只有最优解才会进行信息素更新。当一个决策被做出的时候，相应的信息素会立即减少（局部更新），在每一代结束后最优解的响应信息素的值会得到奖励增加（全局更新），而没有其他信息素的衰变。算法一阐述了最基本的蚁群算法。
算法中应用了四个数据结构，分别是蚂蚁总数(ants)、每代最佳蚂蚁(iterationbest)、所有代中的最佳蚂蚁(globalbest)和信息素矩阵(pheromones)。在每代中，每只蚂蚁递增性的使用信息素构建一个解(selectNextComponent())。当一个解的组件被选择，相应的信息素的值会衰变减少(localPheromoneUpdate())。如果一个比当前最优解(globalbest)更好的解(iterationbest)被发现，那么当前最优解将会被该解替换。然后，全局最优解相应的信息素将会被存储和衰变(globalPheromoneUpdate())。
对于SPP问题，我们可以从两个不同的方面学习使用蚁群算法。如上文中提到的，第一个方面是做出供BLF算法编码的工件序列。第二个方面是对每个单独工件的旋转。在旋转学习模式写，我们可以通过学习优秀的解从而尝试得出工件k水平或垂直放置的通用（全局）偏好，或者可以通过工件k在所有工件序列中的位置尝试得出一个偏好旋转方向。相应的，我们构建了四个不同版本的ACS算法来进行比较：ACS1算法仅仅学习工件顺序和随机旋转方向。在ACS1算法中的信息素值初始化蚂蚁总数(ants)、每代最佳蚂蚁(iterationbest)、所有代中的最佳蚂蚁(globalbest)和信息素矩阵(pheromones)。
forilarr;1tomaxiterationsdo
forkisin;antsdo
candidates={1,...,numberOfComponents};
pickrandomstartcomponentjisin;candidates;
antk.sol={j};
candidates=candidatesminus;{j};
whileantk.solisnotcompletedo
last=j;
j=
selectNextComponent(last,pheromones);
append(antk.sol,j);
candidates=candidatesminus;{j};
localPheromoneUpdate(last,j,pheromones);
end
end
iterationbest=findBest(ants);
if(iterationbest.costlt;globalbest.cost)then
globalbest=iterationbest;
end
globalPheromoneUpdate(globalbest,pheromones);
end
Algorithm1:BasicAntColonyOptimizationFramework.
算法在工件i后根据偏好设置直接处理工件j。ACS2算法学习工件顺序和全部工件的旋转方向，但这两者是相互独立的。因此，在ACS2算法中，我们有两个不同的信息素模型，前一个tau;ij与ACS1中相同用于学习工件顺序。第二个模型中，（risin;{rotated,original}）学习工件i的全局旋转方向。相似的，ACS3算法学习工件顺序和全部工件的旋转方向， 但是它的偏好旋转方向受工件在序列中的位置所影响。ACS3算法用单个的信息素模型tau;ij替代了双信息素模型，但是它显然包含了在所有工件中每个工件的旋转方向。如果问题有n个工件，ACS3算法将其转化为有2n个工件的等价问题。1，.....,n工件是具有初始旋转方向的工件，n 1，.....,2n是将前n个工件旋转90°。当一个工件mle;n被选中为解得组件，那么工件m和工件m n将从候选组合中移除，同理，当工件mgt;n被选中，那么工件m和工件m-n都将被移除。最后，ACS4算法是将ACS1扩展以测试所有工件的可能旋转方向，也就是说它会实现迄今为止最小的填充带总高配置。ACS4因此被用来学习旋转方向以支持更加详细的测试。
在ACS1算法中，selectNextComponent(i,p)步骤会选择下一个解的组件，为工件J的概率是
（1）
q0是固定参数用以决定选择的贪婪程度，eta;ij是一个静态因子用以影响搜索偏好。Ii是待排序的工件组合，ACS3算法的选择工作与ACS1算法相同，但是工件集合包含每个工件的两个旋转方向。
对于ACS2算法，有两个决策需要作出。第一个决策是决定工件的放置位置，这与ACS1和ACS2的方式相同。第二个决策通过使用第二个信息素决定工件的旋转方向。在第一步中，工件过概率p来被选择。
（2）
四个版本的ACS算法信息素tau;更新方式相同。局部信息素更新公式如下
tau;ijlarr;(1minus;rho;)times;tau;ij rho;times; （3） 0le;rho;le;1是一个参数，n是问题实例中的工件总数。全局信息素更新公式如下
tau;ijlarr;(1minus;rho;)times;tau;ij delta;tau; （4）
delta;tau;= (5)
H是最优解下的填充带高度。
在ACS2中，信息素的更新也是相似的方式。对于每个工件i被使用的旋转位置r，局部信息素更新公式如下：
(6)
对于每个工件i在全局最优解中的被使用旋转位置r，全局信息素更新公式如下
(7)
delta;tau;与公式5中相同。
- 实验和结果
我们首先建立的BLF算法的性能基线。我们建立了两个BLF算法版本：第一个随机选择工件顺序和旋转方
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[146065]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
