圖最小線性排序問題的Memetic爬山算法*

陳雄峰，陳 振，徐 戈

1.閩江學(xué)院 計(jì)算機(jī)科學(xué)系，福州 350121

2.福建省信息處理與智能控制重點(diǎn)實(shí)驗(yàn)室，福州 350121

3.福州大學(xué) 離散數(shù)學(xué)與理論計(jì)算機(jī)科學(xué)研究中心，福州 350108

圖最小線性排序問題的Memetic爬山算法*

陳雄峰1,2+，陳 振3，徐 戈1,2

1.閩江學(xué)院 計(jì)算機(jī)科學(xué)系，福州 350121

2.福建省信息處理與智能控制重點(diǎn)實(shí)驗(yàn)室，福州 350121

3.福州大學(xué) 離散數(shù)學(xué)與理論計(jì)算機(jī)科學(xué)研究中心，福州 350108

CHEN Xiongfeng,CHEN Zhen,XU Ge.Memetic hill climbing algorithm for minimum linear arrangement problem.Journal of Frontiers of Computer Science and Technology,2016,10(11):1623-1632.

針對圖最小線性排序問題優(yōu)化目標(biāo)的特性及其可行域總是連通的特點(diǎn)，提出了一個(gè)新型的Memetic爬山算法。在Memetic算法框架及其主要算子內(nèi)部流程中同時(shí)結(jié)合爬山法，并在主要算子內(nèi)部采用迂回爬山策略。設(shè)計(jì)可變型頂點(diǎn)-邊-鄰接交叉算子，改進(jìn)使用基于貪心隨機(jī)自適應(yīng)搜索過程的初始解生成算法，采用動態(tài)更新等保持種群多樣性策略。公認(rèn)測試集的實(shí)驗(yàn)結(jié)果表明，與最近的兩階段模擬退火算法（two-stage simulated annealing，TSSA）和分散搜索與路徑重鏈接算法（scatter search and path relinking，SSPR）相比，該算法具有更好的整體性能。在相近平均運(yùn)行時(shí)間內(nèi)，該算法近優(yōu)解質(zhì)量分別平均提高1.6%和2.01%，21個(gè)測試?yán)又?3個(gè)獲得當(dāng)時(shí)最好的近優(yōu)解，比TSSA算法多出4個(gè)，比SSPR算法多出2個(gè)。

最小線性排序；Memetic算法；爬山法；鄰接交叉

1 引言

圖最小線性排序（minimum linear arrangement，MinLA）問題是對無向圖頂點(diǎn)進(jìn)行線性排序，尋找使得邊長總和最小的頂點(diǎn)線性排序，其中邊長定義為邊的兩個(gè)頂點(diǎn)在序列位置之間的距離。自1964年Harper為設(shè)計(jì)糾錯碼而首次提出以來，MinLA已廣泛應(yīng)用于VLSI（very large scale integration）設(shè)計(jì)、自然語言處理、圖形繪制和并行與分布式處理等許多領(lǐng)域[1-3]。針對一些諸如樹、超立方體等特殊圖，MinLA有多項(xiàng)式時(shí)間的確定性算法，而針對一般圖，MinLA屬于NP難組合優(yōu)化問題，需用啟發(fā)式算法在合理的運(yùn)行時(shí)間內(nèi)求得近優(yōu)解[1-2]。

迄今為止主要的MinLA問題啟發(fā)式算法有譜序列、混合模擬退火、混合遺傳（包括Memetic）、多層加權(quán)邊縮減和分散搜索與路徑重鏈接（scatter search and path relinking，SSPR）等算法[1-7]。這些算法的基本思想包括：（1）采用適當(dāng)?shù)膯l(fā)式引導(dǎo)算法將有邊連接的頂點(diǎn)彼此靠近，以求得高質(zhì)量的近優(yōu)解；（2）使用相對高質(zhì)量的初始解和可調(diào)節(jié)問題解多樣性與同質(zhì)性的目標(biāo)函數(shù)等措施以優(yōu)化搜索區(qū)域；（3）設(shè)計(jì)高效的鄰域函數(shù)或局部搜索、交叉等主要算子以提高搜索效率，減少運(yùn)行時(shí)間[2,7]。對公認(rèn)的測試集[8]實(shí)驗(yàn)結(jié)果表明，結(jié)合譜序列算法生成初始解和模擬退火算法搜尋高質(zhì)量問題解的優(yōu)勢，可同時(shí)改進(jìn)各自原來算法的運(yùn)行時(shí)間和近優(yōu)解質(zhì)量[2,6]。文獻(xiàn)[4]的遺傳爬山混合算法雖然結(jié)合譜序列算法生成初始解、交叉和爬山法的優(yōu)勢，但采用通用型的兩點(diǎn)交叉算子，與之前的算法相比，僅可對少數(shù)測試?yán)荧@得更好的近優(yōu)解和運(yùn)行時(shí)間[2,4-5]。文獻(xiàn)[5]的Memetic算法設(shè)計(jì)了具有問題針對性的交叉算子，使用基于模擬退火算法的局部搜索，可對大部分測試?yán)荧@得好于遺傳爬山混合算法的近優(yōu)解。上述3種算法因?yàn)榉謩e受制于模擬退火算法或通用性交叉算子的搜索效率，運(yùn)行時(shí)間都相對較長。文獻(xiàn)[6]的兩階段模擬退火（two-stage simulated annealing，TSSA）算法集成了相對高質(zhì)量初始解生成方法、可調(diào)節(jié)問題解多樣性與同質(zhì)性的目標(biāo)函數(shù)和針對性的鄰域函數(shù)，對大部分測試?yán)涌色@得當(dāng)時(shí)最好的近優(yōu)解，與之前算法相比，運(yùn)行時(shí)間也大幅減少。文獻(xiàn)[7]的SSPR算法使用與TSSA算法[6]相似的初始解生成方法，與Memetic類似基于種群的算法框架，以分散搜索為局部搜索，以路徑重鏈接進(jìn)行全局探測。與TSSA算法相比，在相近的平均運(yùn)行時(shí)間內(nèi)，SSPR算法可對更多測試?yán)荧@得當(dāng)時(shí)最好的近優(yōu)解。

