各種優(yōu)化算法求解函數(shù)優(yōu)化問題

《各種優(yōu)化算法求解函數(shù)優(yōu)化問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、各種優(yōu)化算法求解函數(shù)優(yōu)化問題1.遺傳算法的簡單介紹及流程1.1遺傳算法的基本原理遺傳算法(GeneticAlgorithm,簡稱GA)是近年來迅速發(fā)展起來的一種全新的隨機搜索優(yōu)化算法。與傳統(tǒng)搜索算法不同,遺傳算法從一組隨機產(chǎn)生的初始解(稱為群體)開始搜索。群體中的每個個體是問題的一個解,稱為染色體。這些染色體在后續(xù)迭代中不斷進化,稱為遺傳。遺傳算法主要通過交叉、變異、選擇運算實現(xiàn)。交叉或變異運算生成下一代染色體,稱為后代。染色體的好壞用適應(yīng)度來衡量。根據(jù)適應(yīng)度的大小從上一代和后代中選擇一定數(shù)量的個體

2、,作為下一代群體,再繼續(xù)進化,這樣經(jīng)過若干代之后,算法收斂于最好的染色體,它很可能就是問題的最優(yōu)解或次優(yōu)解。遺傳算法中使用適應(yīng)度這個概念來度量群體中的各個個體在優(yōu)化計算中有可能達到最優(yōu)解的優(yōu)良程度。度量個體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)。適應(yīng)度函數(shù)的定義一般與具體求解問題有關(guān)。1.2遺傳算法的流程第一步：確定決策變量及各種約束條件，即確定出個體的表現(xiàn)型X和問題的解空間；第二步：確定出目標(biāo)函數(shù)的類型，即求目標(biāo)函數(shù)的最大值還是最小值，以及其數(shù)學(xué)描述形式或量化方法，建立其優(yōu)化模型；第三步：確定表示可行解的染色

3、體編碼方法，即確定出個體的基因型X和遺傳算法的搜索空間。第四步：確定解碼方法，即確定出個體的基因型X和個體的表現(xiàn)型X的對應(yīng)關(guān)系或轉(zhuǎn)換方法；第五步：確定個體時候適應(yīng)度的量化評價方法，即確定出由目標(biāo)函數(shù)f(X)值到個體適應(yīng)度F(X)的轉(zhuǎn)換規(guī)則；第六步：設(shè)計遺傳算子，即確定出選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法；第七步：確定出遺傳算法的運行參數(shù)，即確定出遺傳算法的M、T、Pc、Pm等參數(shù)。1.3遺傳算法求解函數(shù)優(yōu)化問題中的參數(shù)分析目前，函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進行性

4、能評價的常用范例。對于函數(shù)優(yōu)化中求解實數(shù)型變量的問題，一般采用動態(tài)編碼和實數(shù)編碼的方法來提高其搜索效率，所以是求解各類函數(shù)優(yōu)化問題比較適合的算法。1.3.1編碼方案在用遺傳算法求解函數(shù)優(yōu)化問題時，把解空間中的數(shù)據(jù)點都映射到遺傳中對應(yīng)的基因型數(shù)據(jù)，采用二進制編碼，在給定函數(shù)的變量上下界和編碼精度內(nèi)，求得單個變量的編碼長度，然后隨機生成一些固定長度為的二進制數(shù)作為作為初始種群。1.3.2適應(yīng)度函數(shù)先用解碼函數(shù)將二進制代碼轉(zhuǎn)換為解空間中的數(shù)據(jù)，把數(shù)據(jù)帶入測試函數(shù)中，得到種群中每個個體的適應(yīng)值，然后以種群中

5、函數(shù)值取得最大值的個體的函數(shù)值與每個個體的函數(shù)值之差，再與最大函數(shù)值的n倍(假設(shè)種群粒子數(shù)為n)和種群中所有個體的函數(shù)值之和的比值，得到每個個體的適應(yīng)度。如果求函數(shù)最小值問題，則適應(yīng)度值越大其函數(shù)值越小。1.3.3選擇算子遺傳算法最常用的選擇策略就是正比選擇策略，即每個個體被選中進行遺傳運算的概率為該個體的適應(yīng)值和群體中所有個體適應(yīng)值總和的比例。對于個體i，其適應(yīng)度值為Fi，種群規(guī)模為NP，則該個體的選擇概率可以表示為得到選擇概率后，采用旋輪法來實現(xiàn)選擇操作，令PP0=0共轉(zhuǎn)輪NP次，每次轉(zhuǎn)輪時，隨

6、機產(chǎn)生，當(dāng)

7、1，則將它變?yōu)?.1.4遺傳算法求解函數(shù)優(yōu)化問題流程Step1：初始化選擇、交叉、變異概率，設(shè)置初始代數(shù)和最大迭代次數(shù)，隨機生成若干個初始個體構(gòu)成初始種群；Step2：利用解碼函數(shù)將初始種群的二進制編碼轉(zhuǎn)化為解空間中便于計算的數(shù)據(jù)，然后用測試函數(shù)以及適應(yīng)度函數(shù)求得每個個體的適應(yīng)度。Step3：采用輪盤賭選擇種群中的個體進行遺傳運算；Step4：對種群中的個體進行交叉，變異運算，產(chǎn)生下一代新的種群。Step5：如果當(dāng)前的迭代次數(shù)達到設(shè)置的最大迭代次數(shù)，則算法停止，進行Step6；若未達到最大迭代次數(shù)，

8、則轉(zhuǎn)入Step2.Step6：保存種群中每一代的選擇函數(shù)值最小個體作為最優(yōu)個體，并保存其對應(yīng)的函數(shù)值。1.5測試函數(shù)運行結(jié)果及算法參數(shù)對結(jié)果影響分析1.5.1各種函數(shù)測試結(jié)果（1）Quadric函數(shù)狀種群動態(tài)變化圖(-100,100)第1代種群動態(tài)變化圖第50代種群動態(tài)變化圖第100代種群動態(tài)變化圖第200代種群動態(tài)變化圖（2）Tablet函數(shù)測試種群變化圖(-100,100)第1代種群動態(tài)變化圖第50代種群動態(tài)變化圖第100代種群動態(tài)變化圖第200代種群動態(tài)變化圖（