遺傳算法與蟻群算法在商旅問(wèn)題中的應(yīng)用研究

梁晶

（哈爾濱鐵道職業(yè)技術(shù)學(xué)院，黑龍江哈爾濱，150040）

遺傳算法與蟻群算法在商旅問(wèn)題中的應(yīng)用研究

梁晶

（哈爾濱鐵道職業(yè)技術(shù)學(xué)院，黑龍江哈爾濱，150040）

遺傳算法在多個(gè)領(lǐng)域得到了應(yīng)用，如人工智能領(lǐng)域，最優(yōu)化求解問(wèn)題，TSP問(wèn)題等等。本文就遺傳算法的基本定義與思想進(jìn)行了介紹，同時(shí)介紹了由遺傳算法優(yōu)化或者衍生而來(lái)的一些算法的作用。并介紹了遺傳算法的具體應(yīng)用。

遺傳算法；算子；變異；蟻群；算法應(yīng)用

1 遺傳算法簡(jiǎn)介

遺傳算法名稱來(lái)源于生物進(jìn)化理論，本著優(yōu)勝劣汰，適者生存的思想原則。遺傳算法研究的對(duì)象不再是單一的個(gè)體，而是具有共同的特性的種群，這些種群也是同生物體一樣，是由基因組成的。這些基因在算法中是通過(guò)編碼的方式來(lái)實(shí)現(xiàn)。最初的編碼方式常常是計(jì)算機(jī)最容易接受的二進(jìn)制編碼。伴隨著遺傳算法的發(fā)展，實(shí)現(xiàn)能力不斷增強(qiáng)，編碼方式也呈現(xiàn)出多樣化，不僅僅局限于二進(jìn)制編碼，實(shí)數(shù)編碼方式也經(jīng)常使用。

遺傳算法實(shí)現(xiàn)“最優(yōu)解”的方式：我們把實(shí)際應(yīng)用中的某些問(wèn)題，轉(zhuǎn)化為數(shù)學(xué)模型，以數(shù)學(xué)的方式期望達(dá)到某個(gè)控制范圍得以實(shí)現(xiàn)最終結(jié)果的最優(yōu)解。這里要強(qiáng)調(diào)的是，這個(gè)范圍或者某個(gè)具體的數(shù)值我們常常稱之為適應(yīng)度。而且遺傳算法最終的求解目標(biāo)往往不是最優(yōu)，這也是前文最優(yōu)解加上引號(hào)的原因。它期望達(dá)到的是實(shí)現(xiàn)近似的多個(gè)優(yōu)解。首先在第一代的基因中進(jìn)行遺傳和變異算子過(guò)程，產(chǎn)生的新一代種群，進(jìn)行挑選，對(duì)于符合適應(yīng)度要求的進(jìn)行再次變異和遺傳過(guò)程。通過(guò)這一代代的繁殖和挑選，最終實(shí)現(xiàn)了一組距離最優(yōu)化解最近的種群解。

2 遺傳算法計(jì)算機(jī)實(shí)現(xiàn)思想

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

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

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

在解決一些實(shí)際問(wèn)題與實(shí)際應(yīng)用中，我們發(fā)現(xiàn)經(jīng)常會(huì)出現(xiàn)遺傳算法與蟻群算法的融合。而且兩種算法融合后能夠發(fā)揮更好的效果。從本質(zhì)上來(lái)講，兩種算法都可以歸類為隨機(jī)算法后的優(yōu)化過(guò)程算法。但遺傳算法側(cè)重于進(jìn)化，不斷產(chǎn)生優(yōu)秀的后代，而蟻群算法還可以歸類為智能優(yōu)化算法，具有一定記憶功能以及對(duì)最短路徑的求解過(guò)程。所以兩者合作，更利于實(shí)現(xiàn)最優(yōu)解，同時(shí)也可體提高算法的實(shí)現(xiàn)效率。

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

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

