猴群算法是於2008年由Zhao和Tang[8]提出的一種新的用於求解大規模、多峰最佳化問題的智慧型最佳化算法.
基本介紹
- 中文名：猴群算法
- 外文名：monkey algorithm
- 時間：2008年
- 提出者：Zhao和Tang
- 目的：求解大規模、多峰最佳化問題
基本信息,最佳化模型,
基本信息
猴群算法是於2008年由Zhao和Tang[8]提出的一種新的用於求解大規模、多峰最佳化問題的智慧型最佳化算法.其思想在於通過模擬自然界中猴群爬山過程中爬、望和跳的幾個動作,設計了三個搜尋過程：爬過程主要用來搜尋當前所在位置的局部最優解；望過程主要通過眺望來搜尋鄰近領域比當前位置更優的解,以便加速最優解的搜尋過程；跳過程的目的在於由當前搜尋區域轉移到其它區域,以避免搜尋過程陷入局部最優.在猴群算法中,其花費的CPU時間主要在於尋找局部最優位置的爬過程.爬過程中每次疊代的計算量主要集中在目標函式偽梯度的計算,其只涉及到當前位置的兩個臨近位置的目標函式值而與決策向量的維數無關.這一特徵顯著地提高了算法的性能,尤其針對高維最佳化問題時效果更為明顯.另外,跳過程迫使猴群由當前區域轉移到新的區域,從而避免算法陷於局部最優.
作為一種智慧型算法, MA能夠有效地求解高維的、非線性不可微的函式最佳化問題.此外, MA需要調整的參數也少,這使得MA易於實現.儘管猴群算法在求解高維數最佳化問題時有了較大的突破,但其也存在一些不足.首先,對於不同的最佳化問題,在利用MA求解時需要設定不同的參數,並且這些參數對猴群算法來說很重要,一旦設定的不準確,即便是最佳化問題的近似最優解也很難找到.另外,猴群算法求解最佳化問題時耗費的CPU時間也較長,在最佳化效率方面仍具有很大的提高空間.基於以上分析,本文結合了猴群算法和混沌搜尋技術提出了一種改進的猴群算法,稱為混沌混群算法CMA.混沌描述的是一種非線性狀態,它同時具有確定性、隨機性和遍歷性.基於混沌的遍歷性及不重複性而提出的混沌搜尋技術比傳統的隨機搜尋技術速度更快,質量更高.將混沌搜尋技術引入到MA中非常必要,這樣在很大程度上避免了猴群算法陷入局部最優.此外,本文採用了變參數的方法設計了一組設用於各種最佳化問題的混沌猴群算法通用參數,在提高了算法性能同時也為算法的使用者提供了便利.
猴群算法（MA）是由Zhao和Tang提出的一種新的用於求解大規模、多峰最佳化問題的智慧型最佳化算法.其思想在於通過模擬自然界中猴群爬山過程中爬、望和跳的幾個動作，設計了三個搜尋過程：爬過程主要用來搜尋當前所在位置的局部最優解；望過程主要通過眺望來搜尋鄰近領域比當前位置更優的解，以便加速最優解的搜尋過程；跳過程的目的在於由當前搜尋區域轉移到其它區域,以避免搜尋過程陷入局部最優.一般來說,在最佳化問題中如果目標函式是一個多峰函式,局部最優點的數量將隨著決策向量維數的增加而急劇增長.一方面,在求解高維最佳化問題時,常用算法如遺傳算法、蟻群算法、粒子群算法等容易陷入局部最優；另一方面,由於需要大量的計算,這些算法所消耗的CPU時間也會大大增長.而在MA中,跳過程的目的恰恰是迫使猴群由當前區域轉移到新的區域,從而避免算法陷於局部最優.另外, MA花費的CPU時間主要在於尋找局部最優位置的爬過程.而在爬過程中每次疊代的計算量主要集中在目標函式偽梯度的計算,其只涉及到當前位置的兩個臨近位置的目標函式值而與決策向量的維數無關.這一特徵顯著地提高了算法的性能,尤其針對高維最佳化問題時效果更為明顯.
最佳化模型
大部分最佳化問題的數學表達形式是最大化（或者最小化）某一些目標函式.不失一般性,本文將只討論最大化的情況,因為任意的極小化問題都可以通過改變目標函式的符號而轉化成最大化問題.全局最佳化問題的一般化模型可表示為：
其中為上的決策向量,為最佳化問題的目標函式,為約束函式.
考慮由Koziel和Michalewicz提出的最佳化問題
(2.1)
圖2.1描述了模型(2.1)的目標函式f(x1,x2)在區間[0, 10]×[0, 10]的輪廓圖形,從中可以看出f(x1, x2)是一個多峰函式.
圖2-1模型中目標函式的圖像
2.2． 猴群算法(MA)
MA由初始化、爬過程、望過程和跳過程等部分組成,這幾部分分別介紹如下.首先,令正整數M表示猴群的群體規模,第i猴子的當前位置用向量xi=(xi1, xi2, . . . , xin), i = 1, 2, . . . , M表示,每隻猴子的位置實際上對應著最佳化問題的一個決策向量.例如,在例1中,令M = 5 ,即5隻猴子組成一個群體.對於第i只猴子的位置,用向量xi= (xi1, xi2), i = 1, 2, . . . , 5表示,它又表示模型(2.1)的一個決策向量.
2.2.1初始化
給每一隻猴子初始產生一個位置,可用產生隨機變數的方法生成.例如,在求解模型(2.1)時,可用以下隨機方法給產生初始位置.
#include "stdlib.h"
for i =1 to M
Mark :
for j=1 to 2
X[i][j]=10*rand()/(RAND_{MAX}-1);
end
if x[i][1]2-x[i][2]+1 >=0goto Mark ;
if 1x[i][1]+(x[i][2]-4)2>=0goto Mark ;
Return(x[i][1],x[i][2]) ;
end
其中rand()表示生成0到RAND_MAX之間隨機數的函式.
注1.在上述初始化過程中,偽代碼的後三行的目的在於檢驗初始位置是否滿足約束。實際上,帶約束的最佳化問題都可以通過“罰函式”法轉化成無約束的最佳化問題。這樣初始化時就不必檢驗位置的可行性,從而節省初始化過程所需的CPU時間。
2.2.2爬過程
爬過程是一個通過疊代逐步改善最佳化問題的目標函式值的過程。經典算法如梯度法大都是沿著目標函式的梯度方向來改進最佳化問題的目標值的。但很多情況下,最佳化問題目標函式的梯度並不存在.故偽梯度算法越來越受到重視,如SPSA用目標函式的偽梯度來代替經典算法中的梯度。
2.2.3望過程
經過爬過程之後,每隻猴子都到達了各自所在山峰的頂處,即目標函式達到了局部最優。之後,它向四周眺望,觀察在它周圍鄰近領域是否存在比當前山峰更高的山峰。如果是,它就會從當前位置跳過去。MA定義了一個參數β稱為視野長度。視野長度β決定了猴子能從當前位置眺望的最遠距離。
2.2.4跳過程
跳過程的主要目的在於搜尋過程有當前區域轉移到新的區域。選擇所有猴子的重心位置作為支點,每隻猴子沿著當前位置指向支點的方向翻到各自新的搜尋區域。
爬過程、望過程和跳過程形成一次循環,重複此循環直至達到預先設定的循環次數算法終止。猴群算法的計算步驟如下
步驟1、 設定猴群的規模參數M及其它參數,並為猴群隨機生成初始位置。步驟2、 爬過程中根據偽梯度最佳化猴群的位置。
步驟3、 在視野參數範圍內搜尋更優位置,並更新猴群位置到更優位置。
步驟4、 在跳區間內選取,並據此迫使猴群到新的範圍內重新搜尋。
步驟5、 檢驗是否滿足結束條件,若滿足,則算法結束；否則,轉到步驟2。
步驟6、 輸出最優目標函式解及對應的最優位置向量。
2.3． 小結
猴群算法（MA）是受自然界猴群爬山過程啟發而設計的基於群體的搜尋算法.作為一種智慧型算法, MA能夠有效地求解高維的、非線性不可微的函式最佳化問題.此外, MA需要調整的參數也少,這使得MA易於實現.
