基于交叉親和度評(píng)價(jià)的多種群遺傳算法

王　東,歸偉夏

(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院, 廣西南寧530004)

?

基于交叉親和度評(píng)價(jià)的多種群遺傳算法

王東,歸偉夏

(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院, 廣西南寧530004)

摘要：為進(jìn)一步解決傳統(tǒng)多種群遺傳算法進(jìn)化過(guò)程中迅速喪失種群多樣性，導(dǎo)致的易早熟、收斂到局部最優(yōu)解等問(wèn)題，提出一種基于交叉親和度評(píng)價(jià)的多種群遺傳算法，采用多種群并行搜索的思想，結(jié)合模擬退火算法提高算法的搜索能力，種群之間通過(guò)交叉推優(yōu)選出的交流個(gè)體,進(jìn)行親和度評(píng)價(jià)替換目標(biāo)種群個(gè)體來(lái)完成交流。通過(guò)對(duì)TSP問(wèn)題的求解表明，算法得到的解都接近最優(yōu)解，性能優(yōu)于傳統(tǒng)多種群遺傳算法。

關(guān)鍵詞:遺傳算法；交叉親和度評(píng)價(jià)；模擬退火；多種群

0引言

遺傳算法(genetic algorithm，GA)是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的一種隨機(jī)方法，由美國(guó)學(xué)者Holland教授[1-2]于1975年首次提出。由于GA在解決連續(xù)變量的函數(shù)優(yōu)化問(wèn)題中表現(xiàn)出來(lái)很好的魯棒性、自適應(yīng)性和隱含并行性，因此應(yīng)用十分廣泛[3-4]。然而遺傳算法也存在很多問(wèn)題，如計(jì)算代價(jià)太高，收斂速度緩慢，種群不能很好的覆蓋搜索區(qū)域以及易陷入局部最優(yōu)解等問(wèn)題。

多種群并行遺傳[5]是近年來(lái)所提出的改進(jìn)遺傳算法中性能較好的一種方法。其基本思想是用多個(gè)子種群代替原單一種群，使種群很好地覆蓋搜索區(qū)域并使算法的搜索效率得到質(zhì)的提高，每個(gè)子種群按不同的進(jìn)化策略、遺傳算子并行進(jìn)化，并通過(guò)子種群間交換信息(一般為最優(yōu)個(gè)體)來(lái)增加基因模式數(shù)，這樣處理可以選取和保留每個(gè)子種群的優(yōu)秀個(gè)體，在保持優(yōu)秀個(gè)體進(jìn)化穩(wěn)定性的同時(shí)，加快進(jìn)化速度，避免未成熟收斂。

目前關(guān)于多種群進(jìn)化研究眾多，如在搜索區(qū)域進(jìn)行改進(jìn)[6-7]，在遺傳算子上做出改進(jìn)[8]，還可以與其他搜索算法相結(jié)合，如王銀年等[9]提出的改進(jìn)模擬退火遺傳算法，通過(guò)與模擬退火算法相結(jié)合，很好地提高算法的局部搜索能力。然而大多數(shù)學(xué)者在種群之間的交流上沒(méi)有太多改進(jìn)，通常的做法是將本種群中的最優(yōu)個(gè)體直接替換其他種群中最差的個(gè)體，當(dāng)種群規(guī)模不是很大時(shí)，由于外來(lái)優(yōu)秀個(gè)體的進(jìn)入，經(jīng)過(guò)遺傳操作迅速成為本種群的主導(dǎo)，使種群的多樣性迅速下降，對(duì)于許多函數(shù)通常難以跳出局部最優(yōu)解。本文針對(duì)此問(wèn)題，提出一種交叉親和度評(píng)價(jià)的交流算子，即選出種群之間要交流的個(gè)體后，通過(guò)交叉操作選出優(yōu)秀子代，再進(jìn)行親和度評(píng)價(jià)替換目標(biāo)種群中的個(gè)體，使種群在中后期仍然具有很好的多樣性，避免陷入局部最優(yōu)[10]。最后，通過(guò)對(duì)TSP問(wèn)題的求解并與傳統(tǒng)多種群遺傳算法對(duì)比證明算法的有效性。

