遺傳算法原理及其應(yīng)用演示文稿

遺傳算法原理及其應(yīng)用演示文稿目前一頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)遺傳算法原理及其應(yīng)用目前二頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)1.遺傳算法概述2.基本遺傳算法(SGA)目錄1.1遺傳算法的產(chǎn)生與發(fā)展1.2遺傳算法的生理學(xué)基礎(chǔ)1.3遺傳算法的原理與特點(diǎn)1.4遺傳算法的基本操作1.5遺傳算法的應(yīng)用2.1基本遺傳算法描述2.2基本遺傳算法實(shí)現(xiàn)2.3基本遺傳算法流程2.4簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例目前三頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)3.遺傳算法的改進(jìn)4.遺傳算法的應(yīng)用目錄3.1自適應(yīng)遺傳算法3.2CHC算法3.3基于小生境技術(shù)的遺傳算法3.4退火進(jìn)化算法4.1解決帶約束的函數(shù)優(yōu)化問題4.2解決多目標(biāo)優(yōu)化問題4.3解決組合優(yōu)化問題4.4遺傳算法在過程建模中的應(yīng)用4.5遺傳算法在模式識(shí)別中的應(yīng)用目前四頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)1.1遺傳算法的產(chǎn)生與發(fā)展產(chǎn)生早在50年代，一些生物學(xué)家開始研究運(yùn)用數(shù)字計(jì)算機(jī)模擬生物的自然遺傳與自然進(jìn)化過程；1963年，德國(guó)柏林技術(shù)大學(xué)的I.Rechenberg和H.P.Schwefel，做風(fēng)洞實(shí)驗(yàn)時(shí)，產(chǎn)生了進(jìn)化策略的初步思想；60年代，L.J.Fogel在設(shè)計(jì)有限態(tài)自動(dòng)機(jī)時(shí)提出進(jìn)化規(guī)劃的思想。1966年Fogel等出版了《基于模擬進(jìn)化的人工智能》，系統(tǒng)闡述了進(jìn)化規(guī)劃的思想。60年代中期，美國(guó)Michigan大學(xué)的J.H.Holland教授提出借鑒生物自然遺傳的基本原理用于自然和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)；1967年，他的學(xué)生J.D.Bagley在博士論文中首次提出“遺傳算法(GeneticAlgorithms)”一詞；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，標(biāo)志遺傳算法的誕生。5目前五頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)1.1遺傳算法的產(chǎn)生與發(fā)展發(fā)展70年代初，Holland提出了“模式定理”（SchemaTheorem），一般認(rèn)為是“遺傳算法的基本定理”，從而奠定了遺傳算法研究的理論基礎(chǔ)；1985年，在美國(guó)召開了第一屆遺傳算法國(guó)際會(huì)議，并且成立了國(guó)際遺傳算法學(xué)會(huì)(ISGA，InternationalSocietyofGeneticAlgorithms)；1989年，Holland的學(xué)生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，對(duì)遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述；1991年，L.Davis編輯出版了《遺傳算法手冊(cè)》，其中包括了遺傳算法在工程技術(shù)和社會(huì)生活中大量的應(yīng)用實(shí)例。遺傳算法——進(jìn)化計(jì)算——計(jì)算智能——人工智能6目前六頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)1.2遺傳學(xué)基本概念與術(shù)語染色體（chromosome）：遺傳物質(zhì)的載體；脫氧核糖核酸（DNA）：大分子有機(jī)聚合物，雙螺旋結(jié)構(gòu)；RNA遺傳因子（gene）：DNA或RNA長(zhǎng)鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位；基因型（genotype）：遺傳因子組合的模型；表現(xiàn)型（phenotype）：由染色體決定性狀的外部表現(xiàn)；個(gè)體（individual）：指染色體帶有特征的實(shí)體；種群（population）：個(gè)體的集合，該集合內(nèi)個(gè)體數(shù)稱為種群的大小；1111111

