南京信息工程大學課程名稱 專業英語院系 信息與控制學院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