1基于交叉親和度評(píng)價(jià)的多種群遺傳算法

本文提出了一種基于交叉親和度評(píng)價(jià)的多種群遺傳算法，即AEMPGA，不僅在遺傳算子方面做了改進(jìn)，而且在種群的創(chuàng)建以及交流算子進(jìn)行了優(yōu)化。算法采用N加1種群模式，即N個(gè)子種群和一個(gè)最優(yōu)保留種群，在每個(gè)子種群中，采用近鄰法生成初始種群，并結(jié)合模擬退火算法構(gòu)成近鄰模擬退火遺傳算法(NNSAGA)提高算法的局部搜索能力，在子種群之間交流采用交叉推優(yōu)方式，進(jìn)行親和度評(píng)價(jià)操作，使種群的多樣性得以提高。具體流程如圖1所示。

圖1　AEMPGA算法流程圖

1.1　巡回旅行商問(wèn)題

巡回旅行商問(wèn)題[11](traveling salesman problem,TSP)，也稱貨郎擔(dān)問(wèn)題。簡(jiǎn)單來(lái)說(shuō)就是給定n個(gè)城市和兩兩城市之間的距離，要求確定一條經(jīng)過(guò)各城市當(dāng)且僅當(dāng)一次的最短路線。其圖論描述為：給定圖G(E，A)，其中E為頂點(diǎn)集,A為各頂點(diǎn)相互連接組成的邊集，已知各頂點(diǎn)間的連接距離，要求確定一條長(zhǎng)度最短的Hamilton回路，即遍歷所有頂點(diǎn)當(dāng)且僅當(dāng)一次的最短回路。

以n=4為例，假設(shè)有四個(gè)城市A,B,C,D，四個(gè)城市連成一條回路的最短距離為B→A→D→C→B，則所走的距離為d=d(BA)+d(AD)+d(DC)+d(CB)。

1.2　近鄰法

算法采用近鄰法生成初始種群，以第一個(gè)城市為初始結(jié)點(diǎn)找出與其最近的城市作為后綴結(jié)點(diǎn)，第二個(gè)城市為初始結(jié)點(diǎn)找出與其最近的城市作為后綴結(jié)點(diǎn)，依照這樣的做法找出每個(gè)城市的后綴結(jié)點(diǎn)，之后隨機(jī)組合生成初始種群，這樣做的好處是初始種群中的個(gè)體已經(jīng)做了一定的優(yōu)化，在尋優(yōu)的開(kāi)始就向好的方向發(fā)展，經(jīng)過(guò)遺傳操作可以迅速接近最優(yōu)解。

1.3　模擬退火算法

模擬退火算法[12]( simulated annealing algorithm, SAA)于1983年成功地應(yīng)用在組合優(yōu)化的問(wèn)題上。其思想是通過(guò)模擬高溫物體退火過(guò)程的方法來(lái)找到優(yōu)化問(wèn)題最優(yōu)或近似最優(yōu)解的一種很強(qiáng)的局部搜索算法。模擬退火算法在搜索過(guò)程中具有概率突跳的能力，能夠有效地避免搜索過(guò)程陷入局部極小解。模擬退火算法在退火過(guò)程中不但接受好的解，而且還以一定的概率接受差的解，同時(shí)這種概率受到溫度參數(shù)的控制，其大小隨溫度的下降而減小。

求解過(guò)程如下：

①初始化退火溫度Tk(令k=0)，產(chǎn)生隨機(jī)初始解X0。

②在溫度Tk下重復(fù)執(zhí)行如下操作，直至達(dá)到溫度Tk的平衡狀態(tài)：

在解x的領(lǐng)域中產(chǎn)生新的可行解xo；

計(jì)算新解的評(píng)價(jià)函數(shù)f(xo)和舊解的評(píng)價(jià)函數(shù)f(x)的差值df；

