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

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

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

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

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

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

6、）Pc ： 交叉概率 （0.40.9） （4）Pm ： 變異概率 （0.0010.01）產(chǎn)生初始群體產(chǎn)生初始群體是否滿足停止準(zhǔn)則是否滿足停止準(zhǔn)則是是輸出結(jié)果并結(jié)束輸出結(jié)果并結(jié)束計(jì)算個(gè)體適應(yīng)度值計(jì)算個(gè)體適應(yīng)度值比例選擇運(yùn)算比例選擇運(yùn)算單點(diǎn)交叉運(yùn)算單點(diǎn)交叉運(yùn)算基本位變異運(yùn)算基本位變異運(yùn)算否否產(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 中確定位置的個(gè)數(shù)稱為模式 H 的，記作O(H)。例如O(10*1)=3 。 模式 H 中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為模式 H 的，記作(H)。例如(10*1)=4 。 模式階用來(lái)反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會(huì)有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 模式定理：具有以及于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長(zhǎng)。 模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長(zhǎng)，為解釋遺傳算法機(jī)理

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

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

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

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