齊艷玉，蘭燕飛

(天津大學(xué) 系統(tǒng)工程研究所，天津300072)

一些性能優(yōu)異的啟發(fā)式智能算法，如遺傳算法(GA)［1－4］、粒子群算法(PSO)［5］和人工神經(jīng)網(wǎng)絡(luò)(ANN)［6－7］等在很大程度上增強(qiáng)了人類對復(fù)雜優(yōu)化問題的求解能力，已在各個領(lǐng)域得到了廣泛應(yīng)用。但這些算法幾乎毫無例外地都很難逃脫所謂的“維數(shù)災(zāi)難”問題，在實(shí)際應(yīng)用中也受到諸多限制。2008 年ZHAO 和TANG［8］提出一種新的用于求解大規(guī)模、多峰優(yōu)化問題的智能優(yōu)化算法，即猴群算法(MA)。隨后，郝士鵬［9］結(jié)合猴群算法和混沌搜索技術(shù)，提出了混沌猴群算法(CMA)?；诨煦绲谋闅v性及不重復(fù)性而提出的混沌搜索技術(shù)比傳統(tǒng)的隨機(jī)搜索技術(shù)速度更快，質(zhì)量更高，將混沌搜索技術(shù)引入到MA 中在很大程度上避免了猴群算法陷入局部最優(yōu)。作為一種智能算法，MA 及其改進(jìn)算法能夠有效地求解高維、非線性不可微的函數(shù)優(yōu)化問題，并且MA 需要調(diào)整的參數(shù)也少，這使得MA 易于實(shí)現(xiàn)，具有廣闊的應(yīng)用前景。文獻(xiàn)［10］在利用模糊模擬技術(shù)來估計目標(biāo)函數(shù)中模糊事件可信性的基礎(chǔ)上設(shè)計了基于模糊模擬的猴群算法來對無約束優(yōu)化問題進(jìn)行求解，并獲得了原模糊約束滿足問題的約束一致解。文獻(xiàn)［11］針對項目進(jìn)度問題的模糊相關(guān)機(jī)會規(guī)劃模型設(shè)計了猴群算法的模糊模擬求解方法。文獻(xiàn)［12］針對入侵檢測系統(tǒng)存在高漏報率的問題，提出了一種基于猴群算法的入侵檢測技術(shù)，改進(jìn)了生成規(guī)則的質(zhì)量，提高了入侵檢測系統(tǒng)的檢測率。文獻(xiàn)［13］結(jié)合輸電網(wǎng)擴(kuò)展規(guī)劃問題的特點(diǎn)提出了求解含有離散變量優(yōu)化問題的離散猴群算法(DMA)。然而，由于MA 出現(xiàn)的時間較短，對MA 及其改進(jìn)算法的應(yīng)用研究還較少。筆者擬設(shè)計一種適用于求解動態(tài)規(guī)劃問題的智能算法，鑒于CMA 在問題求解的性能方面更優(yōu)于MA，因此，選用CMA 設(shè)計了求解一類動態(tài)規(guī)劃問題的混沌猴群算法。

1 一類動態(tài)優(yōu)化問題的模型

動態(tài)優(yōu)化問題廣泛存在于工程實(shí)際和日常生活中，其最優(yōu)解會因?yàn)槟繕?biāo)函數(shù)、環(huán)境參數(shù)或者約束條件的變化而隨時發(fā)生變化，因此，在解決這些動態(tài)優(yōu)化問題時，需要一類功能強(qiáng)大的智能算法對變化做出準(zhǔn)確響應(yīng)，并及時地做出新環(huán)境下的最優(yōu)或滿意決策。

目前，對動態(tài)優(yōu)化問題的求解，一方面，由于實(shí)際系統(tǒng)的復(fù)雜性較難得到解析解，另一方面，借助計算機(jī)應(yīng)用智能算法求解的研究很少，因此，需利用性能優(yōu)越的智能算法去求解動態(tài)優(yōu)化問題。

考慮如下一類動態(tài)優(yōu)化問題的基本模型［14］:

求解最優(yōu)控制問題，傳統(tǒng)方法包括變分法、最大(最小值)原理、動態(tài)規(guī)劃等。對于一些復(fù)雜的實(shí)際問題，有時利用傳統(tǒng)方法很難求得解析解，然而，實(shí)際應(yīng)用中人們需要得到的往往只是一些階段的數(shù)值解，因此，智能算法作為一種新的求解方法被用來幫助尋找數(shù)值解。

