遺傳算法與蟻群算法在商旅問題中的應用研究

梁晶

（哈爾濱鐵道職業技術學院，黑龍江哈爾濱，150040）

遺傳算法與蟻群算法在商旅問題中的應用研究

梁晶

（哈爾濱鐵道職業技術學院，黑龍江哈爾濱，150040）

遺傳算法在多個領域得到了應用，如人工智能領域，最優化求解問題，TSP問題等等。本文就遺傳算法的基本定義與思想進行了介紹，同時介紹了由遺傳算法優化或者衍生而來的一些算法的作用。并介紹了遺傳算法的具體應用。

遺傳算法；算子；變異；蟻群；算法應用

1 遺傳算法簡介

遺傳算法名稱來源于生物進化理論，本著優勝劣汰，適者生存的思想原則。遺傳算法研究的對象不再是單一的個體，而是具有共同的特性的種群，這些種群也是同生物體一樣，是由基因組成的。這些基因在算法中是通過編碼的方式來實現。最初的編碼方式常常是計算機最容易接受的二進制編碼。伴隨著遺傳算法的發展，實現能力不斷增強，編碼方式也呈現出多樣化，不僅僅局限于二進制編碼，實數編碼方式也經常使用。

遺傳算法實現“最優解”的方式：我們把實際應用中的某些問題，轉化為數學模型，以數學的方式期望達到某個控制范圍得以實現最終結果的最優解。這里要強調的是，這個范圍或者某個具體的數值我們常常稱之為適應度。而且遺傳算法最終的求解目標往往不是最優，這也是前文最優解加上引號的原因。它期望達到的是實現近似的多個優解。首先在第一代的基因中進行遺傳和變異算子過程，產生的新一代種群，進行挑選，對于符合適應度要求的進行再次變異和遺傳過程。通過這一代代的繁殖和挑選，最終實現了一組距離最優化解最近的種群解。

2 遺傳算法計算機實現思想

第一步，初始化操作。從算法思想我們知道，在計算機實現遺傳算法過程中，要進行多代遺傳，那么這個繁衍的次數應該進行設置，避免出現死循環。采用算法對種群進行生成，也就是在設計初期，進行種群個數的設置或者算法生成。第二步，算出關鍵的適應度參數，這是每一代遺傳后，保留或者舍棄個體的判斷標準。如果適應度計算錯誤，那么后面的計算就失去了意義。第三步，選擇運算 ，把遺傳的群體中的個體通過選擇運算，進行挑選，符合的可以直接再次遺傳，不符合的可以重新交叉，產生新一代。選擇算法可以通過邏輯運算以及臨界數值計算來實現。第四步，交叉與變異，定義交叉運算規則，便于產生下一代，實現遺傳過程。而變異是通過改變某些編碼，實現適應度的接近。第五步，當滿足遺傳代數條件后，或者滿足最優設置條件后，算法結束，得到相應的近似化優解。

3 遺傳算法與蟻群算法的合作

3.1 遺傳算法與蟻群算法合作的特性

在解決一些實際問題與實際應用中，我們發現經常會出現遺傳算法與蟻群算法的融合。而且兩種算法融合后能夠發揮更好的效果。從本質上來講，兩種算法都可以歸類為隨機算法后的優化過程算法。但遺傳算法側重于進化，不斷產生優秀的后代，而蟻群算法還可以歸類為智能優化算法，具有一定記憶功能以及對最短路徑的求解過程。所以兩者合作，更利于實現最優解，同時也可體提高算法的實現效率。

3.2 蟻群算法的最短路徑求解思想

蟻群算法常常用于求解最短路徑，利用的生物學中螞蟻覓食的特性。我們通過觀察發現，螞蟻進行群體活動，在覓食過程中總是會找到最短的路徑。螞蟻種群之間是如何實現信息的傳遞的呢？通過研究發現，螞蟻可以分泌一種可揮發的物質，在螞蟻行進過程中，就會分泌這種物質，如果路徑越短，揮發的物質越少，信息源濃度就越高。同時，路徑越不堵塞，通過的越快，揮發的物質就越少，信息源濃度也相應越高。這就是通暢的最短路徑的形成方式。

4 商旅問題的遺傳算法與蟻群算法實現思想

