現(xiàn)代優(yōu)化算法(編輯修改稿)
2025-09-11 23:02 本頁面
【文章內(nèi)容簡介】 過程中，有時會產(chǎn)生一些超常的個體，這些個體因競爭力太突出而控制了選擇運算過程，從而影響算法的全局優(yōu)化性能，導(dǎo)致算法獲得某個局部最優(yōu)解。 遺傳算法的改進途徑 （ 1） 對編碼方式的改進 （ 2） 對遺傳算子 的改進 （ 3） 對控制參數(shù)的改進 （ 4） 對執(zhí)行策略的改進 對編碼方式的改進 二進制編碼優(yōu)點在于編碼 、 解碼操作簡單 ， 交叉 、 變異等操作便于實現(xiàn) ， 缺點在于精度要求較高時 ， 個體編碼串較長 ，使算法的搜索空間急劇擴大 ， 遺傳算法的性能降低 。 格雷編碼克服了二進制編碼的不連續(xù)問題 ， 浮點數(shù)編碼改善了遺傳算法的計算復(fù)雜性 。 對遺傳算子 的改進 排序選擇 均勻交叉 逆序變異 （ 1） 對群體中的所有個體按其適應(yīng)度大小進行降序排序； （ 2） 根據(jù)具體求解問題，設(shè)計一個概率分配表，將各個概率值按上述排列次序分配給各個個體； （ 3） 以各個個體所分配到的概率值作為其遺傳到下一代的概率，基于這些概率用賭盤選擇法來產(chǎn)生下一代群體。 對遺傳算子 的改進 排序選擇 均勻交叉 逆序變異 （ 1） 隨機產(chǎn)生一個與個體編碼長度相同的二進制屏蔽字 P = W1W2… Wn ； （ 2） 按下列規(guī)則從 A、 B兩個父代個體中產(chǎn)生兩個新個體 X、 Y：若 Wi = 0，則 X的第i個基因繼承 A的對應(yīng)基因， Y的第 i個基因繼承 B的對應(yīng)基因；若 Wi = 1，則 A、 B的第 i個基因相互交換，從而生成 X、Y的第 i個基因。 對遺傳算子 的改進 排序選擇 均勻交叉 逆序變異 變異前： 3 4 8 | 7 9 6 5 | 2 1 變異前： 3 4 8 | 5 6 9 7 | 2 1 對控制參數(shù)的改進 Schaffer建議的最優(yōu)參數(shù)范圍是： M = 20100， T = 100500， Pc = ， Pm = 。 對控制參數(shù)的改進 Srinvivas等人提出自適應(yīng)遺傳算法，即 PC和Pm能夠隨適應(yīng)度自動改變，當(dāng)種群的各個個體適應(yīng)度趨于一致或趨于局部最優(yōu)時，使二者增加，而當(dāng)種群適應(yīng)度比較分散時，使二者減小，同時對適應(yīng)值高于群體平均適應(yīng)值的個體，采用較低的 PC和 Pm，使性能優(yōu)良的個體進入下一代，而低于平均適應(yīng)值的個體，采用較高的 PC和 Pm，使性能較差的個體被淘汰 。 對執(zhí)行策略的改進 混合遺傳算法 免疫遺傳算法 小生境遺傳算法 單親遺傳算法 并行遺傳算法 三、遺傳算法的應(yīng)用 遺傳算法的應(yīng)用領(lǐng)域 遺傳算法的應(yīng)用示例 遺傳算法的應(yīng)用領(lǐng)域 （ 1）組合優(yōu)化 （ 2）函數(shù)優(yōu)化 （ 3）自動控制 （ 4）生產(chǎn)調(diào)度 （ 5）圖像處理 （ 6）機器學(xué)習(xí) （ 7）人工生命 （ 8）數(shù)據(jù)挖掘 遺傳算法應(yīng)用于組合優(yōu)化 隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在計算機上用枚舉法很難甚至不可能求出其最優(yōu)解。實踐證明，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、布局優(yōu)化、網(wǎng)絡(luò)路由等具有 NP難度的組合優(yōu)化問題上取得了成功的應(yīng)用。 模擬退火算法 (simulated annealing,簡稱 SA)的思想最早是由 Metropolis等 (1953)提出的，1983年 Kirkpatrick等將其用于組合優(yōu)化。SA算法是基于 Monte Carlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。 模擬退火算法 模擬退火算法在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)解。模擬退火算法是一種通用的優(yōu)化算法，目前已在工程中得到了廣泛應(yīng)用。 物理退火過程和 Metropolis準(zhǔn)則 簡單而言 ， 物理退火過程由以下三部分組成： ⑴加溫過程。其目的是增強粒子的熱運動，使其偏離平衡位置。當(dāng)溫度足夠高時，固體將溶解為液體，從而消除系統(tǒng)原先可能存在的非均勻態(tài)，使隨后進行的冷卻過程以某一平衡態(tài)為起點。溶解過程與系統(tǒng)的熵增過程聯(lián)系，系統(tǒng)能量也隨溫度的升高而增大。 ⑵ 等溫過程 。 物理學(xué)的知識告訴我們 ， 對于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng) ， 系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進行 ， 當(dāng)自由能達(dá)到最小時 ， 系統(tǒng)達(dá)到平衡態(tài) 。 ⑶冷卻過程。目的是使粒子的熱運動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。 Metropolis等在 1953年提出了重要性采樣法，即以概率接受新狀態(tài)。具體而言，在溫度 t,由當(dāng)前狀態(tài) i產(chǎn)生新狀態(tài) j，兩者的能量分別為 ，若 則接受新狀態(tài) j為當(dāng)前狀態(tài)；否則，若概率 大于 區(qū)間內(nèi)的隨機數(shù)則仍舊接受新狀態(tài)j為當(dāng)前狀態(tài)，若不成立則保留 i為當(dāng)前狀態(tài)，其中 k為 Boltzmann常數(shù)。 ji EE 和 ij E
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1