11101117目前七頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)進(jìn)化（evolution）：生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化；適應(yīng)度（fitness）：度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。對(duì)生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會(huì)就會(huì)相對(duì)較少，甚至逐漸滅絕;選擇（selection）：指決定以一定的概率從種群中選擇若干個(gè)體的操作（實(shí)現(xiàn)優(yōu)勝劣汰）；復(fù)制（reproduction）：細(xì)胞在分裂時(shí)，遺傳物質(zhì)DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因;8目前八頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)交叉（crossover）：在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。又稱基因重組，俗稱“雜交”;變異（mutation）：在細(xì)胞進(jìn)行復(fù)制時(shí)可能以很小的概率產(chǎn)生某些復(fù)制差錯(cuò)，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀;編碼（coding）：表現(xiàn)型到基因型的映射；解碼（decoding）：從基因型到表現(xiàn)型的映射。大象灰顏色皮膚為例1111111

編碼解碼9目前九頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)1.3遺傳算法的原理與特點(diǎn)原理遺傳算法(GA)是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索方法。其采納了自然進(jìn)化模型，從代表問題可能潛在解集的一個(gè)種群開始，種群由經(jīng)過基因編碼的一定數(shù)目的個(gè)體組成。每個(gè)個(gè)體實(shí)際上是染色體帶有特征的實(shí)體；初始種群產(chǎn)生后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的解：在每一代，概據(jù)問題域中個(gè)體的適應(yīng)度大小挑選個(gè)體；并借助遺傳算子進(jìn)行組合交叉和主客觀變異，產(chǎn)生出代表新的解集的種群。這一過程循環(huán)執(zhí)行，直到滿足優(yōu)化準(zhǔn)則為止。最后，末代個(gè)體經(jīng)解碼，生成近似最優(yōu)解?；诜N群進(jìn)化機(jī)制的遺傳算法如同自然界進(jìn)化一樣，后生代種群比前生代更加適應(yīng)于環(huán)境，通過逐代進(jìn)化，逼近最優(yōu)解。10目前十頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)1.3遺傳算法的原理與特點(diǎn)遺傳算法的基本流程Fig.2逼近最優(yōu)解的過程Fig.1遺傳算法的基本流程算法結(jié)束?11目前十一頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)1.3遺傳算法的原理與特點(diǎn)特點(diǎn)遺傳算法的本質(zhì)并行性。首先，遺傳算法并行的方式從問題解的串集開始嫂索，而不是從單個(gè)解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。其次，算法內(nèi)含并行性，遺傳算法采用種群方式組織搜索，因而可同時(shí)搜索妥空間的多個(gè)區(qū)域(n-n3)，并相互交流信息，能以較小的計(jì)算獲得較大的收益。遺傳算法基本上不用搜索空間的知識(shí)或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評(píng)估個(gè)體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)他的搜索方向。具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過程獲得的信息自行組織搜索時(shí)，硬度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。遺傳算法可更直接的應(yīng)用，對(duì)給定的問題，可以產(chǎn)生許多潛在解，最終選擇可以由使用者指定，通用性高，應(yīng)用范圍廣。12目前十二頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)1.4遺傳算法的基本操作遺傳基因型(編碼)編碼方式二進(jìn)制編碼、浮點(diǎn)數(shù)編碼、格雷碼編碼、符號(hào)編碼、復(fù)數(shù)編碼、DNA編碼等。以大象灰色皮膚為例：二進(jìn)制編碼：1111111，浮點(diǎn)編碼：127.0編碼原則完備性（completeness）：?jiǎn)栴}空間的所有解都能表示為所設(shè)計(jì)的基因型；健全性（soundness）：任何一個(gè)基因型都對(duì)應(yīng)于一個(gè)可能解；非冗余性（non-redundancy）：?jiǎn)栴}空間和表達(dá)空間一一對(duì)應(yīng)。二進(jìn)制編碼與浮點(diǎn)數(shù)編碼的比較在交叉操作時(shí)，二進(jìn)制編碼比浮點(diǎn)數(shù)編碼產(chǎn)生新個(gè)體的可能性多，而且產(chǎn)生的新個(gè)體不受父?jìng)€(gè)體所構(gòu)成的超體的限制；在變異操作時(shí)，二進(jìn)制編碼的種群穩(wěn)定性比浮點(diǎn)數(shù)編碼差。13目前十三頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)1.4遺傳算法的基本操作選擇適應(yīng)度計(jì)算：按比例的適應(yīng)度函數(shù)（proportionalfitnessassignment）基于排序的適應(yīng)度計(jì)算（Rank-basedfitnessassignment）