2 一類動態(tài)優(yōu)化問題的混沌猴群算法

2.1 混沌猴群算法

猴群算法是一種新的用于求解大規(guī)模、多峰優(yōu)化問題的智能優(yōu)化算法，其思想在于通過模擬自然界中猴群爬山過程設(shè)計了爬、望和跳這3 個過程。郝士鵬結(jié)合猴群算法和混沌搜索技術(shù)提出了一種改進(jìn)的、性能更加優(yōu)越的猴群算法，稱為混沌猴群算法CMA，主要包括混沌初始化、步長遞減的爬過程、參數(shù)遞增的混沌望過程和邊緣跳過程4 個步驟。

2.2 模型的離散化處理

計算機(jī)所處理的數(shù)據(jù)是數(shù)字量，它不僅在數(shù)值上是整量化的，而且在時間上是離散化的，因此在利用CMA 進(jìn)行求解之前，先對模型進(jìn)行離散化處理。離散是按一個等樣采樣周期t 的采樣過程處理，即將t 變?yōu)閗t(k=0，1，2，…，為一正整數(shù))?？刂谱兞縰(t)被認(rèn)為僅在采樣時刻發(fā)生變化，在相鄰兩采樣時刻之間，u(t)是通過零階保持器保持不變的，且等于前一采樣時刻之值，即在kt 和(k+1)t 之間，u(t)=u(kt)=常數(shù)。式(1)通過離散化，可轉(zhuǎn)化為如下形式［15］:

經(jīng)離散化后，可以看出，原問題變?yōu)橐粋€多維的優(yōu)化問題，由于CMA 在求解多維優(yōu)化問題上的優(yōu)越性，因此可采用CMA 對其求解。

2.3 混沌猴群算法求解動態(tài)優(yōu)化問題

(1)解的表示。令正整數(shù)M 為猴群的規(guī)模，xi=(xi1，xi2，…，xin)，i=1，2，…，M，xi表示第i 個猴子的當(dāng)前位置，每只猴子的位置對應(yīng)優(yōu)化問題的一個決策向量。在式(2)中，決策向量為u =(u1，u2，…，uN)，令M =5，則向量ui= (ui1，ui2，…，uiN)，i=1，2，…，5，表示5 只猴子的位置，同時又可以視為式(2)的5 個解。

(2)混沌初始化。郝士鵬采用Logistic 函數(shù)y(k+1)=4y(k)(1－y(k))產(chǎn)生混沌變量來進(jìn)行初始化，其中，y 為混沌變量，k 為迭代次數(shù)。但是Logistic 函數(shù)只有當(dāng)初值y0?{0.00，0.25，0.50，0.75}時，混沌變量y(k)的軌跡才可以遍歷整個值域范圍。筆者采用一個遍歷性更好且沒有初始值限制的混沌函數(shù)y(k+1)=sin 2/y(k)來對模型的解進(jìn)行初始化。在值域［a，b］內(nèi)產(chǎn)生混沌變量的步驟如下:①令k=0，且設(shè)置y(0)的初始值;②利用混沌函數(shù)y(k+1)=sin 2/y(k)產(chǎn)生下一次迭代后的混沌變量值;③利用線性變換公式u(k)=a +y(k)(b－a)將混沌變量的值域轉(zhuǎn)換到優(yōu)化問題的定義域內(nèi);④若達(dá)到規(guī)定最大迭代次數(shù)，則終止;否則，令k =k+1，返回步驟②。

uij(i=1，2，…，M，j=1，2，…，N)的初始值通過在［a，b］上循環(huán)迭代產(chǎn)生混沌變量。

(4)參數(shù)遞增的混沌望過程。經(jīng)過爬過程之后，每只猴子都達(dá)到了各自所在山峰的頂處，即目標(biāo)函數(shù)達(dá)到了局部最優(yōu)。望過程是用來觀察周圍鄰近區(qū)域是否存在比當(dāng)前位置更高的山峰，若存在，則跳過去。CMA 設(shè)計了一種逐漸遞增的視野參數(shù)β 與遞增的望時間ω 來達(dá)到算法的收斂速度和解的質(zhì)量與CPU 的耗費(fèi)時間的平衡:β(k+1)=ρβ(k)，ω(k+1)=φω(k)，其中，ρ 和φ 為遞增因子，k 為循環(huán)次數(shù)。

