遺傳算法概述遺傳算法原理遺傳算法的應(yīng)用

1、一、遺傳算法概述 二、遺傳算法原理三、遺傳算法的應(yīng)用,遺傳算法原理與應(yīng)用,一、遺傳算法概述,1、智能優(yōu)化算法 2、基本遺傳算法 3、遺傳算法的特點(diǎn),1、智能優(yōu)化算法,智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗(yàn)，理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。,常用的智能優(yōu)化算法,（1）遺傳算法 （Genetic Algori

2、thm， 簡稱GA） （2）模擬退火算法（Simulated Annealing， 簡稱SA） （3）禁忌搜索算法（Tabu Search， 簡稱TS） ……,智能優(yōu)化算法的特點(diǎn),它們的共同特點(diǎn)：都是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問題空間，因而具有全局優(yōu)化性能。,遺傳算法起源,遺傳算法是由美國的J. Holland教授于1975年在他的專著《自然界和人工

3、系統(tǒng)的適應(yīng)性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法 。,遺傳算法的搜索機(jī)制,遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。,2、基本遺傳算法,基本遺傳算法（Simple Genetic Algorithms

4、，簡稱SGA，又稱簡單遺傳算法或標(biāo)準(zhǔn)遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。,生物群體的生存過程普遍遵循達(dá)爾文的物競天擇、適者生存的進(jìn)化準(zhǔn)則；生物通過個(gè)體間的選擇、交叉、變異來適應(yīng)大自然環(huán)境。生物染色體用數(shù)學(xué)方式或計(jì)算機(jī)方式來體現(xiàn)就是一串?dāng)?shù)碼，仍叫染色體，有時(shí)也叫個(gè)體；適應(yīng)能力用對(duì)應(yīng)一個(gè)染色體的數(shù)值來衡量；染色體的選擇或淘汰問題是按求最大還是最小問題

5、來進(jìn)行。　　20世紀(jì)60年代以來，如何模仿生物來建立功能強(qiáng)大的算法，進(jìn)而將它們運(yùn)用于復(fù)雜的優(yōu)化問題，越來越成為一個(gè)研究熱點(diǎn)。進(jìn)化計(jì)算(evolutionary computation) 正是在這一背景下蘊(yùn)育而生的。進(jìn)化計(jì)算包括遺傳算法(genetic algorithms，GA) ，進(jìn)化策略(evolution strategies) 、進(jìn)化編程(evolutionary programming) 和遺傳編程(genetic prog

6、ramming)。,遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式構(gòu)造的一類優(yōu)化搜索算法，是對(duì)生物進(jìn)化過程進(jìn)行的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的一種最重要形式。 霍蘭德提出的遺傳算法通常稱為簡單遺傳算法（SGA）?，F(xiàn)以此作為討論主要對(duì)象，加上適應(yīng)的改進(jìn)，來分析遺傳算法的結(jié)構(gòu)和機(jī)理。 1、編碼與解碼,許多應(yīng)用問題的結(jié)構(gòu)很復(fù)雜，但可以化為簡單的位串形式編碼表示。將問題結(jié)構(gòu)變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為

7、原問題結(jié)構(gòu)的過程叫解碼或譯碼。把位串形式編碼表示叫染色體，有時(shí)也叫個(gè)體?！　A的算法過程簡述如下。首先在解空間中取一群點(diǎn)，作為遺傳開始的第一代。每個(gè)點(diǎn)（基因）用一個(gè)二進(jìn)制數(shù)字串表示，其優(yōu)劣程度用一目標(biāo)函數(shù)適應(yīng)度函數(shù)（fitness function）來衡量。遺傳算法最常用的編碼方法是二進(jìn)制編碼。,二進(jìn)制編碼的最大缺點(diǎn)之一是長度較大，對(duì)很多問題用其他主編碼方法可能更有利。其他編碼方法主要有：浮點(diǎn)數(shù)編碼方法、格雷碼、符號(hào)編碼方法、多參

8、數(shù)編碼方法等?！　∨e例：對(duì)于銷售員旅行問題，按一條回路中城市的次序進(jìn)行編碼。從城市w1開始，依次經(jīng)過城市w2 ，……，wn，最后回到城市w1，我們就有如下編碼表示：　　w1 w2 …… wn　　由于是回路，記wn+1=w1。它其實(shí)是1，……，n的一個(gè)循環(huán)排列。要注意w1，w2，……，wn是互不相同的。,2、適應(yīng)度函數(shù)為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)（fitness funct

