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

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

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

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

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

4、高其搜索效率，所以是求解各類函數(shù)優(yōu)化問題比較適合的算法。1.3.1編碼方案在用遺傳算法求解函數(shù)優(yōu)化問題時(shí)，把解空間中的數(shù)據(jù)點(diǎn)都映射到遺傳中對(duì)應(yīng)的基因型數(shù)據(jù)，采用二進(jìn)制編碼，在給定函數(shù)的變量上下界和編碼精度內(nèi)，求得單個(gè)變量的編碼長(zhǎng)度，然后隨機(jī)生成一些固定長(zhǎng)度為的二進(jìn)制數(shù)作為作為初始種群。1.3.2適應(yīng)度函數(shù)先用解碼函數(shù)將二進(jìn)制代碼轉(zhuǎn)換為解空間中的數(shù)據(jù)，把數(shù)據(jù)帶入測(cè)試函數(shù)中，得到種群中每個(gè)個(gè)體的適應(yīng)值，然后以種群中函數(shù)值取得最大值的個(gè)體的函數(shù)值與每個(gè)個(gè)體的函數(shù)值之差，再與最大函數(shù)值的n倍(假設(shè)種群粒子數(shù)為n)和種群中所有個(gè)體的函數(shù)值

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

6、點(diǎn)交叉和雙切點(diǎn)交叉。在這個(gè)算法中，先從種群中隨機(jī)選擇兩個(gè)要進(jìn)行交叉的個(gè)體，然后隨機(jī)生成一個(gè)數(shù)據(jù)點(diǎn)，對(duì)兩個(gè)父串中對(duì)應(yīng)位的數(shù)值進(jìn)行交換，得到兩個(gè)字串。1.3.5變異算子變異是在種群中按照變異概率Pm任選若干基因位改變其位值，對(duì)于0-1編碼來說，就是反轉(zhuǎn)位值。在這個(gè)算法中，先在父串中隨機(jī)生成一個(gè)數(shù)，如果這個(gè)數(shù)對(duì)應(yīng)的位值為0，則將它變?yōu)?；如果這個(gè)數(shù)上的位值為1，則將它變?yōu)?.1.4遺傳算法求解函數(shù)優(yōu)化問題流程Step1：初始化選擇、交叉、變異概率，設(shè)置初始代數(shù)和最大迭代次數(shù)，隨機(jī)生成若干個(gè)初始個(gè)體構(gòu)成初始種群；Step2：利用解碼函數(shù)

7、將初始種群的二進(jìn)制編碼轉(zhuǎn)化為解空間中便于計(jì)算的數(shù)據(jù)，然后用測(cè)試函數(shù)以及適應(yīng)度函數(shù)求得每個(gè)個(gè)體的適應(yīng)度。Step3：采用輪盤賭選擇種群中的個(gè)體進(jìn)行遺傳運(yùn)算；Step4：對(duì)種群中的個(gè)體進(jìn)行交叉，變異運(yùn)算，產(chǎn)生下一代新的種群。Step5：如果當(dāng)前的迭代次數(shù)達(dá)到設(shè)置的最大迭代次數(shù)，則算法停止，進(jìn)行Step6；若未達(dá)到最大迭代次數(shù)，則轉(zhuǎn)入Step2.Step6：保存種群中每一代的選擇函數(shù)值最小個(gè)體作為最優(yōu)個(gè)體，并保存其對(duì)應(yīng)的函數(shù)值。1.5測(cè)試函數(shù)運(yùn)行結(jié)果及算法參數(shù)對(duì)結(jié)果影響分析1.5.1各種函數(shù)測(cè)試結(jié)果（1）Quadric函數(shù)狀種群動(dòng)態(tài)變

8、化圖(-100,100)第1代種群動(dòng)態(tài)變化圖第50代種群動(dòng)態(tài)變化圖第100代種群動(dòng)態(tài)變化圖第200代種群動(dòng)態(tài)變化圖（2）Tablet函數(shù)測(cè)試種群變化圖(-100,100)第1代種群動(dòng)態(tài)變化圖第50代種群動(dòng)態(tài)變化圖第100代種群動(dòng)態(tài)變化圖第200代種群動(dòng)態(tài)變化圖（