選擇算法：輪盤賭選擇（roulettewheelselection）隨機(jī)遍歷抽樣（stochasticuniversalselection）局部選擇（localselection）截?cái)噙x擇（truncationselection）錦標(biāo)賽選擇（tournamentselection）14目前十四頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)交叉或基因重組二進(jìn)制交叉（binaryvaluedcrossover）：?jiǎn)吸c(diǎn)交叉（single-pointcrossover）多點(diǎn)交叉（multiple-pointcrossover）均勻交叉（uniformcrossover）洗牌交叉（shufflecrossover）縮小代理交叉（crossoverwithreducedsurrogate）實(shí)值重組（realvaluedrecombination）：離散重組（discreterecombination）中間重組（intermediaterecombination）線性重組（linearrecombination）（均勻、非均勻）擴(kuò)展線性重組（extendedlinearrecombination15目前十五頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)交叉方式半種群交叉(N/2)對(duì)群體中的要交叉的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)。若群體大小為M，則最多共有[M/2]對(duì)相互配對(duì)的個(gè)體組參與交叉。(若種群數(shù)為奇數(shù)，則其中任一個(gè)個(gè)體多選一次配對(duì))2)全種群交叉(N)對(duì)群體中要交叉的個(gè)體，從種群中隨機(jī)挑選一個(gè)個(gè)體與其完成交叉操作，最多共有M對(duì)相互配對(duì)的個(gè)體參與變異。16目前十六頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)變異方法

二進(jìn)制變異單點(diǎn)變異逆序變異均勻變異實(shí)值變異隨機(jī)變異邊界變異非一致變異自適應(yīng)變異高斯變異17目前十七頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)變異方式基于個(gè)體的變異即對(duì)任意一個(gè)個(gè)體，判斷其是否進(jìn)行變異操作，如果是，則隨機(jī)生成一變異基因發(fā)生變異操作。基于基因座的變異即對(duì)種群中的個(gè)體，判斷每一個(gè)個(gè)體的每一位基因是否進(jìn)行變異操作，如果是，則發(fā)生變異操作。18目前十八頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)1.5遺傳算法的應(yīng)用函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域;組合優(yōu)化實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP完全問題非常有效;自動(dòng)控制如基于遺傳算法的模糊控制器優(yōu)化設(shè)計(jì)、基于遺傳算法的參數(shù)辨識(shí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)等;機(jī)器人智能控制遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行動(dòng)協(xié)調(diào)等;組合圖像處理和模式識(shí)別目前已在圖像恢復(fù)、圖像邊緣持征提取、幾何形狀識(shí)別等方面得到了應(yīng)用;19目前十九頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)人工生命基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)，遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型等方面顯示了初步的應(yīng)用能力；遺傳程序設(shè)計(jì) Koza發(fā)展了遺傳程序設(shè)計(jì)的慨念，他使用了以LISP語言所表示的編碼方法，基于對(duì)一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作自動(dòng)生成計(jì)算機(jī)程序;機(jī)器學(xué)習(xí) 機(jī)器學(xué)習(xí)學(xué)習(xí)能力是高級(jí)自適應(yīng)系統(tǒng)所應(yīng)具備的能力之一。基于遺傳算法的機(jī)器學(xué)習(xí)，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。例如，遺傳算法被用于學(xué)習(xí)模糊控制規(guī)則，利用遺傳算法來學(xué)習(xí)隸屬度函數(shù)，從而更好地改進(jìn)了模糊系統(tǒng)的性能；基于遺傳算法的機(jī)器學(xué)習(xí)可用來調(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)也在學(xué)習(xí)式多機(jī)器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用。20目前二十頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)2基本遺傳算法遺傳算法在自然與社會(huì)現(xiàn)象的模擬、工程計(jì)算等方面得到了廣泛的應(yīng)用。在各個(gè)不同的應(yīng)用領(lǐng)域，為了取得更好的結(jié)果，人們對(duì)GA進(jìn)行了大量的改進(jìn)。為不至于混淆，把Holland提出的算法稱為基本遺傳算法，簡(jiǎn)稱為SGA（SimpleGeneticAlgorithm)，也有稱其為(GA、CGA)。以SGA為例，闡述遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)方法。21目前二十一頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)2.1基本遺傳算法描述2.1.1SGA的構(gòu)成要素(1)染色體編碼方法

