曹 剛，張仁平

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

0 引言

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

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

1 遺傳算法的基本概念

1.1 遺傳算法基本概念

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

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

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

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

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

1.2 遺傳算法基本原理

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

1.3 遺傳算法基本步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 染色體編碼

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

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

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

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

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

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

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

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

2.4 適應(yīng)度計(jì)算(個(gè)體評(píng)價(jià))

將群體中每個(gè)染色體串代入適應(yīng)度函數(shù)，計(jì)算適應(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，依次計(jì)算，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ù)制選擇

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

1)計(jì)算各染色體Ci的適應(yīng)度f(wàn)(Ci)，

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

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

累計(jì)pi得累計(jì)概率gi:

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

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

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

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

對(duì)應(yīng)每個(gè)染色體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

對(duì)應(yīng)每個(gè)染色體Ci的累計(jì)概率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

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

6)交換與變異操作

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

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

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

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

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

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

3 算法結(jié)果分析

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

通過(guò)算法實(shí)現(xiàn)，適應(yīng)度比較高的個(gè)體有:100100、100101、010010、101010。對(duì)應(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ù)具體問(wèn)題進(jìn)行適當(dāng)調(diào)整。

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

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

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

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