1. 概述

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

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

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

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

編輯切換為居中

2. 算法

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

MA 算法的偽代碼：

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

赫茲量化來更詳細(xì)地分析偽代碼的每個關(guān)鍵點。

1. 在優(yōu)化伊始，猴子對于搜索空間是未知的。 動物被隨機(jī)定位在未知的地形中，因為食物出現(xiàn)的位置在任何地方都有同樣可能。

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

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

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

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

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

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

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

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

編輯切換為居中

圖例 1. 猴子按團(tuán)伙移動的示意圖

赫茲量化來看一下 MA 的代碼。

用 S_Monkey 結(jié)構(gòu)描述猴子團(tuán)伙很方便。 該結(jié)構(gòu)包含具有當(dāng)前坐標(biāo)的 c [] 數(shù)組、具有最佳食物坐標(biāo)的 cB [] 數(shù)組（正是從具有這些坐標(biāo)的位置發(fā)生局部跳躍）、h 和 hB — 分別是當(dāng)前位置的高度值，和最高點的值。 lCNT — 局部跳轉(zhuǎn)計數(shù)器，用于限制嘗試改善位置的次數(shù)。

//—————————————————————————————————————————————————————————————————————————————— struct S_Monkey { ?double c ?[]; //coordinates ?double cB []; //best coordinates ?double h; ? ? //height of the mountain ?double hB; ? ?//best height of the mountain ?int ? ?lCNT; ?//local search counter }; //——————————————————————————————————————————————————————————————————————————————

C_AO_MA 猴子算法類與前面討論的算法沒有什么不同。 猴子團(tuán)伙在類中表示為 m[] 結(jié)構(gòu)數(shù)組。 類中聲明的方法和成員代碼量都很小。 這是由于算法簡潔，因此與許多其它優(yōu)化算法不同，此處無需排序。 赫茲量化將需要數(shù)組來設(shè)置優(yōu)化參數(shù)的最大值、最小值和步長，以及常量變量以便能將算法的外部參數(shù)傳遞給它們。 赫茲量化繼續(xù)講述包含 MA 主邏輯的方法。

//—————————————————————————————————————————————————————————————————————————————— class C_AO_MA { ?//---------------------------------------------------------------------------- ?public: S_Monkey m ? ? ? []; //monkeys ?public: double rangeMax ?[]; //maximum search range ?public: double rangeMin ?[]; //minimum search range ?public: double rangeStep []; //step search ?public: double cB ? ? ? ?[]; //best coordinates ?public: double hB; ? ? ? ? ? //best height of the mountain ?public: void Init (const int ? ?coordNumberP, ? ? //coordinates number ? ? ? ? ? ? ? ? ? ? const int ? ?monkeysNumberP, ? //monkeys number ? ? ? ? ? ? ? ? ? ? const double bCoefficientP, ? ?//local search coefficient ? ? ? ? ? ? ? ? ? ? const double vCoefficientP, ? ?//jump coefficient ? ? ? ? ? ? ? ? ? ? const int ? ?jumpsNumberP); ? ?//jumps number ?public: void Moving ? (); ?public: void Revision (); ?//---------------------------------------------------------------------------- ?private: int ? ?coordNumber; ? ? ? //coordinates number ?private: int ? ?monkeysNumber; ? ? //monkeys number ?private: double b []; ? ? ? ? ? ? ?//local search coefficient ?private: double v []; ? ? ? ? ? ? ?//jump coefficient ?private: double bCoefficient; ? ? ?//local search coefficient ?private: double vCoefficient; ? ? ?//jump coefficient ?private: double jumpsNumber; ? ? ? //jumps number ?private: double cc []; ? ? ? ? ? ? //coordinate center ?private: bool ? revision; ?private: double SeInDiSp ?(double In, double InMin, double InMax, double Step); ?private: double RNDfromCI (double min, double max); ?private: double Scale ? ? (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, ?bool revers); }; //——————————————————————————————————————————————————————————————————————————————