4 商旅問(wèn)題的遺傳算法與蟻群算法實(shí)現(xiàn)思想

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

4.1 遺傳算法實(shí)現(xiàn)商旅問(wèn)題

遺傳算法先以城市數(shù)目為種群數(shù)，由于是尋找最短路徑，當(dāng)然是以越小越實(shí)現(xiàn)最優(yōu)解。所以適應(yīng)度參數(shù)可以設(shè)置為任意一個(gè)小于實(shí)際路徑長(zhǎng)度的數(shù)值，這當(dāng)然就實(shí)現(xiàn)了越小越接近于適應(yīng)數(shù)值的目標(biāo)。然后通過(guò)設(shè)置父母初代的不同位置，實(shí)現(xiàn)交叉后的遺傳，當(dāng)然為了判斷基因優(yōu)劣，也可以選取父母中位置相同的位置作為基因，進(jìn)行適應(yīng)判斷，達(dá)到遺傳次數(shù)，找出近似最優(yōu)解。但是為了符合題意，在交叉變異過(guò)程中，走過(guò)的節(jié)點(diǎn)不在選擇范圍之內(nèi)。

4.2 蟻群算法實(shí)現(xiàn)商旅問(wèn)題

蟻群算法利用隨機(jī)算法實(shí)現(xiàn)節(jié)點(diǎn)選擇，然后通過(guò)概率進(jìn)行下一節(jié)點(diǎn)的判斷。第一步驟中，與初始節(jié)點(diǎn)連接的若干節(jié)點(diǎn)的概率應(yīng)該是相同的，但是通過(guò)走過(guò)的螞蟻可以改變概率大小，當(dāng)然是路徑越短，概率越高。但是從這種實(shí)現(xiàn)算法來(lái)看，蟻群算法的全局收斂性較差，可能會(huì)出現(xiàn)路徑錯(cuò)誤或者完成迭代次數(shù)，仍然未實(shí)現(xiàn)路徑判斷的過(guò)程。一旦發(fā)生這種情況，就要重新選擇初始節(jié)點(diǎn)進(jìn)行判斷。當(dāng)完成多路徑選擇后，計(jì)算不同螞蟻所走路徑，通過(guò)記憶的路徑長(zhǎng)短，求出總路徑和，判斷哪只為最短最優(yōu)解。

4.3 遺傳算法實(shí)現(xiàn)商旅問(wèn)題的具體舉例

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

其次，適應(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要求。再次，選擇操作。遺傳算法選擇操作有輪盤賭法、錦標(biāo)賽法等多種方法，本程序采用基于適應(yīng)度比例的選擇策略，即適應(yīng)度越好的個(gè)體被選擇的概率越大，同時(shí)在選擇中保存適應(yīng)度最高的個(gè)體。進(jìn)一步說(shuō)，交叉操作。遺傳算法中交叉操作有多種方法。本程序中對(duì)于個(gè)體，隨機(jī)選擇兩個(gè)個(gè)體，在對(duì)應(yīng)位置交換若干個(gè)基因片段，同時(shí)保證每個(gè)個(gè)體依然是1-n的隨機(jī)排列，防止進(jìn)入局部收斂。最后，本程序中對(duì)于變異操作，隨機(jī)選取個(gè)體，同時(shí)隨機(jī)選取個(gè)體的兩個(gè)基因進(jìn)行交換以實(shí)現(xiàn)變異操作。

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

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

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

[4]基于免疫算法的配電網(wǎng)重構(gòu)[J].蒙文川,邱家駒.中國(guó)電機(jī)工程學(xué)報(bào). 2006(17).

[5]一種自適應(yīng)雜交算子的浮點(diǎn)遺傳算法[J].都偉,韓正之.系統(tǒng)仿真學(xué)報(bào). 2006(06).

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

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

[8]一種求解TSP的高效遺傳算法[J].王超學(xué),崔杜武,王竹榮,費(fèi)蓉.西安理工大學(xué)學(xué)報(bào). 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