桂洪照 東北大學(xué)CCF會(huì)員

?

幾種具有代表性的啟發(fā)式算法研究

桂洪照 東北大學(xué)CCF會(huì)員

【文章摘要】

啟發(fā)式算法（Heuristic Algorithm）來(lái)自人類對(duì)地球生物圈的感悟。人類從生物圈的運(yùn)行規(guī)律中摸索出很多方法與理論。本文介紹了五種重要的啟發(fā)式算法，退火模擬算法，蟻群算法，遺傳算法與人工神經(jīng)網(wǎng)絡(luò)算法。

0 引言

啟發(fā)式算法 （Heuristic Algorithm )相對(duì)于最優(yōu)化算法提出。隨機(jī)概率群體尋優(yōu)過(guò)程當(dāng)中，個(gè)體能夠利用自身或者全局的經(jīng)驗(yàn)來(lái)制定各自的搜索策略，就像算法擁有智能一樣。啟發(fā)式算法最初的概念在上世紀(jì)40年代提出，有了人工網(wǎng)絡(luò)的概念，50年代退火模擬算法，70年代遺傳算法，80年代禁忌搜索，90年代蟻群算法。隨著發(fā)展更多的啟發(fā)式算法被人們所知，粒子群算法，人工蜂群算法，甚至還有情感算法等，它們每個(gè)擁有自己的特點(diǎn)，在其相對(duì)的特定問(wèn)題上為人類做出了巨大的貢獻(xiàn)。

1 具體算法

（Traveling Salesman Problem,TSP）旅行商問(wèn)題是測(cè)驗(yàn)算法能力的一個(gè)很好的試驗(yàn)場(chǎng)，本篇論文將以TSP問(wèn)題為例對(duì)每個(gè)算法做出解釋。

1.1退火模擬算法

模擬退火算法（Simulated Annealing，SA）是一種啟發(fā)式算法，最早的思想是由N. Metropolis等人于1953年提出，SA的核心為模擬物理中材料先加熱再緩慢冷卻以改善其結(jié)構(gòu)的工藝過(guò)程，溫度由高變低時(shí)，由無(wú)序活動(dòng)變?yōu)橛行蚍€(wěn)定，下圖。用熱力學(xué)系統(tǒng)來(lái)模擬求解優(yōu)化問(wèn)題。把系統(tǒng)的能量看作目標(biāo)函數(shù)，把物理系統(tǒng)降溫的過(guò)程模擬成算法在執(zhí)行中的優(yōu)化過(guò)程。它從一個(gè)給定初始解開(kāi)始（較高），隨機(jī)在鄰域產(chǎn)生另一個(gè)解，它按照一定概率接受比當(dāng)前解更差的鄰域。

算法步驟

1) 首先,需要設(shè)置初始溫度和創(chuàng)建隨機(jī)的初始解

2) 然后開(kāi)始循環(huán),直到滿足停止條件

3) 把當(dāng)前的解決方案做一些小的改變，選擇新的相鄰的方案

4) 決定是否移動(dòng)到相鄰的解決方案

5) 降低溫度,繼續(xù)循環(huán)，得到結(jié)果

模擬退火算法有不錯(cuò)的全局收斂性和魯棒性, 可以方便的并行計(jì)算, 有較大概率求得全局最優(yōu)解, 然而 SA 算法運(yùn)算效率較低, 優(yōu)化時(shí)間較長(zhǎng)。

1.2蟻群算法

蟻群優(yōu)化(Ant Colony Optimization ACO)由M.Dorigo等人在1992年發(fā)布。螞蟻在移動(dòng)時(shí)候會(huì)釋放一些信息素，這些信息素使得螞蟻會(huì)跟著前面的同伴走，高的信息素濃度能夠吸引更多的螞蟻。螞蟻?zhàn)哌^(guò)的路徑越短，信息素積累得越快，濃度越高，最終所有螞蟻都選擇了短路徑。在螞蟻選擇信息素濃度較高的路徑時(shí)，螞蟻有一定概率尋找新的路徑（explore），如果新路徑更短，那么螞蟻將被吸引過(guò)來(lái)，經(jīng)過(guò)一定次數(shù)的重復(fù)螞蟻?zhàn)罱K就能找到巢穴和食物間的最短路徑。

算法步驟（以最短路徑問(wèn)題為例）

1）給每條路徑上的信息素濃度賦予初值，把a(bǔ)只模擬螞蟻放在b個(gè)點(diǎn)上

2）依照概率函數(shù)，讓每只螞蟻找出可行路徑，計(jì)算路徑長(zhǎng)度,選出最優(yōu)路徑

3）根據(jù)路線情況,更新本次最短路徑上的信息素濃度，返回前面循環(huán)直到得到最優(yōu)路徑。

ACO有正反饋與并行性、智能適應(yīng)的特點(diǎn)。但計(jì)算量大，消耗時(shí)間久, 常常由于過(guò)程中得到較好解影響，陷入局部最優(yōu)解, 使算法結(jié)束。

1.3遺傳算法

