第11章多機器人協(xié)同調度-遺傳算法智慧物流系統(tǒng)：從設計到實現(xiàn)教學內容CONTENTS1遺傳算法2遺傳算法起源3遺傳算法原理4遺傳算法評價3

章節(jié)目標理解遺傳算法的基本原理與起源；掌握遺傳算法的核心進程與實現(xiàn)方法；了解與評估遺傳算法的優(yōu)點、缺點及應用場景。4遺傳算法：遺傳算法(GeneticAlgorithm,GA)于1975年由美國密歇根大學的Holland教授提出，是建立在達爾文的生物進化論和孟德爾的遺傳學說基礎上的一種隨機搜索算法。它是模擬達爾文生物進化論的自然選擇和遺傳學機理生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。1遺傳算法遺傳算法具有全局搜索能力強、魯棒性強、靈活性和可擴展性強、并行計算能力強等優(yōu)點，但求解過程中伴隨著大量無為的冗余迭代、效率降低、易出現(xiàn)過早收斂與局部最優(yōu)解等現(xiàn)象。5算法起源：遺傳算法的思想源于“自然選擇”和“優(yōu)勝劣汰”的進化規(guī)律，它通過計算的方法類比并模擬了生物學中的遺傳進化過程，主要包括三個核心進程，如下表所示：2遺傳算法起源生物解釋計算機解釋選擇物競天擇，適者生存。生物種群中環(huán)境適應度高的個體得以生存，適應度低的個體容易死亡。計算機種群中每個個體都擁有適應度，根據(jù)適應度的大小決定個體是否被遺傳到下一代種群中。該個體遺傳到下一代的概率與其適應度成正比。交配兩個個體交配時，兩個匹配的染色體可能進行基因交換。設置一個交叉概率，從種群中隨機選擇兩個基因個體，這兩個基因個體按照交叉概率進行基因交換，基因交換的位置隨機選取。變異種群中任意個體的任意基因片段都有可能發(fā)生基因變異。設置一個變異概率，從種群中隨機選擇一個個體，該個體按照變異概率進行基因變異，變異的基因位置是隨機的。61.基因與個體在生物學中，用“AA”、“Aa”、“aa”來表示基因的性狀。在標準的遺傳算法中，使用二進制的符號集{0,1}和十進制來表示等位基因，A用二進制符號的0來表示，a用二進制符號的1來表示。2遺傳算法起源一對等位基因二進制符號十進制AA000Aa/aA011102aa113遺傳算法中的基因表示71.基因與個體在解決實際問題時，根據(jù)實際問題的情況給等位基因賦予具體的性狀，比如機器人的運動方向、目的地等。對于復雜的問題可以采用多位的二進制符號來表示一對等位基因，即如果用n位二進制符號表示一對等位基因，則有2n種表示性狀。這與“自然界中大多數(shù)性狀是由多對等位基因決定”的實際情況也是相吻合的。2遺傳算法起源81.基因與個體在標準遺傳算法中，使用固定長度的二進制符號串來表示個體，即根據(jù)實際情況設置一個固定的基因長度，比如固定長度為6，則某一個體的基因序列可能為：011011011000或011001111000……一個固定長度的基因個體，理論上應當有4**6=4096種不同的排列方式。當固定長度增加1，長度從6變?yōu)?時，所有可能排列的總數(shù)就會迅速擴增到4**7=16384種，在這些排列組合中只有一種或幾種基因序列是最適應自然環(huán)境的，即為最優(yōu)解。當基因長度越長，基因庫就越龐大，計算量就會呈指數(shù)增長。2遺傳算法起源92.種群在生物學中，在一定時間內占據(jù)一定空間的同種生物的所有個體，被稱為種群。在計算機中，用固定基因長度的二進制符號表示個體，因此，用固定數(shù)量的具有固定基因長度的二進制符號串來表示種群。2遺傳算法起源在自然界中，初代種群往往只有具體的數(shù)量，因此是無法包括所有的性狀，它們只具備部分的性狀。在生存過程中，種群中可能會有一部分適應度低的個體被自然界淘汰。因此，每一代種群都會根據(jù)適應度來判斷是否削減種群中的個體；通過雜交的概率決定是否發(fā)生雜交去產生新的性狀個體；通過變異的概率來決定是否發(fā)生變異去產生新的性狀個體。102遺傳算法起源種群迭代的過程113.適應度自然界中的“物競天擇，適者生存”在計算機中同樣適用，在計算機中通過給定一個適應度的算子用來計算所有個體是否適應“自然”。根據(jù)實際問題，計算適應度S的表達式并不相同。例如在路徑規(guī)劃問題中，可以使用路徑長度的倒數(shù)作為適應度S，路徑越短對應適應度S就越大，即適應度S越高；或者相同步數(shù)下走得越遠的個體，其適應度被認為更高。確定了適應度S表達式后還需要估計其取值范圍，并制定合適的淘汰閾值，即適應度低于閾值的個體將被淘汰，適應度高于閾值的個體將被留下。2遺傳算法起源12算法原理：在遺傳算法中，包含五個“隨機規(guī)則”：①初代種群包含的個體是隨機的；②進行交配的個體是隨機的；③交配時若發(fā)生基因交叉，交叉的基因片段是隨機的；④發(fā)生變異的個體是隨機的；⑤發(fā)生變異的基因片段是隨機的。3遺傳算法原理種群在每一次迭代過程中，通過選擇、交配和變異得到的新種群個體數(shù)量和初代種群的個體數(shù)量相同。選擇和交配體現(xiàn)了遺傳算法的搜索能力，變異使遺傳算法能搜索到問題的所有解。13在實際應用中，會設置一個最大迭代數(shù)讓該種群迭代有限次數(shù)，即判斷若干代以后種群中的全部個體或大部分個體的基因序列是否都相同。情況一：相同，則該基因序列就是本問題的最優(yōu)解；情況二：不相同，需要反復調節(jié)各項參數(shù)使得最終結果收斂。遺傳算法流程圖如圖所示。3遺傳算法原理遺傳算法流程圖14遺傳算法通常需要調節(jié)以下參數(shù)：①種群數(shù)目M：每代種群的數(shù)目都為M，一般設為基因序列長度的兩倍；②雜交概率P_c：根據(jù)經驗使用二進制編碼的基因序列雜交率為0.7；③變異概率P_m：根據(jù)經驗一般設為0.001；④最大迭代次數(shù)：根據(jù)經驗一般設為20次。目前沒有調節(jié)這些參數(shù)的有效規(guī)則，只能根據(jù)具體的應用情景和實際效果進行調整。3遺傳算法原理遺傳算法流程圖15算法評價：遺傳算法是一種模擬自然進化過程來尋找最優(yōu)解的人工智能技術，是一種使用高效、魯棒性強的優(yōu)化技術。4遺傳算法評價優(yōu)點：遺傳算法具有良好的全局搜索能力，可以快速的把空間中的全體解搜索出來，而不會陷入局部最優(yōu)解的快速下降陷阱；并且利用它的內在并行性，可以方便的進行分布式計算，加速求解的速度。缺點：遺傳算法的局部搜索能力較差，導致單純的遺傳算法比較費時，在進化后期搜索效率較低；在實際應用中，遺傳算法容易產生早熟收斂的問題。16算法評價：在多機器人物流系統(tǒng)中，遺傳算法在分配任務時，通過計算適應度來判斷基因是否為最優(yōu)。在物流機器人、貨架、取貨點的分配過程中，將計算路徑規(guī)劃算法的執(zhí)行時間（從所有機器人執(zhí)行開始直到最后一個機器人執(zhí)行任務完成的持續(xù)時間）作為分配算法的適應度。時間越短對應路徑就越短，路徑越短執(zhí)行越快完成，這樣分配的組合比其他路徑規(guī)劃的組合更優(yōu)。下圖表示基于遺傳算法進行任務分配，得到每一代中所有基因組合的適應度。4遺傳算法評價17從上圖中分析得出：每一代基因都有12個基因個體，因此在每一代列表都有12個基因適應度；基因