畢業(yè)論文-基于matlab的遺傳算法程序設(shè)計(jì)及優(yōu)化問題研究(編輯修改稿)

　

【文章內(nèi)容簡介】 傳操作的設(shè)計(jì)和控制參數(shù)的設(shè)定 ， 其具體內(nèi)容如下 ： (1)參數(shù)編碼 . 遺傳算法中常用的編碼方法是二進(jìn)制編碼 ， 它將問題空間的參數(shù)用字符集 {0， 1}構(gòu)成染色體位串 ， 符合最小字符集原則 ， 操作簡單 ， 便于用模式定理分析 . (2)適應(yīng)度函數(shù)的設(shè)計(jì) . 適應(yīng)度函數(shù)是評價(jià)個(gè)體適應(yīng)環(huán)境的能力 ， 使選擇操作的依據(jù) ， 是由目標(biāo)函數(shù)變換而成 . 對適應(yīng)度函數(shù)唯一的要求是其結(jié)果為非負(fù)值 . 適應(yīng)度的尺度變換是對目標(biāo)函數(shù)值域的某種映射變換 ， 可克服未成熟收斂和隨機(jī)漫游現(xiàn)象 . 常用的適應(yīng)度函數(shù)尺度變化方法主要有線性變換、冪函數(shù)變換和指數(shù)變換 .[13] (3)遺傳操作的設(shè)計(jì) . 包括選擇、交叉、變異 . ①選擇 (Selection). 選擇是用來確定交叉?zhèn)€體 ， 以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體 . 其主要思想是個(gè)體的復(fù)制概率正比于其適應(yīng)值 ， 但按比例選擇不一定能達(dá)到好的效果 . 選擇操作從早期的輪盤賭選擇發(fā)展到現(xiàn)在最佳個(gè)體保存法、排序選擇法、聯(lián)賽選擇法、隨機(jī)遍歷抽樣法、局部選擇法、柔性分段復(fù)制、穩(wěn)態(tài)復(fù)制、最優(yōu)串復(fù)制、最優(yōu)串保留等 . ②交叉 (Crossover). 交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作 ， 其作用是組合出新的個(gè)體 ， 在串空間進(jìn)行有效搜索 ， 同時(shí)降低對有效模式的破壞概率 . 各種交叉算子均包含兩個(gè)基本內(nèi)容 ： 確定交叉點(diǎn)的位置和進(jìn)行部分基因的 7 交換 . 常用的交叉操作方法有單點(diǎn) 交叉、雙點(diǎn)交叉、一致交叉、均勻交叉、算術(shù)交叉、二維交叉、樹結(jié)構(gòu)交叉、部分匹配交叉、順序交叉和周期交叉等等 . ③變異 (Mutation). 變異是指將個(gè)體編碼串中的某些基因值用其它基因值來替換 ,形成一個(gè)新的個(gè)體 . 遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法 ， 其目的是使遺傳算法具有局部的隨機(jī)搜索能力和保持群體的多樣性 . 變異算法包括確定變異點(diǎn)的位置和進(jìn)行基因值替換 . 常見的變異算子有基本位變異、均勻變異、高斯變異、二元變異、逆轉(zhuǎn)變異、自適應(yīng)變異等 . (4) 控制參數(shù)設(shè)定 . 遺傳算法中需要確定一些參數(shù)取值 ， 主要有 串長 l， 群體大小 n，交叉概率 pc、變異概率 pm等 ， 對遺傳算法性能影響很大 . 目前對參數(shù)根據(jù)情況進(jìn)行調(diào)整變化研究比較多 ， 而一般確定的參數(shù)范圍是 ： n=20～ 200， pc = 015 ～ 110， pm =0～ 0105. 在自然界 ， 由于組成生物群體中各個(gè)體之間的差異 ， 對所處環(huán)境有不同的適應(yīng)和生存能力 ， 遵照自然界生物進(jìn)化的基本原則 ， 適者生存、優(yōu)勝劣汰 ， 將要淘汰那些最差個(gè)體 ， 通過交配將父本優(yōu)秀的染色體和基因遺傳給子代 ， 通過染色體核基因的重新組合產(chǎn)生生命力更強(qiáng)的新的個(gè)體與由它們組成的新群體 . 在特 定的條件下 ， 基因會發(fā)生突變 ,產(chǎn)生新基因和生命力更強(qiáng)的新個(gè)體 ； 但突變是非遺傳的 ， 隨著個(gè)體不斷更新 ， 群體不斷朝著最優(yōu)方向進(jìn)化 ， 遺傳算法是真實(shí)模擬自然界生物進(jìn)化機(jī)制進(jìn)行尋優(yōu)的 . 在此算法中 ,被研究的體系的響應(yīng)曲面看作為一個(gè)群體 ， 相應(yīng)曲面上的每一個(gè)點(diǎn)作為群體中的一個(gè)個(gè)體 ， 個(gè)體用多維向量或矩陣來描述 ， 組成矩陣和向量的參數(shù)相應(yīng)于生物種組成染色體的基因 ， 染色體用固定長度的二進(jìn)制串表述 ， 通過交換、突變等遺傳操作 ， 在參數(shù)的一定范圍內(nèi)進(jìn)行隨機(jī)搜索 ， 不斷改善數(shù)據(jù)結(jié)構(gòu) ， 構(gòu)造出不同的向量 ， 相當(dāng)于得到了被研究的不同的解 ， 目標(biāo)函數(shù)值較優(yōu) 的點(diǎn)被保留 ， 目標(biāo)函數(shù)值較差的點(diǎn)被淘汰 .[14] 由于遺傳操作可以越過位壘 ， 能跳出局部較優(yōu)點(diǎn) ， 到達(dá)全局最優(yōu)點(diǎn) . 遺傳算法是一種迭代算法 ， 它在每一次迭代時(shí)都擁有一組解 ， 這組解最初是隨機(jī)生成的 ， 在每次迭代時(shí)又有一組新的解由模擬進(jìn)化和繼承的遺傳操作生成 ， 每個(gè)解都有一目標(biāo)函數(shù)給與評判 ， 一次迭代成為一代 . 經(jīng)典的遺傳算法結(jié)構(gòu)圖如下 ： 8 圖 1 遺傳算法的結(jié)構(gòu)圖 (1)根據(jù)求解精度的要求 ， 確定使用二進(jìn)制的長度 . 設(shè)值域的取值范 圍為 [ai ,bi ]，若要求精確到小數(shù)點(diǎn)后 6位 ， 則由 (bi ai ) 1062mi 1求得 mi 的最小長度 ， 進(jìn)而可求出位于區(qū)間的任一數(shù) ： xi =ai +decimal(101 ...0012 ) 12 ??miab ii [15] (3) 其中 ， i=1， 2， ...， Popsize； Popsize為種群中染色體的個(gè)數(shù) ； (2)利用隨機(jī)數(shù)發(fā)生器產(chǎn)生種群 ； (3)對種群中每一染色體 vi ， 計(jì)算其對應(yīng)適應(yīng)度 eval(vi )， i=1， 2， ? ， Popsize； (4)計(jì)算種群適應(yīng)度之和 F： F= ? ?vevaliPopsizei??1 (4) (5)計(jì)算每個(gè)染色體選擇概率 Pi： ? ?F vevalp ii ? (5) i=1， 2， ... ， Popsize ； 編碼、生成初始種群 種群中個(gè)體適應(yīng)渡的計(jì)算與評 價(jià)價(jià) 物種的選擇 雜交 變異 9 (6)計(jì)算每個(gè)染色體的累加概率 qi ： qi =??ij jp1 (6) i=1， 2， ...， Popsize ； (7)產(chǎn)生一個(gè)位于 [0， 1]區(qū)間的隨機(jī)數(shù)序列 ， 其長度為 N， 如果其中任意一數(shù) rq1 ，則選擇第一個(gè)染色體 ， 若 qi1? rqi ， 則選擇第 i個(gè)染色體 ， i=1， 2， ... Popsize， 這樣可以獲得新一代種群 ； (8)對新一代種群進(jìn)行交叉運(yùn)算 ： 設(shè)交叉概率為 pc ， 首先產(chǎn)生一個(gè)位于區(qū)間 [0,1]內(nèi)的隨機(jī)數(shù)序列 ， 其長度為 N， 如果其中任意一數(shù) rpc ， 則對應(yīng)染色體被選中 (如果選中奇數(shù)個(gè) ， 則可以去掉一個(gè) )， 然后在 [1， m1]區(qū)間中產(chǎn)生隨機(jī)數(shù) ， 個(gè)數(shù)為選中的染色體數(shù)的一半 ， 然后根據(jù)隨機(jī)數(shù)在對應(yīng)位置進(jìn)行交換操作 ， 從而構(gòu)成新的染色體 ； (9)變異操作 ： 設(shè)變異概率為 pm ， 產(chǎn)生 m N個(gè)位于區(qū)間 [0， 1]上的隨機(jī)數(shù) .如果某一隨機(jī)數(shù) rpm ， 則選中對應(yīng)位 變異 ， 構(gòu)成新的種群 ； (10)第一代計(jì)算完畢 ， 返回③繼續(xù)計(jì)算 ， 直到達(dá)到滿意的結(jié)果為止 . 隨機(jī)初始化種群 p(0)={x1， x2， ...， xn}； t=0； 計(jì)算 p(0)中個(gè)體的適應(yīng)值 ； while(不滿足終止條件 ) { 根據(jù)個(gè)體的適應(yīng)值及選擇策略從 p(t)中選擇下一代生成的父體 p(t)； 執(zhí)行交叉 ,變異和再生成新的種群 p(t+1) ； 計(jì)算 p(t+1)中個(gè)體的適應(yīng)值 ； t=t+1； } 偽代碼為： BEGIN： I=0； Initialize P(I)； 10 Fitness P(I)； While (not Terminate2Condition) { I++； GA2Operation P(I)； Fitness P(I)； } END. 遺傳算法不同于傳統(tǒng)的搜索和優(yōu)化方法 . 主要區(qū)別在于 ： (1)自組織、自適應(yīng)和自學(xué)習(xí)性 (智能性 ). 應(yīng)用遺傳算法求解問題時(shí) ， 在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后 ， 算法將利用進(jìn)化過程中獲得的信息自行組織搜索 . 由于基于自然的選擇策略“適者生存、不適者被淘汰” ， 因而適應(yīng)度大的個(gè)體具有較高的生存概率 . 通常適應(yīng)度大的個(gè)體 具有更適應(yīng)環(huán)境的基因結(jié)構(gòu) ， 再通過基因重組和基因突變等遺傳操作 ， 就可能產(chǎn)生更適應(yīng)環(huán)境的后代 . 進(jìn)化算法的這種自組織、自適應(yīng)特征 ， 使它同時(shí)具有能根據(jù)環(huán)境變化來自動(dòng)發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力 . 自然選擇消除了算法設(shè)計(jì)過程中的一個(gè)最大障礙 ， 即需要事先描述問題的全部特點(diǎn) ， 并要說明針對問題的不同特點(diǎn)算法應(yīng)采取的措施 .因此 ， 利用遺傳算法 ， 我們可以解決那些復(fù)雜的非結(jié)構(gòu)化問題 . (2)遺傳算法的本質(zhì)并行性 . 遺傳算法按并行方式搜索一個(gè)種群數(shù)目的點(diǎn) ， 而不是單點(diǎn) . 它的并行性表現(xiàn)在兩個(gè)方面 ， 一是遺傳算法是內(nèi)在并行的 ( inherent parallelism)， 即遺傳算法本身非常適合大規(guī)模并行 . 最簡單的并行方式是讓幾百甚至數(shù)千臺計(jì)算機(jī)各自進(jìn)行獨(dú)立種群的演化計(jì)算 ， 運(yùn)行過程中甚至不進(jìn)行任何通信 (獨(dú)立的種群之間若有少量的通信一般會帶來更好的結(jié)果 )， 等到運(yùn)算結(jié)束時(shí)才通信比較 ， 選取最佳個(gè)體 .這種并行處理方式對并行系統(tǒng)結(jié)構(gòu)沒有什么限制和要求 ， 可以說 ， 遺傳算法適合在目前所有的并行機(jī)或分布式系統(tǒng)上進(jìn)行并行處理 ， 而且對并行效率沒有太大影響 . 二是遺傳算法的內(nèi)含并行性 . 由于遺傳算法采用種群的方式組織搜索 ， 因而可同時(shí)搜索解空間內(nèi)的多個(gè)區(qū)域 ， 并相互交 流信息 . 使用這種搜索方式 ， 雖然每次只執(zhí)行與種群規(guī)模 N成比例的計(jì)算 ， 但實(shí)質(zhì)上已進(jìn)行了大約 O(N3)次有效搜索 ， 這就使遺傳算法能以較少的計(jì)算 11 獲得較大的收益 . (3)遺傳算法不需要求導(dǎo)或其他輔助知識 ， 而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù) . (4)遺傳算法強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則 ， 而不是確定的轉(zhuǎn)換規(guī)則 . (5)遺傳算法可以更加直接的應(yīng)用 . (6)遺傳算法對給定問題 ， 可以產(chǎn)生許多的潛在解 ， 最終選擇可以由使用者確定 . 在某些特殊情況下 ， 如多目標(biāo)優(yōu)化問題不止一個(gè)解存在 ， 有一組 pareto最優(yōu)解 . 這種遺傳算法對于確 認(rèn)可替代解集而言是特別合適的 .[1617] (1)編碼表示 Holland在運(yùn)用模式定理分析編碼機(jī)制時(shí) ， 建議使用二進(jìn)制編碼 ， 但二進(jìn)制編碼不能直接反映問題的固有結(jié)構(gòu)精度不高 ， 個(gè)體長度大 ， 占用計(jì)算機(jī)內(nèi)存多 .解決這個(gè)問題的措施有 ： ①動(dòng)態(tài)編碼 (dynamic encoding)GA是當(dāng)算法收斂到某局部最優(yōu)時(shí)增加搜索的精度從而使得在全局最優(yōu)點(diǎn)附近 ， 可以進(jìn)行更精確的搜索 ， 增加精度的辦法是在保持串長不變的前提下減小搜索區(qū)域 . ②對于問題的變量是實(shí)向量的情形 ， 可以直接采用實(shí)數(shù)進(jìn)行編碼 ， 這樣可以直接 在解的表現(xiàn)型上進(jìn)行遺傳操作 ， 從而便于引入與問題領(lǐng)域相關(guān)的啟發(fā)式信息以增加算法的搜索能力 . ③復(fù)數(shù)編碼的 GA是為了描述和解決二維問題 ， 基因用 x+yi表示 ,其還可以推廣到多維問題的描述中 . ④多維實(shí)數(shù)編碼 GA使無效交叉發(fā)生的可能性大大降低 ， 同時(shí)其合理的編碼長度也有助于算法在短時(shí)間內(nèi)獲得高精度的全局最優(yōu)解 . ⑤ 在組合優(yōu)化中 ， 可以使用有序串編碼 . 當(dāng)問題的表示是樹和圖時(shí) ， 我們還可以使用結(jié)構(gòu)式編碼 . (2)適應(yīng)度函數(shù) 適應(yīng)度函數(shù)是用來區(qū)分群體中個(gè)體好壞的標(biāo)準(zhǔn) ， 是自然選擇的唯一標(biāo)準(zhǔn) ， 選擇的好壞直接影響算法的優(yōu)劣 . 選 擇的不 容易引起兩種不利于優(yōu)化的現(xiàn)象 ： ①異常個(gè)體引起早熟收斂 ， 影響求得全局最優(yōu)解 . 這種現(xiàn)象常出現(xiàn)在小規(guī)模群體中 . 12 在遺傳進(jìn)化的早期 ， 一些超常個(gè)體的適應(yīng)度很大 ， 在群體中占有很大的比例 ， 這些異常個(gè)體因競爭力太突出而控制了選擇過程 ， 結(jié)果使得算法過早收斂 . ②個(gè)體差距不大 ， 引起搜索成為隨機(jī)漫游 . 當(dāng)群體中個(gè)體的適應(yīng)度差別不大 ， 個(gè)體間競爭力減弱 ， 特別是平均適應(yīng)度以接近最佳適應(yīng)度時(shí) ， 最佳個(gè)體與其他許多個(gè)體在選擇過程中就會有大體相等的選擇機(jī)會 ， 從而使有目標(biāo)的優(yōu)化搜索過程變成無目標(biāo)的隨機(jī)漫游 ， 影響求得全面最優(yōu)解 . 對于上 述問題可以通過引入適應(yīng)度函數(shù)定標(biāo)技術(shù)來加快收斂速度和跳出局部最優(yōu)點(diǎn) . 針對第一種情況 ， 我們可以通過縮小相應(yīng)的適應(yīng)度函數(shù)值降低超常個(gè)體的競爭力 ； 對于第二種情況 ， 我們可以放大相應(yīng)的適應(yīng)度函數(shù)值以拉開個(gè)體之間的差距 ， 提高個(gè)體間的競爭力 .對適應(yīng)值進(jìn)行定標(biāo)就是通過變換改變原適應(yīng)值間的比例關(guān)系 ， 常用的比例變換有線性變換、乘冪變換和指數(shù)變換等 . (3)選擇策略 優(yōu)勝劣汰的選擇機(jī)制使得適應(yīng)值大的個(gè)體有較大的存活機(jī)會 ， 不同的選擇策略對算法性能有較大的影響 . 輪盤賭法是使用最多的選擇策略 ， 但這種策略可能會產(chǎn)生較大的抽樣誤差 ， 于 是對此提出了很多的改進(jìn)方法 ， 如繁殖池選擇、 Boltzmann選擇、非線性排名選擇、基于局部競爭機(jī)制的選擇如 (λ +μ )選擇等等 . (4)控制參數(shù) 控制參數(shù)一般有群體大小、交換概率、變異概率等 ， 這些參數(shù)對遺傳算法性能影響較大 . 在標(biāo)準(zhǔn)的遺傳算法中采用經(jīng)驗(yàn)進(jìn)行估計(jì) ， 這將帶來很大的盲目性而影響算法的全局最優(yōu)性和收斂性 ， 人們意識到這些參數(shù)應(yīng)該隨著遺傳進(jìn)化而自適應(yīng)變化 . 基于這一觀 ， Davis提出自適應(yīng)算子概率方法 ， 即用自適應(yīng)機(jī)制把算子概率與算子產(chǎn)生的個(gè)體適應(yīng)性結(jié)合 ， 高適應(yīng)性值被分配高算子概率 . 這種方法較好地解決了 這一問題 . 遺傳算法的應(yīng)用領(lǐng)域 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架 ， 它不依賴于問題的具體領(lǐng)域 ， 對問題的種類有很強(qiáng)的魯棒性即健壯性 ， 所以廣泛應(yīng)用于很多學(xué)科 .下是遺傳算法的一些主要應(yīng)用領(lǐng)域 ： (1)函數(shù)優(yōu)化 .函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域 ， 也是對遺傳算法進(jìn)行性能評價(jià)的常用算例 .[18] 很多人構(gòu)造出了各種各樣的復(fù)雜形式的測試函數(shù) ， 有連續(xù)函數(shù)好有離散函數(shù) ， 有凸函數(shù)也有凹函數(shù) ， 人們用這些幾何特性各異的函數(shù)來評價(jià)遺傳算法的性能 . 而對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題 ， 用其他優(yōu)化方法較 難求解 ， 遺傳 13 算法卻可以方便地得到較好的結(jié)果 . (2)組合優(yōu)化 . 隨著問題規(guī)模的擴(kuò)大 ， 組合優(yōu)化問題的搜索空間急劇擴(kuò)大 ， 有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或者甚至不可能得到其精確最優(yōu)解 . 對于這類復(fù)雜問題 ，人們已意識到應(yīng)把精力放在尋求其滿意解上 ， 而遺傳算法則是尋求這種滿意解的最佳工具之一 . 實(shí)踐證明 ， 遺傳算法對于組合優(yōu)化中的 NP完全問題非常有效 .， 例如 ， 遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用 . (3)生產(chǎn)調(diào)度問題 . 生產(chǎn)調(diào)度問題在許多情況下所建立起來的數(shù)學(xué)模型難以精確求解 ， 即使經(jīng)過一些簡化之后可以進(jìn)行求解 ， 也會因簡化太多而使得求解結(jié)果與實(shí)際甚遠(yuǎn) . 因此 ， 目前在現(xiàn)實(shí)生產(chǎn)中好主要靠一些經(jīng)驗(yàn)進(jìn)行調(diào)度 . 遺傳算法已成為解決復(fù)雜高度問題的有效工具 ， 在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用 . (4)自動(dòng)控制 . 在自動(dòng)控制領(lǐng)域中許多與優(yōu)化相關(guān)的問題需要求解 ， 遺傳算法的應(yīng)用日益顯示了良好的效果 . 例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、基于遺傳算法的模糊控制器優(yōu)化設(shè)計(jì)、基于遺傳算法的參數(shù)辨識、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值 學(xué)習(xí)都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性 . (5)機(jī)器人智能控制 . 機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng) ， 而遺傳算法的起源就來自于對人工自適應(yīng)系統(tǒng)的研究 ， 所以機(jī)器人智能控