帶有約束優化的遺傳算法求解ＴＳＰ

摘要：主要研究用遺傳算法解決帶有約束的TSP的方法。使用貪婪交叉算子、自適應變異算子和帶有精英保留策略的選擇算子相結合對基本遺傳算法進行了改進，針對實際TSP中的約束條件討論了罰方法在遺傳算法中的應用，提出了自適應的懲罰函數，并將其與改進后的遺傳算法相結合，解決了帶有時間約束的TSP。通過對實驗結果的比較分析，證明了該方法的可行性和有效性。

關鍵詞：旅行商問題； 遺傳算法； 約束優化； 罰函數

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2008)05-1323-03

遺傳算法是1975年由John Holland教授提出。它借用了仿真生物遺傳學和自然選擇機理，通過自然選擇、交叉、變異等機制實現各個個體適應性的提高。遺傳算法在整個進化過程中的遺傳操作是隨機的；但是它呈現出來的特性卻并不是完全隨機的，它能夠有效地利用歷史信息使得下一代群體性能有所提高，一代一代不斷進化，最終收斂到一個即使不是最優解，也是離最優解非常接近的解空間上。遺傳算法涉及到編碼方式、初始種群、適應度函數、遺傳算子和控制參數五大要素。

基本遺傳算法雖然具有全局搜索能力，但是在進化過程中往往容易出現收斂速度緩慢或不收斂，又或陷入局部最優的情況，加快收斂速度又有可能出現早熟現象，過或不及都不能及時準確地獲得最優解。因此，學者們在這些方面進行了大量的研究，希望既能加快收斂速度，又能防止早熟收斂。

1約束優化

1．1約束優化介紹

現實中所遇到的問題大部分都是約束問題。約束優化的一般形式如下：

1．2罰方法在遺傳算法中的應用

在約束優化中，解空間一般包含兩部分，即可行區域和不可行區域。罰方法的主要問題就是如何設計罰函數p(x)，使得它能夠有效地將遺傳搜索引導到解空間中有希望的區域去，通過懲罰不可行解將約束問題轉換為無約束問題。

罰方法在遺傳算法中主要體現在評價函數上，用原來遺傳算法中的目標函數f(x)和罰函數p(x)共同作用來決定染色體的評價函數。如何設計一個好的罰函數直接影響到那些距離最優解很近的不可行解能否進入下一代的進化。

對不可行解的懲罰既可以是常數懲罰，也可以是可變懲罰。對于復雜問題來說常數懲罰的效率不是很高?？勺儜土P通常包含兩個元素：可變的懲罰率;對于違背約束的懲罰量?？勺兊膽土P率可以根據違背約束的程度和遺傳算法的迭代代數來調整。根據Michalewicz的討論[1]，懲罰分為靜態懲罰和動態懲罰兩種。靜態懲罰隨著違背程度的加深而增加懲罰壓力；動態懲罰隨著進化過程而增加懲罰壓力。

1．3自適應的懲罰函數 

在遺傳算法的進化初期，種群的多樣性較大，各個體可以相互交叉產生適應值高的個體。如果此時的懲罰壓力過大，會使得大量不可行解被拋棄，個體的多樣性急劇減少，導致種群過早收斂而陷入局部最優。這時應該隨著違背程度的加深而增加懲罰壓力。隨著進化的進行，越來越多的高適應值個體出現，種群也開始向高適應值個體收斂，這時應該減少不可行解的數量，使種群收斂到可行解上；同時也可以減少進化過程中的運算量，加快收斂到最優解的時間。目前很多懲罰方法已經被提出，如Homaifar、 Lai Qi method、 Joines Houck method、 Michalewicz Janikow method、 Michalewicz Attia method等[1]。本文參考Joines Houck method提出一種結合動態懲罰和靜態懲罰的自適應懲罰函數，讓懲罰壓力既隨違背程度的加深而增加，又隨著進化代數的增加而增加。

2帶有約束的遺傳算法的實現

本文采用實數編碼方法對染色體編碼，使用貪婪交叉算子、自適應的變異算子和輪盤賭選擇算子進行遺傳操作，并使用精英保留策略保留每一代中的最佳個體。在整體流程的設計中，讓父代的N個染色體以選擇概率PC進行選擇，選擇的結果進行自適應變異。為了不使遺傳操作改變原有的好的基因結構，特將父代染色體、交叉的結果和變異結果一起進行輪盤賭選擇；為了保證算法的收斂性，采用精英保留策略將每一代的染色體直接復制進入下一代。

2．1貪婪交叉算子[2]

貪婪交叉算子利用了在全局最優解中會保留大量局部最優片斷的特點，也就是說很多在局部最優中相鄰的片斷在全局最優中也會相鄰。