基本遺傳算法使用固定長(zhǎng)度的二進(jìn)制符號(hào)串來表示群體中的個(gè)體，其等位基因由二值符號(hào)集{0，1}組成。初始群體中各個(gè)個(gè)體的基因值用均勻分布的隨機(jī)數(shù)來生成。如：就可表示一個(gè)個(gè)體，該個(gè)體的染色體長(zhǎng)度是l＝18。(2)個(gè)體適應(yīng)度評(píng)價(jià)基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。 為正確計(jì)算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。這樣，根據(jù)不同種類的問題，必須預(yù)先確定好由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理方法。22目前二十二頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)(3)遺傳算子基本遺傳算法使用下述三種遺傳算子：

?選擇運(yùn)算：使用比例選擇算子；

?交叉運(yùn)算：使用單點(diǎn)交叉算子；?變異運(yùn)算：使用基本位變異算子。

(4)基本遺傳算法的運(yùn)行參數(shù)基本遺傳算法有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：

?

M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為20~100。

?T：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取為100~500

?

pc：交叉概率，一般取為0.4~0.99

?

pm：變異概率，一般取為0.0001~0.1

*這4個(gè)運(yùn)行參數(shù)對(duì)遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)。在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。23目前二十三頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)2.1.2基本遺傳算法的描述基本遺傳算法可定義為一個(gè)7元組：

GA＝(M,F,s,c,m,pc,pm)M——群體大小；F——個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)；s——選擇操作算于；c——交叉操作算子：m——變異操作算于；pc——交叉概率；pm——變異概率；24目前二十四頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)2.2基本遺傳算法的實(shí)現(xiàn)2.2.1編碼與解碼

(1)編碼

假設(shè)某一參數(shù)的取值范圍是[umin,umax]，我們用長(zhǎng)度為l的二進(jìn)制編碼符號(hào)串來表示該參數(shù)，則它總共能夠產(chǎn)生2l種不同的編碼，參數(shù)編碼時(shí)的對(duì)應(yīng)關(guān)系如下：00000000…00000000＝0umin

00000000…00000001＝1umin+ ……11111111…11111111=2l–1umax其中，為二進(jìn)制編碼的編碼精度，其公式為：=Umax

umin2l

125目前二十五頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)x=umin+(

bi·2i-1)

·

1i=lUmax

umin2l

1

(2)解碼

假設(shè)某一個(gè)體的編碼是：

x：blbl-1bl-2……b2b1則對(duì)應(yīng)的解碼公式為：26目前二十六頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)[例]設(shè)-3.0≤x≤12.1,精度要求=1/10000，由公式：Umax

umin2l=+11/1000012.1+3.0+1==151001即：217

<151001<218

解碼：x=umin+(

bi·2i-1)

·

1i=lUmax

umin2l

1=-0.3+70352(12.1+3)/(218-1)=1.052426=Umax

umin2l

1得：27目前二十七頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)2.2.2個(gè)體適應(yīng)度評(píng)價(jià)如前所述，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。

(1)當(dāng)優(yōu)化目標(biāo)是求函數(shù)最大值，并且目標(biāo)函數(shù)總?cè)≌禃r(shí)，可以直接設(shè)定個(gè)體的適應(yīng)度F(X)就等于相應(yīng)的目標(biāo)函數(shù)值f(X)，即：F(X)＝f(X)

