基于自適應(yīng)評價函數(shù)的遺傳算法求解ＴＳＰ問題

摘要：針對TSP問題，提出了一種基于自適應(yīng)評價函數(shù)的改進的遺傳算法，并且給出選擇、交叉和變異操作的設(shè)計，實驗表明算法維持了群體的多樣性，防止算法過早收斂而陷入局部最優(yōu)解，更有效地搜出全局近似最優(yōu)解。

關(guān)鍵詞：遺傳算法；TSP；自適應(yīng)；優(yōu)化

中圖分類號：TP183文獻標(biāo)識碼：A文章編號：1009-3044(2008)12-20ppp-0c

A Enhanced Genetic Algorithm Based on Self-adaptation Evaluating Function for the TSP Problem

WANG Hui

(GuangDong Vocational Institute of Public Administration GD.Guangzhou 510053，China)

Abstract: This article describes a enhanced genetic algorithm based on self-adaptation evaluating function for the TSP problem， and the design of the selection， crossover and mutation operations. Experiments indicate that this algorithm remains the diversify of the groups and avoid leading to local optimization，and more effectively find out close to optimization value.

Key words: Genetic Algorithms;TSP;self-adaptation;Optimization

1 引言

生物通過許多代的進化才能更好的繁殖，適應(yīng)了不斷改變的外界環(huán)境因素而生存。遺傳算法利用生物基礎(chǔ)，將特定問題轉(zhuǎn)化成生物的遺傳問題，經(jīng)過長時間的成長，演化，最后收斂到某個解。生物固有的特征攜帶于雙螺旋的DNA 上， 子代通過父代的DNA 的重組獲得或繼承到父代的優(yōu)良特性。在基因重組的過程中，有可能產(chǎn)生變異，使物種有了多樣性， 有更多的發(fā)展和選擇空間。適者生存，使整體物種向優(yōu)良進化。利用這種思想，可以解決很多實際問題。比如TSP問題， 即貨郎擔(dān)問題: 給定幾個城市及所有城市之間的距離， 必須決定一條路線， 使他能訪問到每個城市一次，然后返回到起點并且旅行路徑最短。

目前求解TSP問題的主要方法有：Hopfield神經(jīng)網(wǎng)絡(luò)方法、模擬退火法以及遺傳算法[1]，等等。而遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局概率搜索算法、具有良好的全局尋優(yōu)能力，成為解決TSP問題的有效方法之一。但遺傳算法解決TSP問題中一個難解決的問題是如何較快地找到最優(yōu)解并防止早熟收斂問題。當(dāng)前許多研究者提出了諸多改進方法來提高遺傳算法的性能，如單親進化遺傳算法[2]，其原理是利用父代個體所提供的有效邊的信息，使用保留最小邊的方法進行個體的進化，此法雖然保證了收斂速度但易陷入局部最優(yōu)，本文提出了一種改進的遺傳算法。

2 遺傳算法

遺傳算法(Genetic Algorithms 簡稱GA )是由美國Michigan大學(xué)的John Holland[3]教授創(chuàng)建的，是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。它的思想源于生物遺傳學(xué)和適者生存的自然規(guī)律，是具有“生存＋檢測”的迭代過程的搜索算法。遺傳算法以一種群體中的所有個體為對象，并利用隨機化技術(shù)指導(dǎo)對一個被編碼的參數(shù)空間進行高效搜索。其中，選擇、交叉和變異構(gòu)成了遺傳算法的遺傳操作。選擇是遺傳算法的關(guān)鍵，它體現(xiàn)了自然界中適者生存的思想；交叉體現(xiàn)了自然界中信息雜交的思想；變異模擬了生物進化過程中的偶然基因突變現(xiàn)象，變異算子則保證了算法能搜索到問題解空間的每一點，從而使算法達(dá)到全局最優(yōu)。

3 TSP問題描述

