桂洪照 東北大學(xué)CCF會員
?
幾種具有代表性的啟發(fā)式算法研究
桂洪照 東北大學(xué)CCF會員
【文章摘要】
啟發(fā)式算法(Heuristic Algorithm)來自人類對地球生物圈的感悟。人類從生物圈的運行規(guī)律中摸索出很多方法與理論。本文介紹了五種重要的啟發(fā)式算法,退火模擬算法,蟻群算法,遺傳算法與人工神經(jīng)網(wǎng)絡(luò)算法。
啟發(fā)式算法 (Heuristic Algorithm )相對于最優(yōu)化算法提出。隨機概率群體尋優(yōu)過程當(dāng)中,個體能夠利用自身或者全局的經(jīng)驗來制定各自的搜索策略,就像算法擁有智能一樣。啟發(fā)式算法最初的概念在上世紀(jì)40年代提出,有了人工網(wǎng)絡(luò)的概念,50年代退火模擬算法,70年代遺傳算法,80年代禁忌搜索,90年代蟻群算法。隨著發(fā)展更多的啟發(fā)式算法被人們所知,粒子群算法,人工蜂群算法,甚至還有情感算法等,它們每個擁有自己的特點,在其相對的特定問題上為人類做出了巨大的貢獻(xiàn)。
(Traveling Salesman Problem,TSP)旅行商問題是測驗算法能力的一個很好的試驗場,本篇論文將以TSP問題為例對每個算法做出解釋。
1.1退火模擬算法
模擬退火算法(Simulated Annealing,SA)是一種啟發(fā)式算法,最早的思想是由N. Metropolis等人于1953年提出,SA的核心為模擬物理中材料先加熱再緩慢冷卻以改善其結(jié)構(gòu)的工藝過程,溫度由高變低時,由無序活動變?yōu)橛行蚍€(wěn)定,下圖。用熱力學(xué)系統(tǒng)來模擬求解優(yōu)化問題。把系統(tǒng)的能量看作目標(biāo)函數(shù),把物理系統(tǒng)降溫的過程模擬成算法在執(zhí)行中的優(yōu)化過程。它從一個給定初始解開始(較高),隨機在鄰域產(chǎn)生另一個解,它按照一定概率接受比當(dāng)前解更差的鄰域。
算法步驟
1) 首先,需要設(shè)置初始溫度和創(chuàng)建隨機的初始解
2) 然后開始循環(huán),直到滿足停止條件
3) 把當(dāng)前的解決方案做一些小的改變,選擇新的相鄰的方案
4) 決定是否移動到相鄰的解決方案
5) 降低溫度,繼續(xù)循環(huán),得到結(jié)果
模擬退火算法有不錯的全局收斂性和魯棒性, 可以方便的并行計算, 有較大概率求得全局最優(yōu)解, 然而 SA 算法運算效率較低, 優(yōu)化時間較長。
1.2蟻群算法
蟻群優(yōu)化(Ant Colony Optimization ACO)由M.Dorigo等人在1992年發(fā)布。螞蟻在移動時候會釋放一些信息素,這些信息素使得螞蟻會跟著前面的同伴走,高的信息素濃度能夠吸引更多的螞蟻。螞蟻走過的路徑越短,信息素積累得越快,濃度越高,最終所有螞蟻都選擇了短路徑。在螞蟻選擇信息素濃度較高的路徑時,螞蟻有一定概率尋找新的路徑(explore),如果新路徑更短,那么螞蟻將被吸引過來,經(jīng)過一定次數(shù)的重復(fù)螞蟻最終就能找到巢穴和食物間的最短路徑。
算法步驟(以最短路徑問題為例)
1)給每條路徑上的信息素濃度賦予初值,把a只模擬螞蟻放在b個點上
2)依照概率函數(shù),讓每只螞蟻找出可行路徑,計算路徑長度,選出最優(yōu)路徑
3)根據(jù)路線情況,更新本次最短路徑上的信息素濃度,返回前面循環(huán)直到得到最優(yōu)路徑。
ACO有正反饋與并行性、智能適應(yīng)的特點。但計算量大,消耗時間久, 常常由于過程中得到較好解影響,陷入局部最優(yōu)解, 使算法結(jié)束。
1.3遺傳算法
遺傳算法(Genetic Algorithm)GA[16]通過模擬生物學(xué)的自然選擇和自然遺傳機制來解決問題,它由J.Holland教授于1975年提出,GA模擬自然界生物進(jìn)化過程,它將問題域中的可能解看作是群體的一個個體或染色體。依照遺傳選擇,自然淘汰的生物進(jìn)化過程,對群體反復(fù)進(jìn)行操作。用適應(yīng)度函數(shù)進(jìn)行評價,保留適應(yīng)的種群,淘汰不適應(yīng)的種群。并將最優(yōu)種群進(jìn)行變異雜交,通過繁殖得到更好的后代。同時使用全局并行搜索來尋找群體的最優(yōu)個體來得到最優(yōu)解。GA有三個基本操作:變異:即按一定概率隨機改變某個體的基因值。交叉:將父本個體按照一定的概率隨機地交換基因形成新的個體。選擇:體現(xiàn)了適者生存,優(yōu)勝劣汰的進(jìn)化規(guī)則。
算法步驟
1)制定搜尋策略與R(控制參數(shù)),隨機產(chǎn)生初始種群A,進(jìn)化代數(shù) i= 1.
2)對A進(jìn)行評價, 若進(jìn)化代數(shù)無法累加或達(dá)到終止條件則終止算法,輸出最佳個體解.
3)操作種群(交叉變異),處理邊界條件,得到臨時種群B并對其評價,計算每個個體的適應(yīng)度值
4)操作種群(選擇)得到新種群.i=i+1,跳到步驟2.
遺傳算法使用范圍廣,能夠處理大多數(shù)組合優(yōu)化問題,處理簡單不需要有很高的數(shù)學(xué)水平, 能夠并行處理,具有較優(yōu)秀的全局搜索能力,然而常有早熟收斂的現(xiàn)象。
1.4人工神經(jīng)網(wǎng)絡(luò)算法
人工神經(jīng)網(wǎng)絡(luò) ( Artificial Neural Network , ANN) 模仿人類的大腦思維及運行方式,它起源于腦神經(jīng)元學(xué)說,在構(gòu)成原理和功能特點等方面更加接近人腦,不是按給定的程序一步一步地執(zhí)行運算,而是能夠自身適應(yīng)環(huán)境、總結(jié)規(guī)律、完成某種運算。它的研究應(yīng)追溯至本世紀(jì)40年代。1982年,Hopfield等人將Hopfield網(wǎng)用于TSP問題的求解,給神經(jīng)網(wǎng)絡(luò)在計算機領(lǐng)域的應(yīng)用打下基石。這種網(wǎng)絡(luò)由神經(jīng)元連接成非線性動態(tài)系統(tǒng),通過引入能量函數(shù)概念,通過網(wǎng)絡(luò)狀態(tài)的變化讓能量不斷減少,最后達(dá)到平衡時即達(dá)到最優(yōu)解。
算法步驟:
1)初始化各層連接權(quán)值,把問題映射為換位矩陣E。
2) 將E與 神經(jīng)網(wǎng)絡(luò)對應(yīng), 每條路徑對應(yīng)E的元素。
3) 設(shè)定能量函數(shù)BP, BP的min值點對應(yīng)問題的解。
4)計算神經(jīng)網(wǎng)絡(luò)的E和偏置電流,。
5)運行網(wǎng)絡(luò)直至局部最優(yōu)解。
Hopfield神經(jīng)網(wǎng)絡(luò)快速且簡單,記憶性強,能夠存儲大量的數(shù)據(jù),但是其優(yōu)化性較差。實驗表明, 神經(jīng)網(wǎng)絡(luò)算法只有局部搜索能力, 若是要提高解有效性概率,那么解的優(yōu)化能力降低, ,需要恰當(dāng)?shù)木W(wǎng)絡(luò)運行參數(shù)的設(shè)置。
在人類對啟發(fā)式算法研究長達(dá)半個世紀(jì)中,涌現(xiàn)出了很多有思想有新意的優(yōu)秀算法。但是啟發(fā)式算法目前仍有不足,它缺乏統(tǒng)一、完整的理論體系,并且面對局部最優(yōu)的問題上略有不足。啟發(fā)式算法需要進(jìn)行大量的計算,通常遇到大型問題,其計算量更是呈現(xiàn)指數(shù)型增長。由于近年來技術(shù)的勃發(fā),啟發(fā)式算法的前景相當(dāng)廣大。蟻群算法結(jié)合了mapreduce并行計算,有效的減少了其計算的時間。一類被稱為超啟發(fā)式算法(Hyper-Heuristic Algorithm)的新算法類型在智能計算領(lǐng)域的著名國際會議上出現(xiàn)。研究者們結(jié)合他們的靈活思維將不同的算法結(jié)合取得到了非常好的成果。隨著人類的不斷進(jìn)步,啟發(fā)式算法在智能計算領(lǐng)域的地位越來越重要,應(yīng)用的領(lǐng)域越來越廣。