9、ion）。TSP的目標(biāo)是路徑總長度為最短，自然地，路徑總長度就可作為TSP問題的適應(yīng)度函數(shù)。　　適應(yīng)度函數(shù)要有效反映每一個(gè)染色體與問題的最優(yōu)解染色體之間的差距。適應(yīng)度函數(shù)的取值大小與求解問題對(duì)象的意義有很大的關(guān)系。3、遺傳算子簡單遺傳算法的遺傳操作主要有有三種:選擇(selection)、交叉(crossover)、變異(mutation)。,,改進(jìn)的遺傳算法大量擴(kuò)充了遺傳操作，以達(dá)到更高的效率。選擇操作也叫復(fù)制（reprodu

10、ction）操作，根據(jù)個(gè)體的適應(yīng)度函數(shù)值所度量的優(yōu)劣程度決定它在下一代是被淘汰還是被遺傳?！　〗徊娌僮鞯暮唵畏绞绞菍⒈贿x擇出的兩個(gè)個(gè)體P1和P2作為父母個(gè)體，將兩者的部分碼值進(jìn)行交換?！　∽儺惒僮鞯暮唵畏绞绞歉淖償?shù)碼串的某個(gè)位置上的數(shù)碼。二進(jìn)制編碼表示的簡單變異操作是將0與1互換：0變異為1，1變異為0。,4、基本概念總結(jié)一、串(String)它是個(gè)體的形式，在算法中為二進(jìn)制串，并且對(duì)應(yīng)于遺傳學(xué)中的染色體Chromosome。

11、二、群體(Population)個(gè)體的集合稱為群體，串是群體的元素三、群體大小(Population Size)在群體中個(gè)體的數(shù)量稱為群體的大小。四、基因(Gene)基因是串中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)串S＝1011，則其中的1，0，1，1這4個(gè)元素分別稱為基因。它們的值稱為等位基因Alletes,五 、基因位置(Gene Position)一個(gè)基因在串中的位置稱為基因位置，有時(shí)也簡稱基因位?；蛭恢糜纱淖笙?/p>

12、右計(jì)算，例如在串S＝1101中，0的基因位置是3。基因位置對(duì)應(yīng)于遺傳學(xué)中的地點(diǎn)(Locus)。六、基因特征值(Gene Feature)在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。七、串結(jié)構(gòu)空間SS在串中，基因任意組合所構(gòu)成的串的集合?；虿僮魇窃诮Y(jié)構(gòu)空間中進(jìn)行的。串結(jié)構(gòu)空間對(duì)應(yīng)于遺傳學(xué)中的基因型(Genotype)的集合。

13、,,,,,,,,,,,,,,八、參數(shù)空間SP這是串空間在物理系統(tǒng)中的映射，它對(duì)應(yīng)于遺傳學(xué)中的表現(xiàn)型(Phenotype)的集合。九、適應(yīng)度(Fitness)表示某一個(gè)體對(duì)于環(huán)境的適應(yīng)程度。十、遺傳算法原理總結(jié),,遺傳算法的求解過程算法的停止條件最簡單的有如下二種：（1）完成了預(yù)先給定的進(jìn)化代數(shù)則停止；（2）群體中的最優(yōu)個(gè)體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時(shí)停止。　　一般遺傳算法的主要步驟如下：　　(

14、1)　 隨機(jī)產(chǎn)生一個(gè)由確定長度的特征字符串組成的初始群體。　　(2)　對(duì)該字符串群體迭代的執(zhí)行下面的步(a)和(b)，直到滿足停止標(biāo)準(zhǔn)：　　 (a) 計(jì)算群體中每個(gè)個(gè)體字符串的適應(yīng)值；　　 (b) 應(yīng)用復(fù)制、交叉和變異等遺傳算子產(chǎn)生下一代群體。 　　(3)　把在后代中出現(xiàn)的最好的個(gè)體字符串指定為遺傳算法的執(zhí)行結(jié)果，這個(gè)結(jié)果可以表示問題的一個(gè)解,基本遺傳算法的總結(jié),（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇

15、、交叉、變異）（4）運(yùn)行參數(shù),編碼,GA是通過某種編碼機(jī)制把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進(jìn)制串進(jìn)行編碼。,函數(shù)優(yōu)化示例,求下列一元函數(shù)的最大值：,x∈[-1,2] ，求解結(jié)果精確到6位小數(shù)。,SGA對(duì)于本例的編碼,由于區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因?yàn)?21 < 3×10