Memetic算法結(jié)合了遺傳或其他進(jìn)化算法和局部搜索，在利用交叉算子全局探測優(yōu)勢的基礎(chǔ)上，通過結(jié)合局部搜索過程增強(qiáng)搜索性，全局探測與局部搜索性能相對均衡，因而被成功地應(yīng)用于處理許多組合優(yōu)化問題[5,9-18]。Memetic算法的缺點(diǎn)是時(shí)間和空間復(fù)雜度較大。本文基于MinLA問題優(yōu)化目標(biāo)的特性，研究選用適當(dāng)?shù)膯l(fā)式方法進(jìn)行針對性設(shè)計(jì)，提出了一個(gè)新型的MinLA問題Memetic爬山混合算法。在公認(rèn)的測試集[8]上進(jìn)行實(shí)驗(yàn)，結(jié)果表明了這些設(shè)計(jì)策略的有效性。與TSSA和SSPR算法相比，本文算法在相近的平均運(yùn)行時(shí)間內(nèi)，對大部分測試?yán)涌捎行岣邌栴}近優(yōu)解的質(zhì)量，并對更多測試?yán)涌色@得當(dāng)前最好的近優(yōu)解。

2 問題表示與目標(biāo)函數(shù)特性

給定無向圖G=(V,E)，其中V(|V|=n)為頂點(diǎn)集合，E(|E|=m)為邊集合。圖G頂點(diǎn)的一個(gè)線性排序φ視為頂點(diǎn)與位置標(biāo)號1,2,…,n之間的一一對應(yīng)函數(shù)，即φ：V→{1,2,…,n}。在圖G頂點(diǎn)為線性排序φ的情況下，頂點(diǎn)v(v∈V)的位置標(biāo)號記為φ(v)，則邊(u,v)∈E的長度為|φ(u)-φ(v)|，圖G總邊長記為LA(G,φ)，定義如式（1）：

LA(G,φ)還可視為所有“頂點(diǎn)v與其全部鄰接點(diǎn)N (v)之間邊長之和L(v,φ)”的累加。L(v,φ)定義如式（2），則LA(G,φ)可表示如式（3）：

MinLA問題就是尋找圖G頂點(diǎn)的一個(gè)線性排序φ*，使得LA(G,φ)最小。

Memetic算法染色體編碼可直接使用頂點(diǎn)線性排序的形式，優(yōu)化目標(biāo)函數(shù)可直接使用LA(G,φ)。基于優(yōu)化目標(biāo)函數(shù)LA(G,φ)具有式（1）、（3）累加項(xiàng)的特性，將“頂點(diǎn)及其任意個(gè)鄰接點(diǎn)”作為Memetic算法的交叉基因片段，對后代個(gè)體繼承或重組“鄰接頂點(diǎn)之間彼此靠近”的優(yōu)良基因片段，減小目標(biāo)函數(shù)值，具有更好的啟發(fā)效果，因而對算法交叉操作所隱含的全局探測過程具有更為有效的引導(dǎo)性。并且可通過靈活限定其中鄰接點(diǎn)個(gè)數(shù)，如當(dāng)其中鄰接點(diǎn)個(gè)數(shù)限定為1時(shí)，就是將“邊”作為交叉基因片段，以適應(yīng)不同類型圖的特點(diǎn)，從而可對更多類型的圖提高近優(yōu)解的質(zhì)量。

3 算法設(shè)計(jì)

3.1 算法框架

MinLA問題Memetic爬山（Memetic hill climbing，MHC）混合算法為交叉、局部搜索結(jié)合爬山法的算法，基本框架如算法1所述。

算法1 MinLA問題Memetic爬山算法

就基于種群的進(jìn)化算法而言，種群規(guī)模在一定范圍（約100個(gè)）以內(nèi)，擴(kuò)大種群規(guī)模會明顯提高進(jìn)化效率[9]。另一方面，面對較大規(guī)模問題時(shí)，因其空間復(fù)雜度較高，受運(yùn)行環(huán)境制約，通常不得不采用較小規(guī)模（30個(gè)及以下）種群。算法框架中采用雙向交叉策略，相當(dāng)于單向交叉并使用兩倍于現(xiàn)有規(guī)模的種群，但只需大約其1/2的內(nèi)存空間和參數(shù)傳遞次數(shù)，可明顯提高算法處理較大規(guī)模問題時(shí)的進(jìn)化效率。實(shí)驗(yàn)表明，與單向交叉并直接使用兩倍于現(xiàn)有規(guī)模的種群相比，當(dāng)問題規(guī)模較小而可使用20～30個(gè)體種群時(shí)，可節(jié)省運(yùn)行時(shí)間約8%～22%；當(dāng)問題規(guī)模較大而不得不使用5～10個(gè)體種群時(shí)，可節(jié)省運(yùn)行時(shí)間約45%～87%。適當(dāng)?shù)姆N群多樣性對提高啟發(fā)式算法的近優(yōu)解質(zhì)量和進(jìn)化效率都有直接的作用[9,13-14]。算法采用動態(tài)更新種群為保持多樣性的主要策略，采用3.2節(jié)初始種群生成策略為平衡多樣性與同質(zhì)性的主要策略，每一代重新隨機(jī)排列種群個(gè)體為次要策略。更新種群時(shí)，保留1～2個(gè)當(dāng)前最好的個(gè)體，其他個(gè)體替換為新的初始個(gè)體。另外，實(shí)驗(yàn)表明使用爬山法時(shí)，接受頂點(diǎn)排序有變化而LA(G,φ)不變即“=”的個(gè)體為后代個(gè)體，非常有利于進(jìn)一步的搜索。算法1中初始種群生成、交叉算子、局部搜索、變異算子將分別在后面3.2～3.5節(jié)詳細(xì)介紹。