(2)對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，理論上只需簡(jiǎn)單地對(duì)其增加一個(gè)負(fù)號(hào)就可將其轉(zhuǎn)化為求目標(biāo)函數(shù)最大值的優(yōu)化問題，即：minf(X)＝max(-f(X))但實(shí)際優(yōu)化問題中的目標(biāo)函數(shù)值有正也有負(fù)，優(yōu)化目標(biāo)有求函數(shù)最大值，也有求函數(shù)最小值，顯然上面兩式保證不了所有情況下個(gè)體的適應(yīng)度都是非負(fù)數(shù)這個(gè)要求，需要進(jìn)行適應(yīng)度函數(shù)尺度轉(zhuǎn)換，將目標(biāo)函數(shù)值f(x)變換為個(gè)體的適應(yīng)度F(x)

。28目前二十八頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)(3)SGA適應(yīng)度函數(shù)變換常用方法：

方法一：對(duì)于求目標(biāo)函數(shù)最大值的優(yōu)化問題，變換方法為：

其中，Cmin為一個(gè)適當(dāng)?shù)叵鄬?duì)比較小的數(shù)，它可用下面方法之一來選?。?/p>

?預(yù)先指定的一個(gè)較小的數(shù)。

?進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。

?當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。

方法二：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，變換方法為：其中，Cmax是一個(gè)適當(dāng)?shù)叵鄬?duì)比較大的數(shù)，它可用下面幾種方法求得：?預(yù)先指定的一個(gè)較大的數(shù)。

?進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。

?當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值。F(X)=f(X)-Cminiff(X)-Cmin>00

iff(X)-Cmin≤0F(X)=Cmax-f(X)

iff(X)Cmax0

iff(X)

Cmax29目前二十九頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)2.2.3比例選擇算子 指?jìng)€(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。 pi=fi/fi(i=1,2,…,M)

式中pi——個(gè)體i被選中的概率；fi——個(gè)體i的適應(yīng)度；

fi——群體的累加適應(yīng)度。顯然，個(gè)體適應(yīng)度愈高，被選中的概率愈大。但是，適應(yīng)度小的個(gè)體也有可能被選中，以便增加下一代群體的多樣性。

執(zhí)行比例選擇的手段是輪盤選擇。個(gè)體被選中的概率取決于個(gè)體的相對(duì)適應(yīng)度：從統(tǒng)計(jì)意義講，適應(yīng)度大的個(gè)體，其刻度長(zhǎng)，被選中的可能性大；反之，適應(yīng)度小的個(gè)體被選中的可能性小，但有時(shí)也會(huì)被“破格”選中。30目前三十頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)2.2.4單點(diǎn)交叉算子Ⅰ.對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)。若群體大小為M，則共有[M/2]對(duì)相互配對(duì)的個(gè)體組。Ⅱ.每一對(duì)相互配對(duì)的個(gè)體，隨機(jī)設(shè)置某一基因座之后的位置為交叉點(diǎn)。若染色體的長(zhǎng)度為l，則共有(l-1)個(gè)可能的交叉點(diǎn)位置。Ⅲ.對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。

單點(diǎn)交叉運(yùn)算的示例如下所示:

單點(diǎn)交叉A；1011011100A’：1011011111B：0001110011B’：0001110000

交叉概率pc=McM式中M——群體中個(gè)體的數(shù)目；Mc——群體中被交換個(gè)體的數(shù)目。31目前三十一頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)2.2.5基本位變異算子 對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將該基因值變?yōu)?，反之，若原有基因值為1，則變異操作將其變?yōu)?。

基本位變異因子的具體執(zhí)行過程是：

Ⅰ.對(duì)個(gè)體的每一個(gè)基因座，依變異概率pm指定其為變異點(diǎn)。

Ⅱ.對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其它等位基因值來代替，從而產(chǎn)生出一個(gè)新的個(gè)體。