依照概率min{1,exp(-df/Tk)}>random[0,1]接收新解，其中random[0,1]是[0,1]區(qū)間內(nèi)的隨機(jī)數(shù)。

③令Tk+1=ATk，k←k+1，其中A∈(0,1)。

若滿足收斂判據(jù)，則退火過(guò)程結(jié)束；否則, 轉(zhuǎn)②。

1.4　交叉推優(yōu)選擇交流個(gè)體

多種群中各子種群是相互獨(dú)立的，種群間通過(guò)個(gè)體的交流來(lái)相互協(xié)調(diào)，交流個(gè)體是發(fā)揮多種群并行結(jié)構(gòu)作用的關(guān)鍵因素，如果沒(méi)有個(gè)體的交流，各種群間失去了聯(lián)系則算法將等同于將多個(gè)不同控制參數(shù)標(biāo)準(zhǔn)遺傳算法進(jìn)行多次計(jì)算，從而失去了多種群的特色。傳統(tǒng)的交流方式有兩種：一種是將本種群中的最優(yōu)個(gè)體直接替換其他種群中最差的個(gè)體，這種方式的優(yōu)點(diǎn)是種群收斂速度快，缺點(diǎn)是當(dāng)種群規(guī)模不是很大時(shí)，由于外來(lái)優(yōu)秀個(gè)體的進(jìn)入，經(jīng)過(guò)遺傳操作迅速成為本種群的主導(dǎo)，使種群的多樣性迅速下降，對(duì)于許多函數(shù)通常難以跳出局部最優(yōu)解；另一種方式是相鄰種群之間隨機(jī)挑出幾個(gè)個(gè)體進(jìn)行交叉，交叉后的子代替換原來(lái)兩種群中最差的個(gè)體[13]。這種方法隨機(jī)性較強(qiáng)，雖然使種群的多樣性得以保持卻沒(méi)有將外來(lái)優(yōu)秀基因帶到本種群，這樣對(duì)于全局的收斂性沒(méi)起到很好的作用。

本文提出的算法將對(duì)此進(jìn)行改進(jìn)，采用單向環(huán)狀拓?fù)?，即將第i個(gè)種群的最優(yōu)個(gè)體經(jīng)交叉推優(yōu)選出的子代遷到第i+1的種群中，第N個(gè)種群的最優(yōu)個(gè)體經(jīng)交叉推優(yōu)選出的子代遷移到第1個(gè)種群中，其中i=1,2,…,N-1，N為種群個(gè)數(shù)。具體來(lái)說(shuō)，首先找到本種群的最優(yōu)解，之后找到目標(biāo)種群的最差解，兩個(gè)個(gè)體進(jìn)行交叉操作，交叉后找出兩個(gè)個(gè)體中較優(yōu)的個(gè)體進(jìn)行親和度評(píng)價(jià)操作替換目標(biāo)種群中的個(gè)體，這樣做的好處是每次交流既帶來(lái)外來(lái)優(yōu)秀個(gè)體的部分基因又保留了目標(biāo)種群個(gè)體的部分基因，使得外來(lái)優(yōu)秀個(gè)體不會(huì)迅速成為主導(dǎo)，這樣不僅帶來(lái)了外來(lái)的優(yōu)秀基因，而且使種群的多樣性得以保持。

1.5　親和度評(píng)價(jià)

經(jīng)過(guò)交叉推優(yōu)選出的交流個(gè)體攜帶源種群的信息進(jìn)入到目標(biāo)種群，增加了目標(biāo)種群基因的模式數(shù)，在一定程度上補(bǔ)充了目標(biāo)種群有可能缺失的有效基因。如果交流的個(gè)體與目標(biāo)種群內(nèi)已有的個(gè)體親和度極大，即基因的相似度極大，則交流將毫無(wú)意義，有可能引起所有個(gè)體都趨向于同一狀態(tài)，使得算法急劇收斂，喪失種群的多樣性，因此進(jìn)行一定的親和度判斷是有必要的，所以本文算法在個(gè)體交流過(guò)程中引入親和度評(píng)價(jià)操作，在一定程度上避免這種情況。

