遺傳算法GeneticAlgorithm專題知識(shí)講座

1、遺傳算法GeneticAlgorithm專題知識(shí)講座遺傳算法GeneticAlgorithm專題知識(shí)講座第1頁(yè)2022/9/4遺傳算法(GA)Darwin(1859): “物竟天擇，適者生存”John Holland (university of Michigan, 1975) Adaptation in Natural and Artificial System遺傳算法作為一個(gè)有效工具，已廣泛地應(yīng)用于最優(yōu)化問(wèn)題求解之中。遺傳算法是一個(gè)基于自然群體遺傳進(jìn)化機(jī)制自適應(yīng)全局優(yōu)化概率搜索算法。它摒棄了傳統(tǒng)搜索方式，模擬自然界生物進(jìn)化過(guò)程，采取人工方式對(duì)目標(biāo)空間進(jìn)行隨機(jī)化搜索。遺傳算法GeneticA

2、lgorithm專題知識(shí)講座第2頁(yè)2022/9/4 遺傳算法模擬自然選擇和自然遺傳過(guò)程中發(fā)生繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代候選解群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。遺傳算法搜索機(jī)制遺傳算法GeneticAlgorithm專題知識(shí)講座第3頁(yè)2022/9/4局部全局遺傳算法(GA)遺傳算法GeneticAlgorithm專題知識(shí)講座第4頁(yè)2022/9/4We have a dream!I am at the topHeight is .I am not at the to

3、p.My high is better!I will continue遺傳算法(GA)GA-第0代遺傳算法GeneticAlgorithm專題知識(shí)講座第5頁(yè)2022/9/4Dead oneNew one遺傳算法(GA)GA-第1代遺傳算法GeneticAlgorithm專題知識(shí)講座第6頁(yè)2022/9/4Not at the top, Come Up!遺傳算法(GA)GA-第?代遺傳算法GeneticAlgorithm專題知識(shí)講座第7頁(yè)2022/9/4I am the BEST !遺傳算法(GA)GA-第N代遺傳算法GeneticAlgorithm專題知識(shí)講座第8頁(yè)2022/9/4適者生存(Su

4、rvival of the Fittest)GA主要采取進(jìn)化規(guī)則是“適者生存”很好解保留，較差解淘汰遺傳算法(GA)遺傳算法GeneticAlgorithm專題知識(shí)講座第9頁(yè)2022/9/4生物進(jìn)化與遺傳算法對(duì)應(yīng)關(guān)系生物進(jìn)化遺傳算法適者生存適應(yīng)函數(shù)值最大解被保留概率最大個(gè)體問(wèn)題一個(gè)解染色體解編碼基因編碼元素群體被選定一組解種群依據(jù)適應(yīng)函數(shù)選擇一組解交叉以一定方式由雙親產(chǎn)生后代過(guò)程變異編碼一些分量發(fā)生改變過(guò)程環(huán)境適應(yīng)函數(shù)遺傳算法GeneticAlgorithm專題知識(shí)講座第10頁(yè)2022/9/4遺傳算法基礎(chǔ)操作選擇(selection): 依據(jù)各個(gè)個(gè)體適應(yīng)值，按照一定規(guī)則或方法，從第t代群體P(

5、t)中選擇出一些優(yōu)良個(gè)體遺傳到下一代群體P(t+1)中。 交叉(crossover): 將群體P(t)內(nèi)各個(gè)個(gè)體隨機(jī)搭配成對(duì)，對(duì)每一個(gè)個(gè)體，以某個(gè)概率Pc (稱為交叉概率，crossvoer rate)交換它們之間個(gè)別染色體。變異(mutation): 對(duì)群體P(t)中每一個(gè)個(gè)體，以某一概率Pm(稱為變異概率，mutation rate)改變某一個(gè)或一些基因座上基因值為其它等位基因。遺傳算法GeneticAlgorithm專題知識(shí)講座第11頁(yè)2022/9/4怎樣設(shè)計(jì)遺傳算法怎樣進(jìn)行編碼？怎樣產(chǎn)生初始種群？怎樣定義適應(yīng)函數(shù)？怎樣進(jìn)行遺傳操作(復(fù)制、交叉、變異)？怎樣產(chǎn)生下一代種群？怎樣定義停頓準(zhǔn)

