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

南京信息工程大学 课程名称专业英语 院系信息与控制学院 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，求1js解相似的线性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<IgotherwisegeG侦 其中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）。我们将此两种方法视为等价的，因为他们有等价的编码。 终止条件：通常情况下，模因演算法的终止条件在达到特定点之后，在此之后进行的迭代，不是