貨郎擔(dān)問題（Traveling Salesman Problem，TSP），也稱為巡回旅行商問題[4]，是一個具有廣泛的應(yīng)用背景和重要理論價值的組合優(yōu)化問題，是一個較古老的問題。最早可以追溯到1759年Euler提出的騎士旅行問題。1948年，由美國蘭德公司推動，TSP問題成為近代組合優(yōu)化領(lǐng)域的一個典型難題，并已經(jīng)被證實是NP（Nondeterministic Polynomial Completeness）難解問題[5]。TSP問題其數(shù)學(xué)描述為：給定m個城市，尋找一條閉合路徑，使得每個城市剛好經(jīng)過一次且總的旅行距離最短。即尋找一條閉合路徑（設(shè)n維向量表示一條路徑）：r=(C1，C2，…，Cn)，使得下列目標(biāo)函數(shù)最小：

上式中Ci 為城市號，d(i，j)表示城市i與城市j之間的距離[6]。對于m個城市的TSP問題，其可能的路徑組合數(shù)為(m-1)!/2。這樣，TSP最優(yōu)解的搜索空間將隨著城市數(shù)m成指數(shù)型增長（所謂的“指數(shù)爆炸”）。因此，TSP問題雖易于描述，但找出其最優(yōu)解卻是非常困難的。因而尋找出有效的近似求解算法就具有重要的意義。很多實際應(yīng)用問題，例如連鎖店的貨物配送路線等，經(jīng)過簡化處理后，均可建模為貨郎擔(dān)問題，因而對貨郎擔(dān)問題求解方法的研究具有重要實際價值。

用遺傳算法解TSP問題，一個旅程很自然地表示為n個城市的排列，如果采用二進制編碼來處理，將會很困難，因為進行一次交叉、變異操作，有可能使該位串代表的解已經(jīng)不適合原問題，結(jié)果必需采用特殊的方法來修改位串，每進行一次迭代都進行這樣的操作，從而使問題變得復(fù)雜起來。如果采用整數(shù)變量進行編碼， 則不會存在這樣的問題，使處理問題變得更簡潔。采用路徑表達(dá)方式和整數(shù)變量編碼：向量ν=(i1，i2…，in)代表一個從城市i1到i2……一直到in再回到i1的旅行。如ν=(3 4 5 7 1 2 9 8 6)。

4 算法設(shè)計

4.1 流程圖

本次算法流程圖如下：

4.2 輸入要求

TSPLIB是一個研究TSP問題的常用數(shù)據(jù)集，本文選取TSPLIB中48城市的數(shù)據(jù)集ATT48作為實驗數(shù)據(jù)集。TSPLIB中給出ATT48的最優(yōu)路徑長為3.3524公里。

4.3 初始化

定義各個參數(shù)： 這里我們求解48個城市的TSP問題，將種群規(guī)模設(shè)置為300，交叉概率Px=0.5，變異概率Pm=0.01，最大迭代的代數(shù)為10000。

4.4 求解過程

4.4.1 染色體群體的初始化

需要初始化300個染色體：可以從不同城市開始對染色體進行初始化。

4.4.2 評價函數(shù)的定義、約束條件

在GA中，適應(yīng)度是描述個體性能的主要指標(biāo)。根據(jù)適應(yīng)度的大小，對個體進行優(yōu)勝劣汰，又是驅(qū)動GA的動力，在遺傳過程中具有重要意義。對于求解有約束優(yōu)化問題時，一般采用將目標(biāo)函數(shù)做適當(dāng)處理，建立適合GA的評價函數(shù)。將目標(biāo)函數(shù)轉(zhuǎn)換成評價函數(shù)一般應(yīng)遵循兩個原則：一是適應(yīng)度必須非負(fù)；二是優(yōu)化過程中目標(biāo)函數(shù)的變化方向應(yīng)與群體進化過程中評價函數(shù)變化方向一致。

