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

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