商旅問題也稱之為貨郎問題，是要遍歷多個節點，每個節點只走一次，完成這個遍歷且回到出發點的最短路徑即為所求。商旅問題用窮舉法當然可以解決，但伴隨城市節點的增多，組合數不斷增大，這種窮舉得代價巨大，甚至難以實現。用遺傳算法和蟻群算法都可優化實現路徑尋找，但仔細揣摩，會發現實現的過程存在差異，通過解決實際問題能夠幫助我們更好的理解兩種算法的優劣與不同。

4.1 遺傳算法實現商旅問題

遺傳算法先以城市數目為種群數，由于是尋找最短路徑，當然是以越小越實現最優解。所以適應度參數可以設置為任意一個小于實際路徑長度的數值，這當然就實現了越小越接近于適應數值的目標。然后通過設置父母初代的不同位置，實現交叉后的遺傳，當然為了判斷基因優劣，也可以選取父母中位置相同的位置作為基因，進行適應判斷，達到遺傳次數，找出近似最優解。但是為了符合題意，在交叉變異過程中，走過的節點不在選擇范圍之內。

4.2 蟻群算法實現商旅問題

蟻群算法利用隨機算法實現節點選擇，然后通過概率進行下一節點的判斷。第一步驟中，與初始節點連接的若干節點的概率應該是相同的，但是通過走過的螞蟻可以改變概率大小，當然是路徑越短，概率越高。但是從這種實現算法來看，蟻群算法的全局收斂性較差，可能會出現路徑錯誤或者完成迭代次數，仍然未實現路徑判斷的過程。一旦發生這種情況，就要重新選擇初始節點進行判斷。當完成多路徑選擇后，計算不同螞蟻所走路徑，通過記憶的路徑長短，求出總路徑和，判斷哪只為最短最優解。

4.3 遺傳算法實現商旅問題的具體舉例

首先，種群初始化。個體編碼方法有二進制編碼和實數編碼，在解決TSP問題過程中個體編碼方法為實數編碼。對于TSP問題，實數編碼為1-n的實數的隨機排列，初始化的參數有種群個數M、染色體基因個數N（即城市的個數）、迭代次數C、交叉概率Pc、變異概率Pmutation。

其次，適應度函數。在TSP問題中，對于任意兩個城市之間的距離D(i,j)已知，每個染色體（即n個城市的隨機排列）可計算出總距離，因此可將一個隨機全排列的總距離的倒數作為適應度函數，即距離越短，適應度函數越好，滿足TSP要求。再次，選擇操作。遺傳算法選擇操作有輪盤賭法、錦標賽法等多種方法，本程序采用基于適應度比例的選擇策略，即適應度越好的個體被選擇的概率越大，同時在選擇中保存適應度最高的個體。進一步說，交叉操作。遺傳算法中交叉操作有多種方法。本程序中對于個體，隨機選擇兩個個體，在對應位置交換若干個基因片段，同時保證每個個體依然是1-n的隨機排列，防止進入局部收斂。最后，本程序中對于變異操作，隨機選取個體，同時隨機選取個體的兩個基因進行交換以實現變異操作。

[1]帶有偵察子群的蟻群系統[J].許劍,呂志民,徐金梧.北京科技大學學報. 2006(08).

[2]蟻群優化算法的收斂性分析[J].朱慶保.控制與決策. 2006(07) .

[3]遺傳算法交叉操作的改進[J].蔡良偉,李霞.系統工程與電子技術. 2006(06).

[4]基于免疫算法的配電網重構[J].蒙文川,邱家駒.中國電機工程學報. 2006(17).

[5]一種自適應雜交算子的浮點遺傳算法[J].都偉,韓正之.系統仿真學報. 2006(06).

[6]變搜索區域多種群遺傳算法[J].鞏敦衛,孫曉燕.控制理論與應用. 2006(02).

[7]一種提高局部搜索能力的混合遺傳算法[J].田延碩,劉曉云.電子科技大學學報. 2006(02).

[8]一種求解TSP的高效遺傳算法[J].王超學,崔杜武,王竹榮,費蓉.西安理工大學學報. 2006(01).

Research on the application of genetic algorithm and ant colony algorithm in business trip

Liang Jing
(Harbin Railway Technical College,Harbin Heilongjiang,150040)

Genetic algorithm has been applied in many fields, such as artificial intelligence, optimization problem, TSP problem and so on. In this paper, the basic concepts and ideas of genetic algorithm are introduced. At the same time, the function of some algorithms which are derived from the genetic algorithm is introduced. The application of genetic algorithm is introduced.

genetic algorithm; operator; mutation; ant colony algorithm; application