英语原文共 24 页，剩余内容已隐藏，支付完成后下载完整资料
基于分组遗传算法的一维装箱问题研究
摘要
分组遗传算法(GGA)是一种经过大量修改以适应分组问题结构的遗传算法。这些问题的目的是找到一个好的分区一个集合,或者组的成员一起集。装箱问题(BPP)是一个众所周知的赋权问题,各种大小的物品必须分类垃圾箱里面的固定能力。另一方面，基于马特洛和托特的优势准则的约简方法是迄今为止BPP优化的最佳方法之一。
在本篇论文中，我们首先描述分组遗传算法的范例作为与经典的Holland形式遗传算法和排序遗传算法相互比较。然后，我们展示了如何利用优势准则激发的局部优化来增强装箱分组遗传算法。一个广泛的实验比较表明，该组合产生的算法优于其任何一个组成部分
关键词：分组，区分，装箱，遗传算法，解决方案的编码，主导地位，减少。
1.介绍
1.1装箱问题
装箱问题的定义如下([Garey and Johnson, 79])：
给定一个有限集O的数字(项的大小)和两个常数C(箱的容量)和N(箱的数量),有可能“包你们项目分成N个箱,即是否存在一个分区的O 放入N或更少的子集,这样元素的子集之和不超过C ? 这种非确定多项式完全决策问题自然会导致与非确定多项式联系优化问题的风险，本文的主体：什么是最好的装箱，即上述区分中子集最小的数量是多少。
由于非确定多项式困难，现在还没有已知的多项式时间下运行装箱问题的最优算法。然而，[Garey and Johnson, 79]引用简单启发式，可以证明它并不比最优箱数上的一个很小的乘数差（但也不比他更好）。这个想法很直接:从一个空箱子开始，将物品一个接一个地拿出来，对于每一个物品，首先搜索迄今为止所使用的箱子，寻找足够大的空间来容纳它们。如果能找到这样的箱，就把项放在那里，如果找不到，就请求一个新的箱。将项目放入找到的第一个可用箱中会产生第一个Fit (FF)启发式。搜索最满的箱子仍然有足够的空间来放置物品，会得到最合适的结果，这似乎是一种更好的启发式，然而，它可以表现得和FF一样好(和FF一样差)，但速度更慢。在运筹学方法领域，[Martello和Toth, 90a]最近为装箱问题引入了一种更强大的近似算法，如下所述。
1.2分组问题
装箱问题是一个大的问题族的成员，其中很多问题在实践中是自然产生的，它包括将一组物品的U划分为一组互不相交的子集U i (U)的集合，即
cup; U i = U and
U i cap; U j = empty;, ine;j.
我们还可以将这些问题看作是将集合U的成员分组为一组或多组(最多为card(U))项，每一项恰好在一组中，即找到这些项的一组。
在大多数这些问题中，并不是所有可能的分组都是允许的:问题的解决方案必须遵守各种硬约束，否则该解决方案是无效的。也就是说，通常一个项不能与其余项的所有可能子集分组。
分组的目标是优化在所有有效分组集上定义的成本函数。以下只是三个例子1对于已知的分组问题，在硬约束条件下，解必须满足(其中C是任意常数)和代价函数最小化。
问题 硬约束 成本
装箱 任何组中小于C的项的大小的和 组的数量
车间布图 任何组中小于C的项的数量 车间总流量
图着色 任何组中没有连接的节点 组的数量
可以看出，分组问题的特点是成本函数依赖于组2的组成，也就是说，单独采取一个项目几乎没有意义。分组遗传算法(GGA)是一种针对分组问题的特殊结构进行了大量改进的遗传算法。Falkenauer, 93]和[Falkenauer, 94]提出了一种适用于许多不同问题的方法。[Falkenauer and Delchambre, 92]提出了一种用于装箱问题(BPP)的“原始”分组遗传算法（GGA）。
在这篇论文中，我们报道了[Falkenauer and Delchambre, 92]的分组遗传算法的一维装箱问题与[Martello and Toth, 90a]的装箱问题的最新或技术杂交（混合）。
本文的其余部分组织如下。在第2节和第3节中，我们指出了标准气体和顺序气体在用于分组问题时各自的弱点。在第4节中，我们介绍了解决这些缺陷的分组GA (GGA)。第5节给出了Martello和Toth支配标准背后的思想。第6节介绍了由于这两种技术的“联姻”而产生的BPP的混合GGA (HGGA)。第7节对HGGA与复杂的分支绑定算法MTP过程[Martello and Toth, 90b]进行了广泛的实验比较。结论见第8节。
2.标准GA（遗传算法）运算符和分组问题
在这一节中，我们研究了经典遗传算子对与分组问题相关的结构的影响。一个简单的编码方案和经典([Holland, 75]类型) 遗传算子的应用是遗传算法中采用的第一个路径处理分组问题的文献(如[Van Driessche and Piessens, 92]， [Ding et al.， 92]， [Jones and Beltramo, 91]， [Von Laszewski, 91])。我们将展示为什么我们认为这不是解决这些问题的最佳遗传算法。
2.1编码与冗余
让我们考虑最简单的编码方案，即每个项目一个基因。例如，染色体ADBCEB编码的解第一项在A组，第二项在D组，第三项在B组，第四项在C组，第五项在E组，第六项在B组
在构建有用表示的六种设计原则中(如[Radcliffe, 91])，图中给出了最小冗余原则——搜索空间中的每个成员(这里是所有有效分组的空间)应该由尽可能少的不同染色体(理想情况下正好是一个)来表示，以减少GA必须搜索的空间的大小。
上面简单的编码是非常冗余的。事实上，分组问题的成本函数只取决于项目的分组，而不是分组的编号。例如，在图着色问题中，无论实际使用的颜色(它们的名称)是什么，只有在节点上的颜色分布才算。因此，A代表琥珀，B代表蓝色，C代表深红色，D代表暗红色，
ABCADD and
CADCBB
两者编码相同的问题解决方案，即图的第一个和第四个节点分别分配一种颜色，第5和第6个节点分配第二种颜色，第2和第3个节点分配第三和第4种颜色。
该方案的冗余度(即编码原问题相同解的不同染色体数)随组数呈指数增长，即间接地随问题的大小增长。因此，遗传算法需要搜索的空间比原始解空间大得多。因此，GA的功率严重受损。
2.2 交叉
让我们看看在标准交叉下，与分组问题相关的显著(强)图式是如何从父母转移到子女的
2.2.1上下文（情景）不敏感
直接的编码导致在标准交叉下将上下文相关的信息从上下文中强制转换出来的不良效果。事实上，在上面的第一个染色体(ABCADD)中，C影响到第三个基因只有在这条特定的染色体，它意味着第三个节点不与任何其他节点分组。在跨界的时候把C从上下文中去掉会带来灾难性的后果。为了看到这一点，让我们把标准的两点交叉应用到上面的两条染色体上:
A|BC|ADD crossed with（添加交叉）
C|AD|CBB would yield（将产生）
CBCCBB as one of the two children.（作为两个子集的一个）
在没有突变的情况下，两个相同个体的重组必须产生与亲本相同的后代。上面的两个父结点对于由遗传算法解决的问题是相同的，因为它们编码的问题的解是相同的。因此，一个正确的重组操作符应该产生一个能再次编码相同解的个体。然而，上面生成的子元素编码了一个“解决方案”，它与父元素编码的解决方案没有任何共同之处:有两个组而不是四个组。
换句话说，在标准编码/交叉的情况下，虽然图式相对于染色体有很好的传输，但是在重组过程中，图式对于需要解决的问题(即优化的代价函数)失去了意义。
2.2.2模式中断
在任何对基因的编码映射项下，实际相关的分组问题通常都有很长的图式。然而，在标准交叉模式下，模式中断的概率随着其定义长度的增加而增加。换句话说，虽然经典的交叉(是否与反转匹配)在基因搜索的开始可能会收敛到一个更好的解决方案，但一旦找到了一个好的候选方案，它不但不会改进这个解决方案，反而会阻碍自己朝着破坏良好模式的方向前进。
2.2.3突变
让我们再次考虑标准编码，看看标准突变的效果，即随机选择的等位基因的随机修饰。
例如，考虑以下染色体:
ABDBAC
这个个体的突变可能产生
ABDEAC
这可能是有益的，因为等位基因E，可能从种群中缺失，出现在基因库中。
当算法接近一个好的解决方案时，问题就出现了，即开发大量相同的等位基因。
标准突变
AAABBB
例如，会导致
AACBBB
一方面，等位基因C出现在人群中，这可能是一个有益的影响。另一方面，新的染色体只包含一个元素的“组”。 由于项目分组通常会带来收益，因此与其他非突变个体相比，这个突变个体的适应度很可能会急剧下降。因此，在算法的下一个步骤中，这个个体很有可能被淘汰，对基因搜索几乎没有任何好处。换句话说，一旦遗传算法开始达到分组问题的良好解决方案，经典的变异就太具有破坏性了。
解决这些问题的一种方法是放弃突变的概念，即随机修改染色体的一小部分(最小的)，让更复杂的操作符同时作用于几个，可能是多个基因，从而获利。但是，这会得到基本上忽略染色体上基因的操作符。我们在下面的4.2节中说明，可以采用更常见的路线。
3. 排序遗传算法操作符和分组问题
在这一节中，我们研究排序遗传算子对与分组问题相关的结构的影响。另一种方法是应用表示集合成员排列的编码方案，以及排序遗传操作符如[Smith, 85]， [Bhuyan et al.， 91]， [Jones and Beltramo, 91]， [Reeves, 94])。我们将再次说明为什么我们认为这种方法不是解决这些问题的最佳方法。
3.1编码与冗余
处理分组问题的另一种方法是表示条目的排列(上面第1节中集合U的成员)，并使用一种解码机制，揭示条目实际分配给每个染色体对应的组(集合的结果分区)。解码机制通常是按照染色体给出的顺序逐一考虑这些条目，并将它们分配给第一组可用的条目。
为了清楚起见，让我们考虑一下装箱问题。假设有10个项目要打包，编号从0到9。例如，一条有效的染色体中，每一项只出现一次
0123456789。
这种编码是高度冗余的。实际上，假设上述chromo-some中的项按如下方式进行分区
0123|45678|9
即有三个箱子，一个箱子里装着0到3的物品，第二个箱子里装着4到8的物品，第三个箱子里装着9的物品。现在，具有相同箱内容的项的任何排列， 例如
3210|45678|9 或
87645|1032|9 ,
编码原装箱问题的相同解决方案。对于第2节中简单的编码，该编码的冗余度随着实例的大小呈指数级增长。遗传算法（GA）的力量再次被严重削弱。
3.2 交叉
3.2.1上下文（情景）不敏感
与使用第2节编码在染色体上操作的经典交叉程序一样，大多数使用置换编码的有序交叉程序在重组期间将上下文相关的信息抛出上下文。
事实上，考虑到解码染色体的机制，很明显，在染色体编码的溶液中，一个基因的意义，在很大程度上取决于它之前染色体上的所有基因。例如再考虑一下装箱问题和染色体
0123456789，
假设它像上面那样从左到右被解码。这条染色体编码的解决方案，其中项目4至8在同一组。然而，这一信息取决于群体左侧的基因，即染色体头部的基因。例如,染色体
9123456780 或
9012345678
很可能对装箱问题的不同解决方案进行编码。实际上，根据项目的大小，分别填充了项目9、1、2或9、0、1的箱可以填充到其他任何项目都无法填满剩余的空间
全文共22161字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[1245]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