基本位變異運(yùn)算的示例如下所示：

A：1010101010A’：1010001010

變異點(diǎn)基本位變異32目前三十二頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)變異是針對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因值執(zhí)行的，因此變異概率pm

也是針對(duì)基因而言，即：式中B——每代中變異的基因數(shù)目；M——每代中群體擁有的個(gè)體數(shù)目

l——個(gè)體中基因串長(zhǎng)度。Pm=BM·l

變異概率33目前三十三頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)2.3GA算法流程圖開始Gen=0編碼隨機(jī)產(chǎn)生M個(gè)初始個(gè)體滿足終止條件?計(jì)算群體中各個(gè)體適應(yīng)度從左至右依次執(zhí)行遺傳算子j=0j=0j=0根據(jù)適應(yīng)度選擇復(fù)制個(gè)體選擇兩個(gè)交叉?zhèn)€體選擇個(gè)體變異點(diǎn)執(zhí)行變異執(zhí)行交叉執(zhí)行復(fù)制將復(fù)制的個(gè)體添入新群體中將交叉后的兩個(gè)新個(gè)體添入新群體中將變異后的個(gè)體添入新群體中j=j+1j=j+2j=j+1

j=M?

j=pc·M?

j=pm·L·M?Gen=Gen+1輸出結(jié)果終止YNYYYNNNpcpm34目前三十四頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)問題的提出一元函數(shù)求最大值：2.4簡(jiǎn)單函數(shù)優(yōu)化實(shí)例35目前三十五頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)編碼表現(xiàn)型：x基因型：二進(jìn)制編碼（串長(zhǎng)取決于求解精度）

按編碼原理：假設(shè)要求求解精度到6位小數(shù)，區(qū)間長(zhǎng)度為2-(-1)＝3，即需將區(qū)間分為3/0.000001=3×106等份。 所以編碼的二進(jìn)制串長(zhǎng)應(yīng)為22位。36目前三十六頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)產(chǎn)生初始種群產(chǎn)生的方式：隨機(jī)產(chǎn)生的結(jié)果：長(zhǎng)度為22的二進(jìn)制串產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50，………37目前三十七頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)計(jì)算適應(yīng)度 直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)①解碼：將個(gè)體s轉(zhuǎn)化為[-1,2]區(qū)間的實(shí)數(shù)：

sx=0.637197②計(jì)算x的函數(shù)值（適應(yīng)度）：

f(x)=xsin(10πx)+2.0=2.58634538目前三十八頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)遺傳操作選擇：比例選擇法；交叉：?jiǎn)吸c(diǎn)交叉；變異：小概率變異39目前三十九頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)模擬結(jié)果

設(shè)置的參數(shù)：種群大小50；交叉概率0.75；變異概率0.05；最大代數(shù)200。

得到的最佳個(gè)體：smaxxmax=1.8506;f(xmax)=3.8503;40目前四十頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)模擬結(jié)果

