遺傳算法與多目標(biāo)優(yōu)化

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

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

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

編碼

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

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

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

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

適應(yīng)度函數(shù)

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

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

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

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

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