1.5.1個(gè)體間親和度計(jì)算

在遺傳算法中，計(jì)算兩個(gè)個(gè)體之間的親和度時(shí)，可以認(rèn)為每個(gè)基因就是一個(gè)特征分量，一條染色體就是其特征向量。所以個(gè)體間的親和度可以用個(gè)體間的距離來(lái)計(jì)算[14],距離越大親和度越小。

例如，某兩個(gè)個(gè)體的染色體分別為X(x1,x2,…,xL)，Y(y1,y2,…,yL)，其中x，y表示組成該染色體的基因值，其中L表示個(gè)體染色體的長(zhǎng)度。個(gè)體之間的差異為兩個(gè)個(gè)體各個(gè)基因的距離求和，則第i個(gè)分量的距離計(jì)算方法如式(1)。

(1)

式中xi與yi為兩個(gè)個(gè)體在第i位的基因值；maxi和mini分別代表第i位的最大基因值和最小基因值。對(duì)于二進(jìn)制編碼maxi=1；mini=0。如果xi=yi，dist(xi,yi)=0；否則，dist(xi,yi) = 1。

X、Y的親和度計(jì)算如式(2)。

(2)

1.5.2替換操作

經(jīng)過(guò)交叉推優(yōu)選擇出的交流個(gè)體與目標(biāo)種群中的每一個(gè)個(gè)體進(jìn)行親和度評(píng)價(jià)，計(jì)算它們之間的acev(X,Y)，設(shè)置一個(gè)l，若兩個(gè)個(gè)體的acev(X,Y)>=l，則認(rèn)定這兩個(gè)個(gè)體親和度高，記錄所有與交流個(gè)體親和度高的個(gè)體，找出與交流個(gè)體親和度最高的個(gè)體，如果交流個(gè)體的適應(yīng)值大于與其親和度最高的個(gè)體，則用交流個(gè)體替換與其親和度最高的個(gè)體，否則用交流個(gè)體替換目標(biāo)種群中適應(yīng)值最小的個(gè)體。如果交流個(gè)體與任一評(píng)判成員的acev(X,Y)

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

2.1　編碼(表達(dá))

染色體通常采用簡(jiǎn)單的二進(jìn)制串，但這種簡(jiǎn)單的表達(dá)方法不能較好地適用于TSP和其他組合優(yōu)化問(wèn)題。過(guò)去幾年里，許多學(xué)者為TSP提出了幾種染色體表達(dá)方法，其中，換位表達(dá)和隨機(jī)鍵表達(dá)比較適用于TSP。本文算法采用換位表達(dá)。其中城市是按訪問(wèn)的順序排列的，這種表達(dá)的搜索空間是城市順序換位的集合，因此這種表達(dá)也稱為路徑表達(dá)或順序表達(dá)。例如對(duì)于一個(gè)5城市的TSP：

5-2-1-3-4 可簡(jiǎn)單表示為[5 2 1 3 4]。

2.2　適應(yīng)度函數(shù)

在TSP問(wèn)題中，對(duì)于任意兩個(gè)城市之間的距離D(i,j)已知，每個(gè)染色體(即n個(gè)城市的隨機(jī)排列)可計(jì)算出總距離，因此本文算法將一個(gè)隨機(jī)全排列的總距離的倒數(shù)作為適應(yīng)度函數(shù)，即距離越短，適應(yīng)度函數(shù)越高，因此滿足TSP要求。

2.3　選擇算子

傳統(tǒng)的基本遺傳算法中個(gè)體的選擇概率與個(gè)體的適應(yīng)值直接相關(guān)。一旦某個(gè)個(gè)體的適應(yīng)值接近于0，則其選擇概率將接近于0，這個(gè)個(gè)體產(chǎn)生后代的可能性就極低，這是基本遺傳算法一個(gè)很大的缺點(diǎn)。因此本文算法采用順序選擇方法，順序選擇策略將選擇概率固定化，其具體步驟為：

