遺傳算法及其在油料保障路徑優(yōu)化中的應(yīng)用研究

曹 剛，張仁平

(1.解放軍76167部隊 保管隊，廣東 韶關(guān)512133;2.解放軍后勤工程學(xué)院軍事油料應(yīng)用與管理工程系，重慶401311)

0 引言

在部隊行軍、交通運輸、市政規(guī)劃、最優(yōu)選址等諸多方面，往往會遇到網(wǎng)絡(luò)最優(yōu)化問題，即路徑優(yōu)化類問題，其核心是求最短路徑，包括含權(quán)路(指道路質(zhì)量、類別、安全等所含不同的權(quán)重系數(shù)，下同)的最短路徑。油料保障路徑優(yōu)化與其它路徑優(yōu)化問題存在不同之處:一是不僅僅要找一條最短路，很多時候需要同時找出最短路或次短路，為指揮員決策作參考;二是有時不僅要知道兩個定點的最短路，而且要知道某個定點到其它定點的最短路徑;三是路徑優(yōu)化中可能尋找排除某一條或幾條道路(可能被炸毀、沖毀)之后的最短路，這就需要在最短路中增加一些附加條件。因此，許多路徑探索的傳統(tǒng)經(jīng)典優(yōu)化算法，典型的有Dijkstra算法、Bellman-Ford-Moore算法、A*(也可讀作 A 星)算法等等［1］，對于油料保障路徑優(yōu)化問題則顯得有些力不從心。

遺傳算法是解決搜索問題的一種通用算法，其共同特征是:1)首先生成一組候選解;2)依據(jù)某些適應(yīng)性條件計算候選解的適應(yīng)度;3)根據(jù)適應(yīng)度決定保留或放棄候選解;4)對保留的候選解進(jìn)行遺傳操作，生成新的候選解。遺傳算法上述特征以一種特殊的方式組合在一起:基于染色體群的并行搜索。這就使得遺傳算法區(qū)別于其他搜索算法，像油料保障路徑優(yōu)化類的路徑探索，遺傳算法就是一個很好的選擇。

1 遺傳算法的基本概念

1.1 遺傳算法基本概念

遺傳算法(Genetic Algorithm，簡稱GA)是模仿達(dá)爾文生物進(jìn)化論和孟德爾遺傳學(xué)機(jī)理的隨機(jī)全局探索和優(yōu)化方法，適合于解決復(fù)雜系統(tǒng)優(yōu)化問題。遺傳算法作為一種實用、有效、魯棒性強(qiáng)、適應(yīng)性好的優(yōu)化算法，近年來發(fā)展極為迅速，已在函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度、自動控制、機(jī)器人學(xué)習(xí)等方面得到廣泛應(yīng)用［2］。

下面介紹遺傳算法常用的幾個基本概念。

1)染色體(Chromosome):染色體由基因組成的遺傳信息的載體，基因是指用一位二進(jìn)制代碼(0或1)表示的一個遺傳因子，基因的數(shù)量就是染色體的長度。使用遺傳算法時，需要首先明確染色體編碼規(guī)則，明確基因的長度，把問題的解變成染色體。一個染色體就代表問題的一個解。

2)群體(Population):每代染色體的集合稱為群體，群體中染色體的數(shù)量稱為群體的大小。使用遺傳算法時，根據(jù)問題設(shè)置群體的大小，一般可設(shè)置為10或20。

3)適應(yīng)度(Fitness):各個個體對環(huán)境的適應(yīng)程度叫做適應(yīng)度。為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)，也是問題的目標(biāo)函數(shù)。

1.2 遺傳算法基本原理

遺傳算法類似于自然進(jìn)化，通過尋找好的染色體來求解問題。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產(chǎn)生的染色體進(jìn)行評價，使適應(yīng)度高的染色體有更多繁殖機(jī)會。在遺傳算法中，通過隨機(jī)方式產(chǎn)生若干個染色體，即假設(shè)解，形成初始群體;通過適應(yīng)度函數(shù)對每個個體進(jìn)行評價，淘汰低適應(yīng)度的個體，選擇高適應(yīng)度的個體進(jìn)行選擇、交換和突變等遺傳操作，經(jīng)過遺傳操作后的個體集合形成下一代新的種群，依次類推。

1.3 遺傳算法基本步驟