3.2 初始種群生成

初始解的質(zhì)量決定了初始搜索區(qū)域的優(yōu)劣，是影響啟發(fā)式算法整體性能的關(guān)鍵因素之一[6,9]。綜合考慮生成初始解的質(zhì)量和計(jì)算時(shí)間，經(jīng)過比較分析，初始解個(gè)體生成算法選用文獻(xiàn)[6-7]基于連接程度的啟發(fā)式“sf(v)=dU(v)-dL(v)”和基于對目標(biāo)函數(shù)影響程度的啟發(fā)式“,w∈N(v)∩L,φ(v)=l” 。其中，v為待標(biāo)號的頂點(diǎn)；U為未標(biāo)號頂點(diǎn)集合；L為已標(biāo)號頂點(diǎn)集合；dU(v)為U中與v鄰接的頂點(diǎn)數(shù)；dL(v)為L中與v鄰接的頂點(diǎn)數(shù)；N(v)為v的全部鄰接頂點(diǎn)集合。構(gòu)造過程使用貪心隨機(jī)自適應(yīng)搜索過程（greedy randomized adaptive search procedure，GRASP）[6-7,9]。

初始解個(gè)體生成算法具體流程如算法2所述。其中，在直接影響初始解個(gè)體特征的3個(gè)關(guān)鍵點(diǎn)都加入限制候選集RCLfirstu、RCLsf和RCLCv。加入RCLfirstu以排除少數(shù)度遠(yuǎn)大于平均度的頂點(diǎn)作為線性序列的第一個(gè)頂點(diǎn)，引導(dǎo)算法將其放置在線性序列的中部，更利于減小目標(biāo)函數(shù)。加入RCLsf和RCLCv目的都是針對頂點(diǎn)度分布相對均勻的圖，以便于在不降低同質(zhì)性的前提下增強(qiáng)其初始解的多樣性，其中RCLCv顯然具有更為直接的影響。通過調(diào)整各限制候選集的閾值，不僅可針對不同類型的圖生成良好的初始解，也可對同一類型的圖生成不同特征的初始解，以保證初始解在特征上具有適當(dāng)?shù)亩鄻有耘c同質(zhì)性。設(shè)置各限制候選集的閾值時(shí)，可通過簡單實(shí)驗(yàn)觀察確定可獲得較好初始解的一個(gè)閾值范圍，而后隨機(jī)使用該范圍的閾值。實(shí)驗(yàn)觀察同一類型圖可設(shè)定大致相同的閾值范圍。要進(jìn)一步提高算法的魯棒性，可讓閾值范圍自適應(yīng)于圖內(nèi)部的鄰接關(guān)系，如圖頂點(diǎn)度的分布特征等。

算法2初始解個(gè)體生成算法

而后組成初始種群時(shí)，在若干（如2～5 000個(gè)）候選初始解個(gè)體中選擇最好的作為一個(gè)種群個(gè)體，不同種群個(gè)體可設(shè)定有不同的候選個(gè)數(shù)，以使初始種群在質(zhì)量上也具有適當(dāng)?shù)亩鄻有?。?shí)驗(yàn)觀察，針對較大規(guī)模的圖，種群中含有10%～20%高質(zhì)量的個(gè)體，非常利于獲得良好的搜索區(qū)域，從而提高算法性能。

3.3 交叉算子

交叉算子的性能是影響Memetic算法整體性能的主要因素，要使得算法獲得高質(zhì)量的近優(yōu)解，通常需針對問題的具體特性，設(shè)計(jì)高性能的交叉算子[5,9-17]。本文基于優(yōu)化目標(biāo)函數(shù)LA(G,φ)式（1）、（3）累加項(xiàng)的特性，將“頂點(diǎn)及其任意個(gè)鄰接點(diǎn)”作為交叉基因片段，結(jié)合爬山法，并采用文獻(xiàn)[18]FM算法迂回爬山策略，設(shè)計(jì)了可變型的頂點(diǎn)-邊-鄰接交叉算子(vertexedge-adjacent crossover，VEAX)。VEAX可通過限定“頂點(diǎn)及其任意個(gè)鄰接點(diǎn)”中的鄰接點(diǎn)個(gè)數(shù)，實(shí)現(xiàn)不同類型的交叉。當(dāng)鄰接點(diǎn)個(gè)數(shù)限定為0時(shí)即為“頂點(diǎn)交叉”，鄰接點(diǎn)個(gè)數(shù)限定為1時(shí)即為“邊交叉”，鄰接點(diǎn)個(gè)數(shù)大于1的交叉簡稱“鄰接交叉”。交叉類型可通過簡單實(shí)驗(yàn)確定，以適應(yīng)不同類型圖的特點(diǎn)，如4.2節(jié)實(shí)驗(yàn)確定其中兩種類型的圖采用“邊交叉”，其他4種類型的圖采用“鄰接交叉”。

