遺傳算法及其在油料保障路徑優化中的應用研究

曹 剛，張仁平

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

0 引言

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

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

1 遺傳算法的基本概念

1.1 遺傳算法基本概念

遺傳算法(Genetic Algorithm，簡稱GA)是模仿達爾文生物進化論和孟德爾遺傳學機理的隨機全局探索和優化方法，適合于解決復雜系統優化問題。遺傳算法作為一種實用、有效、魯棒性強、適應性好的優化算法，近年來發展極為迅速，已在函數優化、組合優化、生產調度、自動控制、機器人學習等方面得到廣泛應用［2］。

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

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

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

3)適應度(Fitness):各個個體對環境的適應程度叫做適應度。為了體現染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數，叫適應度函數，也是問題的目標函數。

1.2 遺傳算法基本原理

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

1.3 遺傳算法基本步驟

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

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

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

3)突變操作:隨機改變染色體中某一位置上的遺傳因子的值。例如，二進制串011在第二位上發生突變，變成001。突變可能發生在染色體的任意位置基因上。通常發生突變的概率很小。

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

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

2)將群體中每個染色體串代入適應度函數，計算適應度。

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

4)進行下列步驟產生下一代群體

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

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

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

5)轉向步驟2

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

2 油料保障路徑優化的實現

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

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

圖1 油料保障實體所在區域路網示意圖

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

2.1 染色體編碼

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

2.2 適應函數

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

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

2.3 產生初始群體

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

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

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

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

將群體中每個染色體串代入適應度函數，計算適應度。以C1為例，011110代表候選優化路徑為{U0、U2、U3、U4、U5、U7}，由于 U4不能直接聯絡到U5，其適應度為∞，即 f(C1)=∞，以 C2為例，001001 代表候選優化路徑為{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。從以上數據可看出，C4最健壯，C1、C3、C4、C5、C9最虛弱。

2.5 復制選擇

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

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

2)計算群體的適應度的總和Sn:

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

累計pi得累計概率gi:

4)產生［0，1］均勻分布的隨機數r;

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

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

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

對應每個染色體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

對應每個染色體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

假設10次生成的［0，1］間的隨機數如下:

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

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

6)交換與變異操作

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

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

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

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

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

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

3 算法結果分析

由于群體數量少，路網節點簡單，運行速度快，算法采用第一種終止方式，算法執行1000代，最優個體為101010，不及第89代最優個體100100和第263代的最優個體100101、100100。

通過算法實現，適應度比較高的個體有:100100、100101、010010、101010。對應路徑分別為

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

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

010010:{U0、U2、U5、U7}

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

交換概率、變異概率、群體數量都是比較重要參數，需要根據具體問題進行適當調整。

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

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

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

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