最簡單的遺傳算法操作主要有三種:選擇(selection)，交換(crossover)和突變(mutatiun)。

1)選擇操作:從群體中選擇某些染色體用于繁殖后代(生成新的候選解)，染色體的適應(yīng)度越高，它被選中的概率就越大。

2)交換操作:隨機(jī)地選定一個位置，將兩個染色體在該位置上交義互換，得到兩個后代。例如，兩個染色體分別為100和111，隨機(jī)選定的位置是第二位，進(jìn)行交換的結(jié)果是110和101。

3)突變操作:隨機(jī)改變?nèi)旧w中某一位置上的遺傳因子的值。例如，二進(jìn)制串011在第二位上發(fā)生突變，變成001。突變可能發(fā)生在染色體的任意位置基因上。通常發(fā)生突變的概率很小。

從表現(xiàn)型到基因型的映射稱為編碼。遺傳算法在進(jìn)行搜索之前，先將解空間的解表示成遺傳空間的染色體，這些基因的不同組合就構(gòu)成了不同的解。假設(shè)一個問題，設(shè)定染色體的長度為m，遺傳算法的基本步驟可以簡單地描述為:

1)隨機(jī)生成n(最好是偶數(shù))個長度為m的染色體，形成初始群體。

2)將群體中每個染色體串代入適應(yīng)度函數(shù)，計算適應(yīng)度。

3)判斷是否滿足算法終止條件，若是，則適應(yīng)度最大的染色體對應(yīng)的候選解就是最優(yōu)解或滿意解;若否，則轉(zhuǎn)步驟4。

4)進(jìn)行下列步驟產(chǎn)生下一代群體

①在當(dāng)前的染色體群中隨機(jī)選取n個染色體作為父體，選取染色體的概率等于該染色體的適應(yīng)度除以群體的適應(yīng)度總和。在選取父體的過程中，一個染色體可以被多次選中。

②對于選中的父體，按照交換概率算出需要交換的染色體數(shù)量(如果需要交換的染色體數(shù)量是奇數(shù)，則要增選一個交換個體或刪去一個個體，使交叉對象成對出現(xiàn))。發(fā)生交換的位置是隨機(jī)的，每個位置的概率是相同的。在遺傳算法中有時會用到多點的交換，即在多個隨機(jī)的點上發(fā)生交換。

3)對于選中的父體，按照突變概率算出需要突變的染色體數(shù)量，分別在每個染色體的隨機(jī)位置進(jìn)行，每個位置的概率是相同的。

5)轉(zhuǎn)向步驟2

每次迭代這一過程稱為一個世代，一個遺傳算法的應(yīng)用通常需要迭代50～500個世代，可以指定迭代的世代數(shù)作為算法的終止條件。

2 油料保障路徑優(yōu)化的實現(xiàn)

用遺傳算法解決油料保障路徑優(yōu)化問題，其核心就是首先生成一組染色體(候選最優(yōu)路徑)，根據(jù)指揮員意圖確定目標(biāo)函數(shù)，計算染色體的適應(yīng)度，再根據(jù)適應(yīng)度決定保留或放棄染色體，并對保留的候選解進(jìn)行遺傳操作，生成新的候選解，依次循環(huán)，找到一個或一組最優(yōu)解。

為了便于算法的理解和實現(xiàn)，下面舉個例子加以說明。

圖1 油料保障實體所在區(qū)域路網(wǎng)示意圖

若交換概率為0.2，變異概率為0.01，用遺傳算法求圖1的從U0到U7的最優(yōu)路徑。

2.1 染色體編碼

按照U0到U7各個頂點(除U0和U7)依次排序，作為染色體的基因排序，一個頂點對應(yīng)一個基因，當(dāng)基因為1時，表示該頂點進(jìn)入最優(yōu)路徑;為0時則退出最優(yōu)路徑。染色體中不為0的基因排序就是各頂點在最優(yōu)路徑中出現(xiàn)的順序，染色體的長度等于圖中的頂點數(shù)。

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

對于圖1，屬于圖論中典型的n個頂點m條邊的路網(wǎng)圖G，假設(shè)相鄰兩頂點 Ui、Uj邊長為d(Ui、Uj)，假設(shè)從U0到U7之間連通路徑的長度定義為算法適應(yīng)函數(shù)f，則

i，j(i≠j)為染色體中不為0的基因在染色體中對應(yīng)的位置，路徑優(yōu)化就是使得f最小的滿意路徑。