6、則？遺傳算法GeneticAlgorithm專題知識(shí)講座第12頁(yè)2022/9/4編碼(Coding)表現(xiàn)型空間編碼(Coding)解碼(Decoding)基因型空間 = 0,1L0111010010100010011001001010010001遺傳算法GeneticAlgorithm專題知識(shí)講座第13頁(yè)2022/9/4選擇(Selection)選擇(復(fù)制)操作把當(dāng)前種群染色體按與適應(yīng)值成正百分比概率復(fù)制到新種群中 主要思想: 適應(yīng)值較高染色體體有較大選擇(復(fù)制)機(jī)會(huì)實(shí)現(xiàn)1：”輪盤賭”選擇(Roulette wheel selection)將種群中全部染色體適應(yīng)值相加求總和，染色體適應(yīng)值按其百

7、分比轉(zhuǎn)化為選擇概率Ps產(chǎn)生一個(gè)在0與總和之間隨機(jī)數(shù)m從種群中編號(hào)為1染色體開(kāi)始，將其適應(yīng)值與后續(xù)染色體適應(yīng)值相加，直到累加和等于或大于m遺傳算法GeneticAlgorithm專題知識(shí)講座第14頁(yè)2022/9/4選擇(Selection)設(shè)種群規(guī)模為Nxi是i為種群中第i個(gè)染色體AC1/6 = 17%3/6 = 50%B2/6 = 33%fitness(A) = 3fitness(B) = 1fitness(C) = 2染色體xi被選概率遺傳算法GeneticAlgorithm專題知識(shí)講座第15頁(yè)2022/9/4選擇(Selection)染色體適應(yīng)值和所占百分比輪盤賭選擇遺傳算法Genetic

8、Algorithm專題知識(shí)講座第16頁(yè)2022/9/4選擇(Selection)隨機(jī)數(shù)234913 386 27所選號(hào)碼 26 2 51 4所選染色體110000001111000011000111010010染色體編號(hào) 1 2 3 4 5 6染色體011101100000100100100110000011適應(yīng)度 8 152 5 128被選概率0.160.30.040.10. 240.16適應(yīng)度累計(jì) 8 23 25 30 42 50染色體被選概率被選染色體遺傳算法GeneticAlgorithm專題知識(shí)講座第17頁(yè)2022/9/4選擇(Selection)輪盤上片分配給群體染色體，使得每一個(gè)

9、片大小與對(duì)于染色體適應(yīng)值成百分比從群體中選擇一個(gè)染色體可視為旋轉(zhuǎn)一個(gè)輪盤，當(dāng)輪盤停頓時(shí)，指針?biāo)钙瑢?duì)于染色體就時(shí)要選染色體。模擬“輪盤賭” 算法：r=random(0, 1)，s=0，i=0；假如sr，則轉(zhuǎn)(4)；s=s+p(xi)，i=i+1, 轉(zhuǎn)(2)xi即為被選中染色體，輸出I結(jié)束遺傳算法GeneticAlgorithm專題知識(shí)講座第18頁(yè)2022/9/4選擇(Selection)其它選擇法：隨機(jī)遍歷抽樣(Stochastic universal sampling)局部選擇(Local selection)截?cái)噙x擇(Truncation selection)競(jìng)標(biāo)賽選擇(Tournamen

10、t selection)特點(diǎn)：選擇操作得到新群體稱為交配池，交配池是當(dāng)前代和下一代之間中間群體，其規(guī)模為初始群體規(guī)模。選擇操作作用效果是提升了群體平均適應(yīng)值(低適應(yīng)值個(gè)體趨于淘汰，高適應(yīng)值個(gè)體趨于選擇)，但這也損失了群體多樣性。選擇操作沒(méi)有產(chǎn)生新個(gè)體，群體中最好個(gè)體適應(yīng)值不會(huì)改變。遺傳算法GeneticAlgorithm專題知識(shí)講座第19頁(yè)2022/9/4交叉(crossover, Recombination)遺傳交叉(雜交、交配、有性重組)操作發(fā)生在兩個(gè)染色體之間，由兩個(gè)被稱之為雙親父代染色體，經(jīng)雜交以后，產(chǎn)生兩個(gè)含有雙親個(gè)別基因新染色體，從而檢測(cè)搜索空間中新點(diǎn)。選擇(復(fù)制)操作每次作用在一

