幾種具有代表性的啟發式算法研究

桂洪照 東北大學CCF會員

?

幾種具有代表性的啟發式算法研究

桂洪照 東北大學CCF會員

【文章摘要】

啟發式算法（Heuristic Algorithm）來自人類對地球生物圈的感悟。人類從生物圈的運行規律中摸索出很多方法與理論。本文介紹了五種重要的啟發式算法，退火模擬算法，蟻群算法，遺傳算法與人工神經網絡算法。

0 引言

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

1 具體算法

（Traveling Salesman Problem,TSP）旅行商問題是測驗算法能力的一個很好的試驗場，本篇論文將以TSP問題為例對每個算法做出解釋。

1.1退火模擬算法

模擬退火算法（Simulated Annealing，SA）是一種啟發式算法，最早的思想是由N. Metropolis等人于1953年提出，SA的核心為模擬物理中材料先加熱再緩慢冷卻以改善其結構的工藝過程，溫度由高變低時，由無序活動變為有序穩定，下圖。用熱力學系統來模擬求解優化問題。把系統的能量看作目標函數，把物理系統降溫的過程模擬成算法在執行中的優化過程。它從一個給定初始解開始（較高），隨機在鄰域產生另一個解，它按照一定概率接受比當前解更差的鄰域。

算法步驟

1) 首先,需要設置初始溫度和創建隨機的初始解

2) 然后開始循環,直到滿足停止條件

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

4) 決定是否移動到相鄰的解決方案

5) 降低溫度,繼續循環，得到結果

模擬退火算法有不錯的全局收斂性和魯棒性, 可以方便的并行計算, 有較大概率求得全局最優解, 然而 SA 算法運算效率較低, 優化時間較長。

1.2蟻群算法

蟻群優化(Ant Colony Optimization ACO)由M.Dorigo等人在1992年發布。螞蟻在移動時候會釋放一些信息素，這些信息素使得螞蟻會跟著前面的同伴走，高的信息素濃度能夠吸引更多的螞蟻。螞蟻走過的路徑越短，信息素積累得越快，濃度越高，最終所有螞蟻都選擇了短路徑。在螞蟻選擇信息素濃度較高的路徑時，螞蟻有一定概率尋找新的路徑（explore），如果新路徑更短，那么螞蟻將被吸引過來，經過一定次數的重復螞蟻最終就能找到巢穴和食物間的最短路徑。

算法步驟（以最短路徑問題為例）

1）給每條路徑上的信息素濃度賦予初值，把a只模擬螞蟻放在b個點上

2）依照概率函數，讓每只螞蟻找出可行路徑，計算路徑長度,選出最優路徑

3）根據路線情況,更新本次最短路徑上的信息素濃度，返回前面循環直到得到最優路徑。

ACO有正反饋與并行性、智能適應的特點。但計算量大，消耗時間久, 常常由于過程中得到較好解影響，陷入局部最優解, 使算法結束。

1.3遺傳算法

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

算法步驟

1）制定搜尋策略與R(控制參數)，隨機產生初始種群A，進化代數 i= 1.

2）對A進行評價, 若進化代數無法累加或達到終止條件則終止算法，輸出最佳個體解.

3）操作種群（交叉變異），處理邊界條件，得到臨時種群B并對其評價，計算每個個體的適應度值

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

遺傳算法使用范圍廣，能夠處理大多數組合優化問題，處理簡單不需要有很高的數學水平, 能夠并行處理，具有較優秀的全局搜索能力，然而常有早熟收斂的現象。

1.4人工神經網絡算法

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

算法步驟：

1）初始化各層連接權值，把問題映射為換位矩陣E。

2） 將E與 神經網絡對應, 每條路徑對應E的元素。

3） 設定能量函數BP, BP的min值點對應問題的解。

4）計算神經網絡的E和偏置電流,。

5）運行網絡直至局部最優解。

Hopfield神經網絡快速且簡單，記憶性強，能夠存儲大量的數據，但是其優化性較差。實驗表明, 神經網絡算法只有局部搜索能力, 若是要提高解有效性概率，那么解的優化能力降低, ,需要恰當的網絡運行參數的設置。

2 結束語

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