圖1所示為“鄰接交叉”。pf、pm上將進(jìn)行“頂點(diǎn)2及其鄰接點(diǎn)1、3”的交叉，pm上7、9、0為分別與pf上2、1、3對應(yīng)位置的頂點(diǎn)。采用與PR[7]和通用型的部分匹配交叉算子（partially-matched crossover，PMX）相同的交換機(jī)制。交叉過程可簡化為直接在pm上進(jìn)行頂點(diǎn)交換，如圖1雙箭頭虛線所示。因此，cm可視為由pm進(jìn)化而來，在pm的基礎(chǔ)上，不僅可快速計(jì)算cm的目標(biāo)函數(shù)值，而且可結(jié)合爬山法進(jìn)行高效率的后代選擇。

Fig.1 VEAX diagram圖1 VEAX示意圖

VEAX算法流程如算法3所述。其中，交叉過程采用與文獻(xiàn)[18]FM算法類似的迂回爬山策略，接受可使得目標(biāo)函數(shù)值最小的“某一對及其之前的全部頂點(diǎn)交換”。這一策略可使得算法比較容易跳出局部優(yōu)解的區(qū)域，從而大大提高搜索效率[14,18]。逐對交叉頂點(diǎn)時(shí)，首先交叉被選擇的頂點(diǎn)u與其對應(yīng)頂點(diǎn)，可更好引導(dǎo)子個(gè)體繼承或重組優(yōu)良的“頂點(diǎn)u及其鄰接點(diǎn)”部分排序。另外，實(shí)驗(yàn)觀察交叉過程也可能出現(xiàn)多次達(dá)到目標(biāo)函數(shù)值最小的現(xiàn)象，算法3通過加入限制候選集，以優(yōu)化可接受交換頂點(diǎn)對數(shù)的范圍，隨機(jī)接受其中的某一次，可更好地適應(yīng)不同規(guī)模問題解空間的特點(diǎn)。

算法3頂點(diǎn)-邊-鄰接交叉算子VEAX算法

輸入：圖G(V,E),父個(gè)體pf,母個(gè)體pm,一次交叉“頂點(diǎn)及其任意個(gè)鄰接點(diǎn)”個(gè)數(shù)cross_VEAnumber，一個(gè)“頂點(diǎn)及其任意個(gè)鄰接點(diǎn)”中鄰接點(diǎn)限定最大個(gè)數(shù)VEA_adjnumber，交叉過程中有多次目標(biāo)函數(shù)值達(dá)到最小情況下可接受交換頂點(diǎn)對數(shù)閾值比例accept_α

算法3中VEA_adjnumber取值決定交叉類型，如本節(jié)第一段所述可首先通過簡單實(shí)驗(yàn)確定。而后為使算法在獲得高質(zhì)量的問題解與避免陷入局部優(yōu)解之間達(dá)到良好的平衡，可進(jìn)行詳細(xì)實(shí)驗(yàn)確定cross_VEAnumber。一次交叉過程交換頂點(diǎn)對的最大數(shù)為s-1=VEA_adjnumber×cross_VEAnumber，可視為交叉所隱含的全局搜索的步長上界。針對相對高質(zhì)量的種群，應(yīng)采用交叉局部化的思想才能有較高的搜索效率[9,13]。如4.2節(jié)實(shí)驗(yàn)，VEA_adjnumber限定小于16；當(dāng)母個(gè)體pm為當(dāng)前最好個(gè)體時(shí)，cross_VEA number限定取值1～4，當(dāng)母個(gè)體pm為非當(dāng)前最好個(gè)體時(shí)，cross_VEAnumber設(shè)定為當(dāng)前最好個(gè)體的1.5～2.5倍，隨著當(dāng)前最好個(gè)體質(zhì)量的進(jìn)化提高而逐步加大倍數(shù)。這一cross_VEAnumber取值方案可使得更新種群后非當(dāng)前最好個(gè)體加快進(jìn)化，盡快接近當(dāng)前最好個(gè)體，進(jìn)而可交叉生成更好的后代個(gè)體。accept_α的取值將確定全局搜索步長的下界，適當(dāng)取值可進(jìn)一步優(yōu)化步長的范圍。相對較小規(guī)模問題（如邊數(shù)< 500）交叉時(shí)容易陷入局部優(yōu)解，accept_α應(yīng)設(shè)定為接近0，使步長接近上界，而相對較大規(guī)模問題交叉時(shí)容易錯過高質(zhì)量的問題解，accept_α應(yīng)設(shè)定為接近1.0，使算法可進(jìn)行較小步長的全局搜索，具體參見第4章“實(shí)驗(yàn)結(jié)果與分析”相關(guān)內(nèi)容。

基于交叉局部化，如上所述VEAX交叉最大頂點(diǎn)對數(shù)s-1為常數(shù)。VEAX中使用集合L存放交叉過程的頂點(diǎn)對及當(dāng)前目標(biāo)函數(shù)值，使得c0,c1,…,cs-1可共用一個(gè)大小為|V|的存儲空間，大大節(jié)省了存儲空間。VEAX基本操作為頂點(diǎn)交叉和計(jì)算L(w,ck)(w∈V，0≤k≤s-1)，交叉最大頂點(diǎn)數(shù)為常數(shù)(s-1)×2，L(w,ck)平均時(shí)間復(fù)雜度為O(Ave(|N(w)|))，因此VEAX平均時(shí)間復(fù)雜度也僅為O(Ave(|N(w)|))。通常Ave(|N(w)|)遠(yuǎn)小于|V|，VEAX具有快速高效的性能。