進(jìn)化的過程：世代數(shù)自變量適應(yīng)度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.850341目前四十一頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)3遺傳算法的改進(jìn)傳統(tǒng)的GA在解決時(shí)就存在如下問題：首先，模型復(fù)雜，參數(shù)太多難以達(dá)到優(yōu)化目的，優(yōu)化速度慢且達(dá)不到最優(yōu)解。其次，約束條件復(fù)雜、繁多，算法收斂的時(shí)候很難滿足約束條件。因此，在處理交通控制問題上揚(yáng)長(zhǎng)避短，需要改進(jìn)遺傳算法，使其達(dá)到智能控制的效果。改進(jìn)措施 改變遺傳算法的組成成分；采用混合遺傳算法；采用動(dòng)態(tài)自適應(yīng)技術(shù)；采用非標(biāo)準(zhǔn)的遺傳操作算子；采用并行遺傳算法等。42目前四十二頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)參數(shù)分析交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性；Pc越大，新個(gè)體產(chǎn)生的速度就越快，但過大會(huì)使優(yōu)秀個(gè)體的結(jié)構(gòu)很快被破壞；Pc過小，搜索過程緩慢，以至停止不前；Pm過小，不易產(chǎn)生新個(gè)體結(jié)構(gòu)，Pm過大，變成純粹的隨機(jī)搜索；43目前四十三頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)自適應(yīng)策略Srinvivas等提出一種自適應(yīng)遺傳算法，Pc和Pm能夠隨適應(yīng)度自動(dòng)改變：當(dāng)種群各個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使Pc和Pm增加；而當(dāng)群體適應(yīng)度比較分散時(shí)，使Pc和Pm減少；對(duì)于適應(yīng)度較高的個(gè)體，對(duì)應(yīng)于較低的Pc和Pm；而較低適應(yīng)度的個(gè)體，對(duì)應(yīng)于較高的Pc和Pm。44目前四十四頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)自適應(yīng)方法fmax——群體中最大的適應(yīng)度值；favg——每代群體的平均適應(yīng)度值；f’——要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；f——要交叉或變異的個(gè)體適應(yīng)度值；k1、k2、k3、k4取(0,1)的值45目前四十五頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)自適應(yīng)方法進(jìn)一步改進(jìn)適用于進(jìn)化后期，不適于進(jìn)化前期，因?yàn)榍捌诘膬?yōu)秀個(gè)體有可能是局部最優(yōu)點(diǎn)；使最大適應(yīng)度個(gè)體的交叉概率和變異概率由0提高到Pc2和Pm2；采用精英選擇策略；46目前四十六頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)自適應(yīng)方法進(jìn)一步改進(jìn)47目前四十七頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)改進(jìn)思路1991年Eshelman提出的一種改進(jìn)遺傳算法；C：跨世代精英選擇（Crossgenerationalelitistselection）策略；H：異物種重組（Heterogeneousrecombination）；C：大變異（Cataclysmicmutation）。4.3.1CHC算法

48目前四十八頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)選擇上一代種群與通過新的交叉方法產(chǎn)生的個(gè)體群混合起來，從中按一定概率選擇較優(yōu)的個(gè)體；即使交叉操作產(chǎn)生較劣個(gè)體偏多，由于原種群大多數(shù)個(gè)體殘留，不會(huì)引起個(gè)體的評(píng)價(jià)值降低；可以更好地保持遺傳多樣性；排序方法，克服比例適應(yīng)度計(jì)算的尺度問題。49目前四十九頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)交叉均勻交叉的改進(jìn)：當(dāng)兩個(gè)父?jìng)€(gè)體位值相異的位數(shù)為m時(shí)，從中隨機(jī)選取m/2個(gè)位置，實(shí)行父?jìng)€(gè)體位值的交換；確定一閾值，當(dāng)個(gè)體間距離低于該閾值時(shí)，不進(jìn)行交叉操作。進(jìn)化收斂的同時(shí)，逐漸地減小該閾值。50目前五十頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)變異在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定收斂時(shí)期，從最優(yōu)個(gè)體中選擇一部分個(gè)體進(jìn)行初始化；初始化：選擇一定比例（擴(kuò)散率，一般0.35）的基因座，隨機(jī)地決定它們的位值。4.3.1CHC算法

51目前五十一頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)小生境概念小生境（niche）：生物學(xué)中，特定環(huán)境中的一種組織功能；在SGA中，容易“近親繁殖”；NGA（NicheGenericAlgorithm），將每一代個(gè)體劃分為若干類，每類選出優(yōu)秀個(gè)體組成一個(gè)種群；優(yōu)勢(shì)：保持解的多樣性，提高全局搜索能力，適合復(fù)雜多峰函數(shù)的優(yōu)化。4.3.3基于小生境技術(shù)的遺傳算法

52目前五十二頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)選擇策略預(yù)選擇機(jī)制、排擠機(jī)制、分享機(jī)制；預(yù)選擇（preselection,1970）機(jī)制當(dāng)子個(gè)體的適應(yīng)度超過其父?jìng)€(gè)體適應(yīng)度時(shí)，子個(gè)體才可以替代父?jìng)€(gè)體，否則父?jìng)€(gè)體仍保留；有效維持種群多樣性，造就小生境進(jìn)化環(huán)境。4.3.3基于小生境技術(shù)的遺傳算法