16、6 < 222 ，所以本例的二進(jìn)制編碼長度至少需要22位，本例的編碼過程實(shí)質(zhì)上是將區(qū)間[-1，2]內(nèi)對(duì)應(yīng)的實(shí)數(shù)值轉(zhuǎn)化為一個(gè)二進(jìn)制串（b21b20…b0）。,幾個(gè)術(shù)語,基因型：1000101110110101000111,表現(xiàn)型：0.637197,,,編碼,解碼,,個(gè)體（染色體）,,基因,初始種群,SGA采用隨機(jī)方法生成若干個(gè)個(gè)體的集合，該集合稱為初始種群。初始種群中個(gè)體的數(shù)量稱為種群規(guī)模。,適應(yīng)度函數(shù),遺傳算法對(duì)一個(gè)個(gè)體（解）的好

17、壞用適應(yīng)度函數(shù)值來評(píng)價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問題本身的要求而定。,選擇算子,遺傳算法使用選擇運(yùn)算來實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個(gè)體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。,輪盤賭選擇

18、方法,輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n ，個(gè)體i 的適應(yīng)度為 Fi，則個(gè)體i 被選中遺傳到下一代群體的概率為：,輪盤賭選擇方法的實(shí)現(xiàn)步驟,（1） 計(jì)算群體中所有個(gè)體的適應(yīng)度函數(shù)值（需要解碼）；（2） 利用比例選擇算子的公式，計(jì)算每個(gè)個(gè)體被選中遺傳到下一代群體的概率；（3） 采用模擬賭盤操作（即生成0到1之間的隨機(jī)數(shù)與每個(gè)個(gè)體遺傳到下一代群體的概率進(jìn)行匹配）來確

19、定各個(gè)個(gè)體是否遺傳到下一代群體中。,交叉算子,所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。 SGA中交叉算子采用單點(diǎn)交叉算子。,單點(diǎn)交叉運(yùn)算,交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|00

20、00011111100010111100|01110000000010000,交叉點(diǎn),變異算子,所謂變異運(yùn)算，是指依據(jù)變異概率 Pm 將個(gè)體編碼串中的某些基因值用其它基因值來替換，從而形成一個(gè)新的個(gè)體。遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力，同時(shí)保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。 SGA中變異算子采用基本位變異算子。,基本位變異算子,基本位變異算

21、子是指對(duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)? 。,基本位變異算子的執(zhí)行過程,變異前：000001110000000010000變異后：000001110001000010000,變異點(diǎn),運(yùn)行參數(shù),（1）M ： 種群規(guī)模 （2）T ： 遺傳運(yùn)算的終止

22、進(jìn)化代數(shù) （3）Pc ： 交叉概率 （4）Pm ： 變異概率,3、遺傳算法的特點(diǎn),（1）群體搜索，易于并行化處理； （2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。,二、遺傳算法原理,1、遺傳算法的數(shù)學(xué)基礎(chǔ) 2、遺傳算法的收斂性分析 3、遺傳算法的改進(jìn),1、遺傳算法的數(shù)學(xué)基礎(chǔ),（1）模式定理 （2）積木塊假設(shè),模式,模式是指種群個(gè)體基因串中的相似樣板，它用來描述基因串中某些特

23、征位相同的結(jié)構(gòu)。在二進(jìn)制編碼中，模式是基于三個(gè)字符集(0,1,*)的字符串，符號(hào)*代表任意字符，即 0 或者 1。 模式示例：10**1,兩個(gè)定義,定義1：模式 H 中確定位置的個(gè)數(shù)稱為模式 H 的階，記作O(H)。例如O(10**1)=3 。定義2：模式 H 中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為模式 H 的定義距，記作δ(H)。例如δ(10**1)=4 。,模式的階和定義距的含義,

24、模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會(huì)有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。,模式定理,模式定理：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。 模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。,模式定理,從模式定理可看出，有高平

25、均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串?dāng)?shù)目，這主要是因?yàn)檫x擇使最好的模式有更多的復(fù)制，交叉算子不容易破壞高頻率出現(xiàn)的、短定義長的模式，而一般突變概率又相當(dāng)小，因而它對(duì)這些重要的模式幾乎沒有影響。,積木塊假設(shè),積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全

26、局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。,2、遺傳算法的收斂性分析,遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。,種群規(guī)模對(duì)收斂性的影響,通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會(huì)增加計(jì)