3.4 局部搜索

MinLA問題解為一維線性排序，頂點(diǎn)位置變化直接影響目標(biāo)函數(shù)值。依據(jù)這一特征，算法的局部搜索選用窗口窮盡搜索策略。每次局部搜索隨機(jī)選擇若干個(gè)窗口，實(shí)驗(yàn)觀察每個(gè)窗口設(shè)定為4個(gè)連續(xù)頂點(diǎn)效果最好，在窗口內(nèi)進(jìn)行窮盡搜索，獲取窗口內(nèi)最好頂點(diǎn)排序。局部搜索概率PLS和每次局部搜索窗口個(gè)數(shù)的設(shè)定，應(yīng)考慮與全局搜索即交叉之間的平衡，同時(shí)兼顧運(yùn)行時(shí)間。經(jīng)過實(shí)驗(yàn)，算法中PLS的取值范圍隨著當(dāng)前最好個(gè)體質(zhì)量的進(jìn)化提高而逐步擴(kuò)大，從2%～12%逐步擴(kuò)大到2%～100%，在某一取值范圍內(nèi)個(gè)體質(zhì)量越高，PLS取值越大。每次進(jìn)行局部搜索的窗口個(gè)數(shù)約為每次交叉最大頂點(diǎn)對數(shù)的0.5～3.0倍，通常情況下圖越稀疏倍數(shù)應(yīng)越大，以協(xié)調(diào)局部搜索和全局搜索。此外，與3.3節(jié)“交叉算子”中cross_VEAnumber設(shè)定同理，種群中非當(dāng)前最好個(gè)體的窗口個(gè)數(shù)設(shè)定為當(dāng)前最好個(gè)體的兩倍。

3.5 變異算子

將染色體上連續(xù)部分作為交叉基因片段時(shí)，如單/雙點(diǎn)交叉和PMX等，通常采用交換染色體任意兩個(gè)位置的編碼作為變異策略，以彌補(bǔ)其交叉時(shí)全局探測性能的局限。本文交叉算子采用非連續(xù)的交叉基因片段和交換策略，需要彌補(bǔ)交叉時(shí)局部搜索性能的局限，因此選用有鄰接的幾個(gè)頂點(diǎn)往其中位數(shù)位置聚集成為一個(gè)連續(xù)部分的變異策略。聚集過程類似于文獻(xiàn)[6]的鄰域函數(shù)和文獻(xiàn)[16]的局部搜索，但聚集后的前后順序不一定是聚集前的順序，而是重新隨機(jī)排列以增強(qiáng)變異的效果。算法流程類似3.3節(jié)VEAX，也結(jié)合了迂回爬山策略，隨機(jī)接受目標(biāo)函數(shù)值LA(G,φ)沒有變大即“≤”的“某一步及其之前的全部聚集”所帶來的變異。實(shí)驗(yàn)觀察，一次變異的有鄰接頂點(diǎn)個(gè)數(shù)設(shè)定為1～5個(gè)（實(shí)際影響2～10個(gè)）效果最好。這一變異策略對較小規(guī)模的圖和高質(zhì)量初始解，提高問題近優(yōu)解質(zhì)量的作用尤為明顯。變異概率PMU設(shè)定策略與3.4節(jié)“局部搜索”中PLS相同，取值約為PLS的15%，即0.3%～15%。

3.6 算法可行性分析

Memetic算法雖然被廣泛應(yīng)用于處理許多組合優(yōu)化問題[5,9-17]，但其缺點(diǎn)是必須進(jìn)行大量的適應(yīng)值估算，具有較大的時(shí)間和空間復(fù)雜度。問題針對性設(shè)計(jì)利用問題領(lǐng)域先驗(yàn)知識增強(qiáng)算法的整體性能，是改進(jìn)Memetic算法性能的主要措施之一，主要包括問題解表示、初始解生成和搜索算子設(shè)計(jì)三方面[9,13]。針對性問題解表示和初始解生成的目的是提高算法搜索區(qū)域的質(zhì)量，針對性搜索算子設(shè)計(jì)是為了使搜索過程更為適合問題的特點(diǎn)及其解空間的適應(yīng)值地貌特征，增強(qiáng)其搜索求解的效率。

本文基于MinLA問題優(yōu)化目標(biāo)的特性，研究選用適當(dāng)?shù)膯l(fā)式，針對性設(shè)計(jì)一個(gè)MinLA問題Memetic爬山混合算法。首先改進(jìn)使用文獻(xiàn)[6-7]初始解生成方法以提高初始搜索區(qū)域的質(zhì)量。而后針對MinLA問題可行域總是連通的特點(diǎn)，利用爬山法在連通可行域上搜索效率高的優(yōu)勢[4,9,13,16-17]，在算法框架的后代個(gè)體選擇和交叉、變異和局部搜索主要算子內(nèi)部鄰域個(gè)體選擇時(shí)都結(jié)合了爬山法，以提高算法的搜索效率。此外，為使算法更易于跳出局部優(yōu)解區(qū)域，針對其交叉、變異算子內(nèi)部搜索過程中會出現(xiàn)“問題解質(zhì)量多次下降后再爬升”的現(xiàn)象，采用文獻(xiàn)[18]著名的FM劃分算法的爬山接受策略，即接受逐對交換頂點(diǎn)過程獲得最好爬升的“某一對及其之前可能出現(xiàn)下降的全部頂點(diǎn)交換”，這里稱之為迂回爬山策略。對公認(rèn)的測試集實(shí)驗(yàn)結(jié)果表明了這些設(shè)計(jì)策略是有效的。