2.3 產(chǎn)生初始群體

初始群體是遺傳算法搜索最優(yōu)的出發(fā)點。群體規(guī)模越大，搜索的范圍越廣，但是每代的遺傳操作越長，反之亦然。通常，M取50～100。初始群體中的每個個體是按隨機(jī)方法產(chǎn)生的。對于上例，為了便于說明，假設(shè)只產(chǎn)生10個初始個體，個體為6位的0/1隨機(jī)數(shù)，組成一個初始個體。

C1=011110，C2=001001，C3=000110，C4=111001，C5=101000

C6=011001，C7=101101，C8=001100，C9=111101，C10=101010

2.4 適應(yīng)度計算(個體評價)

將群體中每個染色體串代入適應(yīng)度函數(shù)，計算適應(yīng)度。以C1為例，011110代表候選優(yōu)化路徑為{U0、U2、U3、U4、U5、U7}，由于 U4不能直接聯(lián)絡(luò)到U5，其適應(yīng)度為∞，即 f(C1)=∞，以 C2為例，001001 代表候選優(yōu)化路徑為{U0、U3、U6、U7}，f(C2)=15，依次計算，f(C3)=∞，f(C4)=∞，f(C5)=∞，f(C6)=15，f(C7)=22，f(C8)=22，f(C9)= ∞，f(C10)=13。從以上數(shù)據(jù)可看出，C4最健壯，C1、C3、C4、C5、C9最虛弱。

2.5 復(fù)制選擇

顯然，個體適應(yīng)度愈高，被選中的概率愈大。但是，適應(yīng)度小的個體也有可能被選中，以便增加下一代群體的多樣性。近年來，在遺傳算法中常常采用擇優(yōu)選擇法。這種方法沒有明顯的復(fù)制操作，而是根據(jù)個體的相對適應(yīng)度，反復(fù)地從群體中選擇M個個體組成下一代群體。當(dāng)然，個體的適應(yīng)度愈高，它被重復(fù)選中的可能性愈大，而重復(fù)選中的就相當(dāng)于復(fù)制。相反適應(yīng)度小的個體往往未能選中，它就被淘汰，其操作過程為:

1)計算各染色體Ci的適應(yīng)度f(Ci)，

2)計算群體的適應(yīng)度的總和Sn:

3)用Sn減去各個體適應(yīng)度的差除以Sn，得相對適應(yīng)度，進(jìn)行歸一化處理就成為該個體被選中的概率

累計pi得累計概率gi:

4)產(chǎn)生［0，1］均勻分布的隨機(jī)數(shù)r;

5)將r與gi相比較，若gi-1＜r＜gi，則選個體 i進(jìn)入下一代新群體;

6)反復(fù)執(zhí)行(4)及(5)項，直至新群體的個體數(shù)目等于父代群體規(guī)模，本例中為10。

對于本例中，若取1000為∞，則第一代種群的適應(yīng)度總和Sn=1000+15+1000+1000+1000+15+22+22+1000+13=5087

對應(yīng)每個染色體Ci的選擇概率pi如下:

p1=0.089269，p2=0.110783，p3=0.089269，

p4=0.089269，p5=0.089269，p6=0.110783，

p7=0.110630，p8=0.110630，p9=0.089269，

p10=0.110829

對應(yīng)每個染色體Ci的累計概率gi如下:

g1=p1=0.089269，g2=p1+p2=0.200052，g3=0.289321，g4=0.378590，g5=0.467859，g6=0.578642，g7=0.689272，g8=0.799902，g9=0.889171，g10=1.000000

假設(shè)10次生成的［0，1］間的隨機(jī)數(shù)如下:

0.181431 ，0.322062，0.766503，0.881893，0.650871，0.582475，0.177618，0.343242，0.032685，0.197577

第一個隨機(jī)數(shù)大于g1，小于g2，這樣染色體C2被選中，依次類推，產(chǎn)生新的種群由下列染色體組成:C2、C4、C8、C9、C7、C7、C2、C4、C1、C2。

6)交換與變異操作

假設(shè)交換概率為0.2，可算出有兩個染色體需要交換操作，增加算法個體自學(xué)習(xí)過程，選出排在前面適應(yīng)度最差的是C4=111001、C9=111101進(jìn)行交換，假設(shè)取上面第一個隨機(jī)數(shù)，則在第二位進(jìn)行交換，由于基因都是“1”，則交換前后沒有發(fā)生改變。C'4=111001=C4、C'9=111101=C9。