①按適應(yīng)值大小對(duì)個(gè)體進(jìn)行排序。

②定義最好個(gè)體的選擇概率為q(根據(jù)實(shí)際問(wèn)題設(shè)定)，這樣每個(gè)個(gè)體都有可能被選中從而產(chǎn)生后代。

③根據(jù)輪盤賭策略確定用于交叉的雙親個(gè)體。

2.4　交叉算子

本文算法采用基于位置的交叉，它基本上是一種換位表達(dá)的均勻交叉加一個(gè)修復(fù)程序。

基于位置交叉的步驟：

①?gòu)囊粋€(gè)雙親上隨機(jī)地選一組位置；

②將這些位置復(fù)制到一個(gè)空字串的相應(yīng)位置，產(chǎn)生一個(gè)原始后代；

③刪去第二雙親上該組中已有的城市。剩下的城市構(gòu)成了原始后代需要的順序；

④按照這個(gè)城市順序，從左到右將這些城市定位到后代空缺的位置上。

該步驟可用圖2來(lái)說(shuō)明。

圖2　交叉操作步驟圖Fig.2　Crossover operation steps

同理依據(jù)雙親1和雙親2可以確定出另一個(gè)后代[5 1 3 6 2 4]。

2.5　變異算子

本文算法的變異算子采用插入變異與反轉(zhuǎn)變異相結(jié)合的混合變異算子。插入變異是隨機(jī)選擇一個(gè)城市，并將它插入到一個(gè)隨機(jī)的位置中，反轉(zhuǎn)變異是在染色體上隨機(jī)地選擇兩點(diǎn)，將兩點(diǎn)間的子串反轉(zhuǎn)。

首先進(jìn)行插入變異，之后進(jìn)行反轉(zhuǎn)變異，該步驟可用圖3來(lái)說(shuō)明。

圖3　變異操作步驟圖Fig.3　Mutation steps

2.6　最優(yōu)保存

本文算法設(shè)有一個(gè)最優(yōu)保留種群，用于存儲(chǔ)記錄最優(yōu)個(gè)體，子種群每經(jīng)過(guò)一代遺傳操作就向最優(yōu)保存種群提交找到的最優(yōu)個(gè)體，最優(yōu)種群將子種群提交的個(gè)體與歷史存儲(chǔ)記錄作對(duì)比，如果優(yōu)于歷史記錄的個(gè)體則予以替換，當(dāng)所有子種群進(jìn)行完以上操作后，從最優(yōu)保留種群中選擇出一個(gè)最優(yōu)的個(gè)體作為全局最優(yōu)解。

3算法步驟與仿真實(shí)驗(yàn)

3.1　算法步驟

Step 1: 確定種群規(guī)模NIND，種群個(gè)數(shù)MP，進(jìn)化代數(shù)MAXGEN，交叉概率Pc，變異概率Pm,給定城市的坐標(biāo)位置及個(gè)數(shù)X(i,j),模擬退火參數(shù)初始溫度T0,終止溫度Tend、退火參數(shù)k以及保存當(dāng)前最優(yōu)染色體Tmax。

Step 2: 依據(jù)“2.2”所述確定目標(biāo)函數(shù)及其數(shù)學(xué)描述形式或量化方法。

Step 3: 采用近鄰法產(chǎn)生具有代表性的初始種群，個(gè)體數(shù)目一定，每個(gè)個(gè)體表示染色體的基因編碼。

Step 4: 計(jì)算個(gè)體的適應(yīng)度，并判斷是否符合優(yōu)化準(zhǔn)則，若符合，輸出最佳個(gè)體及其代表的最優(yōu)解，否則轉(zhuǎn)向step 5。

Step 5: 采用順序選擇方法，依據(jù)“2.3”所述進(jìn)行選擇，確定出要進(jìn)行交叉的個(gè)體。

Step 6: 交叉操作，采用基于位置的交換，依據(jù)“2.4”所述進(jìn)行交叉操作。