4 實(shí)驗(yàn)結(jié)果與分析

算法使用C++語言實(shí)現(xiàn)，測試運(yùn)行環(huán)境為Windows XP，Pentium?dual-core CPU 3.2 GHz，RAM 2.0 GB。使用文獻(xiàn)[8]提出的公認(rèn)測試集，包括均勻隨機(jī)（uniform random）、幾何隨機(jī)（geometric random）、已知最優(yōu)解（包括樹、超立方和網(wǎng)格）、有限元離散化（finite element discretizations）、VLSI設(shè)計(jì)（VLSI design）和圖繪制競賽（graph-drawing competition）6種類型的圖。種群規(guī)模Np依據(jù)圖的邊數(shù)確定，具體為：（1）邊數(shù)<500，Np=30；（2）500≤邊數(shù)<1 500，Np=20；（3）1 500≤邊數(shù)<10 000，Np=10；（4）邊數(shù)≥10 000，Np=5。交叉類型（頂點(diǎn)或邊或鄰接）、accept_α和一次連續(xù)交叉“頂點(diǎn)或邊或鄰接”個(gè)數(shù)cross_VEAnumber依據(jù)圖類型實(shí)驗(yàn)確定，分別設(shè)定為近優(yōu)解LA(G,φ)最小的取值。交叉概率為1.0，變異、局部搜索概率等其他取值如上文相關(guān)章節(jié)所述。Nu取300，即當(dāng)前最好個(gè)體300代沒有進(jìn)化就更新種群，“算法終止條件”設(shè)定為“3 000代當(dāng)前最好個(gè)體LA(G,φ)進(jìn)化減小量≤當(dāng)前最好個(gè)體LA(G,φ)×10-6”。

4.1 算法性能

算法整體性能以獲得的近優(yōu)解平均LA(G,φ)和平均運(yùn)行時(shí)間來衡量。在平均運(yùn)行時(shí)間均控制在1 000 s內(nèi)的情況下，與最近的整體性能最好的兩個(gè)算法TSSA[6]和SSPR[7]與其他典型算法GH[4]、DTSA[19]、SSSA[20]、AMG[21]進(jìn)行比較。實(shí)驗(yàn)結(jié)果如表1所示，其中“其他典型算法”為上述4種算法最好的平均LA(G, φ)；“TSSA”和“SSPR”分別為兩種算法所獲得多個(gè)近優(yōu)解的平均LA(G,φ)[7]；“本文算法MHC”為在控制與文獻(xiàn)[7]相近平均運(yùn)行時(shí)間的情況下，所獲得10個(gè)不同近優(yōu)解的平均LA(G,φ)；“比其他改進(jìn)”、“比TSSA改進(jìn)”、“比SSPR改進(jìn)”分別是“本文算法MHC”較之三者的減小百分比。

文獻(xiàn)[7]測試運(yùn)行環(huán)境同樣是CPU 3.2 GHz，RAM 2.0 GB，因此可以認(rèn)為本文算法MHC的運(yùn)行時(shí)間介于SSPR和TSSA算法之間。與TSSA和其他典型算法相比，基于種群的本文算法MHC和SSPR具有更好的全局探測性能，因而可對更多類型的測試?yán)荧@得高質(zhì)量的近優(yōu)解，特別是對較為稠密的測試?yán)佑葹槊黠@。本文算法MHC與SSPR相比，具有更好的啟發(fā)式，因而可大幅提高絕大部分測試?yán)咏鼉?yōu)解的質(zhì)量，其中少數(shù)測試?yán)拥慕鼉?yōu)解質(zhì)量低于SSPR，主要原因是種群多樣性控制策略還不夠精細(xì)。對測試?yán)觛d96a，本文算法MHC和SSPR近優(yōu)解質(zhì)量都大幅低于TSSA，主要原因是未能獲得良好的初始解。

4.2 交叉算子VEAX收斂性

為進(jìn)一步驗(yàn)證頂點(diǎn)-邊-鄰接交叉算子VEAX（算法3）的有效性，以及VEA_adjnumber（交叉類型）、accept_α取值的合理性，分別對測試集的所有例子進(jìn)行收斂性測試。測試時(shí)除了要測試的參數(shù)，其他參數(shù)和運(yùn)行時(shí)間與4.1節(jié)保持一致。VEA_adjnumber取值0、1和大于1分別表示“頂點(diǎn)交叉”、“邊交叉”和“鄰接交叉”，由于需要控制運(yùn)行時(shí)間和基于交叉局部化的思想，其中平均鄰接點(diǎn)個(gè)數(shù)大于16的測試?yán)覸EA_adjnumber=16，其他的不限。accept_α分別取值0.1，0.2，…，1.0。所有測試結(jié)果表明，除了“圖繪制競賽”略有不同，同一類型測試?yán)拥淖詈媒徊骖愋蚢ccept_α取值相同。限于篇幅，僅列舉不同類型圖的代表性例子和accept_α分別取值0、0.5、1.0的測試結(jié)果，如表2、表3所示，其中數(shù)值為所獲得10個(gè)不同近優(yōu)解的平均LA(G,φ)。一次交叉連續(xù)“頂點(diǎn)-邊-鄰接”個(gè)數(shù)cross_VEAnumber采用類似方法實(shí)驗(yàn)確定，表2中“一次交叉?zhèn)€數(shù)”直接列出其最好取值范圍。

