遺傳算法原理與應(yīng)用課件

非線性規(guī)劃算法主要內(nèi)容一、非線性規(guī)劃二、遺傳算法二、模擬退火法一、遺傳算法概述1、智能優(yōu)化算法2、基本遺傳算法3、遺傳算法的特點(diǎn)常用的智能優(yōu)化算法（1）遺傳算法（GeneticAlgorithm，簡(jiǎn)稱GA）（2）模擬退火算法（SimulatedAnnealing，簡(jiǎn)稱SA）（3）禁忌搜索算法（TabuSearch，簡(jiǎn)稱TS）

……智能優(yōu)化算法的特點(diǎn)

它們的共同特點(diǎn)：都是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問題空間，因而具有全局優(yōu)化性能。遺傳算法起源

遺傳算法是由美國(guó)的J.Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。2、基本遺傳算法

基本遺傳算法（SimpleGeneticAlgorithms，簡(jiǎn)稱SGA，又稱簡(jiǎn)單遺傳算法或標(biāo)準(zhǔn)遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過程簡(jiǎn)單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)?；具z傳算法的組成（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運(yùn)行參數(shù)

編碼GA是通過某種編碼機(jī)制把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進(jìn)制串進(jìn)行編碼。SGA對(duì)于本例的編碼

由于區(qū)間長(zhǎng)度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因?yàn)?21<3×106<222

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

遺傳算法使用選擇運(yùn)算來實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個(gè)體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。輪盤賭選擇方法

輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個(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)行匹配）來確定各個(gè)個(gè)體是否遺傳到下一代群體中。單點(diǎn)交叉運(yùn)算交叉前：00000|01000011100|000101交叉后：00000|00010111100|010000交叉點(diǎn)變異算子

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

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