多维分配问题的模因演算法

南京信息工程大学课程名称 专业英语院系 信息与控制学院0000年0月0日多维分配问题的模因演算法GregoryGutinandDanielKarapetyan伦敦大学皇家霍洛威学院，英国，伦敦gutin@cs.rhul.ac.uk,daniel.karapetyan@摘要：众所周知，多维分配问题(MAP或有尺寸情况下的S-AP)是分配问题的延伸。多维分配问题(MAP或S-AP)的尺寸的情况下是众所周知的分配问题的延伸。虽然在S值越大情况有许多许多应用，但MAP中研究得最多的情况是3-AP问题。本文中，我们提出了MAP问题模因演算法，这是一个遗传算法与局部搜索过程相结合的模因论算法。本论文的主要创新是一个动态调整种群规模的想法，该方法在给定小和大的固定运行时间下都表现出了出色的灵活性。1.介绍多维分配问题(MAP或S-AP)的尺寸的情况下是一个众所周知的指派问题(AP，线性AP问题)，这完全是二维MAP情况下的一个延伸。MAP有着一些列的应用，详见［1］。对于给定的s(s>2)，S-AP问题表述如下所示。令X］=X2=...=X,=｛1,2,...,n｝，且X=X1xX2x...xXs。对于向量eeX来说，匕表示第j次调整，即eeX。每个向量eeX都被赋予一个非负权重^(e)。如果对于任意的，。k与jeb,2,...,s｝，均有/eiei成立，那么A集合”凌.疽被认为是一个(有可能的)局部分配。那么A权重为w(A)=Z«w(ei)。分配问题(或完全分配问题)是具有n个变量的局部分配问题°S-AP的目的就是找到一种最小权重的分配策略。尽管S-AP在s>3情况下是一个NP难题［3］，但AP仍然可以在多项式时间内解决［2］。在以下方面，MAP是一个很困难的问题。MAP权重矩阵中包含总数量为ns个的数值，因而它存在n!s-1种可能的分配策略，现在已知的最快算法来寻找最优分配所需要的时间仍需O(n!s-2n3)。不失一般性，我们令ei=1，从每个可能的组合ei中寻找到最后一维的e，求1 j s解相似的线性AP问题最优值所花费的时间为O(n3)。只有n2个权重，(N-1)!个可能路径的旅行商问题，其解决花费的时间为O(n22n)。相比较而言，MAP问题要复杂得多。算法模因演算法是一种遗传算法与局部搜索相结合的新算法。其主要思想如下所示：产生第一代种群，即可能的解决办法的集合。对第一代种群进行局部搜索。重复以下过程直至达到迭代终止条件：运用所谓的遗传算子，从上一代的种群产生新一代种群。利用局部搜索策略已达到改善种群的目的。选择若干最好个体进入到下一代种群中。虽然模因演算法里的遗传算子集和其应用方法相差可以很大，但其总体步骤是相同的。在本算法中，我们用以下步骤来获取下一代种群：gi+1=selection({gi}Umutation(gi\{gi},p,^)UC)其中gk表示第k代种群和gk表示第k代种群中的第j次分配。gk表示第k代的最佳分配。常量pm=°・5和um-0.1分别表示突变概率与强度。选择算子输出的是m,+1个不同的最佳分配方案，其中m.表示第k代种群大小(如果已给定的方案数量比m.+1还要少，选择算子则将所有方案输出并且相应地更新m的值)。i+1为了获得集合C(交叉部分)，我们重复的进行局部搜索crossover(g：,gp操作(P-m+—m.)12次，其中u，ve{1，2，...,m,}在每一次交叉操作中随机选择，p=3表示在选择算子中有多少次需要产生更多的分配方案。种群的变异函数定义如下：fLocalSearch(perturb(g,u))ifr<pmutation(G,p,u)=U<Ig otherwisegeG侦其中re[0,1]，每次为一个随机数。交叉算子，扰动算子和局部搜索算子将会在后面讨论。编码：遗传算法里编码是一种解的序列，它代表一个数值，就像布尔值或布尔数字一样。遗传算子中使用这种方式来表示。Huang,G和Lim,A［4］提到，在已知前两维的前提下，通过局部搜索确定第三维（需要注意文献［4］中的算法仅针对3-AP问题）。为了不失一般性，由于第一维通常情况下是固定的，需要存储只有一个分配的第二维。然而，编码需要一个特定的局部搜索和并且目前为止只对3-AP问题解决方面很有效。我们使用一种不同的编码：一个分配向量看作一个原子，因此编码后的分配仅仅是一个向量的组合。向量总是以首坐标升序的顺序排列，如（2,4,1），（4，3,4），（3，1，3），（1，2,2），排序后为（1，2,2），（2,4，1），（3，1，3），（4,3,4）。我们将此两种方法视为等价的，因为他们有等价的编码。终止条件：通常情况下，模因演算法的终止条件在达到特定点之后，在此之后进行的迭代，不是无意义就是效率不高。常用的做法是记录没有产生的最佳个体的迭代次数，当迭代次数达到莫已设定的值时，算法停止。在本文中我们使用不同的方法。为了能够正确地比较不同的算法并且满足现实世界的要求，我们限定了算法的运行时间。除了前面提到的终止条件的优点之外，更值得注意的是，它还可以根据需要灵活地产生快速或高质量的解决方案。种群的大小：模因算法里运行时间匹配给定边界的最常用的方法，就是产生一些固定大小的种群，直至迭代结束。很显然，种群过多与过少都会对模因算法的运行产生消极的影响。因此，我们需要固定种群的总数量和改变每个种群的规模。通过计算的实验结果表明，在固定运行时间的情况下，最适合的种群规模大约为50，而且它并不依赖于局部搜索程序或给定的时间。因为局部搜索的运行时间可以差别很大（比如上一代的种群通常包含有比第一代更好的解决方案,因此其处理速度会变得更快。），并且也令算法更简洁,我们根据已有的时间动态地调整种群的大小，以令种群的总数量总是趋近于I。特别的，下一代种群规模的计算公式如下：区+i=（niax{min{寸六，k}4}［fe otherwise其中T是给定的限制时间，，是已用的时间，A表示生成以前种群所花费的时间，I是规定的种群限制数量，K=1.25是一个常量，用来限制种群规模变化程度。需要注意的是，m，是实数，第i代的实际种群规模气定义如下：

if(p-|_m-J— )iseven+1otherwise上述公式保证了P•mt1-m,足够合适，也就是由交叉所产生的分配数量，甚至是种群规模永远不会太小。第一代种群的规模是以不同寻常的方式获得的(见下文)。第一代种群：文献［5］中提到(利用模因算法和自启发结构相结合的方式，已通过实验证明［6］)，任何MAP与元启发式问题最好从开始从贪婪自启发方面着手。因此,我们从贪婪算法入手，然后经过扰乱步骤获取第一代种群的子个体。如下所示g；=LocalSearch(perturb(greedy,Af/))其中greedy是经由贪婪自启发步骤获得的分配，叩=2.0是扰动强度系数。因为扰动的执行为随机性改，因为保证了第一代种群的多样性。该算法对于第一代种群生成的分配直到T/1时间，但无论如何都会至少产生4次(前面提到，T是给定的限制时间，I是规定的种群限制数量)。交叉:一个典型的交叉算子包含了两种方案与两个父代，经过交叉产生两个新解决方案，两个子代。交叉是主要的遗传算子方法，也就是遗传算法的精髓。由于选择操作的存在，那么好的染色体片段与解决方案相比其他的更容易遗传到下一代所以如果父母双方都有一些相似的染色体片段，那么说明这些染色体片段很可能是够优秀的，他们应该毫无改变的复制到子代染色体中。而其他部分的染色体可能是随机混合和变异的，即便如此他们也不应该被完全舍弃。最标准的交叉，如一点交叉和多点交叉，均不保留该个体的可行性，因为并不是每个向量序列都可以解码成一个可行的分配方案。我们提出了一个特殊的交叉算子。设x和y是父代个体和x'和y'为子代个体。首先，我们检索父代个体中的相同向量并初始化向量集：x，=y=xAJ。设k=1xAyl，即在父代两个体中染色体片段相同部分的数量，p=x\x■和q=y\y，其中p和q是有序集。兀与巧是大小为n-k的随机排列。对于每个J=1,2,...,n-k，交叉集为*=x■up”.、的概率为80%，而y'=y'Uq的概率20%。兀(J) w(j)因为这个过程会产生不可行的个体，因此它需要另外一个纠正子代个体的步骤。为了达到这个目的，每一世代产生的种群中，我们都进行如下操作。对于任意一个，，为＜i:乌=马，令乌=r，其中勇{1，2,…,,n}^{cd气}是随机选择的。最后，所有的向量按照第一个坐标升序排序，因为它是编码所需的。换句话说，我们的交叉算子将父代个体中相同的向量复制到子代个体中。剩下的向量根据随机的复制到子代个体，一个来自于第一个父体，一个来自于第二个父体，然后选择性的加入第一和第二个子个体，两者的概率分别为80%和20。既然所获得的子代个体有的是不可行的，那么交叉可以起到修正子代个体的作用，对于每一个自带个体的每一个维度，它利用随机选择正常的个体取代重复的坐标，即目前该维度还没有使用的坐标。扰动算法：扰动过程Perturb3,r)是根据给定的强度，随机的修改分配x。在模因算法中，扰动被用来产生第一代种群和当出现下一代种群的时候对已存在的分配进行变异操作。扰动过程产生［nR/2］次随机互换。每个交换随机选择两个向量和某些维度，交换相应的坐标：交换弋与弋，其中u,vg{1,2,...,n}而且dg{1,2,...,s}为随机选择;重复此过程［叩/2］次。例如，perturb3,1)修改了分配x中的n个向量。实验结论：广泛的计算实验依赖进行大量的实例家庭［1］和几个局部搜索程序［5］。MDV2的结果，选为模因算法的最佳局部搜索过程，MDV2结合了MDV与双目标问题［5］。实验结果表明［1］,考虑到相同的运行时间，本文提出的算法明显优于所有高质量的MAP算法。值得我们注意的是，我们对GK算法中的算法参数，比如I，Rf，R刀尝试使用不同的数值进行试验，我们得出结论是改变这些数值后，对结果的影响很小，不会明显影响算法的性能。参考文献［1］ .Gutin,G.,Karapetyan,D.:Amemeticalgorithmforthemultidimensionalassignmentproblem.PreprintinarXiv(2009),/abs/0906.0862［2］ ..Kuhn,H.W.:Thehungarianmethodfortheassignmentproblem.NavalResearchLogisticQuarterly2,8397(1955)..Garey,M.R.,Johnson,D.S.:ComputersandIntractability:AGuidetotheTheoryofNP-Completeness.W.H.Freeman,NewYork(1979)..Huang,G.,Lim,A.:Ahybridgeneticalgorithmforthethree-indexassignmentproblem.EuropeanJournalofOperationalResearch172(1),249-257(2006)..Gutin,G.,Karapetyan,D.:Localsearchheuristicsforthemultidimensionalassignmentproblem.In:Proc.GolumbicFestschrift.LNCS,vol.5420,pp.100-115.Springer,Heidelberg(2009)..Karapetyan,D.,Guti