遺傳算法原理及其應用演示文稿

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

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

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

選擇算法：輪盤賭選擇（roulettewheelselection）隨機遍歷抽樣（stochasticuniversalselection）局部選擇（localselection）截斷選擇（truncationselection）錦標賽選擇（tournamentselection）14當前14頁，總共70頁。交叉或基因重組二進制交叉（binaryvaluedcrossover）：單點交叉（single-pointcrossover）多點交叉（multiple-pointcrossover）均勻交叉（uniformcrossover）洗牌交叉（shufflecrossover）縮小代理交叉（crossoverwithreducedsurrogate）實值重組（realvaluedrecombination）：離散重組（discreterecombination）中間重組（intermediaterecombination）線性重組（linearrecombination）（均勻、非均勻）擴展線性重組（extendedlinearrecombination15當前15頁，總共70頁。交叉方式半種群交叉(N/2)對群體中的要交叉的個體進行兩兩隨機配對。若群體大小為M，則最多共有[M/2]對相互配對的個體組參與交叉。(若種群數(shù)為奇數(shù)，則其中任一個個體多選一次配對)2)全種群交叉(N)對群體中要交叉的個體，從種群中隨機挑選一個個體與其完成交叉操作，最多共有M對相互配對的個體參與變異。16當前16頁，總共70頁。變異方法

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

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

?選擇運算：使用比例選擇算子；

?交叉運算：使用單點交叉算子；?變異運算：使用基本位變異算子。

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

?

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

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

?

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

?

pm：變異概率，一般取為0.0001~0.1 *這4個運行參數(shù)對遺傳算法的求解結果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)。在遺傳算法的實際應用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。23當前23頁，總共70頁。2.1.2基本遺傳算法的描述基本遺傳算法可定義為一個7元組：

GA＝(M,F,s,c,m,pc,pm)M——群體大??；F——個體適應度評價函數(shù)；s——選擇操作算于；c——交叉操作算子：m——變異操作算于；pc——交叉概率；pm——變異概率；24當前24頁，總共70頁。2.2基本遺傳算法的實現(xiàn)2.2.1編碼與解碼

(1)編碼

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

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

umin2l

125當前25頁，總共70頁。x=umin+(

bi·2i-1)

·

1i=lUmax

umin2l

1

(2)解碼

假設某一個體的編碼是：

x：blbl-1bl-2……b2b1則對應的解碼公式為：26當前26頁，總共70頁。[例]設-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當前27頁，總共70頁。2.2.2個體適應度評價如前所述，要求所有個體的適應度必須為正數(shù)或零，不能是負數(shù)。

(1)當優(yōu)化目標是求函數(shù)最大值，并且目標函數(shù)總取正值時，可以直接設定個體的適應度F(X)就等于相應的目標函數(shù)值f(X)，即：F(X)＝f(X)

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

。28當前28頁，總共70頁。(3)SGA適應度函數(shù)變換常用方法：

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

其中，Cmin為一個適當?shù)叵鄬Ρ容^小的數(shù)，它可用下面方法之一來選取：

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

?進化到當前代為止的最小目標函數(shù)值。

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

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

?進化到當前代為止的最大目標函數(shù)值。

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

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

iff(X)Cmax0

iff(X)

Cmax29當前29頁，總共70頁。2.2.3比例選擇算子 指個體被選中并遺傳到下一代群體中的概率與該個體的適應度大小成正比。 pi=fi/fi(i=1,2,…,M)

式中pi——個體i被選中的概率；fi——個體i的適應度；

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

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

單點交叉運算的示例如下所示:

單點交叉A；1011011100A’：1011011111B：0001110011B’：0001110000

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

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

Ⅰ.對個體的每一個基因座，依變異概率pm指定其為變異點。

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

基本位變異運算的示例如下所示：

A：1010101010A’：1010001010

變異點基本位變異32當前32頁，總共70頁。變異是針對個體的某一個或某一些基因座上的基因值執(zhí)行的，因此變異概率pm

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

l——個體中基因串長度。Pm=BM·l

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

j=M?

j=pc·M?

j=pm·L·M?Gen=Gen+1輸出結果終止YNYYYNNNpcpm34當前34頁，總共70頁。問題的提出一元函數(shù)求最大值：2.4簡單函數(shù)優(yōu)化實例35當前35頁，總共70頁。編碼表現(xiàn)型：x基因型：二進制編碼（串長取決于求解精度）

按編碼原理：假設要求求解精度到6位小數(shù)，區(qū)間長度為2-(-1)＝3，即需將區(qū)間分為3/0.000001=3×106等份。 所以編碼的二進制串長應為22位。36當前36頁，總共70頁。產(chǎn)生初始種群產(chǎn)生的方式：隨機產(chǎn)生的結果：長度為22的二進制串產(chǎn)生的數(shù)量：種群的大小（規(guī)模），如30，50，………37當前37頁，總共70頁。計算適應度 直接用目標函數(shù)作為適應度函數(shù)①解碼：將個體s轉化為[-1,2]區(qū)間的實數(shù)：

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

f(x)=xsin(10πx)+2.0=2.58634538當前38頁，總共70頁。遺傳操作選擇：比例選擇法；交叉：單點交叉；變異：小概率變異39當前39頁，總共70頁。模擬結果

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

得到的最佳個體：smaxxmax=1.8506;f(xmax)=3.8503;40當前40頁，總共70頁。模擬結果

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

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

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

52當前52頁，總共70頁。選擇策略預選擇機制、排擠機制、分享機制；預選擇（preselection,1970）機制當子個體的適應度超過其父個體適應度時，子個體才可以替代父個體，否則父個體仍保留；有效維持種群多樣性，造就小生境進化環(huán)境。4.3.3基于小生境技術的遺傳算法

53當前53頁，總共70頁。排擠（crowding,1975）機制設置排擠因子CF（CF=2或3），隨機選取1/CF個個體組成排擠成員，排擠與其相似（用距離來度量）的個體；個體之間的相似性可用個體編碼串之間的海明距離來度量。4.3.3基于小生境技術的遺傳算法

54當前54頁，總共70頁。共享（sharing,1987）機制通過個體之間的相似性程度的共享函數(shù)來調整各個體的適應度；共享函數(shù)的目的：將搜索空間的多個峰值在地理上區(qū)分開來，每一個峰值處接受一定比例數(shù)目的個體，比例數(shù)目與峰值高度有關；4.3.3基于小生境技術的遺傳算法

55當前55頁，總共70頁。共享（sharing,1987）機制共享函數(shù)的值越大，表明個體之間越相似，記為Sh(dij)，dij為兩個個體i和j之間的距離；

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

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

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