算法定義
退火進化算法(annealing evolution algorithm, AEA)
別名:遺傳模擬退火算法,混合模擬退火算法
遺傳算法(GA)模擬退火算法(SA)是人工智慧中用於解決組合最佳化問題的經典算法,
但是,SA 在全局搜尋能力方面不足,GA 在局部搜尋能力方面不足。而退火進化算法
(annealing evolution algorithm, AEA)綜合了SA和GA算法,優勢互補,
發揮SA 局部搜尋能力和GA 全局搜尋能力,克服SA 全局搜尋能力差及效率不高的問題
和GA 局部搜尋能力差及其早熟現象。
AEA把SA算法與GA結合在一起,通過變異與選擇不斷改善解群體,並行搜尋解空間,
從而有可能更迅速地找到全局最優解。由於在選擇中採用Metropolis準則,
因而保留了SA算法易跳出某局部極值“陷阱”的優點,易於向全局極小值快速收斂。
求解過程
(1)初始化進化代數計數器k←0,隨機給出種群P(k)初值,給定初試退火溫度T0。
(2)評價當前群體P(k)的適應度。
(3)個體交叉操作(附帶保優操作): P(k)’←Crossover[P(k)]。
(4)個體變異操作(附帶保優操作): P(k)”←Mutation[P(k)’]。
(5)由SA狀態函式產生新個體。
(6)個體模擬退火操作(Metropolis準則接受新個體): P(k)”’←SA[P(k)”]。
(7)判斷SA抽樣是否穩定,若不穩定,則返回(5);若穩定,則往下執行退溫操作T←T’
(8)個體複製操作,由擇優選擇模型保留最佳種群:P(k+1)←Reproduction[P(k)∪P(k)”’]。
(9)終止條件判斷,若不滿足終止條件,則k←k+1,轉到(2);若滿足終止條件,
則輸出當前最優個體,結束算法。