（1）評價函數(shù)：G－全程的總費用（設(shè)有n個城市，從第1個到第n個再回到第1個的總費用），其中G為一常量或一個自適應(yīng)變化的值。

適應(yīng)值公式可以表示為：F=G-Cost

每一個染色體的評價值可以這樣計算：F=G-Cost，其中Cost表示按順序遍歷此染色體中所有城市所需的費用；G可以是常量也可以是一個隨著迭代次數(shù)而變化的函數(shù)，即G=f(g)，g表示第g代。

如果G取值太大，則無法體現(xiàn)每個染色體之間的差別；如果G取值太小，則可能在一輪選擇中有太多的染色體被淘汰，失去了群體的多樣性，無法產(chǎn)生更好的后代，從而有可能導(dǎo)致計算收斂于局部最大值。

設(shè)第g代的所有染色體中的最大費用為Maxg(costj)，0

所以我們可以定義：wh06.tif，其中con定義為隨著“代”數(shù)g而變化的函數(shù)，即con(g)=f(g)，其中1≤con(g)≤∞。可見，當(dāng)con＝1時，wh07.tif，當(dāng)con＝∞時，G(g)=Maxg(costj)。Con(g)=(MAXGENS*n)/(MAXGENS-g)（g為“代”數(shù)），取n＝4。

（2）約束條件：任何一個染色體向量里面的任何兩個點都不能相同。

4.4.3 選擇

（1）采用輪盤式選擇法：根據(jù)每個染色體的評價值決定其被選擇的概率，然后選擇產(chǎn)生新的染色體群體。選擇概率＝個體最佳適應(yīng)值/群體總適應(yīng)值，群體總適應(yīng)值＝個體最佳適應(yīng)值的累加(個體最佳適應(yīng)值的計算方法參考4.4.2)；

（2）如果新的群體的最佳染色體比歷史最佳染色體差，則用歷史最佳染色體替換新群體中的最差染色體。

4.4.4雜交

（1）染色體的選擇：根據(jù)雜交概率Px選擇m個用于雜交的染色體。如果m為奇數(shù)，則丟棄最后一個被選擇到的染色體；

（2）對于第i對(i=1，…，(m-1)/2)被選中的染色體，產(chǎn)生兩個2到city_num -1之間的隨機數(shù)：j和k（j<=k），要求k-j>city_num/2(city_num為城市數(shù)目)，即每一次都不要讓超過一半的基因參加雜交；

（3）j和k之間的數(shù)不變，兩個染色體的第1到j(luò)-1位進行雜交，第k+1到city_num位進行雜交；

（注：位＝城市）如：

P1=(1 2 3 4 5 6 7 8 9)

P2=(4 1 6 8 7 2 9 3 5)

j=2， k=6，那么第1到1位，第7到9位將被雜交。（注：位＝城市）

則雜交后的后代為：（切割點以“|”表示）

O1=(4 | 2 3 4 5 6 | 9 3 5)

O2=(1 | 1 6 8 7 2 | 7 8 9)

（4）其中，O1和O2中都有重復(fù)的數(shù)（O1： 4 3 5；O2：1 8 7）。為保證新染色體是有效的，必須采用修正算法：

①對O1，從左到右搜索，當(dāng)找到一個重復(fù)數(shù)時停止（如第一個：4）；

②對O2，從右到左搜索，當(dāng)找到一個重復(fù)數(shù)時停止（如倒數(shù)第三個：7）；

③雜交上兩步所得的兩個數(shù)。得到：

O1=(7 | 2 3 4 5 6 | 9 3 5)

O2=(1 | 1 6 8 7 2 | 4 8 9)

④ 重復(fù)1到3直到O1搜索完畢。得到結(jié)果如下：

O1=(7 | 2 8 4 1 6 | 9 3 5)

O2=(1 | 5 6 8 7 2 | 4 3 9)

4.4.5 變異

（1）變異位的選擇：根據(jù)變異概率Pm按位選擇，即對每個染色體中的每一位（城市）產(chǎn)生一個隨機數(shù)r，如果r