27、算量，造成收斂時(shí)間太長，表現(xiàn)為收斂速度緩慢。,選擇操作對(duì)收斂性的影響,選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個(gè)體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。,交叉概率對(duì)收斂性的影響,交叉操作用于個(gè)體對(duì)，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時(shí)，種群中個(gè)體更新很快，會(huì)造成高適應(yīng)度值的個(gè)

28、體很快被破壞掉；概率太小時(shí)，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前，造成算法的不收斂。,變異概率對(duì)收斂性的影響,變異操作是對(duì)種群模式的擾動(dòng)，有利于增加種群的多樣性 。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會(huì)使遺傳算法成為隨機(jī)搜索算法。,遺傳算法的本質(zhì),遺傳算法本質(zhì)上是對(duì)染色體模式所進(jìn)行的一系列運(yùn)算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過這些遺傳操作，模

29、式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。,3、遺傳算法的改進(jìn),遺傳欺騙問題：在遺傳算法進(jìn)化過程中，有時(shí)會(huì)產(chǎn)生一些超常的個(gè)體，這些個(gè)體因競爭力太突出而控制了選擇運(yùn)算過程，從而影響算法的全局優(yōu)化性能，導(dǎo)致算法獲得某個(gè)局部最優(yōu)解。,遺傳算法的改進(jìn)途徑,（1）對(duì)編碼方式的改進(jìn) （2）對(duì)遺傳算子 的改進(jìn)（3）對(duì)控制參數(shù)的改進(jìn) （4）對(duì)執(zhí)行策略的改進(jìn),對(duì)編碼方式的改進(jìn),二進(jìn)制編碼優(yōu)點(diǎn)在于編碼、解碼操作簡單，交叉、變異等操作便于實(shí)現(xiàn)，缺點(diǎn)

30、在于精度要求較高時(shí)，個(gè)體編碼串較長，使算法的搜索空間急劇擴(kuò)大，遺傳算法的性能降低。格雷編碼克服了二進(jìn)制編碼的不連續(xù)問題 ，浮點(diǎn)數(shù)編碼改善了遺傳算法的計(jì)算復(fù)雜性 。,對(duì)遺傳算子 的改進(jìn),排序選擇 均勻交叉 逆序變異,（1） 對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行降序排序；（2） 根據(jù)具體求解問題，設(shè)計(jì)一個(gè)概率分配表，將各個(gè)概率值按上述排列次序分配給各個(gè)個(gè)體；（3） 以各個(gè)個(gè)體所分配到的概率值作為其遺傳到下一代的概率，基于這些概率用賭

31、盤選擇法來產(chǎn)生下一代群體。,對(duì)遺傳算子 的改進(jìn),排序選擇 均勻交叉 逆序變異,（1） 隨機(jī)產(chǎn)生一個(gè)與個(gè)體編碼長度相同的二進(jìn)制屏蔽字P = W1W2…Wn ；（2） 按下列規(guī)則從A、B兩個(gè)父代個(gè)體中產(chǎn)生兩個(gè)新個(gè)體X、Y：若Wi = 0，則X的第i個(gè)基因繼承A的對(duì)應(yīng)基因，Y的第i個(gè)基因繼承B的對(duì)應(yīng)基因；若Wi = 1，則A、B的第i個(gè)基因相互交換，從而生成X、Y的第i個(gè)基因。,對(duì)遺傳算子 的改進(jìn),排序選擇 均勻交叉 逆序變異,變異

32、前：3 4 8 | 7 9 6 5 | 2 1變異前：3 4 8 | 5 6 9 7 | 2 1,對(duì)控制參數(shù)的改進(jìn),Schaffer建議的最優(yōu)參數(shù)范圍是： M = 20-100， T = 100-500， Pc = 0.4-0.9， P

33、m = 0.001-0.01。,對(duì)控制參數(shù)的改進(jìn),Srinvivas等人提出自適應(yīng)遺傳算法，即PC和Pm能夠隨適應(yīng)度自動(dòng)改變，當(dāng)種群的各個(gè)個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使二者增加，而當(dāng)種群適應(yīng)度比較分散時(shí)，使二者減小，同時(shí)對(duì)適應(yīng)值高于群體平均適應(yīng)值的個(gè)體，采用較低的PC和Pm，使性能優(yōu)良的個(gè)體進(jìn)入下一代，而低于平均適應(yīng)值的個(gè)體，采用較高的PC和Pm，使性能較差的個(gè)體被淘汰 。,對(duì)執(zhí)行策略的改進(jìn),混合遺傳算法免疫遺傳算法小生境遺