遺傳算法（Genetic Algorithm）GA[16]通過(guò)模擬生物學(xué)的自然選擇和自然遺傳機(jī)制來(lái)解決問(wèn)題，它由J.Holland教授于1975年提出,GA模擬自然界生物進(jìn)化過(guò)程，它將問(wèn)題域中的可能解看作是群體的一個(gè)個(gè)體或染色體。依照遺傳選擇，自然淘汰的生物進(jìn)化過(guò)程，對(duì)群體反復(fù)進(jìn)行操作。用適應(yīng)度函數(shù)進(jìn)行評(píng)價(jià)，保留適應(yīng)的種群，淘汰不適應(yīng)的種群。并將最優(yōu)種群進(jìn)行變異雜交，通過(guò)繁殖得到更好的后代。同時(shí)使用全局并行搜索來(lái)尋找群體的最優(yōu)個(gè)體來(lái)得到最優(yōu)解。GA有三個(gè)基本操作：變異：即按一定概率隨機(jī)改變某個(gè)體的基因值。交叉：將父本個(gè)體按照一定的概率隨機(jī)地交換基因形成新的個(gè)體。選擇：體現(xiàn)了適者生存，優(yōu)勝劣汰的進(jìn)化規(guī)則。

算法步驟

1）制定搜尋策略與R(控制參數(shù))，隨機(jī)產(chǎn)生初始種群A，進(jìn)化代數(shù) i= 1.

2）對(duì)A進(jìn)行評(píng)價(jià), 若進(jìn)化代數(shù)無(wú)法累加或達(dá)到終止條件則終止算法，輸出最佳個(gè)體解.

3）操作種群（交叉變異），處理邊界條件，得到臨時(shí)種群B并對(duì)其評(píng)價(jià)，計(jì)算每個(gè)個(gè)體的適應(yīng)度值

4）操作種群（選擇）得到新種群.i=i+1，跳到步驟2.

遺傳算法使用范圍廣，能夠處理大多數(shù)組合優(yōu)化問(wèn)題，處理簡(jiǎn)單不需要有很高的數(shù)學(xué)水平, 能夠并行處理，具有較優(yōu)秀的全局搜索能力，然而常有早熟收斂的現(xiàn)象。

1.4人工神經(jīng)網(wǎng)絡(luò)算法

人工神經(jīng)網(wǎng)絡(luò) ( Artificial Neural Network , ANN) 模仿人類的大腦思維及運(yùn)行方式，它起源于腦神經(jīng)元學(xué)說(shuō)，在構(gòu)成原理和功能特點(diǎn)等方面更加接近人腦，不是按給定的程序一步一步地執(zhí)行運(yùn)算，而是能夠自身適應(yīng)環(huán)境、總結(jié)規(guī)律、完成某種運(yùn)算。它的研究應(yīng)追溯至本世紀(jì)40年代。1982年，Hopfield等人將Hopfield網(wǎng)用于TSP問(wèn)題的求解，給神經(jīng)網(wǎng)絡(luò)在計(jì)算機(jī)領(lǐng)域的應(yīng)用打下基石。這種網(wǎng)絡(luò)由神經(jīng)元連接成非線性動(dòng)態(tài)系統(tǒng)，通過(guò)引入能量函數(shù)概念，通過(guò)網(wǎng)絡(luò)狀態(tài)的變化讓能量不斷減少，最后達(dá)到平衡時(shí)即達(dá)到最優(yōu)解。

算法步驟：

1）初始化各層連接權(quán)值，把問(wèn)題映射為換位矩陣E。

2） 將E與 神經(jīng)網(wǎng)絡(luò)對(duì)應(yīng), 每條路徑對(duì)應(yīng)E的元素。

3） 設(shè)定能量函數(shù)BP, BP的min值點(diǎn)對(duì)應(yīng)問(wèn)題的解。

4）計(jì)算神經(jīng)網(wǎng)絡(luò)的E和偏置電流,。

5）運(yùn)行網(wǎng)絡(luò)直至局部最優(yōu)解。

Hopfield神經(jīng)網(wǎng)絡(luò)快速且簡(jiǎn)單，記憶性強(qiáng)，能夠存儲(chǔ)大量的數(shù)據(jù)，但是其優(yōu)化性較差。實(shí)驗(yàn)表明, 神經(jīng)網(wǎng)絡(luò)算法只有局部搜索能力, 若是要提高解有效性概率，那么解的優(yōu)化能力降低, ,需要恰當(dāng)?shù)木W(wǎng)絡(luò)運(yùn)行參數(shù)的設(shè)置。

2 結(jié)束語(yǔ)

在人類對(duì)啟發(fā)式算法研究長(zhǎng)達(dá)半個(gè)世紀(jì)中，涌現(xiàn)出了很多有思想有新意的優(yōu)秀算法。但是啟發(fā)式算法目前仍有不足，它缺乏統(tǒng)一、完整的理論體系，并且面對(duì)局部最優(yōu)的問(wèn)題上略有不足。啟發(fā)式算法需要進(jìn)行大量的計(jì)算，通常遇到大型問(wèn)題，其計(jì)算量更是呈現(xiàn)指數(shù)型增長(zhǎng)。由于近年來(lái)技術(shù)的勃發(fā)，啟發(fā)式算法的前景相當(dāng)廣大。蟻群算法結(jié)合了mapreduce并行計(jì)算，有效的減少了其計(jì)算的時(shí)間。一類被稱為超啟發(fā)式算法（Hyper-Heuristic Algorithm）的新算法類型在智能計(jì)算領(lǐng)域的著名國(guó)際會(huì)議上出現(xiàn)。研究者們結(jié)合他們的靈活思維將不同的算法結(jié)合取得到了非常好的成果。隨著人類的不斷進(jìn)步，啟發(fā)式算法在智能計(jì)算領(lǐng)域的地位越來(lái)越重要，應(yīng)用的領(lǐng)域越來(lái)越廣。