貪婪交叉算子的思想是：

a）在父代中隨機選定一個城市C作為子代的初始城市。

b）分別從兩個父代中找到C的右城市并計算C到這兩個城市的距離。

c）將距離小的對應的右城市添加到子代1中，并從父代中刪除C，修改C為距離最近的右城市。

d）如果父代中的城市數為1則結束；否則轉向b）繼續執行。

同理，向左進行搜索，將結果放入子代2中。在具體操作時，只需將原父代倒序一次，那么向左搜索也就變成向右搜索了。由于使用貪婪交叉算子時考慮到了TSP中邊的鄰接問題，每次都選取距離該城市較近的鄰接城市，從而可以加快收斂速度。

2．2自適應的變異算子

變異在遺傳算法中的作用主要是增加群體的多樣性，使算法能夠跳出局部最優。變異概率取得過小，不能很好地改變群體的多樣性；如果取得過大，又會破壞好的基因片斷。因此使用自適應的變異算子。經過上述貪婪交叉算子之后，群體的平均適應度相對較高。對于個體適應度高于平均適應度的優良個體，應該采取保護策略予以保留，這時的變異概率不宜取得過大，而對于個體適應度低于平均適應度的個體，則應以較高的概率淘汰。自適應變異算子定義如下：

3算法實現

3．1實驗結果

本文算法用Java語言實現，對TSPLIB的att48中的城市數據進行了測試，在交叉概率為0．9，初始種群為1 000，最大進化代數為500的條件下，首先對改進的遺傳算法單獨進行測試，然后在同樣條件下再對有時間約束的遺傳算法測試。設車的平均行駛速度為100 km/h，起始配送點為節點6，有條件約束的節點為10，時間為48 h。經過大量測試發現，在α＝0．8，β＝0．8，C=0．1附近取得較好的解。通過10次測試，結果如表1、圖2~4所示。圖2表示無約束的改進遺傳算法的進化過程和最短路徑；圖3為TSPLIB公布的att48目前最好的路徑；圖4表示有時間約束的改進遺傳算法的進化過程和最短路徑。

4結束語

從圖2中可以看出，在無約束的遺傳算法中，最短路徑曲線單調遞減，直到收斂到最優解，它對應的路徑是一條無交叉的折線。在用該算法進行的10次測試中，有7次可以得到33 600.561 458 470 7的結果，證明該算法穩定性很好、準確度高；每一次測試都在200多代收斂，說明了該改進算法的收斂速度快。圖4(a)的曲線在進化初期出現了比較大的抖動，不是單調遞減的，造成這個現象的原因就在于自適應罰函數的存在。在進化初期，代數較小，這時進化代數起的作用比較小，對一些距離最優解比較近的非可行解懲罰也比較小，而這些非可行解附帶比較多的最優解片段，因此可能被接納作為當代最優解。隨著進化的進行，進化代數增大，罰函數項在適應度函數中占的比重也越來越大，對非可行解的懲罰也越來越重。當初被接納的非可行解通過無數次的交叉之后，它們附帶的有用信息也轉移到了其他個體身上，這時它們就被淘汰了，所以到了后期，曲線比較平緩，不會再出現劇烈的抖動。也正是因為約束的存在，圖4(b)的求解路徑要滿足約束條件，出現交叉。

本文提出的算法是基于改進遺傳算法上的約束優化算法，得益于遺傳算法的全局搜索能力和魯棒性，該算法在實際的TSP工程應用中具有較好的穩健性。當有多個約束條件時也可以處理，具有較強的可擴展性。通過改進的遺傳算法加快了收斂速度、節省了時間，進一步增強了該算法的實用性。

參考文獻：

[1]MICHALEWICZ Z. A survey of constraint handling techniques in evolutionary computation methods[C]//Proc of the 4th Annual Con-ference on Evolutionary Programming. Cambridge: MIT Press， 1995:135－155.

[2]謝勝利，唐敏，董金祥.求解TSP問題的一種改進的遺傳算法[J]. 計算機工程與應用， 2002，38(8):58-60， 245.

[3]玄光男，程潤偉.遺傳算法與工程優化[M].北京:清華大學出版社， 2004.

[4]李敏強，寇紀松，林丹，等.遺傳算法的基本理論與應用[M].北京:科學出版社， 2002.

[5]MICHALEWICZ Z， JANIKOW C. Handling constraints in genetic algorithms[C]//Proc of the 4th International Conference on Genetic Algorithms. Los Altos: Morgan Kaufmann Publishers， 1991.

[6]許麗佳，蒲海波，蔣宏健.改進遺傳算法的路徑規劃研究[J].微計算機信息，2006， 22(2):251-253.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”