Step 7: 變異操作，傳統(tǒng)遺傳算法采用單變異位算法，多變異位是選擇多個(gè)位置進(jìn)行變異操作每次選擇都按照“2.5”所述選擇。本文算法采用多變異位算法進(jìn)行變異操作，這樣做大大增加了種群的多樣性。

通過(guò)自適應(yīng)方法產(chǎn)生變異概率[15]：

(3)

式中，fmax為群體中最大的適應(yīng)度值，favg為每代群體的平均適應(yīng)度值，f為要變異的個(gè)體的適應(yīng)度值。其中本文取Pm1=0.1，Pm2=0.01。如果群體最大適應(yīng)值等于最小適應(yīng)值，則只產(chǎn)生一個(gè)變異位，否則隨機(jī)產(chǎn)生變異位的個(gè)數(shù)，再隨機(jī)產(chǎn)生每次變異的位置，然后對(duì)選中個(gè)體進(jìn)行變異。

Step 8: 模擬退火操作由經(jīng)過(guò)遺傳操作產(chǎn)生的新一代種群作為模擬退火的初始種群，依照“1.3”中第二點(diǎn)所述接受新解，溫度下降。

Step 9: 交叉推優(yōu)選擇交流個(gè)體進(jìn)行遷移操作，選擇出每一個(gè)種群中的最優(yōu)個(gè)體按照“1.4”中所述進(jìn)行交叉推優(yōu)操作并按“1.5”所述進(jìn)行親和度評(píng)價(jià)，選擇交流個(gè)體進(jìn)行遷移操作。

Step 10: 最優(yōu)保存。按照“2.6”中所述進(jìn)行最優(yōu)保存。

Step 11: 終止判斷。判斷算法是否滿足退火終止條件即低于最低溫度，若滿足，則終止算法并輸出當(dāng)前最優(yōu)記錄，否則令T=k×T，轉(zhuǎn)step 4繼續(xù)執(zhí)行算法。

3.2　仿真實(shí)驗(yàn)

本文采用標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)Tsplib數(shù)據(jù)庫(kù)中的5個(gè)數(shù)據(jù)集ulysses16、ulysses22、oliver30、chn31和dantzig42進(jìn)行了算法的驗(yàn)證。(實(shí)驗(yàn)環(huán)境CPU Intel Core 2.67 GHZ，操作系統(tǒng)windows 7.0，編程工具matlabR2014a)

實(shí)驗(yàn)選取傳統(tǒng)多種群遺傳算法(MPGA)和模擬退火多種群遺傳算法(SAMPGA)與本文算法進(jìn)行對(duì)比，每個(gè)實(shí)驗(yàn)每個(gè)算法的平均值均進(jìn)行100次求均值所得，Tbest為標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)給出的最優(yōu)解，實(shí)驗(yàn)中模擬退火終止溫度Tend都設(shè)為1。

實(shí)驗(yàn)1：ulysses16。

實(shí)驗(yàn)1參數(shù)設(shè)置如表1所示。

表1　實(shí)驗(yàn)1參數(shù)

1.此處無(wú)參數(shù)。

實(shí)驗(yàn)1結(jié)果對(duì)比如表2所示。

表2　實(shí)驗(yàn)1結(jié)果對(duì)比

實(shí)驗(yàn)2：ulysses22。

實(shí)驗(yàn)2參數(shù)設(shè)置如表3所示。

表3　實(shí)驗(yàn)2參數(shù)

1.此處無(wú)參數(shù)。

實(shí)驗(yàn)2結(jié)果對(duì)比如表4所示。

表4　實(shí)驗(yàn)2結(jié)果對(duì)比

實(shí)驗(yàn)3：oliver30。

實(shí)驗(yàn)3參數(shù)設(shè)置如表5所示。

表5　實(shí)驗(yàn)3參數(shù)

1.此處無(wú)參數(shù)。

實(shí)驗(yàn)3結(jié)果對(duì)比如表6所示。

表6　實(shí)驗(yàn)3結(jié)果對(duì)比

實(shí)驗(yàn)4：chn31。

