【正文】 第四章 遺傳算法（續(xù)） 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 遺傳算法簡(jiǎn)介 遺傳算法的產(chǎn)生與發(fā)展 生物進(jìn)化理論和遺傳學(xué)的基本知識(shí) 遺傳算法的思路與特點(diǎn) 遺傳算法的基本操作 遺傳算法的應(yīng)用 基本遺傳算法 簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例 遺傳基因型 適應(yīng)度函數(shù)及其尺度變換 遺傳操作 —— 選擇 遺傳操作 —— 交叉 /基因重組 遺傳操作 —— 變異 算法的設(shè)計(jì)與實(shí)現(xiàn) 模式定理 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 遺傳算法的改進(jìn) CHC算法 自適應(yīng)遺傳算法 基于小生境技術(shù)的遺傳算法 遺傳算法的應(yīng)用 解決帶約束的函數(shù)優(yōu)化問(wèn)題 解決多目標(biāo)優(yōu)化問(wèn)題 解決組合優(yōu)化問(wèn)題 遺傳算法在過(guò)程建模中的應(yīng)用 遺傳算法在模式識(shí)別中的應(yīng)用 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 改進(jìn)的途徑 ? 改變遺傳算法的組成成分； ? 采用混合遺傳算法； ? 采用動(dòng)態(tài)自適應(yīng)技術(shù)； ? 采用非標(biāo)準(zhǔn)的遺傳操作算子； ? 采用并行遺傳算法等。 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 改進(jìn)思路 ? 1991年 Eshelman提出的一種改進(jìn)遺傳算法； ? C：跨世代精英選擇（ Cross generational elitist selection）策略； ? H：異物種重組（ Heterogeneous rebination）； ? C：大變異（ Cataclysmic mutation）。 CHC算法 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 選擇 ? 上一代種群與通過(guò)新的交叉方法產(chǎn)生的個(gè)體群混合起來(lái)，從中按一定概率選擇較優(yōu)的個(gè)體； ? 即使交叉操作產(chǎn)生較劣個(gè)體偏多，由于原種群大多數(shù)個(gè)體殘留，不會(huì)引起個(gè)體的評(píng)價(jià)值降低； ? 可以更好地保持遺傳多樣性； ? 排序方法，克服比例適應(yīng)度計(jì)算的尺度問(wèn)題。 CHC算法 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 交叉 ? 均勻交叉的改進(jìn)：當(dāng)兩個(gè)父?jìng)€(gè)體位值相異的位數(shù)為m時(shí)，從中隨機(jī)選取 m/2個(gè)位置，實(shí)行父?jìng)€(gè)體位值的交換； ? 確定一閾值，當(dāng)個(gè)體間距離低于該閾值時(shí)，不進(jìn)行交叉操作。進(jìn)化收斂的同時(shí)，逐漸地減小該閾值。 CHC算法 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 變異 ? 在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定收斂時(shí)期，從最優(yōu)個(gè)體中選擇一部分個(gè)體進(jìn)行初始化； ? 初始化：選擇一定比例（擴(kuò)散率，一般 ）的基因座，隨機(jī)地決定它們的位值。 CHC算法 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 參數(shù)分析 ? 交叉概率 Pc和變異概率 Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性； ? Pc越大，新個(gè)體產(chǎn)生的速度就越快，但過(guò)大會(huì)使優(yōu)秀個(gè)體的結(jié)構(gòu)很快被破壞； Pc過(guò)小，搜索過(guò)程緩慢，以至停止不前； ? Pm過(guò)小，不易產(chǎn)生新個(gè)體結(jié)構(gòu)， Pm過(guò)大，變成純粹的隨機(jī)搜索； 自適應(yīng)遺傳算法 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 自適應(yīng)策略 ? Srinvivas等提出一種自適應(yīng)遺傳算法， Pc和 Pm能夠隨適應(yīng)度自動(dòng)改變： ? 當(dāng)種群各個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使 Pc和 Pm增加；而當(dāng)群體適應(yīng)度比較分散時(shí)，使 Pc和 Pm減少； ? 對(duì)于適應(yīng)度較高的個(gè)體，對(duì)應(yīng)于較低的 Pc和 Pm ；而較低適應(yīng)度的個(gè)體，對(duì)應(yīng)于較高的 Pc和 Pm 。 自適應(yīng)遺傳算法 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 自適應(yīng)方法 fmax—— 群體中最大的適應(yīng)度值； favg—— 每代群體的平均適應(yīng)度值； f’—— 要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值； f—— 要交叉或變異的個(gè)體適應(yīng)度值； 自適應(yīng)遺傳算法 ????????????????????a vga vga vgma vga vga vgcffkffffffkPffkffffffkP ,)( ,)39。(4m a xm a x32m a xm a x1k k k k4 取 (0,1)的值 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 自適應(yīng)方法進(jìn)一步改進(jìn) ? 適用于進(jìn)化后期，不適于進(jìn)化前期，因?yàn)榍捌诘膬?yōu)秀個(gè)體有可能是局部最優(yōu)點(diǎn)； ? 使最大適應(yīng)度個(gè)體的交叉概率和變異概率由 0提高到 Pc2和 Pm2 ； ? 采用精英選擇策略； 自適應(yīng)遺傳算法 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 自適應(yīng)方法進(jìn)一步改進(jìn) 自適應(yīng)遺傳算法 , , , ,)()( ,)39。)((21211m a xm a x32111m a x211????????????????????????????mmcca v gma v ga v gmmmma v gca v ga v ga v gccccPPPPffPffffffkPPPPffPffffffPPPP 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 小生境概念 ? 小生境（ niche）：生物學(xué)中，特定環(huán)境中的一種組織功能； ? 在 SGA中，容易“近親繁殖”； ? NGA（ Niche Generic Algorithm），將每一代個(gè)體劃分為若干類，每類選出優(yōu)秀個(gè)體組成一個(gè)種群； ? 優(yōu)勢(shì)：保持解的多樣性，提高全局搜索能力，適合復(fù)雜多峰函數(shù)的優(yōu)化。 基于小生境技術(shù)的遺傳算法 遺傳算法的改進(jìn) 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 ? 選擇策略 ? 預(yù)選擇機(jī)制、排擠機(jī)制、分享機(jī)制； ? 預(yù)選擇（ preselection,1970）機(jī)制 ? 當(dāng)子個(gè)體的適應(yīng)度超過(guò)其父?jìng)€(gè)體適應(yīng)度時(shí)，子個(gè)體才可以替代父?jìng)€(gè)體，否則父?jìng)€(gè)體仍保留； ? 有效維持種群多樣性，造就小生境進(jìn)化環(huán)境。 基于小生境技術(shù)的遺傳算法 遺傳算