（2）隨機選取同一個染色體中的另外一個位（城市）j（1<= j <=city_num并且j不等于i），如：

V=(7 6 1 4 5 2 9 3 5)

（3）在改染色體中雜交第i和第j個城市得到新的變異后的染色體，如（假設(shè)i=2，i=7）：

V=(7 9 1 4 5 2 6 3 5)。

4.4.6 退出條件

當(dāng)?shù)鷶?shù)達(dá)到最大迭代“代”數(shù)(10000)時退出。

5 實驗結(jié)果及分析

5.1 實驗結(jié)果

進行多次實驗，算法找到的最優(yōu)路徑長度大多落在3.4-3.7之間，實驗中在進化到9860代時，找到的48城市的最短路徑為 3.433997 。說明繼續(xù)進化還會得到更好解。

5.2 自適應(yīng)函數(shù)G(g) 分析：

GA用適應(yīng)值作為復(fù)制的選擇壓力，如果群體的適應(yīng)值變化不大或過大，會引起選擇壓力不足或波動，導(dǎo)致選代過程過早收斂或發(fā)生震蕩。在下面圖2（橫座標(biāo)是g，縱座標(biāo)是G）中，我們可以看出迭代到500代函數(shù)G(g)的取值隨進化代數(shù)g的增加的變化趨勢：G(g)隨著進化代數(shù)的增加而減小而且只與進化的代數(shù)有關(guān)，是自適應(yīng)的（隨著“代”數(shù)而自動調(diào)節(jié)的）；

通過計算過程中記錄的適應(yīng)值和演化代數(shù)數(shù)據(jù)，可以從圖2中看出算法的收斂速度。我們可以看出，在算法執(zhí)行的早期，個體適應(yīng)值下降的非常快，說明早期雜交算子作用非常明顯，后期，算法效率趨于平緩，但仍有少許變化，可以說明設(shè)計的變異算子也起到了作用。

6 結(jié)束語

本文針對TSP問題，提出了一種全新的遺傳算法，設(shè)計了編碼方式、交叉操作、變異操作和適應(yīng)度函數(shù)以及選擇方法，實驗數(shù)據(jù)表明：評價函數(shù)能夠根據(jù)進化實際情況自動調(diào)整， 克服了簡單遺傳算法存在早收斂及進化后期搜索效率較低的缺點， 提高了算法的收斂速度，較好地解決了群體中多樣性和收斂速度的矛盾。我們認(rèn)為遺傳算法的編碼和遺傳操作必須能夠充分反映和充分利用遺傳信息，實驗結(jié)果也進一步表明，同時采用不同的方法控制遺傳算法的不同參數(shù)， 遺傳算法的適應(yīng)性將會隨著具有動態(tài)自適應(yīng)能力參數(shù)數(shù)量的增加而增強。

參考文獻

[1] ChristofidesN．Worst-caseAnalysis 0f aNewHeuristicfortheTraveling SalesmanProblem[J].TechnicalReport，2002(2):27-31．

[2] 馬欣，朱雙東，楊斐.旅行商問題(TsP)的一種改進遺傳算法[J].計算機仿真，2003(4):36-37．

[3] Holland J H. Adaptation in natural and artificial systems. Univ of Michigan Press， Ann Arbor Mich，1975

[4] 潘正君，康立山，陳毓屏.演化計算.北京：清華大學(xué)出版社/廣西科學(xué)技術(shù)出版社，20O0:149-161．

[5] Garey.M. and Johnson.D. Computers and Intractability. W.H.Freeman.San Francisco，1979.

[6] 陳國良，王熙法.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996．

收稿日期：2008-03-22

作者簡介：王會（1980-），女，廣東廣州人，助教，學(xué)士，從事計算機程序設(shè)計語言等的教學(xué)，中山大學(xué)在職碩士研究生，研究方向：軟件工程。

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”