實(shí)驗(yàn)4參數(shù)設(shè)置如表7所示。

表7　實(shí)驗(yàn)4參數(shù)

1.此處無(wú)參數(shù)。

實(shí)驗(yàn)4結(jié)果對(duì)比如表8所示，所得最優(yōu)值路徑如圖4所示。

表8　實(shí)驗(yàn)4結(jié)果對(duì)比

實(shí)驗(yàn)5：dantzig42。

實(shí)驗(yàn)5參數(shù)設(shè)置如表9所示，所得最優(yōu)值路徑如圖5所示。

表9　實(shí)驗(yàn)5參數(shù)

1.此處無(wú)參數(shù)。

實(shí)驗(yàn)5結(jié)果對(duì)比如表10所示。

表10　實(shí)驗(yàn)5結(jié)果對(duì)比

圖4實(shí)驗(yàn)4所得最優(yōu)值路徑圖

Fig.4The optimum path of experiment 4

圖5實(shí)驗(yàn)5所得最優(yōu)值路徑圖

Fig.5The optimum path of experiment 5

從以上實(shí)驗(yàn)結(jié)果可以看出，本文算法得到的解集中最優(yōu)解與最差解之間的距離較小，即得到的解較為集中，且明顯優(yōu)于傳統(tǒng)多種群遺傳算法和模擬退火多種群遺傳算法得到的解集，所得最優(yōu)解都接近標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)給出的最優(yōu)解，有些甚至等于或優(yōu)于最優(yōu)解。如實(shí)驗(yàn)4 chn31數(shù)據(jù)集，本文算法得到的最優(yōu)解等于標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)給出的最優(yōu)解15 377；實(shí)驗(yàn)5 dantzig42數(shù)據(jù)集，本文算法得到的最優(yōu)解比標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)給出的最優(yōu)解699低13.484 3，優(yōu)于標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)給出的最優(yōu)解。在城市數(shù)較少的時(shí)候，本文算法和傳統(tǒng)多種群遺傳算法都可以找到相同的最優(yōu)解，而當(dāng)城市數(shù)擴(kuò)大時(shí)，本文算法找到的最優(yōu)解都優(yōu)于傳統(tǒng)多種群遺傳算法。從實(shí)驗(yàn)的參數(shù)設(shè)計(jì)可以看出，隨著城市數(shù)的擴(kuò)大，種群規(guī)模、種群數(shù)量、模擬退火的初始溫度以及最大遺傳代數(shù)都在同步提高。這是由于數(shù)據(jù)集增大導(dǎo)致數(shù)據(jù)量增大，增加種群的數(shù)量可以提高搜索的并行性以此提高算法的搜索效率，而種群規(guī)模、模擬退火的初始溫度提高則擴(kuò)大了搜索的范圍。

4結(jié)語(yǔ)

本文通過(guò)分析傳統(tǒng)多種群遺傳算法存在易于早熟收斂的不足，設(shè)計(jì)出了一種改進(jìn)的遺傳算法AEMPGA，通過(guò)對(duì)TSP問(wèn)題進(jìn)行求解證明算法的有效性。與模擬退火算法相結(jié)合提高了算法的局部搜索能力，在種群的建立、遺傳算子方面也做了許多改進(jìn)，尤其是設(shè)計(jì)了新的基于交叉親和度評(píng)價(jià)的交流方式，使交流更為有效，提高了種群的多樣性。通過(guò)與其他多種群遺傳算法對(duì)比，實(shí)驗(yàn)證明了本文算法的有效性。然而實(shí)驗(yàn)選取的數(shù)據(jù)量均為小型數(shù)據(jù)集，城市數(shù)較少，對(duì)于大規(guī)模數(shù)據(jù)，算法的效果不是很好，容易出現(xiàn)尋優(yōu)時(shí)間過(guò)長(zhǎng)等缺陷。因此在今后的研究中要針對(duì)大規(guī)模數(shù)據(jù)的問(wèn)題設(shè)計(jì)更為理想的算法。

參考文獻(xiàn)：