Table 1 Test results of MHC algorithm and comparison of typical heuristic algorithms表1 MHC算法測試結(jié)果及典型啟發(fā)式算法比較

Table 2 Comparison of VEAX convergence with 3 kinds of crossover表2 3種交叉類型VEAX收斂性比較

Table 3 Comparisonof VEAX convergence with deferent accept_α表3 不同accept_α取值VEAX收斂性比較

實(shí)驗(yàn)結(jié)果表明,交叉類型“邊交叉”和“鄰接交叉”的啟發(fā)性明顯優(yōu)于“頂點(diǎn)交叉”，依據(jù)不同類型圖的特點(diǎn)確定交叉類型、cross_VEAnumber和accept_α，可更為充分體現(xiàn)VEAX良好的收斂性能，進(jìn)而更為有效提高算法的近優(yōu)解質(zhì)量。

5 結(jié)束語

本文依據(jù)MinLA問題優(yōu)化目標(biāo)的特性及其可行域總是連通的特點(diǎn)，將“邊”或“頂點(diǎn)及其任意個(gè)鄰接點(diǎn)”作為交叉基因片段，在交叉算子內(nèi)部流程結(jié)合爬山法的優(yōu)勢，采用迂回爬山策略，設(shè)計(jì)可靈活變型的頂點(diǎn)-邊-鄰接交叉算子VEAX，可更為高效地交叉生成高質(zhì)量的后代個(gè)體，是提高算法整體性能的主要因素。其次為算法框架方面，利用Memetic算法兼具全局探測性和局部搜索性的優(yōu)點(diǎn)，采用爬山法選擇后代，并協(xié)調(diào)全局與局部搜索，使得算法在近優(yōu)解質(zhì)量與運(yùn)行時(shí)間之間達(dá)到良好的平衡。設(shè)定不同參數(shù)閾值以生成不同特征的初始解，以及動態(tài)更新種群等保持種群多樣性與同質(zhì)性平衡的策略，也是保證算法具有較高進(jìn)化效率的必要基礎(chǔ)。實(shí)驗(yàn)表明，與最近的整體性能最好的兩個(gè)算法TSSA和SSPR相比，基于以上策略的Memetic爬山算法整體性能明顯更好。針對問題特點(diǎn)而設(shè)計(jì)的VEAX具有良好的收斂性能，其設(shè)計(jì)思想可為研究其他類似問題啟發(fā)式算法所借鑒。后續(xù)研究的重點(diǎn)將是更為深入分析MinLA問題的特點(diǎn)，提出更為精細(xì)的初始解生成和種群多樣性調(diào)節(jié)等策略，并結(jié)合其他搜索方法的優(yōu)勢和自適應(yīng)機(jī)制，進(jìn)一步提高算法整體性能和魯棒性。此外，結(jié)合多層技術(shù)以擴(kuò)大算法可有效處理問題規(guī)模，也將作為后續(xù)主要研究方向之一。

[1]Diaz J,Petit J,Serna M.A survey of graph layout problems [J].ACM Computing Surveys,2002,34(3):313-356.

[2]Petit J.Addenda to the survey of layout problems[J].Bulletin of EATCS,2013(105):177-201.

[3]Liu Xu.Researeh on load balancing algorithms based on graph partitioning and graph layout[D].Mianyang,China: ChinaAcademy of Engineering Physics,2008.

[4]Poranen T.A genetic hillclimbing algorithm for the optimal linear arrangement problem[J].Fundamenta Informaticae, 2005,68(4):333-356.

[5]Rodriguez-Tello E,Hao J K,Torres-Jimenez J.Memetic algorithms for the MinLA problem[C]//LNCS 3871:Proceedings of the 7th International Conference on Artificial Evolution, Lille,France,Oct 26-28,2005.Berlin,Heidelberg:Springer, 2006:73-84.

[6]Rodriguez-Tello E,Hao J K,Torres-Jimenez J.An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem[J].Computers&Operations Research,2008,35(10):3331-3346.

[7]Martí R,Pantrigo J J,Duarte A,et al.Scatter search and path relinking:a tutorial on the linear arrangement problem [J].International Journal of Swarm Intelligence Research,2011, 2(2):1-21.

[8]Petit J.Experiments on the minimum linear arrangement problem[J].Journal of Experimental Algorithmics,2003,8:112-128.

[9]Areibi S.Effective exploration&exploitation of the solution space via memetic algorithms for the circuit partition problem[M]//RecentAdvances in MemeticAlgorithms.Berlin,Heidelberg:Springer,2005:161-182.

[10]Tang Maolin,Yao Xin.A memetic algorithm for VLSI floorplanning[J].IEEE Transactions on Systems,Man,and Cybernetics:Part B Cybernetics,2007,37(1):62-69.

[11]Chen Jianli,Zhu Wenxing,Ali M M.A hybrid simulated an-nealing algorithm for nonslicing VLSI floorplanning[J]. IEEE Transactions on Systems,Man,and Cybernetics:Part CApplications and Reviews,2011,41(4):544-553.

[12]Chen Jianli,Zhu Wenxing,Peng Zheng.A heuristic algorithm for the strip packing problem[J].Journal of Heuristics,2012,18(4):677-697.

[13]Nagata Y,Kobayashi S.A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem [J].INFORMS Journal on Computing,2013,25(2):346-363.

