遺傳算法簡介主要內容1、遺傳算法的原理和組成；2、遺傳算子；3、遺傳算法的實現(xiàn)；4、遺傳算法的數(shù)學理論；5、遺傳算法的應用。一、遺傳算法（Geneticalgorithm，GA）GA的尋優(yōu)機制

GA模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。

美國J.Holland教授1975年《自然界和人工系統(tǒng)的適應性》GA的組成（1）編碼（產生初始種群）（2）適應度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運行參數(shù)

編碼

GA是通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。GA通常使用二進制串進行編碼。編碼示例例1求下列一元函數(shù)的最大值：

x∈[-1,2]，求解結果精確到6位小數(shù)。由于區(qū)間長度為3，求解結果精確到6位小數(shù)可將自變量定義區(qū)間劃分為3×10^6等份。又因為2^21<3×10^6<2^22，所以本例的二進制編碼長度至少需要22位。本例的編碼過程實質上是將區(qū)間[-1，2]內對應的實數(shù)值轉化為一個二進制串（b21b20…b0）。幾個術語

基因型：1000101110110101000111表現(xiàn)型：0.637197編碼解碼個體（染色體）基因多維優(yōu)化如何編碼？缺點是什么？初始種群

GA可采用隨機方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量稱為種群規(guī)模。如何隨機生成？

適應度函數(shù)

遺傳算法對一個個體（解）的好壞用適應度函數(shù)值（通常為正實數(shù)）來評價，適應度函數(shù)值越大，解的質量越好。適應度函數(shù)是遺傳算法進化過程的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。適應度函數(shù)的編制影響求解效果選擇算子遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。GA中選擇算子可采用輪盤賭選擇方法。1、個體被選擇概率的計算被選擇概率00.1440.6360.69111234各個體被分配的區(qū)間2、輪盤賭選擇方法（或比例選擇算子）00.1440.6360.69111234各個體區(qū)間有序隨機數(shù)產生隨機數(shù)0.95010.23110.60680.48600.23110.48600.60680.95010.2311<0.144?否個體1落選0.2311<0.636?是個體2入選0.4806<0.636?是個體2入選0.6068<0.636?是個體2入選0.9501<0.636?否個體2落選0.9501<0.691?否個體3落選0.9501<1?是個體4入選最終選擇了3個個體2，1個個體43、輪盤賭選擇方法的實現(xiàn)步驟（1）計算群體中所有個體的適應度函數(shù)值（需要解碼）；（2）利用比例選擇算子的公式，計算每個個體被選中遺傳到下一代群體的概率；（3）采用模擬賭盤操作（即生成0到1之間的隨機數(shù)與每個個體遺傳到下一代群體的概率進行匹配）來確定各個個體是否遺傳到下一代群體中。交叉算子所謂交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用，是產生新個體的主要方法。GA中交叉算子可采用單點交叉算子。單點交叉運算示例交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點實數(shù)編碼如何交叉？如何決定哪對個體應交叉？變異算子所謂變異運算，是指依據(jù)變異概率Pm將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。GA中變異算子可采用基本位變異算子。基本位變異算子基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?。基本位變異算子的執(zhí)行過程變異前：000001110000000010000變異后：000001110001000010000變異點如何決定哪個個體變異？實數(shù)編碼個體如何變異？運行參數(shù)（1）M：種群規(guī)模（20-100）（2）T：遺傳運算的終止進化代數(shù)（100～500）（3）Pc：交叉概率（0.4～0.9）（4）Pm：變異概率（0.001～0.01）SGA的框圖產生初始群體是否滿足停止準則是輸出結果并結束計算個體適應度值比例選擇運算單點交叉運算基本位變異運算否產生新一代群體執(zhí)行M/2次遺傳算法的特點（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。二、遺傳算法的數(shù)學原理模式的概念個體編碼串適應度01110134101011340111002511100150平均適應度35.75個體編碼串適應度01110134111111981110015011101053平均適應度58.75第1代群體第2代群體?模式是指種群個體基因串中的相似樣板111***模式H中確定位置的個數(shù)稱為模式H的階，記作O(H)。例如O(10**1)=3。模式H中第一個確定位置和最后一個確定位置之間的距離稱為模式H的定義距，記作δ(H)。例如δ(10**1)=4。模式的階與定義距模式的階和定義距的含義模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的性質，而模式的定義距就反映了這種性質的差異。模式定理模式定理：具有低階、短定義距以及平均適應度高于種群平均適應度的模式在子代中呈指數(shù)增長。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了數(shù)學基礎。模式定理的含義從模式定理可看出，有高平均適應度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串數(shù)目，這主要是因為選擇使最好的模式有更多的復制，交叉算子不容易破壞高頻率出現(xiàn)的、短定義長的模式，而一般突變概率又相當小，因而它對這些重要的模式幾乎沒有影響。積木塊假設積木塊假設：遺傳算法通過短定義距、低階以及高平均適應度的模式（積木塊），在遺傳操作下相互結合，最終接近全局最優(yōu)解。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。三、遺傳算法的應用示例測試函數(shù)Pc=0.8;Pm=0.05;b=2;popSize=30;epochs=50;實數(shù)編碼GA運行結果四、多目標優(yōu)化簡介一、問題定義

具有多個目標函數(shù)。

各個函數(shù)之間在最優(yōu)化方向上存在沖突。往往需要人的參與。目標函數(shù)集要么是求極大，要么是求極小，兩者只能取其一。二、發(fā)展簡史法國經濟學家V.Pareto，1896年提出Von.Neumann和J.Morgenstern提出多目標決策問題，1944年T.C.Koopmans多目標最優(yōu)化問題，Pareto最優(yōu)解概念，1951年H.W.Kuhn和A.W.T.Tucker向量極值問題的Pareto最優(yōu)解的概念Z.Johnsen系統(tǒng)地提出了關于多目標決策問題的研究報告，1968年1由人來判斷（非Pareto機制）基本原則：通過加入決策者判斷，縮小多目標問題有效解集的范圍。2不由人來判斷(Paretooptimality)基本原則：多目標問題優(yōu)化解的自身特性來搜索多目標問題有效解集的范圍。三、多目標優(yōu)化的最優(yōu)性判斷

加權:由決策者決定每個目標函數(shù)不同的權重因子，將所有的目標函數(shù)整合為一個目標函數(shù)。

目標規(guī)劃：由決策者確定每個目標函數(shù)所能達到的目標值，然后將這些值作為附加的約束整合進問題中，從而優(yōu)化目標轉換為最大或最小化目標值和目標函數(shù)值之間的絕對偏差。由人來判斷四、Pareto最優(yōu)解概念占優(yōu)1、對于所有j=1,2,…,m，有不劣于2、至少存在一個優(yōu)于，有非劣解集（Non-dominatedset）在一組解P中，非劣解解集P’是指所有那些不被P中任何個體占優(yōu)的解組成的一組解。當P是整個搜索空間時，所得的非劣解集P’被稱為Pareto最優(yōu)解集。若目標函數(shù)中有沖突，則一般不存在唯一最優(yōu)解，而存在若干個可行解。Pareto最優(yōu)解示意圖Pareto最優(yōu)解不一定對其他所有解占優(yōu)，但是所有其他解都不能對它占優(yōu)。ABCXYf1f2解點A,B,C是Pareto最優(yōu)點APareto支配XCPareto支配YMin