遺傳算法與多目標優(yōu)化選編課件

1、1、遺傳算法的原理和組成；2、遺傳算子；3、遺傳算法的實現(xiàn)；4、遺傳算法的數(shù)學(xué)理論；5、遺傳算法的應(yīng)用。一、遺傳算法（一、遺傳算法（Genetic algorithm，GA） GA是通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。GA通常使用進行編碼。 編碼示例 例1 求下列一元函數(shù)的最大值： 0 . 2)10sin()(xxxf 由于區(qū)間長度為3，求解結(jié)果精確到6位小數(shù) 可將自變量定義區(qū)間劃分為3106等份。 又因為221 3106 222 ，所以本例的二進制編碼長度至少需要22位。 本例的編碼過程實質(zhì)上是將區(qū)間-1，2內(nèi)

2、對應(yīng)的實數(shù)值轉(zhuǎn)化為一個二進制串（b21b20b0）。 基因型：1000101110110101000111 表現(xiàn)型：0.637197 編碼解碼個體（染色體）基因 GA可采用生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量稱。 遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值（通常為正實數(shù)）來評價，。適應(yīng)度函數(shù)是遺傳算法進化過程的驅(qū)動力，也是進行自然選擇的唯一標準，它的設(shè)計應(yīng)結(jié)合求解問題本身的要求而定。 遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：的個體被到下一代群體中的；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個體，

3、遺傳到下一代群體。GA中選擇算子可采用選擇方法。 00.1440.6360.69111234各個體被分配的區(qū)間各個體被分配的區(qū)間00.1440.6360.69111234各個體區(qū)間各個體區(qū)間有序隨機數(shù)有序隨機數(shù)產(chǎn)生隨機數(shù)產(chǎn)生隨機數(shù)0.144 ? 否個體1落選0.636 ? 是個體2入選0.636 ? 是個體2入選0.636 ? 是個體2入選0.636 ? 否個體2落選0.691 ? 否個體3落選1 ? 是個體4入選 （1） 計算群體中所有個體的適應(yīng)度函數(shù)值（需要解碼）； （2） 利用比例選擇算子的公式，計算每個個體被選中遺傳到下一代群體的概率； （3） 采用模擬賭盤操作（即生成0到1之間的隨機

4、數(shù)與每個個體遺傳到下一代群體的概率進行匹配）來確定各個個體是否遺傳到下一代群體中。 所謂交叉運算，是指對兩個相互配兩個相互配對的染色體對的染色體依據(jù)交叉概率交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個新的個形成兩個新的個體體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。 GA中交叉算子可采用單點交叉算子。 交叉前： 00000 11100 交叉后： 00000 11100交叉點交叉點 所謂變異運算，是指依據(jù) Pm 將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產(chǎn)生新個體的輔助方法，它

5、決定了遺傳算法的，同時。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。 GA中變異算子可采用基本位變異算子。 基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)? 。 變異前： 00000111000 000010000 變異后： 00000111000 000010000變異點變異點 （1）M ： 種群規(guī)模（ 20-100 ） （2）T ： 遺傳運算的終止進化代數(shù) （100500） （3

6、）Pc ： 交叉概率 （0.40.9） （4）Pm ： 變異概率 （0.0010.01）產(chǎn)生初始群體產(chǎn)生初始群體是否滿足停止準則是否滿足停止準則是是輸出結(jié)果并結(jié)束輸出結(jié)果并結(jié)束計算個體適應(yīng)度值計算個體適應(yīng)度值比例選擇運算比例選擇運算單點交叉運算單點交叉運算基本位變異運算基本位變異運算否否產(chǎn)生新一代群體產(chǎn)生新一代群體執(zhí)行執(zhí)行M/2M/2次次 （1）群體搜索，易于并行化處理； （2）不是盲目窮舉，而是啟發(fā)式搜索； （3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。2221 maxxx 二、遺傳算法的數(shù)學(xué)原理二、遺傳算法的數(shù)學(xué)原理模式的概念01110134101011340111002500

7、135.750111013411111198001500105358.75 模式 H 中確定位置的個數(shù)稱為模式 H 的，記作O(H)。例如O(10*1)=3 。 模式 H 中第一個確定位置和最后一個確定位置之間的距離稱為模式 H 的，記作(H)。例如(10*1)=4 。 模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 模式定理：具有以及于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。 模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理

8、提供了數(shù)學(xué)基礎(chǔ)。 從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串數(shù)目，這主要是因為選擇使最好的模式有更多的復(fù)制，而一般突變概率又相當小，因而它對這些重要的模式幾乎沒有影響。 積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。 三、遺傳算法的應(yīng)用示例三、遺傳算法的應(yīng)用示例512511211cos1cos, maxiiixiiixiixxf0510

9、15202530354045501012141618202224262830epochFitness一、問題定義一、問題定義Tmfff)(),.,(),()(min21xxxxFJjhIigtsji,.,2 , 1 , 0)(,.,2 , 1 , 0)(. .xx具有多個目標函數(shù)。 各個函數(shù)之間在最優(yōu)化方向上存在沖突。 往往需要人的參與。 目標函數(shù)集要么是求極大，要么是求極小，兩者只能取其一。二、發(fā)展簡史二、發(fā)展簡史法國經(jīng)濟學(xué)家V. Pareto，1896年提出 Von. Neumann和J. Morgenstern提出多目標決策問題，1944年 T. C. Koopmans 多目標最優(yōu)化問題

10、 ，Pareto最優(yōu)解概念，1951年H. W. Kuhn和A. W. T. Tucker 向量極值問題的Pareto最優(yōu)解的概念Z. Johnsen系統(tǒng)地提出了關(guān)于多目標決策問題的研究報告， 1968年1 由人來判斷（非Pareto機制） 基本原則：通過加入決策者判斷，縮小多目標問題有效解集的范圍。2 不由人來判斷(Pareto optimality) 基本原則：多目標問題優(yōu)化解的自身特性來搜索多目標問題有效解集的范圍。三、多目標優(yōu)化的最優(yōu)性判斷三、多目標優(yōu)化的最優(yōu)性判斷 : 由決策者決定每個目標函數(shù)不同的權(quán)重因子，將所有的目標函數(shù)整合為一個目標函數(shù)。 ：由決策者確定每個目標函數(shù)所能達到的目

11、標值，然后將這些值作為附加的約束整合進問題中，從而優(yōu)化目標轉(zhuǎn)換為最大或最小化目標值和目標函數(shù)值之間的絕對偏差。四、四、Pareto最優(yōu)解概念最優(yōu)解概念1、對于所有j=1,2,m，有 1xjf2xjf不劣于2、至少存在一個 mj,.,2 , 1 1xjf2xjf優(yōu)于，有（Non-dominated set） 在一組解P中，非劣解解集P是指所有那些不被P中任何個體占優(yōu)的解組成的一組解。當P是整個搜索空間時，所得的非劣解集P被稱為Pareto最優(yōu)解集最優(yōu)解集。 若目標函數(shù)中有沖突，則一般不存在唯一最優(yōu)解，而存在若干個可行解。 Pareto最優(yōu)解不一定對其他所有解占優(yōu)，但是所有其他解都不能對它占優(yōu)。ABCXYf1f2解點解點A, B, C是是Pareto最優(yōu)點最優(yōu)點A