34、傳算法單親遺傳算法并行遺傳算法,三、遺傳算法的應(yīng)用,1、遺傳算法的應(yīng)用領(lǐng)域 2、遺傳算法的應(yīng)用示例,1、遺傳算法的應(yīng)用領(lǐng)域,（1）組合優(yōu)化 （2）函數(shù)優(yōu)化 （3）自動(dòng)控制 （4）生產(chǎn)調(diào)度 （5）圖像處理 （6）機(jī)器學(xué)習(xí) （7）人工生命 （8）數(shù)據(jù)挖掘,遺傳算法應(yīng)用于組合優(yōu)化,隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，有時(shí)在計(jì)算機(jī)上用枚舉法很難甚至不可能求出其最優(yōu)解。實(shí)踐證明，遺

35、傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、布局優(yōu)化、網(wǎng)絡(luò)路由等具有NP難度的組合優(yōu)化問題上取得了成功的應(yīng)用。,雖然遺傳算法使用簡單、魯棒性強(qiáng)、應(yīng)用范圍甚廣，但是它本身也存在著許多不足，尤其是容易過早收斂，使搜索陷入局部最優(yōu)解，因此可以把模擬退火引入到遺傳算法中。模擬退火遺傳算法如下：（1）初始化控制參數(shù)：N為群體規(guī)模；Pm為變異概率；T0為退火初始溫度；α為溫度冷卻參數(shù)；（2）隨機(jī)產(chǎn)生初始解群；（3）對(duì)現(xiàn)有解群實(shí)施如下操作

36、，直至產(chǎn)生出下一代新的群體：·評(píng)價(jià)群體中每個(gè)個(gè)體的適應(yīng)函數(shù)值f(xi)，i=1,2,…,N, 以空間利用率作為適應(yīng)度函數(shù)；·采用輪盤賭選擇法對(duì)個(gè)體進(jìn)行選擇；,模擬退火遺傳算法,輪盤賭選擇法的基本思想是：生成一個(gè)隨機(jī)數(shù)γ∈[0，1]，并且計(jì)算個(gè)體的相對(duì)適應(yīng)度值pi=fi/∑fi，如果p0+p1+…+pi-1random[0,1]的概率接受新的解，即接受新個(gè)體。·對(duì)交叉后的個(gè)體進(jìn)行變異操作，按第三步中的方

37、法決定是否接收變異后的解；,（4）若滿足收斂條件，進(jìn)化過程結(jié)束；否則Tk+1=αTk,轉(zhuǎn)（3）。模擬退火遺傳算法首先利用輪盤賭選擇方法，淘汰了適應(yīng)度較低的個(gè)體。而交叉操作是遺傳算法中的核心，尋優(yōu)過程主要通過它實(shí)現(xiàn)，模擬退火遺傳算法吸取了這一思想，對(duì)選擇后個(gè)體均實(shí)話交叉操作，并且把交叉和變異后的子代與父代競爭，通過Boltzmann機(jī)制來接收子代，不但有利于優(yōu)良個(gè)體的保留，同時(shí)防止了早熟收斂的問題。隨著進(jìn)化過程的進(jìn)行，溫度逐漸下降，接收

38、劣質(zhì)解的概率也逐漸減小，有效地利用了模擬退火算法的爬山特性，提高了算法的收斂速度。,2、遺傳算法的應(yīng)用示例,彈藥裝載問題（Ammunition Loading Problem，簡稱ALP），就是在滿足各類通用彈藥運(yùn)輸規(guī)程和安全性的前提下，如何將一批通用彈藥箱裝入軍用運(yùn)輸工具，使得通用彈藥的裝載效率達(dá)到最大值的問題。,AGSAA的基本原理,在彈藥裝載中，考慮到模擬退火算法的基本思想是跳出局部最優(yōu)解，將模擬退火思想引入遺傳算法，應(yīng)用改進(jìn)型遺

39、傳算法和模擬退火算法相結(jié)合，構(gòu)建自適應(yīng)遺傳模擬退火算法（AGSAA），從而綜合了全局優(yōu)化和局部搜索的特點(diǎn)，為解決彈藥裝載這一組合優(yōu)化問題提供了新的思路。,AGSAA的編碼方式,AGSAA采用二進(jìn)制編碼方式，每一個(gè)二進(jìn)制位對(duì)應(yīng)一個(gè)待裝彈藥箱，若為１，表示該彈藥箱裝入運(yùn)輸工具，為０則不裝。,AGSAA的解碼和適應(yīng)度函數(shù),AGSAA采用彈藥裝載的啟發(fā)式算法來解碼，解碼后最終確定裝入運(yùn)輸工具的彈藥箱。適應(yīng)度函數(shù)主要考慮兩個(gè)方面，即載重率和積載率

