物流路徑規劃中使用的遺傳算法基本原理介紹

 服務介紹         |    2019-02-13 08:39

作者 | 蘇向陽

來源 |?運籌OR帷幄(ID:ORAI_China)

編委 | Mark

編者按

遺傳算法是計算數學中用于解決最優化的搜索算法,也是最為經典的智能算法之一。日本新干線N700系列車“氣動雙翼”的獨特空氣動力造型車鼻就是遺傳算法運算結果。通過閱讀這篇文章,你將了解遺傳算法的發展,優缺點以及實例求解過程。

01

簡介

遺傳算法(Genetic Algorithm, GA)來源于進化論和群體遺傳學,由美國的 Holland 教授于 1975 年在他的專著《自然界和人工系統的適應性》[1]中首先提出。遺傳算法作為一種非確定性的擬自然算法,為復雜系統的優化提供了一種新思路,對于諸多NP-Hard問題,遺傳算法都有不錯的表現。相對于傳統算法而言,遺傳算法有以下突出優點[2,3]:

1. 可適用于灰箱甚至黑箱問題;

2. 搜索從群體出發,具有潛在的并行性;

3. 搜索使用評價函數(適應度函數)啟發,過程簡單;

4.? 收斂性較強。

5. 具有可擴展性,容易與其他算法(粒子群、模擬退火等)結合。

遺傳算法的不足[4]:

1. 算法參數的選擇嚴重影響解的品質,而目前這些參數的選擇大部分是依靠經驗;

2. 遺傳算法的本質是隨機性搜索,不能保證所得解為全局最優解;

3.遺傳算法常見的編碼方法有二進制編碼、Gray編碼等。二進制編碼比較常見,但是二進制編碼容易產生漢明距離注1(Hamming Distance),可能會產生漢明懸崖注2(Hamming Cliff),Gray可以克服漢明懸崖的問題,但是往往由于實際問題的復雜度過大導致Gray編碼難以精確地描述問題。

4.在處理具有多個最優解的多峰問題時容易陷入局部最小值而停止搜索,造成早熟問題,無法達到全局最優。

注1:將一個字符串變換成另外一個字符串所需要替換的字符個數

注2:相鄰整數的二進制編碼之間存在漢明距離,交叉和遺傳難以跨越

02

算法的發展與重心

經過多年的發展,遺傳算法的研究熱點及發展方向可以由圖1進行展示[5]:

圖1 遺傳算法研究進展

Fig.1 Research progress of genetic algorithm

遺傳算法的搜索核心是遺傳算子的選擇,因此對于遺傳算法的研究,其中最常見的內容與方向是遺傳算子,遺傳算子的選擇多樣性也導致了算法表現的多樣性,常見的選擇方式如圖2所示:

圖2 遺傳算子的研究

Fig.2 Research of genetic operators

遺傳算法作為一種搜索算法,在諸多領域均有很好的表現[6],如函數優化、組合優化、生產調度、自動控制、機器學習、圖像處理、人工生命、遺傳編程、機器學習、數據挖掘等。

03

實例說明

為了更通俗地理解遺傳算法,下面將通過一些實例進行描述:

如果想在一座連綿的大山上找到其最高點,正常情況下你需要爬遍整座山才可以找到最高峰,但大多數的智能算法并不需要搜索整個山峰,不同的智能算法有不同的求解思路,舉幾個簡單例子:

1. 爬山算法(也稱為貪心算法)。假設有一只猴子從山的任意一點出發,當它爬到第一個高峰值點的時候便停止前進,并認為當前的山峰為整座山最高的點。這種情況下,運氣好可能會到達最高點,但是大概率情況下都不會是最高點。

2. 模擬退火算法。假設有一只神志不清的猴子,當它爬到山峰的時候,它有一定的概率繼續出發,也有概率停止前進。這種情況下它也有可能通過有限的時間找到整座山的最高點。

3. 遺傳算法。假設山上有一群猴子,猴子生存的食物只有在山峰處才有,而且山峰越高食物量越充裕。那么這些猴子為了生存,會不斷聚集在各個山頭上進行生存繁衍,而這些山峰可以理解為各種局部最優解(圖3中類似綠色和藍色的地方),如果種群規模足夠大,勢必會有一群猴子聚集在了整座山的最高點,也就是全局最優解(圖3中紅色位置)。

圖3 山體示意圖

Fig3 An outline of a mountain

基于以上三種算法的描述,我們可以對智能算法有一個簡單的了解:無論是哪種算法,都具有一定的隨機性,都不能保證最終選擇的山峰為整座山的最高點。但是在實際生活中,有諸多類似的問題,如果要考慮所有的情況可能會花費大量的時間,而恰巧我們并不需要一個最好的結果,我們只需要快速找到一個相對較好的結果便可以滿足要求的時候,智能算法的意義便得到了體現。

通俗了解后,雖然心里有大概思路,但還是云里霧里,這個時候我們可以考慮結合一些實際的例子來理解遺傳算法。

3.1經典問題(0-1背包問題)

