【正文】 表 62 均值和方差表 遺傳算法 懲罰函數(shù)法 種群 300 種群 200 初始懲罰因子 M=10 初始懲罰因子 M=1 最大值 最小值 均 值 方 差 我們將表 61 中的數(shù)據(jù)以圖的形式進(jìn)行表示，得到兩種算法取得最優(yōu)適應(yīng)度值的變化曲線，如下圖所示。 24 6 算法的 結(jié)果 分析 概述 在以上算法分析設(shè)計的基礎(chǔ)上，我們用 MATLAB 語言分別實(shí)現(xiàn)了求解非線性規(guī)劃問題的遺傳算法和 外點(diǎn) 罰函數(shù)法 。因?yàn)槲覀兯笫亲钚』瘑栴}，在龐大的種群和多次迭代過程中為方便找出局部最小值和全局最優(yōu)值，我們可以對每次結(jié)果進(jìn)行排序。程序中多處涉及到隨機(jī)數(shù)的生成，像一開始初始種群的生成，后面的選擇、交叉、變異的循環(huán)條件判斷，都有用到。 （ 10） 均勻變異實(shí)現(xiàn)變異過程。 （ 4）對 適值 e 從小到大排序，排序后的適值 記為 s， 并記錄變動情況 l。這里由于是對每個基因座 進(jìn)行變異操作，為了保證變異效果， Pm取值較大，為 。一般 根據(jù)問題規(guī)模而定，這里 我們?nèi)?300。 例如：對染色體 Chromosome=[1， 2， 3， 4， 5]進(jìn)行變異，從 1 號位基因開始，每次隨機(jī)產(chǎn)生一個隨機(jī)數(shù) x，若這個隨機(jī)數(shù) xPm，則進(jìn)行變異，在指定范圍內(nèi)隨機(jī)產(chǎn)生一個實(shí)數(shù) ，來替換掉 1 號基因位的值；若 xPm，則本次不進(jìn)行變異，繼續(xù)對 2 號位基因值進(jìn)行變異操作，直到 5 號位結(jié)束。常用的交叉有單點(diǎn)交叉，雙點(diǎn)、多點(diǎn)交叉等。 然后再 根據(jù)公式 （ ） ， 將 懲罰函數(shù) ??xp加入目標(biāo)函數(shù) ??xf ，也就是將 約束條件加入目標(biāo)函數(shù)，確定適應(yīng)度函數(shù) ??xeval [3][8]。對于極大化問題，取 ? ?? ???? ?? ，其他 可行，若 0 x0xpxp （ ） 令 ? ?maxxp和 ? ?minxf分別為現(xiàn)行種群中的 ??xp 的最大值和 ??xf 的最小值。我們希望給 b 較小懲罰。 Glover 和 Greenberg 建議的約束管理技術(shù)允許在搜索空間里的不可行 域中進(jìn)行搜索，這比將搜索限制在可行域內(nèi)的方法能更快地活的最優(yōu)解或獲得更好的最終解。Michalewicz 等則認(rèn)為對有非線性約束的優(yōu)化問題， 15%的替代率為最好。 對于許多組合優(yōu)化問題，構(gòu)造修復(fù)程序相對比較容易。 適應(yīng)度函數(shù)設(shè)計 1）滿足約束 由于對染色體作遺傳運(yùn)算時通常獲得不可行的后代，因此運(yùn)用遺傳算法解非線性規(guī)劃問題的核心問題是如何滿足約束的問題。 從非線性規(guī)劃的數(shù)學(xué)模型可知， 我們最終要求解的是 一組解 nxxx ,..., 21 ，其滿足約束條件，并使目標(biāo)函數(shù) ? ?nxxf ,...,1 達(dá)到最小值(或最大值 )。 （ 5）終止代數(shù) T。當(dāng) pop_size 取值較小時，可提高遺傳算法的運(yùn)算速度，卻降低了群體的多樣性，有可能會引起遺傳算法的早熟現(xiàn)象；當(dāng) pop_size 取值較大時，又會使遺傳算法的運(yùn)行效率降低。 以事先設(shè)定的變異概率 Pm來對這些基因座的基因值進(jìn)行變異。常用的配對策略是隨機(jī)配對，即將群體中的 M 個個體以隨機(jī)的方式組成 ? ?2/M 對配對個體組，交叉操作是在這些配對個體組中的兩個個體之間進(jìn)行的。選擇操作的主要目的是為了避免基因缺失、提高全局收斂性和計算效率。遺傳算法的一個特點(diǎn)是它僅使用所求問題的目標(biāo)函數(shù)值就可得到下一步的有關(guān)搜索信息。在遺傳算法中把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間 的轉(zhuǎn)換方法 稱為編碼。 13 （ 7）人工生命。 （ 4）自動控制。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進(jìn)行性能評價的常用算例。 遺傳運(yùn)算模擬了基因在每一代中創(chuàng)造新后代的繁殖過程，進(jìn)化運(yùn)算則是種群逐代更新的過程。生成的下一代染色體稱為后代。達(dá)爾文的自然選擇學(xué)說表明，遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。 （ 2） 假設(shè)已獲得迭代點(diǎn) 1?kX ，以 1?kX 為初始點(diǎn)，求解無約束問題 ),(min kMXF （ ） 設(shè)其最優(yōu)點(diǎn)為 kX 。 （ 3） 罰函數(shù)法在實(shí)際計算中的缺點(diǎn)是罰因子 M 的取值難于把握 ， 太小起不到懲罰作用 ； 太大則由于誤差的影響會導(dǎo)致錯誤 。簡言之，外點(diǎn)罰函數(shù)法的思想是：當(dāng)點(diǎn) DX? 時，設(shè)法加大不可行點(diǎn)處的函數(shù)值，使不可行點(diǎn)不能成為 ),( kMXF 在 nR 中的最優(yōu)解。 對于問題 （ ） ，構(gòu)造一函數(shù)為 )()(),( XMXfMXF kk ??? （ ） 其中， ? ? ? ? ))(()()()( 2121 XguXgXhX ili imj j ?? ?? ??? （ ） 在 （ ） 中， )(X? 又稱為懲罰函數(shù)， ??? ?? ??? .,0 ,0)( 時當(dāng) 時，當(dāng) DX DXX? （ ） .,2,10)(,1 0)(,0))(( liXg XgXgu i ii ????? ??? 時，當(dāng) 時，當(dāng) （ ） 7 0?kM 是一個逐漸增大的參數(shù)，稱為懲罰因子。對于靜態(tài)的最優(yōu)化問題，當(dāng)目標(biāo)函數(shù)或約束條件出現(xiàn)未知量的非線性函 數(shù)，且不便于線性化，或勉強(qiáng)線性化后會招致較大誤差時，就可應(yīng)用非線性規(guī)劃的方法去處理。它又分兩類，一類叫懲罰函數(shù)法，或稱外點(diǎn)法；另一類叫障礙函數(shù)法，或稱內(nèi)點(diǎn)法。 ② 牛頓法 ：收斂速度快，但不穩(wěn)定，計算也較困難。這類迭代算法可分為兩類。它也是針對單峰 函數(shù)的。實(shí)用非線性規(guī)劃問題要求整體解，而現(xiàn)有解法大多只是求出局部解。然后將各種限制條件加以抽象 ， 得出決策變量應(yīng)滿足的一些等式或 不等式，稱之為約束條件 [4]。 本文的主要 內(nèi)容 就是應(yīng)用 遺傳算法的基本思想，結(jié)合本次實(shí)驗(yàn)的實(shí)際情況，對基本遺傳算法 加以改進(jìn)，將遺傳算法應(yīng)用于求解非線 性規(guī)劃問題，形成 求解非線性規(guī)劃問題的遺傳算法 。傳統(tǒng)的解決非線性規(guī)劃問題的方法有多種，如 搜索法、梯度法、變尺度法、罰函數(shù)法、拉格朗日乘子法 、 可行方向法等， 雖然解法很多 ， 非線性規(guī)劃目前還沒有能適用于各種問題的算法 ， 各個方法都有自己特定的適用范圍。 SUMT Algorithm I 目 錄 1 概論 .................................................................................................................................. 1 背景介紹 ............................................................................................................... 1 非線性規(guī)劃簡介 ........................................................................................ 1 遺傳算法簡介 ............................................................................................ 1 研究內(nèi)容 ............................................................................................................... 2 2 非線 性規(guī)劃 ...................................................................................................................... 3 非線性規(guī)劃的概念 ............................................................................................... 3 非線性規(guī)劃的數(shù)學(xué)模型 ....................................................................................... 3 非線性規(guī)劃的求解方法 ....................................................................................... 4 一維最優(yōu)化方法 ........................................................................................ 4 無約束最優(yōu)化方法 .................................................................................... 4 約束最優(yōu)化方法 ........................................................................................ 5 非線性規(guī)劃的應(yīng)用 ............................................................................................... 5 3 傳統(tǒng)非線性規(guī)劃算法 —— 外點(diǎn)罰函數(shù)法 ...................................................................... 6 算法概述 ............................................................................................................... 6 算法描述 ............................................................................................................... 6 算法性能分析 ....................................................................................................... 7 外點(diǎn) 罰函數(shù) 法的程序設(shè)計 ................................................................................... 8 程序步驟 ..................................................................................................... 8 程序流程圖 ................................................................................................. 8 4 遺傳算法 ........................................................................................................................ 10 遺傳算法概述 ..................................................................................................... 10 遺傳算法的生物學(xué)基礎(chǔ) .......................................................................... 10 遺傳算法的一般結(jié)構(gòu) .............................................................................. 10 遺傳算法的特點(diǎn) ...................................................................................... 12 II 遺傳算法的應(yīng)用 ...................................................................................... 12 遺傳算法實(shí)現(xiàn)的關(guān)鍵技術(shù) ................................................................................. 13 5 求解非線性規(guī)劃問題的遺傳算法設(shè)計 .................................................................