40、，對(duì)這兩個(gè)因素加權(quán)，來計(jì)算適應(yīng)度函數(shù)值。,彈藥裝載的啟發(fā)式算法,（1）定位規(guī)則（Locating rule） 　　 定位規(guī)則是指用來確定當(dāng)前待裝彈藥箱在運(yùn)輸工具剩余裝載空間中擺放位置的規(guī)則。　　 （2）定序規(guī)則（Ordering rule） 定序規(guī)則是指用來確定彈藥箱放入運(yùn)輸工具裝載空間先后順序的規(guī)則。,遺傳算子的選擇,AGSAA的選擇算子采用輪盤賭選擇算子，并結(jié)合最優(yōu)保存策略；變異算子采用基本位變異算子；同時(shí)，在變異運(yùn)算

41、之后，增加退火算子，以增強(qiáng)算法的局部搜索能力；交叉概率和變異概率為自適應(yīng)概率，以提高種群的進(jìn)化效率。,交叉算子的選擇,由于AGSAA是采用將彈藥箱的編號(hào)排列成串來進(jìn)行編碼的，如果個(gè)體交叉采用傳統(tǒng)方式進(jìn)行，就有可能使個(gè)體的編碼產(chǎn)生重復(fù)基因（即一個(gè)彈藥箱編號(hào)在一個(gè)個(gè)體中出現(xiàn)兩次以上），從而產(chǎn)生不符合條件的個(gè)體，因此，AGSAA采用的是部分映射交叉算子。,部分映射交叉算子,交叉前：　　 8 7 | 4 3 | 1 2 6 5

42、1 2 | 5 7 | 8 3 4 6交叉后：　　 8 3 | 6 7 | 1 2 4 5 1 7 | 6 2 | 8 3 4 5,參考文獻(xiàn),1 張偉，李守智，高峰等. 幾種智能最優(yōu)化算法的比較研究. Proceedings of the 24th Chinese Control Conference, Guangzhou, P.R. China July 15-18, 2005:1316～13202馬玉明,賀愛玲,

43、李愛民. 遺傳算法的理論研究綜述. 山東輕工業(yè)學(xué)院學(xué)報(bào), 2004,18(3):77～803 Andreas Bortfeldt, Hermann Gehring. A Hybrid Genetic Algorithm for The Container Loading Problem. European Journal of Operational Research, 2001(131):143～161.4 D.Y.He, J.Z

44、.Cha. Research on Solution to Complex Container Loading Problem Based on Genetic Algorithm. The First International Conference on Machine Learning and Cybernetics. Beijing-China,2002:78～82,參考文獻(xiàn),5 C.Pimpawat, N.Chaiyarata

45、na. Using A Co-Operative Co-Evolutionary Genetic Algorithm to Solve A Three-Dimensional Container Loading Problem. The Second International Conference on Machine Learning and Cybernetics. Mongkut-Thailand, 2003:1197～1204

46、6王春水，肖學(xué)柱，陳漢明. 遺傳算法的應(yīng)用舉例. 計(jì)算機(jī)仿真2005，22(6):155～1577姚文俊. 遺傳算法及其研究進(jìn)展. 計(jì)算機(jī)與數(shù)字工程, 2004，32(4):41～438吉根林. 遺傳算法研究綜述. 計(jì)算機(jī)應(yīng)用與軟件, 2004，21(2):69～739高艷霞，劉峰，王道洪. 改進(jìn)型遺傳算法及其應(yīng)用研究. 上海大學(xué)學(xué)報(bào), 2004(10):249～253,參考文獻(xiàn),10馬立肖,王江晴. 遺傳算法在組合優(yōu)化問題中的

47、應(yīng)用. 計(jì)算機(jī)工程與科學(xué), 2005，27(7):72～73、8211曹先彬, 劉克勝, 王煦法. 基于免疫遺傳算法的裝箱問題求解. 小型微型計(jì)算機(jī)系統(tǒng). 2000, 21(4):361～363 12 Rudolf Berghammer, Florian Reuter. A Linear Approximation Algorithm for Bin Packing with Absolute Approximation Facto