公開 Init() 方法初始化算法。 在此，赫茲量化設(shè)置數(shù)組的大小。 赫茲量化用盡可能小的“雙精度”值初始化猴子找到的最佳領(lǐng)土的品質(zhì)，赫茲量化將對 MA 結(jié)構(gòu)數(shù)組的相應(yīng)變量執(zhí)行相同的操作。

//—————————————————————————————————————————————————————————————————————————————— void C_AO_MA::Init (const int ? ?coordNumberP, ? ?//coordinates number ? ? ? ? ? ? ? ? ? ?const int ? ?monkeysNumberP, ?//monkeys number ? ? ? ? ? ? ? ? ? ?const double bCoefficientP, ? //local search coefficient ? ? ? ? ? ? ? ? ? ?const double vCoefficientP, ? //jump coefficient ? ? ? ? ? ? ? ? ? ?const int ? ?jumpsNumberP) ? ?//jumps number { ?MathSrand ((int)GetMicrosecondCount ()); // reset of the generator ?hB ? ? ? = -DBL_MAX; ?revision = false; ?coordNumber ? = coordNumberP; ?monkeysNumber = monkeysNumberP; ?bCoefficient ?= bCoefficientP; ?vCoefficient ?= vCoefficientP; ?jumpsNumber ? = jumpsNumberP; ?ArrayResize (rangeMax, ?coordNumber); ?ArrayResize (rangeMin, ?coordNumber); ?ArrayResize (rangeStep, coordNumber); ?ArrayResize (b, ? ? ? ? coordNumber); ?ArrayResize (v, ? ? ? ? coordNumber); ?ArrayResize (cc, ? ? ? ?coordNumber); ?ArrayResize (m, monkeysNumber); ?for (int i = 0; i < monkeysNumber; i++) ?{ ? ?ArrayResize (m [i].c, ?coordNumber); ? ?ArrayResize (m [i].cB, coordNumber); ? ?m [i].h ? ?= -DBL_MAX; ? ?m [i].hB ? = -DBL_MAX; ? ?m [i].lCNT = 0; ?} ?ArrayResize (cB, coordNumber); } //——————————————————————————————————————————————————————————————————————————————

第一個公開方法 Moving()，需要在每次迭代時執(zhí)行，實現(xiàn)猴子跳躍邏輯。 在第一次迭代中，若 “revision” 標(biāo)志為 “false” 時，則有必要采用所研究空間坐標(biāo)范圍內(nèi)的隨機(jī)值初始化代理者，這相當(dāng)于猴子在團(tuán)伙棲息地內(nèi)的隨機(jī)位置。 為了減少重復(fù)的乘法運算，例如計算全局和局部跳轉(zhuǎn)的系數(shù)，我們將相應(yīng)坐標(biāo)的值（每個坐標(biāo)可以有自己的維度）存儲在 v [] 和 b [] 數(shù)組當(dāng)中。 赫茲量化將每只猴子的局部跳躍計數(shù)器重置為零。

//---------------------------------------------------------------------------- if (!revision) { ?hB = -DBL_MAX; ?for (int monk = 0; monk < monkeysNumber; monk++) ?{ ? ?for (int c = 0; c < coordNumber; c++) ? ?{ ? ? ?m [monk].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]); ? ? ?m [monk].c [c] = SeInDiSp ?(m [monk].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); ? ? ?m [monk].h ? ? = -DBL_MAX; ? ? ?m [monk].hB ? ?= -DBL_MAX; ? ? ?m [monk].lCNT ?= 0; ? ?} ?} ?for (int c = 0; c < coordNumber; c++) ?{ ? ?v [c] = (rangeMax [c] - rangeMin [c]) * vCoefficient; ? ?b [c] = (rangeMax [c] - rangeMin [c]) * bCoefficient; ?} ?revision = true; }

為了計算所有猴子的坐標(biāo)中心，需用到 cc [] 數(shù)組，其維度對應(yīng)于坐標(biāo)數(shù)量。 此處的思路是將猴子的坐標(biāo)相加，然后將結(jié)果總和除以團(tuán)伙規(guī)模。 因此，坐標(biāo)的中心既是坐標(biāo)的算術(shù)平均值。