問題描述:假設一個你有一個可以裝五公斤重的背包,現在地上有三塊重金屬A、B、C供你挑選,重量分別為1公斤、2公斤、3公斤,價值分別為1萬元、5萬元、10萬元。為了使得總體收益最大,應該選擇哪些金屬塊裝入背包。

問題分析:這種規模的問題我們可以直觀看出最優解為,選擇B、C帶走可以獲得最大收益。但當問題規模擴大十倍百倍的時候,我們就必須要借助計算機來進行求解了。

下面分別以三種算法為例進行說明:

1. 爬山算法。初始點不確定,背包放不下就放手。

假設第一步選擇A金屬,有如下情況:A→B→C(保留AB),A→C→B(保留AC);假設第一步選擇B金屬,有如下情況:B→A→C(保留BA),B→C→A(保留BC);假設第一步選擇C金屬,有如下情況:C→A→B(保留CA),C→B→A(保留CB);

可以看出,一共六種情況下,只有兩種情況(選擇BC)是可以得到最好結果的。側面說明了爬山算法具有很大的不確定性。

2. 模擬退火算法。?? 模擬退火與爬山最大的不同就是,每次拿到金屬塊的時候我們有一定的概率來決定是否將這塊金屬放入背包。我們假設這個概率為0.5(幾乎所有的智能算法都需要提前設定初始參數,而不同的初始參數對求解結果及求解效率的影響非常大。)每次拿到金屬塊都有0.5的概率保留或者選擇下一塊,當執行足夠多的次數后總能得到結果,結果雖然不一定是最好的,但整體隨機性更大,當問題規模較大的時候更有可能選出最優解。

3. 種群遺傳算法。初始隨機產生100個15位2進制變量(每3位分別對應A、B、C,0為不取,1為?。?。其中111為不可能的情況,設定這種基因片段不能繁衍下一代。

總生存力為五個基因片段之和,設定第一個位置出現1則生存力加0.01,第二個位置出現1則生存力加0.05,第三個位置出現1則生存力加0.1。則a為0;b1、b2和b3分別為0.1、0.05和0.01。c1、c2和c3分別為0.06、0.11和0.15。

生存力越高則生存率越高,依據輪盤賭選擇策略(生成隨機數,落在生存率區間選擇相應的個體),選擇遺傳下一代的個體。

生存率=個體生存力/總生存力。

選擇方法:隨機生成6個0-1的數,根據落在哪里選對應的個體。

表1表2分別表示了種群的選擇和遺傳。

由于問題簡單,規模較小,一次遺傳之后便可以得出很明顯的結果:種群中留有大量的011基因,即選擇BC的結果。但是當問題規模擴大十倍百倍的時候往往需要多次迭代才會有明顯的區分度。

另一方面,如果種群陷入了100與100的配對循環,那么這種情況下,永遠不可能得出最好的情況011,這個時候需要對基因的某一段進行變異,將100變異為101或110,種群就會出現更優的基因型。但是在實際問題中變異不一定是向好的方向發展,也有可能會出現更壞的結果。

總的來說,遺傳算法的選擇充滿了不確定性。但是當你設定無窮大的種群規模,足夠長的繁衍時間后,最終總會達到最優,但是時間也會成倍上升。

圖3 算法流程圖

Fig.3 Flowchart of algorithm

適應度的概念在遺傳算法中表示為個體趨近于最優解的程度,適應度越高遺傳到下一代的概率就越大。上述的例子中,我們自己選擇了適應度函數(生存力),在日常建模的時候,生存力函數可以是目標函數,也可以自己選擇。在演化計算中,某些特殊算子的選擇方式(例如這里的輪盤賭選擇)要注意兩點[7,8]:1.適應度必須非負;2.優化過程中目標函數的變化方向應與群體進化過程中適應度函數變化方向一致。

但在諸多大規模非凸非線性問題的求解時,上述觀點不再適用。

結語

雖然遺傳算法有著一定的弊端和不足,但是遺傳算法在諸多領域還是有著很不錯的表現并已經運用到實際生活中。為了不斷適應各種問題,近年來不斷有學者提出改進策略,以使遺傳算法有更廣泛的應用領域。

參考文獻:

[1] HOLLAND J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology,control,and artificial intelligence[M].2nd ed.Cambridge: MIT Press,1992.

[2]葛繼科,邱玉輝,吳春明,蒲國林.遺傳算法研究綜述[J].計算機應用研究,2008(10):2911-2916.

[3]雷德明.多維實數編碼遺傳算法[J].控制與決策,2000(02):239-241.

[4]臧文科. DNA遺傳算法的集成研究與應用[D].山東師范大學,2018.

[5]馬永杰,云文霞.遺傳算法研究進展[J].計算機應用研究,2012,29(04):1201-1206+1210.

[6]吉根林.遺傳算法研究綜述[J].計算機應用與軟件,2004(02):69-73.

[7] Nix A E , Vose M D . Modeling genetic algorithms with Markov chains[J]. Annals of Mathematics & Artificial Intelligence, 1992, 5(1):79-88.

[8]楊新武,楊麗軍.基于交叉模型的改進遺傳算法[J].控制與決策,2016,31(10):1837-1844.