【正文】 基本遺傳算法 ? 實值變異 一般采用： ? 二進制變異 遺傳操作 ——變異 為變量的取值范圍。 子代的每個變量均產(chǎn)生一個 α 。 遺傳操作 ——交叉 /基因重組 父個體 1 12 25 5 父個體 2 123 4 34 子個體 1 123 4 5 子個體 2 12 4 34 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 69 基本遺傳算法 ? 實值重組 ? 中間重組 子個體＝父個體 1＋ α （父個體 2－父個體 1） α是比例因子，由 [d,1+d]上均勻分布地隨機數(shù)產(chǎn)生。 遺傳操作 ——選擇 競賽規(guī)模 1 2 3 5 10 30 選擇強度 0 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 67 基本遺傳算法 ? 常用選擇方法 ? 早熟現(xiàn)象 ——適應(yīng)度高的個體迅速繁殖，使搜索過程過早結(jié)束； ? 種群中個體的適應(yīng)度接近，導(dǎo)致進化過程陷入局部最優(yōu)點； ? 基本遺傳算法達到收斂的代數(shù)與選擇強度成反比，較高的選擇強度是很好的選擇方法，但太高會導(dǎo)致收斂過快。 遺傳操作 ——選擇 1)1( ??? ii ccP智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 60 基本遺傳算法 ? 常用選擇方法 ? 輪盤賭選擇法（ roulette wheel selection） 遺傳操作 ——選擇 個體 1 2 3 4 5 6 7 8 9 10 11 適應(yīng)度 選擇概率 累計概率 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 61 基本遺傳算法 ? 常用選擇方法 ? 隨機遍歷抽樣法（ stochastic universal sampling） 遺傳操作 ——選擇 個體 1 2 3 4 5 6 7 8 9 10 11 適應(yīng)度 選擇概率 累計概率 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 62 基本遺傳算法 ? 常用選擇方法 ? 局部選擇法（ local selection） (1)線形鄰集 遺傳操作 ——選擇 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 63 基本遺傳算法 ? 常用選擇方法 ? 局部選擇法（ local selection） (2)兩對角鄰集 遺傳操作 ——選擇 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 64 基本遺傳算法 ? 常用選擇方法 ? 局部選擇法（ local selection） (2)兩對角鄰集 遺傳操作 ——選擇 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 65 基本遺傳算法 ? 常用選擇方法 ? 截斷選擇法（ truncation selection） 個體按適應(yīng)度排列，只有優(yōu)秀個體能夠成為父個體，參數(shù)為截斷閾值（被選作父個體的百分比）。 遺傳操作 ——選擇 ??? MikikiiffP1個體 f f2 P 1 2 3 4 5 6 7 8 9 10 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 58 基本遺傳算法 ? 個體選擇概率的常用分配方法 ? 基于排序的適應(yīng)度分配（ rankbased fitness assignment） 線性排序（ by Baker） μ為種群大小， i為個體序號， ηmax代表選擇壓力。α 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 55 基本遺傳算法 ? 幾個概念 ? 選擇壓力（ selection pressure） :最佳個體選中的概率與平均個體選中概率的比值； ? 偏差（ bias）：個體正規(guī)化適應(yīng)度與其期望再生概率的絕對差值； ? 個體擴展（ spread）：單個個體子代個數(shù)的范圍； ? 多樣化損失（ loss of diversity）：在選擇階段未選中個體數(shù)目占種群的比例； 遺傳操作 ——選擇 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 56 基本遺傳算法 ? 幾個概念 ? 選擇強度（ selection intensity） :將正規(guī)高斯分布應(yīng)用于選擇方法，期望平均適應(yīng)度； ? 選擇方差（ selection variance）：將正規(guī)高斯分布應(yīng)用于選擇方法，期望種群適應(yīng)度的方差。 a越大，大適應(yīng)度的個體被復(fù)制的強制性就越弱。 適應(yīng)度函數(shù)及其尺度變換 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 52 基本遺傳算法 ? 適應(yīng)度函數(shù)的線性變換法 f’=α*f+β 系數(shù)的確定滿足以下條件： ① f’avg= favg ② f’max= cmult f’avg cmult =~， α和 β取適當(dāng)值，以保證適應(yīng)度值非負。為式中，其他)( ,0)( ),())((m a xm a xm a xxfccxfxfcxfF i t??? ???智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 50 基本遺傳算法 ? 幾種常見的適應(yīng)度函數(shù) ? 界限構(gòu)造法 2 若目標(biāo)函數(shù)為最大化問題： 若目標(biāo)函數(shù)為最小化問題： c為目標(biāo)函數(shù)的保守估計值。 適應(yīng)度函數(shù)及其尺度變換 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 47 基本遺傳算法 ? 適應(yīng)度函數(shù)的設(shè)計 ? 單值、連續(xù)、非負、最大化 ? 合理、一致性（能夠反映解的優(yōu)劣） ? 計算量小 ? 通用性強 適應(yīng)度函數(shù)及其尺度變換 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 48 基本遺傳算法 ? 幾種常見的適應(yīng)度函數(shù) ? 直接轉(zhuǎn)換 若目標(biāo)函數(shù)為最大化問題： Fit ( f (x) )= f (x) 若目標(biāo)函數(shù)為最小化問題： Fit ( f (x) )= f (x) 適應(yīng)度函數(shù)及其尺度變換 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 49 基本遺傳算法 ? 幾種常見的適應(yīng)度函數(shù) ? 界限構(gòu)造法 1 若目標(biāo)函數(shù)為最大化問題： 若目標(biāo)函數(shù)為最小化問題： 適應(yīng)度函數(shù)及其尺度變換 的最小估計值。 遺傳基因型 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 46 基本遺傳算法 ? 適應(yīng)度函數(shù)的重要性 適應(yīng)度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。 遺傳基因型 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 44 基本遺傳算法 ? 多種編碼方式 ? 二進制編碼； ? 浮點數(shù)編碼； ? 格雷碼編碼； ? 符號編碼； ? 復(fù)數(shù)編碼； ? DNA編碼等。 f(xmax)=。 得到的最佳個體 ： smax=1111001100111011111100。)2()( 10210202021 xbbbbiii ??? ???12)1(239。 所以編碼的二進制串長應(yīng)為 22位。 x19即為區(qū)間 [1,2]內(nèi)的最大值點： 此時，函數(shù)最大值 f(x19)比 f()=。即的實數(shù)遞減序列。 遺傳算法的應(yīng)用 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 31 遺傳算法簡介 ? 人工生命 基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)，遺傳算法已在其進化模型、學(xué)習(xí)模型、行為模型等方面顯示了初步的應(yīng)用能力； ? 遺傳程序設(shè)計 Koza發(fā)展了遺傳程序設(shè)計的慨念，他使用了以LISP語言所表示的編碼方法，基于對一種樹型結(jié)構(gòu)所進行的遺傳操作自動生成計算機程序。 遺傳算法的應(yīng)用 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 30 遺傳算法簡介 ? 機器人智能控制 遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學(xué)求解、細胞機器人的結(jié)構(gòu)優(yōu)化和行動協(xié)調(diào)等 。 ? 組合優(yōu)化 實踐證明，遺傳算法對于組合優(yōu)化中的 NP完全問題非常有效 。 ? 本質(zhì)并行性 內(nèi)在并行性與內(nèi)含并行性 ? 不需求導(dǎo) 只需目標(biāo)函數(shù)和適應(yīng)度函數(shù) ? 概率轉(zhuǎn)換規(guī)則 強調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)換規(guī)則 遺傳算法的思路與特點 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 17 遺傳算法簡介 ? 簡單實例 1. 產(chǎn)生初始種群 2. 計算適應(yīng)度 遺傳算法的基本操作 0001100000 0101111001 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 （ 8） （ 5） （ 2） （ 10） （ 7） （ 12） （ 5） （ 19） （ 10） （ 14） 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 18 遺傳算法簡介 ? 簡單實例 3. 選擇 遺傳算法的基本操作 個體 染色體 適應(yīng)度 選擇概率 累積概率 1 0001100000 8 2 0101111001 5 3 0000000101 2 4 1001110100 10 5 1010101010 7 6 1110010110 12 7 1001011011 5 8 1100000001 19 9 1001110100 10 10 0001010011 14 8 8＋ 5＋ 2＋ 10＋ 7＋ 12＋ 5＋ 19＋ 10＋ 14 5 8＋ 5＋ 2＋ 10＋ 7＋ 12＋ 5＋ 19＋ 10＋ 14 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 19 遺傳算法簡介 ? 簡單實例 3. 選擇 遺傳算法的基本操作 個體 染色體 適應(yīng)度 選擇概率 累積概率 1 0001100000 8 2 0101111001 5 3 0000000101 2 4 1001110100 10 5 1010101010 7 6 1110010110 12 7 1001011011 5 8 1100000001 19 9 1001110100 10 10 0001010011 14 智能優(yōu)化計算 華東理工大學(xué)自動化系 2022年 20 遺傳算法簡介 ? 簡單實例 3. 選擇 在 0～ 1之間產(chǎn)生一個 隨機數(shù)： 遺傳算法的基本操作 個體 染色體 適應(yīng)度 選擇概率 累積概率 1 0001100000 8 2 0101111001 5 3 0000000101 2 4 1001110100 10 5 1010101010 7 6 1110010110