[1]ELANSARY A M, ELDAMATTY A A, NASSEF A O.A coupled finite element genetic algorithm technique for optimum design of steel conical tanks [J]. Thin-Walled Structures,2010,48(3):260-273.

[2]DEB K.An efficient constraint handing method for genetic algorithms[J]. Comput.Methods Appl.Mech.Engrg, 2000，186(24):311-338.

[3]李孝忠,任吉棟.改進(jìn)的DNA遺傳算法在指派問(wèn)題中的應(yīng)用[J]. 天津科技大學(xué)學(xué)報(bào),2011,26(2):61-64.

[4]孫月峰,張勝紅,王曉玲,等.基于混合遺傳算法的區(qū)域大系統(tǒng)多目標(biāo)水資源優(yōu)化配置模型[J]. 系統(tǒng)工程理論與實(shí)踐,2009,29(1):139-144.

[5]呂卉,周聰,鄒娟,等.基于多種群進(jìn)化的遺傳算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2010,46 (28):57-60.

[6]劉守生,于盛林,丁勇,等.基于均勻分割的多種群并行遺傳算法[J]. 數(shù)據(jù)采集與處理,2003,18(2):142-144.

[7]鞏敦衛(wèi),孫曉燕.變搜索區(qū)域多種群遺傳算法[J]. 控制理論與應(yīng)用,2006,23(2):257-260.

[8]李鑫.改進(jìn)變異操作的多種群遺傳算法[J]. 信息系統(tǒng)工程,2012,20(9):136-140.

[9]王銀年,葛洪偉.求解TSP問(wèn)題的改進(jìn)模擬退火遺傳算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2010,46(5):44-47.

[10]CHANG W A, RAMAKRISHNA R S.A genetic algorithm for shortest path routing problem and the sizing of populations[J]. IEEE Trans on Evolutionary Computation,2002,6(6):566-579.

[11]馬良.旅行推銷員問(wèn)題的算法綜述[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2000,30(2):156-165.

[12]楊理云.用模擬退火算法求解旅行商問(wèn)題[J]. 微電子學(xué)與計(jì)算機(jī),2007,24(5):193-196.

[13]周松儒,歸偉夏.一種基于免疫原理的多種群DNA遺傳算法[J]. 廣西大學(xué)學(xué)報(bào):自然科學(xué)版,2013,38(5):1135-1139.

[14]李軍華,黎明,袁麗華.遺傳算法求解TSP的種群多樣性研究[J]. 小型微型計(jì)算機(jī)機(jī)系統(tǒng),2008,29(3):544-547.

[15]SCINVIVAS M, PATNAIK L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Trans SMC, 1994, 24(4):656-666.

(責(zé)任編輯梁碧芬)

A multi-population genetic algorithm based on cross accessibility evaluation

WANG Dong， GUI Wei-xia

(College of Computer, Electronics and Information, Guangxi University, Nanning 530004, China)

Abstract:To solve traditional multiple population genetic algorithm for rapid loss of species diversity in the process of evolution, which may result in easy premature convergence to local optimal solution, a multiple population genetic algorithm based on cross accessibility evaluation is put forward. By adopting the idea of parallel search multiple species, it combines with the simulated annealing algorithm to improve the search ability.The individualis elected by crossover excellent recommendation among multiple populations and the target population is replaced through evaluating accessibility to complete communication. Finally, the algorithm is used to solve the TSP problem. The results show that the solution is close to the optimal solution and the performance is superior to traditional multiple population genetic algorithm.

Key words:genetic algorithms; cross accessibility evaluation; simulated annealing; multi-population

中圖分類號(hào)：TP18

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001-7445(2015)06-1508-09

doi:10.13624/j.cnki.issn.1001-7445.2015.1508

通訊作者：歸偉夏(1974—),女,廣西南寧人,廣西大學(xué)副教授,博士;E-mail:740473@qq.com。

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61363002);廣西教育廳科研基金資助項(xiàng)目(LX2014002)

收稿日期：2015-09-01；

修訂日期：2015-10-01