11、個(gè)染色體上，而交叉操作每次作用在從交配池中隨機(jī)選取兩個(gè)個(gè)體上(交叉概率Pc)。交叉產(chǎn)生兩個(gè)子染色體，他們與其父代不一樣，且彼此不一樣, 每個(gè)子染色體都帶有雙親染色體遺傳基因。遺傳算法GeneticAlgorithm專題知識(shí)講座第20頁(yè)2022/9/4單點(diǎn)交叉(1-point crossover)在雙親父代染色體中隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)位置在交叉點(diǎn)位置分離雙親染色體交換交叉點(diǎn)位置右邊基因碼產(chǎn)生兩個(gè)子代染色體交叉概率Pc 普通范圍為(60%, 90%)，平均約80%11111111父代1111000000000000子代111100000000000011111111交叉點(diǎn)位置遺傳算法GeneticA

12、lgorithm專題知識(shí)講座第21頁(yè)2022/9/4交叉(crossover, Recombination)單點(diǎn)交叉操作能夠產(chǎn)生與父代染色體完全不一樣子代染色體；它不會(huì)改變父代染色體中相同基因。但當(dāng)雙親染色體相同時(shí)，交叉操作是不起作用。假如交叉概率Pc 50%,則交配池中50%染色體(二分之一染色體)將進(jìn)行交叉操作，余下50%染色體進(jìn)行選擇(復(fù)制)操作。GA利用選擇和交叉操作能夠產(chǎn)生含有更高平均適應(yīng)值和更加好染色體群體遺傳算法GeneticAlgorithm專題知識(shí)講座第22頁(yè)2022/9/4變異(Mutation)以變異概率Pm改變?nèi)旧w某一個(gè)基因,當(dāng)以二進(jìn)制編碼時(shí)，變異基因由0變成1，或者

13、由1變成0。變異概率Pm 普通介于1/種群規(guī)模與1/染色體長(zhǎng)度之間，平均約1-2%11010100父代01010101子代變異基因變異基因遺傳算法GeneticAlgorithm專題知識(shí)講座第23頁(yè)2022/9/4變異(Mutation)比起選擇和交叉操作，變異操作是GA中次要操作，但它在恢復(fù)群體中失去多樣性方面含有潛在作用。 在GA執(zhí)行開(kāi)始階段，染色體中一個(gè)特定位上值1可能與好性能緊密聯(lián)絡(luò)，即搜索空間中一些初始染色體在那個(gè)位上值1可能一致產(chǎn)生高適應(yīng)值。因?yàn)樵礁哌m應(yīng)值與染色體中那個(gè)位上值1相聯(lián)系，選擇操作就越會(huì)使群體遺傳多樣性損失。 等抵達(dá)一定程度時(shí)，值0會(huì)從整個(gè)群體中那個(gè)位上消失，然而全局最