假設(shè)變異概率0.01，可算出有一個基因需要變異。增加算法個體自學(xué)習(xí)過程，除去進(jìn)行交換的C4、C9后繼續(xù)選出排在前面適應(yīng)度最差的仍然是C4=111001，變異基因的位置也是隨機(jī)確定的，假設(shè)取上面第一個隨機(jī)數(shù)，則在第二位進(jìn)行突變，變成C″4=101001，可算出 f(C″4)=15，相對之前的∞ (取值1000)，適應(yīng)度提高不少。為了提高遺傳算法的收斂速度，改善算法效率，需要比較變異前后染色體的適應(yīng)度，若適應(yīng)度提高則保留，反之則去除或者重新變異一次。至此，完成第二代群體。

通過比較可以看出，第二代群體比第一代群體(即初始群體)的適應(yīng)度明顯提高。由于在交換和變異中增加個體學(xué)習(xí)，有效避免了交換與變異的風(fēng)險，提高算法的收斂速度，但是卻影響了算法的多樣性。繼續(xù)轉(zhuǎn)向第四步:適應(yīng)度計算(個體評價)，反復(fù)迭代直至滿足終止條件。

使遺傳算法終止的方法主要有二種:

1)規(guī)定最大迭代數(shù)N。一旦遺傳算法的迭代次數(shù)達(dá)到N，則停止操作，輸出結(jié)果。通常N取100～1000次。隨著計算機(jī)速度提高，此方法最常用。

2)記錄適應(yīng)度的變化趨勢。在算法初期，群體的平均適應(yīng)度較小，隨著復(fù)制、交叉、變異等操作，適應(yīng)度值增加。如果這種增加已趨緩和或停止，即終止遺傳算法。一般如果連續(xù)10次適應(yīng)度沒有增加，則停止。

3 算法結(jié)果分析

由于群體數(shù)量少，路網(wǎng)節(jié)點簡單，運行速度快，算法采用第一種終止方式，算法執(zhí)行1000代，最優(yōu)個體為101010，不及第89代最優(yōu)個體100100和第263代的最優(yōu)個體100101、100100。

通過算法實現(xiàn)，適應(yīng)度比較高的個體有:100100、100101、010010、101010。對應(yīng)路徑分別為

100100:{U0、U1、U4、U7};

100101:{U0、U1、U4、U6、U7}

010010:{U0、U2、U5、U7}

101010:{U0、U1、U3、U5、U7}

交換概率、變異概率、群體數(shù)量都是比較重要參數(shù)，需要根據(jù)具體問題進(jìn)行適當(dāng)調(diào)整。

最后需要進(jìn)行兩點說明:一是如果要考慮油料保障行進(jìn)速度、行進(jìn)安全性等問題，屬于多目標(biāo)優(yōu)化問題，解決的思路是先用多目標(biāo)優(yōu)化方法，如模糊層次分析法，進(jìn)行無量綱處理，轉(zhuǎn)化為最短路問題［3］。不屬于本文研究范圍，在此不再贅述。二是油料保障路徑優(yōu)化時，由于最優(yōu)路徑(含次優(yōu)路徑)大大少于路網(wǎng)數(shù)量，經(jīng)歷的節(jié)點遠(yuǎn)小于路網(wǎng)節(jié)點，用傳統(tǒng)遺傳算法進(jìn)行編碼、選擇、交叉操作，很可能將大量運算浪費在處理無效數(shù)據(jù)上，在運算過程中也會產(chǎn)生較多的無效解，因此需要在算法的編碼、交叉等操作方面加以改進(jìn)。

［1］熊偉，張仁平，劉奇韜，等.A*算法及其在地理信息系統(tǒng)中的應(yīng)用［J］.計算機(jī)系統(tǒng)應(yīng)用，2007，(4):14.

［2］雷英杰，張善文，李續(xù)武，等.MATLAB遺傳算法工具箱及應(yīng)用［M］.西安電子科技大學(xué)出版社，2005:8.

［3］張仁平，許紅，熊偉.不同含權(quán)方式物資輸送路徑優(yōu)化模型研究［J］.中國儲運，2009，(4):95.