[14]Lin Geng,Zhu Wenxing.An efficient memetic algorithm for the max-bisection problem[J].IEEE Transactions on Computers,2014,63(6):1365-1376.

[15]Freitas A R R,Silva V M R,Campelo F,et al.Optimizing two-level reverse distribution networks with hybrid memetic algorithms[J].Optimization Letters,2014,8(2):753-762.

[16]Chen Xiongfeng,Wu Jinglan,Zhu Wenxing.An enhanced hybrid genetic simulated annealing algorithm for VLSI standard cell placement[J].Pattern Recognition and Artificial Intelligence,2014,27(9):815-825.

[17]Chen Xiongfeng,Wu Jinglan,Zhu Wenxing.An effective genetic algorithm for VLSI standard cell array placement[J]. Journal of Xiamen University:Natural Science,2014,53(6): 797-803.

[18]Fiduccia C M,Mattheyses R M.A linear-time heuristic for improving network partitions[C]//Proceedings of the 19th Conference on Design Automation,Las Vegas,USA,Jun 14-16,1982.Piscataway,USA:IEEE,1982:175-181.

[19]Bar-Yehuda R,Even G,Feldman J,et al.Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems[J].Journal of Graph Algorithms andApplications,2001,5(4):1-27.

[20]Petit J.Combining spectral sequencing and parallel simulated annealing for the MinLA problem[J].Parallel Processing Letters,2003,13(1):77-91.

[21]Safro I,Ron D,Brandt A.Graph minimum linear arrangement by multilevel weighted edge contractions[J].Journal ofAlgorithms,2006,60(1):24-41.

附中文參考文獻(xiàn)：

[3]劉旭.基于圖剖分和圖排序的負(fù)載平衡算法研究[D].綿陽:中國工程物理研究院,2008.

[16]陳雄峰,吳景嵐,朱文興.VLSI標(biāo)準(zhǔn)單元布局問題的增強(qiáng)型混合遺傳模擬退火算法[J].模式識別與人工智能, 2014,27(9):815-825.

[17]陳雄峰,吳景嵐,朱文興.VLSI標(biāo)準(zhǔn)單元陣列布局問題的一個(gè)高效遺傳算法[J].廈門大學(xué)學(xué)報(bào):自然科學(xué)版,2014, 53(6):797-803.

CHEN Xiongfeng was born in 1969.He received the M.S.degree from Fuzhou University in 2006.Now he is an associate professor at Minjiang University.His research interests include intelligent computing and software engineering,etc.

陳雄峰（1969—），男，福建仙游人，2006年于福州大學(xué)獲得碩士學(xué)位，現(xiàn)為閩江學(xué)院副教授，主要研究領(lǐng)域?yàn)橹悄苡?jì)算，軟件工程等。

CHEN Zhen was born in 1984.He is a Ph.D.candidate at Fuzhou University.His research interest is optimization theory and algorithm.

陳振（1984—），男，福建莆田人，福州大學(xué)博士研究生，主要研究領(lǐng)域?yàn)樽顑?yōu)化理論與算法。

XU Ge was born in 1978.He received the Ph.D.degree from Peking University in 2012.Now he is an associate professor at Minjiang University.His research interests include natural language processing and sentiment analysis,etc.徐戈（1978—），男，浙江淳安人，2012年于北京大學(xué)獲得博士學(xué)位，現(xiàn)為閩江學(xué)院副教授，主要研究領(lǐng)域?yàn)樽匀徽Z言處理，情感分析等。

Memetic Hill ClimbingAlgorithm for Minimum LinearArrangement Problem?

CHEN Xiongfeng1,2+,CHEN Zhen3,XU Ge1,2
1.Department of Computer Science,Minjiang University,Fuzhou 350121,China
2.Fujian Provincial Key Laboratory of Information Processing and Intelligent Control,Fuzhou 350121,China
3.Center for Discrete Mathematics and Theoretical Computer Science,Fuzhou University,Fuzhou 350108,China
+Corresponding author:E-mail:chenxf2000126@126.com

According to the properties of optimization objective of the minimum linear arrangement(MinLA)problem,and considering that the feasible region of the problem is always connected,this paper presents a new Memetic hill climbing algorithm for solving the MinLA problem.It combines the framework of Memetic algorithm and the internal procedure of its main operators with hill climbing method simultaneously,and adopts an indirect-climbing strategy in the internal procedure of its main operators.It uses a specific variable-type crossover operator named vertexedge-adjacent crossover,improves the algorithm for generating initial solutions based on greedy randomized adaptive search procedure(GRASP),and adopts the strategies including dynamic updating for maintaining population diversity. Compared with two recent algorithms named two-stage simulated annealing(TSSA)and scatter search and path relinking (SSPR),the experimental results on the acknowledged test suite show that the proposed algorithm has better compre-hensive performance.In the same average running time,the proposed algorithm improves the quality of the near-optimal solutions by an average of 1.6%and 2.01%respectively,and obtains the best near-optimal solutions at that time for 13 instances from the 21 test instances,which is more 4 than TSSAand more 2 than SSPR.

minimum linear arrangement;Memetic algorithm;hill climbing method;adjacent crossover

10.3778/j.issn.1673-9418.1601065

A

TP18

*The National Natural Science Foundation of China under Grant No.61170308(國家自然科學(xué)基金);the National Natural Science Foundation for Young Scholars of China under Grant No.61300156(國家自然科學(xué)基金青年科學(xué)基金).

Received 2016-01,Accepted 2016-04.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-04-01,http://www.cnki.net/kcms/detail/11.5602.TP.20160401.1614.004.html