14、優(yōu)解可能在染色體中那個(gè)位上為0。假如搜索范圍縮小到實(shí)際包含全局最優(yōu)解那個(gè)別搜索空間，在那個(gè)位上值0就可能恰好是抵達(dá)全局最優(yōu)解所需要。遺傳算法GeneticAlgorithm專題知識(shí)講座第24頁(yè)2022/9/4適應(yīng)函數(shù)(Fitness Function)GA在搜索中不依靠外部信息，僅以適應(yīng)函數(shù)為依據(jù)，利用群體中每個(gè)染色體(個(gè)體)適應(yīng)值來(lái)進(jìn)行搜索。以染色體適應(yīng)值大小來(lái)確定該染色體被遺傳到下一代群體中概率。染色體適應(yīng)值越大，該染色體被遺傳到下一代概率也越大；反之，染色體適應(yīng)值越小，該染色體被遺傳到下一代概率也越小。所以適應(yīng)函數(shù)選取至關(guān)主要，直接影響到GA收斂速度以及能否找到最優(yōu)解。群體中每個(gè)染色體都

15、需要計(jì)算適應(yīng)值適應(yīng)函數(shù)普通由目標(biāo)函數(shù)變換而成遺傳算法GeneticAlgorithm專題知識(shí)講座第25頁(yè)2022/9/4適應(yīng)函數(shù)(Fitness Function)適應(yīng)函數(shù)常見(jiàn)形式：直接將目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)函數(shù)若目標(biāo)函數(shù)為最大化問(wèn)題： Fitness(f(x) = f(x)若目標(biāo)函數(shù)為最小化問(wèn)題： Fitness(f(x) = -f(x)缺點(diǎn): (1)可能不滿足輪盤賭選擇中概率非負(fù)要求 (2)一些代求解函數(shù)值分布上相差很大，由此得到評(píng)價(jià)適應(yīng)值可能不利于表達(dá)群體評(píng)價(jià)性能，影響算法性能。遺傳算法GeneticAlgorithm專題知識(shí)講座第26頁(yè)2022/9/4適應(yīng)函數(shù)(Fitness Funct

16、ion)界限結(jié)構(gòu)法 目標(biāo)函數(shù)為最大化問(wèn)題其中Cmin為f(x)最小預(yù)計(jì)值 目標(biāo)函數(shù)為最小化問(wèn)題其中Cmaxn為f(x)最大預(yù)計(jì)值遺傳算法GeneticAlgorithm專題知識(shí)講座第27頁(yè)2022/9/4停頓準(zhǔn)則(Termination Criteria)種群中個(gè)體最大適應(yīng)值超出預(yù)設(shè)定值種群中個(gè)體平均適應(yīng)值超出預(yù)設(shè)定值種群中個(gè)體進(jìn)化代數(shù)超出預(yù)設(shè)定值遺傳算法GeneticAlgorithm專題知識(shí)講座第28頁(yè)2022/9/4基礎(chǔ)步驟(Step by Step)(1) 隨機(jī)產(chǎn)生初始種群;(2) 計(jì)算種群體中每個(gè)個(gè)體適應(yīng)度值,判斷是否滿足停頓條件，若不滿足，則轉(zhuǎn)第(3)步,不然轉(zhuǎn)第(6)步;(3)

17、按由個(gè)體適應(yīng)值所決定某個(gè)規(guī)則選擇將進(jìn)入下一代個(gè)體;(4) 按交叉概率Pc進(jìn)行交叉操作,生產(chǎn)新個(gè)體;(5) 按變異概率Pm進(jìn)行變異操作,生產(chǎn)新個(gè)體;(6) 輸出種群中適應(yīng)度值最優(yōu)染色體作為問(wèn)題滿意解或最優(yōu)解。遺傳算法GeneticAlgorithm專題知識(shí)講座第29頁(yè)2022/9/4流程圖(Flow Chart)遺傳算法GeneticAlgorithm專題知識(shí)講座第30頁(yè)2022/9/4基礎(chǔ)遺傳算法基礎(chǔ)遺傳算法（Simple Genetic Algorithms,簡(jiǎn)稱SGA）是一個(gè)統(tǒng)一最基礎(chǔ)遺傳算法，它只使用選擇、交叉、變異這三種基礎(chǔ)遺傳算子，其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，輕易了解，是其它一些遺傳算法

18、雛形和基礎(chǔ)，它不但給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也含有一定應(yīng)用價(jià)值。遺傳算法GeneticAlgorithm專題知識(shí)講座第31頁(yè)2022/9/4SGA偽碼描述Procedure Genetic Algorithm begint = 0 ;初始化 P(t) ;計(jì)算 P(t) 適應(yīng)值 ;while (不滿足停頓準(zhǔn)則) do begin t = t+1 ; 從P(t-1)中選擇 P(t) ; % selection 重組 P(t) ; % crossover and mutation 計(jì)算 P(t) 適應(yīng)值; end end遺傳算法GeneticAlgorithm專題知識(shí)講座第32頁(yè)2022

19、/9/4遺傳算法應(yīng)用函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能測(cè)試評(píng)價(jià)常見(jiàn)算例。對(duì)于一些非線性、多模型、多目標(biāo)函數(shù)優(yōu)化問(wèn)題，用其它優(yōu)化方法較難求解，而遺傳算法卻能夠方便地得到很好結(jié)果。遺傳算法提供了一個(gè)求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題通用框架，它不依賴于問(wèn)題詳細(xì)領(lǐng)域，對(duì)問(wèn)題種類有很強(qiáng)魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面列舉一些遺傳算法主要應(yīng)用領(lǐng)域。遺傳算法GeneticAlgorithm專題知識(shí)講座第33頁(yè)2022/9/4遺傳算法應(yīng)用組合優(yōu)化 遺傳算法是尋求組合優(yōu)化問(wèn)題滿意解最正確工具之一，實(shí)踐證實(shí)，遺傳算法對(duì)于組合優(yōu)化問(wèn)題中NP完全問(wèn)題非常有效。比如，遺傳算法已經(jīng)在求解旅行商問(wèn)題(

20、Traveling Salesman Problem , TSP)、背包問(wèn)題(Knapsack Problem)、裝箱問(wèn)題(Bin Packing Problem) 等方面得到成功應(yīng)用。生產(chǎn)調(diào)度問(wèn)題 生產(chǎn)調(diào)度問(wèn)題在很多情況下所建立起來(lái)數(shù)學(xué)模型難以準(zhǔn)確求解，即使經(jīng)過(guò)一些簡(jiǎn)化之后能夠進(jìn)行求解也會(huì)因簡(jiǎn)化得太多而使求解結(jié)果與實(shí)際相差太遠(yuǎn)?，F(xiàn)在遺傳算法已經(jīng)成為處理復(fù)雜調(diào)度問(wèn)題有效工具。遺傳算法GeneticAlgorithm專題知識(shí)講座第34頁(yè)2022/9/4遺傳算法應(yīng)用自動(dòng)控制 遺傳算法已經(jīng)在自動(dòng)控制領(lǐng)域中得到了很好應(yīng)用，比如基于遺傳算法含糊控制器優(yōu)化設(shè)計(jì)、基于遺傳算法參數(shù)辨識(shí)、基于遺傳算法含糊控制規(guī)

21、則學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)等。機(jī)器人智能控制 機(jī)器人是一類復(fù)雜難以準(zhǔn)確建模人工系統(tǒng)，而遺傳算法起源就來(lái)自于對(duì)人工自適應(yīng)系統(tǒng)研究，所以機(jī)器人智能控制自然成為遺傳算法一個(gè)主要應(yīng)用領(lǐng)域。 遺傳算法GeneticAlgorithm專題知識(shí)講座第35頁(yè)2022/9/4遺傳算法應(yīng)用圖象處理和模式識(shí)別 圖像處理和模式識(shí)別是計(jì)算機(jī)視覺(jué)中一個(gè)主要研究領(lǐng)域。在圖像處理過(guò)程中，如掃描、特征提取、圖像分割等不可防止地存在一些誤差，這些誤差會(huì)影響圖像處理效果。怎樣使這些誤差最小是使計(jì)算機(jī)視覺(jué)到達(dá)實(shí)用化主要要求，遺傳算法在這些圖像處理中優(yōu)化計(jì)算方面得到了很好應(yīng)用。人工生命 人工生命是用計(jì)算

22、機(jī)、機(jī)械等人工媒體模擬或結(jié)構(gòu)出含有自然生物系統(tǒng)特有行為人造系統(tǒng)。自組織能力和自學(xué)習(xí)能力是人工生命兩大主要特征。人工生命與遺傳算法有著親密關(guān)系，基于遺傳算法進(jìn)化模型是研究人工生命現(xiàn)象主要理論基礎(chǔ)。遺傳算法GeneticAlgorithm專題知識(shí)講座第36頁(yè)2022/9/4遺傳算法應(yīng)用遺傳程序設(shè)計(jì) Koza發(fā)展了遺傳程序設(shè)計(jì)概念，他使用了以LISP語(yǔ)言所表示編碼方法，基于對(duì)一個(gè)樹(shù)形結(jié)構(gòu)所進(jìn)行遺傳操作來(lái)自動(dòng)生成計(jì)算機(jī)程序。 機(jī)器學(xué)習(xí) 基于遺傳算法機(jī)器學(xué)習(xí)，在很多領(lǐng)域中都得到了應(yīng)用。比如基于遺傳算法機(jī)器學(xué)習(xí)可用來(lái)調(diào)整人工神經(jīng)網(wǎng)絡(luò)連接權(quán)，也能夠用于人工神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)。分類器系統(tǒng)在多機(jī)器人路徑規(guī)

