資源描述：
《遺傳算法及其在油料保障路徑優(yōu)化中的應(yīng)用研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、遺傳算法及其在油料保障路徑優(yōu)化中的應(yīng)用研究剛1，張仁平2曹(1．解放軍76167部隊(duì)保管隊(duì)，廣東韶關(guān)512133;解放軍后勤工程學(xué)院軍事油料應(yīng)用與管理工程系，重慶401311)2．【摘要】路徑探索算法是古老而常新的問題。在介紹遺傳算法的基礎(chǔ)上，通過一個(gè)簡(jiǎn)單例子詳細(xì)分析用遺傳算法解決油料保障路徑問題。最后對(duì)算法結(jié)果進(jìn)行總結(jié)和分析?！娟P(guān)鍵詞】油料保障;路徑優(yōu)化;遺傳算法【文章編號(hào)】1008-8032(2012)06-0046-03【中圖分類號(hào)】E919【文獻(xiàn)標(biāo)識(shí)碼】A探索和優(yōu)化方法，適合于解決復(fù)雜系統(tǒng)優(yōu)化問題。遺傳算法作為一種實(shí)用、有效、魯棒性強(qiáng)、適應(yīng)性好
2、的優(yōu)化算法，近年來發(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)度，把問題的解變成染色體。一個(gè)染色體就代表問題的一個(gè)解。2)群體(Population):每代染色體的集合稱為群體，群體中染色體的數(shù)量稱為群體的大小。使用遺傳算法時(shí)，根據(jù)問題設(shè)置群體的大小，一般可設(shè)置為
3、10或20。3)適應(yīng)度(Fitness):各個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)程度叫做適應(yīng)度。為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)，也是問題的目標(biāo)函數(shù)。0引言在部隊(duì)行軍、交通運(yùn)輸、市政規(guī)劃、最優(yōu)選址等諸多方面，往往會(huì)遇到網(wǎng)絡(luò)最優(yōu)化問題，即路徑優(yōu)化類問題，其核心是求最短路徑，包括含權(quán)路(指道路質(zhì)量、類別、安全等所含不同的權(quán)重系數(shù)，下同)的最短路徑。油料保障路徑優(yōu)化與其它路徑優(yōu)化問題存在不同之處:一是不僅僅要找一條最短路，很多時(shí)候需要同時(shí)找出最短路或次短路，為指揮員決策作參考;二是有時(shí)不僅要知道兩個(gè)定點(diǎn)的最短路，而且要知道
4、某個(gè)定點(diǎn)到其它定點(diǎn)的最短路徑;三是路徑優(yōu)化中可能尋找排除某一條或幾條道路(可能被炸毀、沖毀)之后的最短路，這就需要在最短路中增加一些附加條件。因此，許多路徑探索的傳統(tǒng)經(jīng)典優(yōu)化算法，典型的有Dijkstra算法、Bellman-Ford-Moore算法、A*(也可讀作A星)算法等等［1］，對(duì)于油料保障路徑優(yōu)化問題則顯得有些力不從心。遺傳算法是解決搜索問題的一種通用算法，其共同特征是:1)首先生成一組候選解;2)依據(jù)某些適應(yīng)性條件計(jì)算候選解的適應(yīng)度;3)根據(jù)適應(yīng)度決定保留或放棄候選解;4)對(duì)保留的候選解進(jìn)行遺傳操作，生成新的候選解。遺傳算法上述特征以一種特
5、殊的方式組合在一起:基于染色體群的并行搜索。這就使得遺傳算法區(qū)別于其他搜索算法，像油料保障路徑優(yōu)化類的路徑探索，遺傳算法就是一個(gè)很好的選擇。1.2遺傳算法基本原理遺傳算法類似于自然進(jìn)化，通過尋找好的染色體來求解問題。與自然界相似，遺傳算法對(duì)求解問題的本身一無所知，它所需要的僅是對(duì)算法所產(chǎn)生的染色體進(jìn)行評(píng)價(jià)，使適應(yīng)度高的染色體有更多繁殖機(jī)會(huì)。在遺傳算法中，通過隨機(jī)方式產(chǎn)生若干個(gè)染色體，即假設(shè)解，形成初始群體;通過適應(yīng)度函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，淘汰低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體進(jìn)行選擇、交換和突變等遺傳操作，經(jīng)過遺傳操作后的個(gè)體集合形成下一代新的種群，
6、依次類推。11.1遺傳算法的基本概念遺傳算法基本概念遺傳算法(GeneticAlgorithm，簡(jiǎn)稱GA)是模仿達(dá)爾文生物進(jìn)化論和孟德爾遺傳學(xué)機(jī)理的隨機(jī)全局收稿日期:2012-09-14作者簡(jiǎn)介:曹剛(1979－)，工程師，主要從事軍用油料的管理及研究。47第6期曹剛等:遺傳算法及其在油料保障路徑優(yōu)化中的應(yīng)用研究心就是首先生成一組染色體(候選最優(yōu)路徑)，根據(jù)指揮員意圖確定目標(biāo)函數(shù)，計(jì)算染色體的適應(yīng)度，再根據(jù)適應(yīng)度決定保留或放棄染色體，并對(duì)保留的候選解進(jìn)行遺傳操作，生成新的候選解，依次循環(huán)，找到一個(gè)或一組最優(yōu)解。為了便于算法的理解和實(shí)現(xiàn)，下面舉個(gè)例子加以
7、說明。1.3遺傳算法基本步驟最簡(jiǎn)單的遺傳算法操作主要有三種:選擇(se-lection)，交換(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ā)生在染色體的
8、任意位置基因上。通常發(fā)生突變的概率很小。從表現(xiàn)型到基因型的映射稱為編碼。遺傳算法在進(jìn)行搜索之前