(5)邊緣跳過程。假設(shè)經(jīng)過望過程后猴子已經(jīng)不能在其視野范圍內(nèi)找到更好的位置，邊緣跳過程的主要目的在于搜索由當(dāng)前區(qū)域轉(zhuǎn)移到新的區(qū)域，猴子跳的方向?yàn)檠刂赶蚝锶褐c(diǎn)的方向跳到視野的最邊緣處。

(6)終止。經(jīng)過步長遞減的爬過程、參數(shù)遞增的混沌望過程和邊緣跳過程之后，完成了一次完整的循環(huán)，在達(dá)到預(yù)設(shè)的循環(huán)次數(shù)之后，CMA將終止。

3 數(shù)值算例

考慮如下例子:

對式(3)求解的CMA 用C + +語言實(shí)現(xiàn)，參數(shù)的設(shè)置見表1，結(jié)果見表2。

表1 CMA 的參數(shù)

表2 例子的結(jié)果

J 的最優(yōu)值為0，由表2 可以看出，用CMA 計算出的結(jié)果非常接近最優(yōu)值，并且N 越大，結(jié)果越精確，可以根據(jù)實(shí)際需要選擇合適的N 值，圖1為N=10 時的控制函數(shù)u(t)的曲線。

圖1 控制函數(shù)u(t)的曲線

4 結(jié)論

筆者介紹了CMA 在求解動態(tài)優(yōu)化問題中的應(yīng)用，給出了詳細(xì)的求解方法，并通過一個算例驗(yàn)證了方法的可行性。由于MA 及其改進(jìn)算法CMA 是一種性能良好的智能算法，在實(shí)際應(yīng)用中有廣闊的應(yīng)用前景，因此關(guān)于MA 及其改進(jìn)算法的研究和應(yīng)用還有大量的工作要做。

［1］ HOLLAND J H. Adaptation in natural and artificial systems［M］. Michigan: University of Michigan Press，1975:12－98.

［2］ CHANG T J，YANG S C，CHANG K J.Portfolio optimization problems in different risk measures using genetic algorithm［J］. Expert Systems with Applications，2009，36(7):10529－10537.

［3］ IP W H，HUANG M，YUNG K L，et al. Genetic algorithm solution for a risk－based partner selection problem in a virtual enterprise［J］. Computers ＆ Operations Research，2003，30(2):213－231.

［4］ WU Q H，CAO Y J，WEN J Y.Optimal reactive power dispatch using an adaptive genetic algorithm［J］. International Journal of Electrical Power Energy Systems，1998，20(8):563－569.

［5］ KENNEDY J，EBERHART R C.Particle swarm optimization［C］//IEEE International Conference on Neural Networks. Perth:［s.n.］，1995:1942－1948.

［6］ HAGAN M T，DEMUTH H B.Neural networks for control［C］//Proceedings of the 1999 American Control Conference.［S.l.］:［s.n.］，1999:1642－1656.

［7］ HOPFIELD J J.Neural networks and physical systems with emergent collective computational properties［C］//Proceedings of the National Academy of Sciences.［S.l.］:［s.n.］，1982:2554－2558.

［8］ ZHAO R Q，TANG W S. Monkey algorithm for global numerical optimization［J］. Journal of Uncertain Systems，2008，2(3):164－175.

［9］ 郝士鵬.混沌猴群算法及其應(yīng)用［D］.天津:天津大學(xué)圖書館，2010.

［10］趙瑞清，郝士鵬. 一類新的模糊約束滿足問題的建模與求解［J］.系統(tǒng)工程學(xué)報，2010，25(3):415－420.

［11］趙濤，夏雨，宗瑪利.基于猴群算法的加氣站項目進(jìn)度研究［J］.價值工程，2010，29(8):90－92.

［12］張佳佳，張亞平，孫濟(jì)洲.基于猴群算法的入侵檢測技術(shù)［J］.計算機(jī)工程，2011，37(14):131－133.

［13］王靖然，余貽鑫，曾沅.離散猴群算法及其在輸電網(wǎng)擴(kuò)展規(guī)劃中的應(yīng)用［J］. 天津大學(xué)學(xué)報，2010，43(9):798－803.

［14］劉豹，唐萬生. 現(xiàn)代控制理論［M］. 北京:機(jī)械工業(yè)出版社，2006:23－104.

［15］老大中.變分法基礎(chǔ)［M］. 北京:國防工業(yè)出版社，2006:76－132.