23、劃系統(tǒng)中得到了成功應(yīng)用。遺傳算法GeneticAlgorithm專題知識(shí)講座第37頁(yè)2022/9/4SGA實(shí)例1：函數(shù)最值SGA參數(shù):編碼方式: 二進(jìn)制碼 e.g. 000000; 01101 13; 1111131種群規(guī)模: 4隨機(jī)初始群體“轉(zhuǎn)盤賭”選擇一點(diǎn)雜交, 二進(jìn)制變異 求函數(shù)f(x)=x2最大值，x為自然數(shù)且0 x31.手工方式完成演示SGA過(guò)程遺傳算法GeneticAlgorithm專題知識(shí)講座第38頁(yè)2022/9/4SGA實(shí)例1 max x2 : 選擇操作遺傳算法GeneticAlgorithm專題知識(shí)講座第39頁(yè)2022/9/4SGA實(shí)例1 max x2 : 交叉操作遺傳算法G

24、eneticAlgorithm專題知識(shí)講座第40頁(yè)2022/9/4SGA實(shí)例1 max x2 : 變異操作遺傳算法GeneticAlgorithm專題知識(shí)講座第41頁(yè)2022/9/4SGA實(shí)例2 : 連續(xù)函數(shù)最值求以下函數(shù)最大值：遺傳算法GeneticAlgorithm專題知識(shí)講座第42頁(yè)2022/9/4SGA實(shí)例2 : 編碼高精度 編碼 x,y 0,1L 必須可逆(一個(gè)表現(xiàn)型對(duì)應(yīng)一個(gè)基因型) 解碼算子：: 0,1L x,y 染色體長(zhǎng)度L決定可行解最大精度長(zhǎng)染色體(慢進(jìn)化) 實(shí)數(shù)問(wèn)題：變量z為實(shí)數(shù)，怎樣把a(bǔ)1,aL 0,1Lzx,y遺傳算法GeneticAlgorithm專題知識(shí)講座第43頁(yè)2022/9/4SGA實(shí)例2 : 編碼設(shè)定求解準(zhǔn)確到6位小數(shù)，因區(qū)間長(zhǎng)度位2-(-1)=3,則需將區(qū)間分為3X106等份。因 2097152221 3X1062224194304。故編碼二進(jìn)制串長(zhǎng)L=22。將一個(gè)二進(jìn)制串(b21b20b0)轉(zhuǎn)化為10進(jìn)制數(shù)：e.g. -1; 2 1.627 888 1.627888 = -1+3x(1110000000111111000101) 2 /(222-1) = -1+3