隨機搜尋

隨機搜尋，是指在目標位置基本服從均勻分布的條件下, 搜尋軌跡隨機且均勻散布在目標分布區域內的一種搜尋方式。常用的隨機搜尋算法主要包括模擬退火算法、遺傳算法、進化策略等。

基本介紹

• 中文名：隨機搜尋
• 外文名：organic search
• 同義詞：隨機搜尋
• 主要方法：模擬退火、遺傳算法、進化策略
• 優點：簡便易行
• 套用學科：計算機科學、通信工程、控制科學

簡介

隨機搜尋是一種在巨大數據規模下執行一個耗時上無法接受的程式的最佳化方法，是指在目標位置基本服從均勻分布的條件下, 搜尋軌跡隨機且均勻散布在目標分布區域內的一種搜尋方式。它可以用以對一個搜尋算法施展最佳化的前提是：

1、數據規模大，精確的結果難以在一定時間計算出。

2、結果的些許的不精確能夠被接受。

3、求取的結果是最最佳化（optimization）問題，有一個成本計算模型。

常用的隨機搜尋算法主要包括模擬退火算法、遺傳算法、進化策略等。近年出現的一些隨機搜尋算法(如模擬退火算法，遺傳算法，進化策略)為NP完全問題的解決提供了一條新途徑，它們都是利用自然現象與最佳化過程的某些相似性而逐步發展起來的隨機搜尋技術。

如果被搜尋目標位置在多數情況下不服從均勻分布, 以及隨機搜尋軌跡的隨意性和搜尋力散布的均勻性等特徵, 使得隨機搜尋的效率較低, 所以, 儘管隨機搜尋簡便易行, 但許多軍事指揮員通常情況下都不願採用。

模擬退火算法（SA）

算法思路

模擬退火(SimulatedAnnealing，SA)算法是Kirkpatrick等人提出的隨機搜尋算法，是求解複雜大規模最佳化問題比較常用的算法。

模擬退火算法源於固體退火過程的模擬。固體退火是先將固體加熱至熔化，再徐徐冷卻使之凝固成規整的晶體，熔解是為了消除系統中原先可能存在的非均勻狀態，冷卻過程之所以徐徐進行是為了使系統在每一溫度下都達到平衡態。因為在平衡態，系統的自由能達到最小值。如果將最佳化問題的目標函式類比為能量函式，控制參數類比為溫度T，模擬固體退火過程就可將給定控制參數值時最佳化問題的相對最優解求出，然後減少控制參數使其趨於0，最終求得組合最佳化問題的整體最優解。

遺傳算法(GA)

遣傳算法(GeneticAlgorithm，GA)是70年代中期由美國Michigan大學的JohnHolland教授和他的學生們發展建立的(這時的算法被稱為傳統GA)。Hollstien第一個嘗試將GA套用於函式最佳化問題，DeJong也通過實驗對GA套用於函式最佳化問題進行了研究，並結合模式定理得出一系列實驗結果。

遺傳算法的幾個關鍵步驟如下：

編碼

使用遺傳算法進行搜尋之前首先將變數進行編碼，最常用的編碼方式是二值編碼，即將x用字元{0，1}組成定長的字元串(設長為l)，這些字元串的不同組合就構成了不同的點。

產生初始群體

隨機產生n個初始字元串組成一群體，一般說來，初始群體點的質量很差，遺傳算法就是從這些群體出發開始疊代。

計算適應性值

適應性函式F(x)是表明個體對環境適應能力強弱的，計算適應性函式值即按編碼規則將群體中每一個個體的編碼值所對應的自變數取值xi代入F(xi)(i=1，…，n)算出其函式值，F(x_i)值越大，表明其對環境的適應能力越強。

選擇

一個群體中同時有n個個體存在，這些個體哪個保留用以繁殖後代，哪個被淘汰是根據它們對環境的適應能力決定的，適應性強的有更多的機會保留下來，這一思想通過選擇過程來體現。選擇的原則是適應性值大的個體為下一代貢獻一個或多個後代的機率大。選擇的方式是以一定的機率從群體中選取n個個體(有重複選取)作為下一代的雙親用於繁殖後代，一般每個個體被選擇的機率P(i)與F(xi)成正比，所以選擇體現了自然界中適者生存的思想。

交換

以一定的機率從群體中隨機選取兩個個體，再隨機選擇一個交換位置i(1≤i≤l)，交換兩個個體位置i左邊的部分，產生兩個新個體，新個體組合了其父輩個體的特性。交換的目的在於產生新的基因組合，而不是一代代重複同樣的個體。

變異

變異首先在群體中隨機選擇一個個體，對於選中的個體以一定的機率隨機地改變字元串中某個字元的值，對於二值編碼就是將1變成0或將0變成1。變異模擬了生物進化過程中的基因突變現象，它為新點的產生提供了機會。

進化策略(ES)

起源

進化策略源於自然界生物進化過程。自然界生物的進化通過兩個基本過程:自然選擇和有性生殖不斷進化。在漫長的進化過程中，生物逐漸從簡單的低級生物到人類，這是一個完美的進化過程。按達爾文進化論的觀點，這一過程遵循適者生存，優勝劣汰的自然選擇原則，它使自然界生物的演化問題得到較好地解決。正因為如此，人們開始把進化這種奇異的本領看成值得仿效的東西。即用搜尋和最佳化過程模擬生物體的進化過程，用搜尋空間中的點模擬自然界生物體，經過變形後的目標函式度量生物體對環境的適應能力，生物優勝劣汰類比為最佳化和搜尋過程中用好的可行解取代較差可行解的疊代過程。這樣就形成了進化策略和遺傳算法。

基本作法

進化策略(EvolutionStrategies，ES)的研究源於60年代。它利用生物的進化與數值最佳化過程之間的某種相似性，模仿生物進化過程的求解數值最佳化問題的算法。其基本作法是:給定n個個體作為父本，由它們產生λ個後代λ個後代中選n個最好的作為下一代的父本繼續疊代。當λ=n=1時，稱為二元進化策略，n>1時稱為多元進化策略，引入多元是為了更好地模擬自然進化，改進最佳化結果。

研究方向

上述隨機搜尋算法在解決實際問題中都發揮了巨大的作用，但它們還有一些需要進一步研究的問題:

(1)理論研究

從理論和實驗上研究算法的計算複雜性，證明GA和ES的全局收斂性問題，探討群體規模和遺傳運算元的控制參數選取問題。

(2)引入新的遺傳運算元

對GA和ES來說，遺傳運算元在算法中起了重要作用，但傳統的遺傳運算元有很大局限性，為提高算法的效率，必須引進新的更高級的遺傳運算元。

(3)加強算法搜尋的目的性

SA、GA、ES較完全隨機算法的優點在於搜尋過程不是完全盲目的，而帶有一定的目的性，但仍需發展一些啟發式策略，引入領域知識，對搜尋過程給予更加明確的引導。

(4)進一步研究算法的並行性，可以提高計算效率。