【文章內(nèi)容簡(jiǎn)介】 法 ? 二進(jìn)制編碼與浮點(diǎn)數(shù)編碼的比較 ? 在交叉操作時(shí)，二進(jìn)制編碼比浮點(diǎn)數(shù)編碼產(chǎn)生新個(gè)體的可能性多，而且產(chǎn)生的新個(gè)體不受父?jìng)€(gè)體所構(gòu)成的超體的限制； ? 在變異操作時(shí)，二進(jìn)制編碼的種群穩(wěn)定性比浮點(diǎn)數(shù)編碼差。 遺傳基因型 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 46 基本遺傳算法 ? 適應(yīng)度函數(shù)的重要性 適應(yīng)度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。 一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的，對(duì)目標(biāo)函數(shù)值域的某種映射變換稱(chēng)為適應(yīng)度的 尺度變換 （ fitness scaling）。 適應(yīng)度函數(shù)及其尺度變換 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 47 基本遺傳算法 ? 適應(yīng)度函數(shù)的設(shè)計(jì) ? 單值、連續(xù)、非負(fù)、最大化 ? 合理、一致性（能夠反映解的優(yōu)劣） ? 計(jì)算量小 ? 通用性強(qiáng) 適應(yīng)度函數(shù)及其尺度變換 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 48 基本遺傳算法 ? 幾種常見(jiàn)的適應(yīng)度函數(shù) ? 直接轉(zhuǎn)換 若目標(biāo)函數(shù)為最大化問(wèn)題： Fit ( f (x) )= f (x) 若目標(biāo)函數(shù)為最小化問(wèn)題： Fit ( f (x) )= f (x) 適應(yīng)度函數(shù)及其尺度變換 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 49 基本遺傳算法 ? 幾種常見(jiàn)的適應(yīng)度函數(shù) ? 界限構(gòu)造法 1 若目標(biāo)函數(shù)為最大化問(wèn)題： 若目標(biāo)函數(shù)為最小化問(wèn)題： 適應(yīng)度函數(shù)及其尺度變換 的最小估計(jì)值。為式中，其他)( ,0)( ,)())((m i nm i nm i nxfccxfcxfxfF i t??? ???的最大估計(jì)值。為式中，其他)( ,0)( ),())((m a xm a xm a xxfccxfxfcxfF i t??? ???智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 50 基本遺傳算法 ? 幾種常見(jiàn)的適應(yīng)度函數(shù) ? 界限構(gòu)造法 2 若目標(biāo)函數(shù)為最大化問(wèn)題： 若目標(biāo)函數(shù)為最小化問(wèn)題： c為目標(biāo)函數(shù)的保守估計(jì)值。 適應(yīng)度函數(shù)及其尺度變換 0)(,0 )(1 1))(( ?????? xfccxfcxfF i t0)(,0 )(1 1))(( ?????? xfccxfcxfF i t智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 51 基本遺傳算法 ? 適應(yīng)度函數(shù)的作用 適應(yīng)度函數(shù)設(shè)計(jì)不當(dāng)有可能出現(xiàn)欺騙問(wèn)題： （ 1）進(jìn)化初期，個(gè)別超常個(gè)體控制選擇過(guò)程； （ 2）進(jìn)化末期，個(gè)體差異太小導(dǎo)致陷入局部極值。 適應(yīng)度函數(shù)及其尺度變換 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 52 基本遺傳算法 ? 適應(yīng)度函數(shù)的線(xiàn)性變換法 f’=α*f+β 系數(shù)的確定滿(mǎn)足以下條件： ① f’avg= favg ② f’max= cmult f’avg cmult =~， α和 β取適當(dāng)值，以保證適應(yīng)度值非負(fù)。 適應(yīng)度函數(shù)及其尺度變換 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 53 基本遺傳算法 ? 適應(yīng)度函數(shù)的冪函數(shù)變換法 f’= f k k與所求優(yōu)化問(wèn)題相關(guān) 適應(yīng)度函數(shù)及其尺度變換 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 900 . 10 . 20 . 30 . 40 . 50 . 60 . 70 . 80 . 91k 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 54 基本遺傳算法 ? 適應(yīng)度函數(shù)的指數(shù)變換法 f’= eaf a決定了復(fù)制的強(qiáng)制性。 a越大，大適應(yīng)度的個(gè)體被復(fù)制的強(qiáng)制性就越弱。 適應(yīng)度函數(shù)及其尺度變換 1 2 3 4 5 6 7 8 9 1000 . 10 . 20 . 30 . 40 . 50 . 60 . 70 . 80 . 91ff 39。α 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 55 基本遺傳算法 ? 幾個(gè)概念 ? 選擇壓力（ selection pressure） :最佳個(gè)體選中的概率與平均個(gè)體選中概率的比值； ? 偏差（ bias）：個(gè)體正規(guī)化適應(yīng)度與其期望再生概率的絕對(duì)差值； ? 個(gè)體擴(kuò)展（ spread）：?jiǎn)蝹€(gè)個(gè)體子代個(gè)數(shù)的范圍； ? 多樣化損失（ loss of diversity）：在選擇階段未選中個(gè)體數(shù)目占種群的比例； 遺傳操作 ——選擇 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 56 基本遺傳算法 ? 幾個(gè)概念 ? 選擇強(qiáng)度（ selection intensity） :將正規(guī)高斯分布應(yīng)用于選擇方法，期望平均適應(yīng)度； ? 選擇方差（ selection variance）：將正規(guī)高斯分布應(yīng)用于選擇方法，期望種群適應(yīng)度的方差。 遺傳操作 ——選擇 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 57 基本遺傳算法 ? 個(gè)體選擇概率的常用分配方法 ? 按比例的適應(yīng)度分配（ proportional fitness assignment） 某個(gè)體 i，其適應(yīng)度為 fi，則其被選取的概率 Pi為： 如果尺度變換不合適， 可能造成早熟。 遺傳操作 ——選擇 ??? MikikiiffP1個(gè)體 f f2 P 1 2 3 4 5 6 7 8 9 10 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 58 基本遺傳算法 ? 個(gè)體選擇概率的常用分配方法 ? 基于排序的適應(yīng)度分配（ rankbased fitness assignment） 線(xiàn)性排序（ by Baker） μ為種群大小， i為個(gè)體序號(hào)， ηmax代表選擇壓力。 遺傳操作 ——選擇 m a xm i nm a xm i nm a xm a x 2,21],11)([1 ???????? ?????????? iPi智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 59 基本遺傳算法 ? 個(gè)體選擇概率的常用分配方法 ? 基于排序的適應(yīng)度分配（ rankbased fitness assignment） 非線(xiàn)性排序（ by Michalewicz） i為個(gè)體序號(hào)， c為排序第一的個(gè)體的選擇概率。 遺傳操作 ——選擇 1)1( ??? ii ccP智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 60 基本遺傳算法 ? 常用選擇方法 ? 輪盤(pán)賭選擇法（ roulette wheel selection） 遺傳操作 ——選擇 個(gè)體 1 2 3 4 5 6 7 8 9 10 11 適應(yīng)度 選擇概率 累計(jì)概率 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 61 基本遺傳算法 ? 常用選擇方法 ? 隨機(jī)遍歷抽樣法（ stochastic universal sampling） 遺傳操作 ——選擇 個(gè)體 1 2 3 4 5 6 7 8 9 10 11 適應(yīng)度 選擇概率 累計(jì)概率 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 62 基本遺傳算法 ? 常用選擇方法 ? 局部選擇法（ local selection） (1)線(xiàn)形鄰集 遺傳操作 ——選擇 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 63 基本遺傳算法 ? 常用選擇方法 ? 局部選擇法（ local selection） (2)兩對(duì)角鄰集 遺傳操作 ——選擇 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 64 基本遺傳算法 ? 常用選擇方法 ? 局部選擇法（ local selection） (2)兩對(duì)角鄰集 遺傳操作 ——選擇 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 65 基本遺傳算法 ? 常用選擇方法 ? 截?cái)噙x擇法（ truncation selection） 個(gè)體按適應(yīng)度排列，只有優(yōu)秀個(gè)體能夠成為父?jìng)€(gè)體，參數(shù)為截?cái)嚅撝担ū贿x作父?jìng)€(gè)體的百分比）。 遺傳操作 ——選擇 截?cái)嚅撝? 1％ 10％ 20％ 40％ 50％ 80％ 選擇強(qiáng)度 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 66 基本遺傳算法 ? 常用選擇方法 ? 錦標(biāo)賽選擇法（ tournament selection） 隨機(jī)從種群中挑選一定數(shù)目個(gè)體（競(jìng)賽規(guī)模），其中最好的個(gè)體作為父?jìng)€(gè)體，此過(guò)程重復(fù)進(jìn)行完成個(gè)體的選擇。 遺傳操作 ——選擇 競(jìng)賽規(guī)模 1 2 3 5 10 30 選擇強(qiáng)度 0 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 67 基本遺傳算法 ? 常用選擇方法 ? 早熟現(xiàn)象 ——適應(yīng)度高的個(gè)體迅速繁殖，使搜索過(guò)程過(guò)早結(jié)束； ? 種群中個(gè)體的適應(yīng)度接近，導(dǎo)致進(jìn)化過(guò)程陷入局部最優(yōu)點(diǎn)； ? 基本遺傳算法達(dá)到收斂的代數(shù)與選擇強(qiáng)度成反比，較高的選擇強(qiáng)度是很好的選擇方法，但太高會(huì)導(dǎo)致收斂過(guò)快。 遺傳操作 ——選擇 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 68 基本遺傳算法 ? 實(shí)值重組 ? 離散重組 子個(gè)體的每個(gè)變量可以按等概率隨機(jī)地挑選父?jìng)€(gè)體。 遺傳操作 ——交叉 /基因重組 父?jìng)€(gè)體 1 12 25 5 父?jìng)€(gè)體 2 123 4 34 子個(gè)體 1 123 4 5 子個(gè)體 2 12 4 34 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 69 基本遺傳算法 ? 實(shí)值重組 ? 中間重組 子個(gè)體＝父?jìng)€(gè)體 1＋ α （父?jìng)€(gè)體 2－父?jìng)€(gè)體 1） α是比例因子，由 [d,1+d]上均勻分布地隨機(jī)數(shù)產(chǎn)生。 d=0時(shí)為中間重組，一般取 d=。 子代的每個(gè)變量均產(chǎn)生一個(gè) α 。 遺傳操作 ——交叉 /基因重組 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 70 基本遺傳算法 ? 實(shí)值重組 ? 中間重組 遺傳操作 ——交叉 /基因重組 父?jìng)€(gè)體 1 12 25 5 父?jìng)€(gè)體 2 123 4 34 子個(gè)體 1 子個(gè)體 2 α值樣本 1 α值樣本 2 12＋ （ 123－ 12） = 25＋ （ 4－ 25） = 12＋ （ 123－ 12） = 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 71 基本遺傳算法 ? 實(shí)值重組 ? 中間重組 遺傳操作 ——交叉 /基因重組 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 72 基本遺傳算法 ? 實(shí)值重組 ? 線(xiàn)性重組 遺傳操作 ——交叉 /基因重組 父?jìng)€(gè)體 1 12 25