齊艷玉，蘭燕飛

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

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

1 一類動(dòng)態(tài)優(yōu)化問(wèn)題的模型

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

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

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

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

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

2.1 混沌猴群算法

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

2.2 模型的離散化處理

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

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

2.3 混沌猴群算法求解動(dòng)態(tài)優(yōu)化問(wèn)題

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

(2)混沌初始化。郝士鵬采用Logistic 函數(shù)y(k+1)=4y(k)(1－y(k))產(chǎn)生混沌變量來(lái)進(jìn)行初始化，其中，y 為混沌變量，k 為迭代次數(shù)。但是Logistic 函數(shù)只有當(dāng)初值y0?{0.00，0.25，0.50，0.75}時(shí)，混沌變量y(k)的軌跡才可以遍歷整個(gè)值域范圍。筆者采用一個(gè)遍歷性更好且沒(méi)有初始值限制的混沌函數(shù)y(k+1)=sin 2/y(k)來(lái)對(duì)模型的解進(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)化問(wèn)題的定義域內(nèi);④若達(dá)到規(guī)定最大迭代次數(shù)，則終止;否則，令k =k+1，返回步驟②。

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

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

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

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

3 數(shù)值算例

考慮如下例子:

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

表1 CMA 的參數(shù)

表2 例子的結(jié)果

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

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

4 結(jié)論

筆者介紹了CMA 在求解動(dòng)態(tài)優(yōu)化問(wèn)題中的應(yīng)用，給出了詳細(xì)的求解方法，并通過(guò)一個(gè)算例驗(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é)圖書(shū)館，2010.

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

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

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

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

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

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