53目前五十三頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)排擠（crowding,1975）機(jī)制設(shè)置排擠因子CF（CF=2或3），隨機(jī)選取1/CF個(gè)個(gè)體組成排擠成員，排擠與其相似（用距離來度量）的個(gè)體；個(gè)體之間的相似性可用個(gè)體編碼串之間的海明距離來度量。4.3.3基于小生境技術(shù)的遺傳算法

54目前五十四頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)共享（sharing,1987）機(jī)制通過個(gè)體之間的相似性程度的共享函數(shù)來調(diào)整各個(gè)體的適應(yīng)度；共享函數(shù)的目的：將搜索空間的多個(gè)峰值在地理上區(qū)分開來，每一個(gè)峰值處接受一定比例數(shù)目的個(gè)體，比例數(shù)目與峰值高度有關(guān)；4.3.3基于小生境技術(shù)的遺傳算法

55目前五十五頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)共享（sharing,1987）機(jī)制共享函數(shù)的值越大，表明個(gè)體之間越相似，記為Sh(dij)，dij為兩個(gè)個(gè)體i和j之間的距離；

σshare是niche的半徑，由使用者給定。4.3.3基于小生境技術(shù)的遺傳算法

56目前五十六頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)共享（sharing,1987）機(jī)制共享法將個(gè)體的適應(yīng)度降低，即適應(yīng)度值fi除以一個(gè)niche計(jì)數(shù)mi：在距離為σshare的范圍內(nèi)的個(gè)體彼此削減適應(yīng)度，這些個(gè)體將收斂在一個(gè)niche內(nèi)，避免了整個(gè)種群的收斂。4.3.3基于小生境技術(shù)的遺傳算法

57目前五十七頁(yè)\總數(shù)七十頁(yè)\編于十九點(diǎn)退火進(jìn)化算法退火進(jìn)化算法(annealingevolutionalgorithm,AEA） 遺傳算法（GA)模擬退火算法（SA）是人工智能中用于解決組合優(yōu)化問題的經(jīng)典但是，SA在全局搜索能力方面不足，GA在局部搜索能力方面不足。而退火進(jìn)化算法（annealingevolutionalgorithm,AEA)綜合了SA和GA算法，優(yōu)勢(shì)互補(bǔ)，發(fā)揮SA局部搜索能力和GA全局搜索能力,克服SA全局搜索能力差及效率不高的問題和GA局部搜索能力差及其早熟現(xiàn)象。AEA把SA算法與GA結(jié)合在一起，通過變異與選擇不斷改善解群體，并行搜索解空間，從而有可能更迅速地找到全局最優(yōu)解。由于在選擇中采用Metropolis準(zhǔn)則，因而保留了SA算法易跳出某局部極值“陷阱”的優(yōu)點(diǎn)，易于向全局極小值快速收斂。算法求解過程如下：(1)初始化進(jìn)化代數(shù)計(jì)數(shù)器k←0，隨機(jī)給出種群P(k)初值，給定初試退火溫度T0。(2)評(píng)價(jià)當(dāng)前群體P(k)的適應(yīng)度。(3)個(gè)體交叉操作（附帶保優(yōu)操作）：P(k)’←Crossover[P(k)]。(4)個(gè)體變異操作（附帶保優(yōu)操作）：P(k)”←Mutation[P(k)’]。(5)由SA狀態(tài)函數(shù)產(chǎn)生新個(gè)體。(6)個(gè)體模擬退火操作(Metropolis準(zhǔn)則接受新個(gè)體)：P(k)”’←SA[P(k)”]。(7)判斷SA抽樣是否穩(wěn)定，若不穩(wěn)定，則返回(5)；若穩(wěn)定，則往下執(zhí)行退溫操作T←T’(8)個(gè)體復(fù)制操作，由擇優(yōu)選