英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

用于最小生成集问题的遗传算法

给定一组正整数S，最小生成集问题在于找到具有最小基数的一组正整数T，使得S的每个元素可以表示为T中的元素的子集的总和。它构成自然 组合数理论中的问题，与一些现实世界的问题有关，如规划辐射治疗。

我们为这个问题提出了一个新的表述（基于多背包问题的术语），用于设计一种进化方法，其性能由三种搜索策略驱动; 一种用于构建初始解决方案的新型随机贪婪启发式方案，由实数交叉点启发的专用交叉运算符，以及并入避免过早收敛的重启机制。 涉及多达100,000个元素的问题实例的计算结果表明，我们的创新遗传算法是现有方法非常有吸引力的替代方案。

1. 介绍

他的最小生成集（MGS）问题，组合数理论中的一个自然问题[1]定义如下：给定一组正整数，S = {s1，。 。 这个问题包括找到不同整数T = {t1，...的最小基数集合。 。 称为生成集合，使得S的每个元素等于T的子集的总和.MGS问题已被证明是NP-hard [1]，并且与其他问题相关， 规划辐射干预[2-4]：S的元素代表各个点所需的辐射剂量，而T的元素代表同时递送到多个点的剂量。 那么，目标是找到适当组合的剂量集合（T的子集），产生初始要求（S）。 其他变体，即T的元素可以是负数或分数的情况，也被认为是别的。

Collins等人提出的贪心算法到目前为止，[1]是MGS问题的唯一提出的方法。其想法是通过其他整数sj，先前接受的解决方案组件tk和新的候选解决方案组件d的组合来表示最大的整数集合si。重复该过程，直到所有整数siisin;S具有基于解的组合的表示。 Fagnot等人[7]给出了最小2生成集合的一些基本属性，MGS问题的自然限制，其中S的每个元素必须由T中的至多两个元素的总和表示，并证明其硬度。然而，令人惊讶的是，从实际的角度来看，迄今为止（据我们所知），并没有采用单一的元启发式方法来解决这个问题。这个事实是我们开发一种旨在优化MGS问题的遗传算法（GA）的主要动机。 GA是一种众所周知的元启发式，已被证明在解决硬优化问题方面非常有效。

在GA中，称为chromo-somes的候选解决方案的群体使用三个遗传算子在连续世代进化：选择，交叉和突变。 首先，基于一些标准，每个染色体被分配一个适应度值，然后调用选择机制来选择相对适合的染色体作为繁殖过程的一部分。 然后，通过交叉和变异算子创建新的染色体。 交叉通过重组现有特征产生新的个体，而使用变异算子来维持群体多样性，以避免过早收敛。

本文提出的成功解决MGS问题的方案有四个方面：

1.我们使用众所周知的多重背包（MK）问题中使用的术语重新定义了MGS问题，该问题已经在这类算法中进行了广泛的研究。

2.我们设计一个专门设计用于在合理计算时间为给定MGS案例生成可行解的随机贪心程序。 高度限制的组合优化问题，如MGS问题已被证明是元启发式求解器的挑战[10]。 这是一个难以定义一个有效的邻域的情况，因此没有本地搜索可用。因此，为了产生实际的实现，通常需要并入专门的建设性贪婪启发式。

3 在新制定的基础上，我们提出了一种GA方法来处理包含初始种群生成方法（基于所提出的随机贪婪算法）的MGS问题，其目的是获得多样化且足够的质量解决方案 和重新启动机制，替代通常的GA突变，以在染色体变得非常相似时再生群体多样性。

4 此外，拟议的GA包含创新专业化的重组运营商，灵感来自于实参的交叉[12]，将后代的可行性和合法性作为解决问题的方法。

本文的其余部分安排如下。 第2节介绍了基于MK的MGS问题的解释，它们的相似之处和差异。 第3节介绍了MGS问题的新的随机贪婪启发式，它是构建GA的基本组成部分之一。 第4节描述了MGS问题的进化方法。 第5节提供了对GA性能的分析，并与现有文献进行了比较。 最后，第6节总结了结果和结论。

1. 将搜索对象作为背包的MGS问题

在MK问题中，我们给出了一组对象O和一组背包K.每个对象ojisin;O具有利润p（oj）和权重w（oj），并且每个背包kiisin;K具有 一个容量C（ki）。 MK问题中的目标是将每个对象分配给至多一个背包，使得每个背包中的对象的总重量不超过其容量，并且包含在背包中的所有对象的总利润是 最大化。 其数学公式如图1所示。 1（左）[13,14]基于一组二进制变量xoj ki，其中xoj ki = 1表示对象oj包含在背包ki中，而xoj ki = 0。 对于MK问题和其变体，GAs和其他元启发式应用程序[15-17,14]通常将解码解码为整数数组，其长度等于对象数，并且相应的第零个元素表示包含在其中的背包ki ，如果没有分配给任何背包，则为无效值。

在MGS问题中，元素siisin;S可被识别为容量等于其si值（C（si）= si，siisin;S）的背包。 然后，候选生成集合中的元素tjisin;T是可以插入到背包中的对象，权重等于它们的值（w（oj）= tj，tjisin;T）。 以这种方式，可以将MGS问题的目标重新构建为构造较小的对象集合T，使得每个背包通过将包含不同对象的副本完全填充。注意到没有大于最大值的整数值j S中的元素，Smax，可能属于发电机组T，我们可以重新构建构造问题将对象T的集合作为从集合{1，...中选择的集合......，Smax}将属于T.

MK数学公式可以适应MGS问题，如图1所示。 1（右）。 有xjsi = 1表示整数j有助于填充背包si（xjsi = 0，否则）; 因此，xj必须等于1，表示整数j属于生成集T.

而这种基于背包的解释为MGS问题提供了一个数学适应性和图形比喻，这就是找到适当地组合填充所有knap-sacks的对象，它们的区别应该清楚地表明：

容量约束（2）变为等式约束，即背包中对象的权重之和必须等于其容量。

没有利润，所以他们从目标（1）消失。 另外，将目标转化为最小化问题，减少创建对象的数量。

物体可以放置在多个背包中，因此不存在约束（3）。

背包不能携带两个或更多具有相同权重的对象，因此整数j在约束（2）中的求和中只应用一次。

必须创建对象来解决问题，而最初在MK问题中给出对象。

他成为一个困难的限制，因为求解者必须考虑每个可能的对象的组合。 这可以通过在集合{1...max}中的元素的组合的空间中搜索来解决,利用数学公式（图1，右），或者为可能的Smax对象应用具有整数数组的元启发式。 然而，这对于大的Smax值来说是不切实际的。 例如，我们无法获得CPLEX V12.1和图1中的模型的任何有效解决方案。 1（右）为| S |的随机实例 = 20，Smax = 4096。

关于我们提出的GA，由于将MG问题的GA直接适应于MGS，所以不可行，我们将提出一种随机贪婪启发式，从{1，。 。 。，Smax}（第3节）。 我们的GA将在不同阶段使用它，即初始化，重启和交叉。 为了解决极其困难的问题，一个常见的策略是将启发式下级过程纳入元启发式阶段。

最后，请注意，给定这个重新组合的背包问题的解决方案，即一组对象（O = {oj}），我们可以通过构建具有对象的权重值的集合来直接获得S的生成集合T（T = {tj = w（oj），ojisin;O}）。

3 随机贪婪启发式

在本节中，我们提出了MGS问题的随机贪婪启发式，称为RG-MGS。 RG-MGS的设计（图2）是在本文提出的MGS问题的新公式中规定的。 因此，其输入之一是与S相关联的背包K集合，输出是所创建的对象集合O.

RG-MGS从所有背包开始，一次构建一个对象，将其添加到当前的部分解决方案O中，直到所有背包完成。 具体来说，算法管理背包中的空闲空间，F = {f1，。 。 （fn}（fi存储背包ki中的可用空间），并创建一个具有属于集合{1，...的权重值的对象。 。 ，Fmax}（最大可能物体的重量等于任何背包中的最大自由空间，Fmax），目的是在插入新物体之后最大限度地减少knap-sack中的全局自由空间。 为此，RG-MGS使用具有权重omega;来填充的对象的全局贡献（（omega;，F））

nomega;，如果omega;le;fi

（omega;，F）=ı（omega;，fi），其中ı（omega;，fi）= 0，

自从计算全球贡献全部集合{1，...，Fmax}中可能的权重值可能成为耗时的策略，RG-MGS采用替代随机方式采样技术包括随机选择nsample（RG-MGS的控制参数）权重值（步骤4之后，它选择一个全球贡献值,在这些采样权重之间是最大的（步骤5），并建立一个对象具有正确的权重（步骤6和7）。 随后，RS-MGS将足够的新物品引入每个背包中可用空间并更新自由空间（步骤8-13）。表示包含对象的背包的集合o。 算法结束当分配给背包的对象完全是他们的各自的能力。

在RG-MGS运行期间，可能会创建对象具有相同的权重，然后是最终相关联的生成集合将变得不可行。 因此，RG-MGS结束执行通过调用一个叫做Eliminate-Duplicates的修复程序，

这解决了这个问题的情况（图3）。 的主要思想消除重复如下。 每当有存在两个不同的对象，oi和oj，其中w（oi）= w（oj），这个过程注意包含两个对象的背包套（（oi）cap;（oj））。 如果这个集合不是空的，那么一个新的对象有两倍的oi的重量被创建（步骤4），它替换了oi和oj这些背包。 此外，消除重复替换oj在那些独特包含oj的背包中。 最后，它删除解决方案的对象oj（步骤12）。 如果已经有一个对象以oi的重量的两倍，程序将解决新的在随后的迭代中发生冲突。

综上所述，确定用相同的权重替换两个对象重量和另一个重量。在另一种基于构造的元启发式，即GRASP，通常通过选择iter-从受限候选人名单随机的元素,元素具有良好的评估。 最近的设计却有证明了这种经典设计可以在一些问题上得到改进首先应用随机抽样，然后执行贪心,从采样元素的选择（参见例如[21]）。 我们的这里的建议符合最近的GRASP设计。

1. MGS问题的稳态遗传算法

GAs [8,9]是基于遗传过程的自适应方法生物有机体。 它们广泛应用于许多组合和实参优化问题。 GAs从ini-随机解决方案（或种子候选人有一些好的启发式方法）形成所谓的染色体群体的大小Np。 染色体从人口向人口发展通过连续迭代，称为世代，保持Np固定在整个迭代。 每个染色体都有一个适合度值与之相关联。

在每一代，染色体通过适应度进行评估功能（与问题的目标相关）来评估它们能力在下一代生存下来。 最适合的chromo-选择一些人组成一个新的人口，随后进行遗传操作：单个染色体的突变和两个之间的交叉（父母得到后代）。 遗传性运营商被应用于选定的解决方案来生产新的解决方案父母的遗传特征和相关的适应性,ness函数评估它们实现目标的程度

的优化问题。

一代放弃现有人口造成了整个后代的人口，这成为当前新增的人口。 相反，稳态GAs ]通常会产生一个单一的解决方案，并将其插入到任何一个时间的扩展。 替代/删除策略定义了当前人口中的哪一个成员被迫为新的后代而灭亡，以便在下一次迭代中竞争。

在本节中，我们介绍使用高级稳态GA来解决MGS问题。 接下来，第4.1节总结了所提出的GA中的整体进化过程流程，第4.2节解释了设计用于从两个父色谱柱生成可行解的特定交叉算子的细节。

4.1 总体GA算法

提出的GA的概要，称为GA-MGS，如图1所示。 它是一个稳态GA，其染色体表示填充不同背包的对象集合，其适应度值等于所使用对象的数量。 染色体编码每个物体的重量和放置在那里的背包组。

GA-MGS分为两个阶段：第一，初始化，在此期间，人口填充了由RG-MGS程序生成的Np解（第3节），接下来，群体进行采用以下操作的进化循环 ：

1. 使用二进制浏览选择机制（步骤5和6）从群体中选择两个父母。 这种选择技术广泛应用于GAs，由于其简单性和逃离本地最优性的能力。 它选择从人群中随机挑选的两个适合的染色体。
2. 创建应用交叉算子的子代（步骤7;第4.2节）。 这是一种在组合两个父母的特征的个人之间共享信息以产生潜在更好的后代的方法。 基本思想是，良好个体之间的遗传物质交换有望产生好的或更好的个体。 因此，该操作员利用了人口中可用的信息。
3. 从人口中选择一个人，并决定这个个体是否被后代所取代（步骤9-12）。 对于这个决定，我们考虑替代最坏的策略，只有新人更好的时候，才能取代最差的人口。 这种机制即使当随机选择父母时也会引起高选择性压力。
4. 当人口收敛（人口中所有个体的适应度函数值相等）时，重启过程被触发（步骤13-18）。 在这种情况下，人口由RG-MGS方法产生的Np-1新解决方案和从当前人口中随机选择的新解决方案重新进行。 这种多样性的来源允许与替代和父母选择机制相关联的高选择压力被抵消，目的是避免过早收敛。

重复这些步骤，直到满足某些终止条件（例如最大迭代次数或允许的最大计算时间;步骤4）为止。 在迭代过程中产生的最佳染色体Cb作为总体结果保持不变。

4.2 交叉运算符来诱导对象偏好

交叉运算符一直被认为是指导GA搜索过程的主要组成部分[9,26]，因为它收集，组合和利用先前样本的可用信息来影响未来的搜索方向[27 -29]。 实际编码遗传算法[30,31,12]是一个突出的研究领域，在复杂的实际编码交叉算子的开发中已经付出了巨大的努力。 Herrera等 [27]提出了一种分类法，对实际编码的GAs的交叉算子进行分类。 基于邻居的交叉运算符是一类已被认为在许多情况下有效的分类法。 他们通过抽取与父母基因价值相关联的概率分布来确定后代的基因，这些分布通常定义分布的中心位置和程度。

在文献中提出的几个邻域交叉运算器的启发下，我们在本节介绍了三个交叉运算器（

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[139572]，资料为PDF文档或Word文档，PDF文档可免费转换为Word