1.現代優化算法概論(Modern Optimization Algorithms, MOA)
現代優化算法又稱智能優化算法或啟發式算法,是一種具有全局優化性能強、通用性強、且适用于并行處理的算法。
基本思路:都是從任意解出發,按照某種機制,以一定的機率在整個求解空間中探尋最優解。由于他們可以把搜尋空間擴充到整個問題空間,因而具有全局優化性能。
特點:
- 基于客觀世界中的一些自然現象;
- 建立在計算機疊代計算的基礎上;
- 具有普适性,可解決實際應用問題。
- 不依賴于初始條件
- 收斂速度慢,能獲得全局最優,适用于求解空間未知的情況
- SA、GA可應用于大規模、多峰多态函數、含離散變量等全局優化問題;求解速度和品質遠超過正常方法。
2.模拟退火算法 (Simulated Annealing Algorithm, SA)
算法目的:
- 解決NP複雜性問題
- 克服優化過程中陷入局部最小
- 克服初始值依賴性
在同一個溫度,分子停留在能量小的狀态的機率比停留在能量大的狀态的機率大(能量越高越不穩定)
數學表達:若在溫度T,目前狀态i → 新狀态j,若Ej<Ei,則接受 j 為目前狀态; 否則,以機率 p=exp[-(Ej-Ei)/kBT] 接受j 為目前狀态。即:p大于[0,1)區間的随機數,則仍接受狀态 j 為目前狀态; 否則保留狀态 i 為目前狀态。
算法描述:
随機産生一個初始解 x0 ,令xbest = x0 ,并計算目标函數值E( x0 );
設定初始溫度T = T0,疊代次數 i = 1 ;
do while T > Tmin
for j = 1 ~ k
對目前最優解 xbest 按照某一鄰域函數,産生一新的解 xnew 計算新的目标函數值E(xnew ),并計算目标函數值的增量 ∆E= E(xnew )- E(xbest );
if ∆E <0
xbest = xnew ;
if ∆E >0
p = exp (- ∆E / T(i));
if c = random[0,1]<p,
xbest = xnew
else
xbest = xbest End
for update T, i = i+1;
End Do 輸出目前最優點,計算結束
原則:産生的候選解因遍布全部解空間(保證全局最優)
方法:在目前狀态的鄰域結構内以一定機率方式(均勻分布,指數分布,正态分布等)産生
優點:品質高、初始魯棒性強、簡單通用易實作
缺點:由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度,以及各溫度下足夠多次的抽樣,是以優化過程較長。
改進:略
3.遺傳算法 (Genetic Algorithm, GA)
遺傳算法是一種基于自然群體遺傳進化機制的自适應全局優化機率搜尋算法。
基本思想(傳統簡單遺傳算法):遺傳算法模拟自然選擇和自然遺傳過程中發生的繁殖、交叉和基因突變現象,在每次疊代中都保留一組候選解,并按照某種名額從解群中選取較優的個體,利用遺傳算子(選擇、交叉和變異)對這些個體進行組合,産生新一代的候選解群,重複此過程,直到滿足某種收斂标準為止。
進化規則:“适者生存”:較好的解被保留,較差的解被淘汰
個體:模拟生物個體是對問題中對象(一般就是問題的解)的一種稱呼,一個個體也就是搜尋空間中的一個點。
種群:模拟生物種群是由若幹個個體組成的群體,它一般是整個搜尋空間的一個很小的子集。
适應度:借鑒生物個體對環境的适應程度,對問題中的個體對象所設計的表征其優劣的一種測度。
适應度函數:全體個體與其适應度之間的一個對應關系。它一般是一個實值函數,該函數就是遺傳算法中指導搜尋的評價函數。
染色體:問題中個體的某種字元串形式的編碼表示。
基因:字元串中的字元
如何設計遺傳算法:
- 如何進行編碼
- 如何産生初始種群
- 如何定義适應度函數
- 如何進行遺傳操作(選擇、交叉和變異)
- 如何産生下一代種群
- 如何定義停止規則
選擇:選擇操作把目前種群的染色體按與适應值成正比的機率複制到新的種群中
輪盤賭:
-
- 将種群中所有染色體編号,并根據各自的适應值計算按比例配置設定的機率
- 依次計算染色體累加機率
- 産生(0,1)間的随機數,若其最多能大于序列中第m個值,則第m個染色體被選擇
輪盤賭算法描述:
- 在[0, 1]區間内産生一個均勻分布的随機數r。
- 若r≤q1,則染色體x1被選中。
- 若qk-1<r≤qk(2≤k≤N), 則染色體xk被選中。
其中的qi稱為染色體xi (i=1, 2, …, n)的積累機率, 其計算公式為
交叉:每次作用在從交配池中随機選取的兩個個體上(交叉機率Pc)
GA利用選擇和交叉操作可以産生具有更高平均适應值和更好染色體的群體
變異:以變異機率pm改變染色體id某個基因,當以二進制編碼時,變異的基因由0變成1,或者由1變成0。變異機率pm一般介于1/種群規模與1/染色體長度之間,平均約1%-2%
比起選擇和交叉操作,變異操作是GA中的次要操作,但是它在恢複群體失去的多樣性方面具有潛在的作用。
停止準則:
- 種群中的個體的最大适應值超過預設定值
- 種群中個體的平均适應值超過預設定值
- 種群中個體的進化代數超過預設定值
基本步驟:
- 随機産生初始種群
- 計算種群體中每個個體的适應度值,判斷是否滿足停止條件,若不滿足,則轉第(c)步,否則,轉第(f)步;
- 按由個體适應值所決定的某個規則選擇進入下一代的個體;
- 按交叉機率pc進行交叉操作,産生新個體
- 按變異機率pm進行變異操作,産生新個體;
- 輸出種群中适應值最優的染色體作為問題的最優解或滿意解
4.差分進化 (Differential Evolution Algorithm, DEA)
基于群體差異的啟發式随機搜尋算法
特點:原理簡單,受控參數少,魯棒性強
與遺傳算法十分相似
流程:變異、交叉和選擇
選擇政策:競标賽選擇
交叉操作方式與遺傳算法大體相同
變異操作方面使用差分政策:
利用群體中個體的差分量對個體進行擾動,實作個體變異
差分政策的變異方式,有效利用群體分布特征,提高算法的搜尋能力,避免遺傳算法中變異方式的不足
算法流程:
- 初始化種群
- 變異操作:
常見的差分政策:随機選取種群中的兩個不同個體,将其向量差縮放後與待變異個體進行向量合成,即
- 交叉操作
- 為了確定變異中間體{vi(g+1)}的每個“染色體”至少有一個“基因”遺傳給下一代,第一個交叉操作的基因是随機取出vi(g+1)中的第jrand位“基因”作為交叉後“染色體”ui(g+1)第jrand位等位“基因”。後續的交叉過程,則是通過交叉機率CR來選取xi(g)還是vi(g+1)的等位基因作為ui(g+1)的等位基因。
- 選擇操作:
差分算法采用貪婪算法來選擇進入下一代群體的個體
缺點:随着代數的增加,個體間的差異會逐漸降低。個體差異性的減小又影響變異所帶來的多樣性,進而導緻算法過早收斂到局部極值附近時,形成早收斂現象。
改進:略