猴子算法（MA）是一種元啟發(fā)式搜索算法。 本文將講述該算法的主要組成部分，并提出上漲（向上走勢(shì)）、局部跳躍和全局跳躍的解決方案。 該算法由 R. Zhao 和 W.Tang 于 2007 年提出。 該算法模擬猴子在山上移動(dòng)和跳躍尋找食物時(shí)的行為。 據(jù)推測(cè)，猴子遵循這樣一個(gè)事實(shí)，即山越高，山頂上的食物就越多。

猴子探索的區(qū)域是適應(yīng)度函數(shù)地域，因此最高的山對(duì)應(yīng)于問題的解（赫茲量化軟件考慮全局最大化問題）。 從當(dāng)前位置開始，每只猴子都會(huì)向上移動(dòng)，直至抵達(dá)山頂。 攀爬過程旨在逐步提高目標(biāo)函數(shù)的值。 然后，猴子向隨機(jī)方向進(jìn)行一系列局部跳躍，希望找到更高的山峰，并重復(fù)向上的運(yùn)動(dòng)。 在進(jìn)行了一定次數(shù)的攀爬和局部跳躍后，猴子認(rèn)為它已經(jīng)充分探索了初始位置附近的地域。

為了探索搜索新的空間區(qū)域，猴子進(jìn)行了一次長(zhǎng)距離跳躍。 上述步數(shù)在算法參數(shù)中重復(fù)指定次數(shù)。 該問題的解則聲明為給定猴子種群發(fā)現(xiàn)的最高頂點(diǎn)。 然而，MA 算法在攀登過程中花費(fèi)了大量的計(jì)算時(shí)間用于尋找局部最優(yōu)解。 全局跳躍過程可以加快算法的收斂速度。 這個(gè)過程的目的是迫使猴子尋找新的搜索機(jī)會(huì)，以免陷于本地搜索。 該算法具有結(jié)構(gòu)簡(jiǎn)單、可靠性較高、能很好地搜索局部最優(yōu)解等優(yōu)點(diǎn)。

MA 算法是一種新型的進(jìn)化算法，可以解決許多具有非線性、不可微分性、和高維性的復(fù)雜優(yōu)化問題。 與其它算法的不同之處在于，MA 算法花費(fèi)的時(shí)間主要集中于攀爬過程中尋找局部最優(yōu)解。 在下一章節(jié)中，我將講述算法的主要組件、表示的解、初始化、攀登、觀察和跳躍。

2. 算法

為了便于理解猴子算法，從偽代碼開始是合理的。

MA 算法的偽代碼：

1. 將猴子隨機(jī)分布在搜索空間當(dāng)中。2. 測(cè)量猴子位置的高度。3. 執(zhí)行固定次數(shù)的局部跳轉(zhuǎn)。4. 如果在步驟 3 中得到的新頂點(diǎn)更高，則y以后應(yīng)從該位置進(jìn)行局部跳轉(zhuǎn)。5. 如果局部跳轉(zhuǎn)次數(shù)限制已用盡，且未找到新頂點(diǎn)，則進(jìn)行全局跳轉(zhuǎn)。6. 在步驟 5 之后，重復(fù)步驟 37. 從步驟 2 開始重復(fù)，直到滿足停止準(zhǔn)則。

赫茲量化軟件來(lái)更詳細(xì)地分析偽代碼的每個(gè)關(guān)鍵點(diǎn)。

1. 在優(yōu)化伊始，猴子對(duì)于搜索空間是未知的。 動(dòng)物被隨機(jī)定位在未知的地形中，因?yàn)槭澄锍霈F(xiàn)的位置在任何地方都有同樣可能。

2. 測(cè)量猴子所在高度的過程是由適應(yīng)度函數(shù)履行任務(wù)。

3. 進(jìn)行局部跳轉(zhuǎn)時(shí)，算法參數(shù)中指定的數(shù)字有限制。 這意味著猴子正試圖通過在覓食區(qū)域進(jìn)行小范圍局部跳躍來(lái)改善其當(dāng)前位置。 如果新找到的食物來(lái)源更好，則轉(zhuǎn)到步驟 4。

4. 找到新的食物來(lái)源，重置局部跳躍計(jì)數(shù)。 現(xiàn)在，將從該位置尋找新的食物來(lái)源。

5. 如果局部跳躍不能導(dǎo)致發(fā)現(xiàn)更好的食物來(lái)源，猴子得出結(jié)論，當(dāng)前區(qū)域已充分探索，是時(shí)候?qū)ふ腋h(yuǎn)的新地方了。 在此刻，出現(xiàn)進(jìn)一步跳躍的方向問題？ 該算法的思路是取所有猴子的坐標(biāo)中心，從而提供一些交流 — 猴群中每只猴子之間的交流：猴子可以大聲尖叫，并且具有良好的空間聽力，能夠判定彼此間的確切位置。 同時(shí)，知道彼此的位置（伙伴們不會(huì)在沒有食物的地方呼喚），故可大致計(jì)算出食物的最佳新位置，因此，有必要朝這個(gè)方向跳躍。

在原始算法中，猴子沿著一條穿過所有猴子坐標(biāo)中心和動(dòng)物當(dāng)前位置的線進(jìn)行全局跳躍。 跳轉(zhuǎn)的方向可以是朝向坐標(biāo)中心，也可以是與中心相反的方向。 從中心朝反方向的跳躍，與為所有猴子尋找具有近似坐標(biāo)的食物的邏輯相矛盾，這已被我使用該算法的實(shí)驗(yàn)所證實(shí) — 事實(shí)上，它有 50% 的概率，這是與全局最優(yōu)值的距離。

實(shí)踐表明，跳出坐標(biāo)中心之外，比不跳或朝反方向跳躍更有利可圖。 不會(huì)發(fā)生所有猴子集中在某一點(diǎn)的情況，盡管乍一看這種邏輯不可避免。 事實(shí)上，猴子已經(jīng)用盡了局部跳躍的極限，跳得比中心更遠(yuǎn)，從而扭轉(zhuǎn)了種群中所有猴子的位置。 如果我們?cè)谀X海中想象高等類人猿服從這個(gè)算法，赫茲量化軟件會(huì)看到動(dòng)物團(tuán)伙不時(shí)跳過群體的幾何中心，而團(tuán)伙本身則朝著食物更豐富的來(lái)源移動(dòng)。 這種“團(tuán)伙移動(dòng)”的效果在算法的動(dòng)畫上可以清晰地看到（原來(lái)的算法沒有這個(gè)效果，且結(jié)果更差）。

6. 進(jìn)行全局跳躍后，猴子開始把食物來(lái)源的位置指定到新的地方。 該過程一直持續(xù)到滿足停止準(zhǔn)則。

該算法的整個(gè)思路可以很容易地適應(yīng)單個(gè)示意圖。 猴子的運(yùn)動(dòng)用圖例 1 中帶有數(shù)字的圓圈表示。 每個(gè)數(shù)字都是猴子的新位置。 黃色小圓圈表示失敗的局部跳轉(zhuǎn)嘗試。 數(shù)字 6 表示局部跳躍極限已用盡，且未找到新的最佳食物來(lái)源位置。 沒有數(shù)字的圓圈代表其余團(tuán)伙的位置。 團(tuán)伙的幾何中心由一個(gè)帶有坐標(biāo)（x，y）的小圓圈表示。