易新兵，楊 凱

（1.空軍工程大學(xué)航空航天工程學(xué)院，陜西 西安710038；2.95019部隊，湖北 老河口441800）

1 引言

近年來，在優(yōu)化算法領(lǐng)域出現(xiàn)的群智能SI（Swarm Intelligence）優(yōu)化算法［1］，作為解決傳統(tǒng)復(fù)雜問題的一種新興演化計算技術(shù)已成為國內(nèi)外眾多研究者關(guān)注的熱點。它通過模擬自然界昆蟲的行為研究，利用特定規(guī)則來指導(dǎo)整個解空間中優(yōu)良解的探索，人工魚群算法是一種群智能優(yōu)化算法，它研究模擬魚類的覓食行為、追尾行為和聚群行為等，通過每條人工魚的局部尋優(yōu)達到全局尋優(yōu)。它作為一種新型的尋優(yōu)策略，具有魯棒性強、全局收斂性好、對初值敏感性小等優(yōu)勢，可以用于解決各種連續(xù)優(yōu)化和組合優(yōu)化問題［2］。但是，由于固定步長和隨機行為的存在，該算法存在著尋優(yōu)精度不高、后期收斂速度變慢及不易跳出局部極值等不足。由于混沌運動的遍歷性，混沌作為一種局部搜索方法可以提高人工魚群算法的全局搜索能力。人工魚群算法已搜索的最優(yōu)解能夠反饋指導(dǎo)人工魚移動，并引入吞食行為，以降低算法復(fù)雜度。因此，研究基于混沌搜索和人工魚群行為的混合算法改進及其尋優(yōu)性能，可以改良單一算法的全局尋優(yōu)精度和收斂速度，對于解決現(xiàn)實的復(fù)雜工程優(yōu)化問題具有重要的理論意義和實際價值。

文獻［3］介紹了人工魚吞食（Swallowing）行為，定義在算法達到一定迭代次數(shù)后每次淘汰掉一個弱小人工魚；文獻［4］采用混沌人工魚群算法對灌區(qū)優(yōu)化配水模型進行了優(yōu)化計算。本文以混沌優(yōu)化搜索和改進人工魚行為為重點，組合映射產(chǎn)生復(fù)合混沌搜索局部極值策略，并引入人工魚的反饋－吞食行為，提高人工魚群算法全局收斂性，反饋信息和吞食行為提高算法的收斂精度和速度，基于此策略和行為的混合算法性能得到更大提升。（

2 基于復(fù)合映射的混沌搜索

混沌運動具有遍歷性、隨機性等特性，能在一定范圍內(nèi)按其自身規(guī)律不重復(fù)地遍歷所有狀態(tài)［5］，其軌跡對初始值極其敏感，由確定性的迭代公式產(chǎn)生?；诖颂卣鞯幕煦缬成淇梢宰鳛橐环N局部搜索方法來提高其他優(yōu)化算法的全局搜索能力，并能夠避免算法陷入局部極值。

2.1 復(fù)合混沌映射

本文提出了利用Tent映射和Logistic映射進行復(fù)合產(chǎn)生混沌映射的搜索方法。

Logistic映射定義為：

將式（2）的初始值xn產(chǎn)生的迭代數(shù)列xn＋1∈（0，1）代入式（1）中，作為Tent映射的初始值進行復(fù)合迭代，可以得到新的映射，其具有類拋物線型，該復(fù)合映射在μ∈［1，2］時是單一的滿映射，序列具有有界性，并可進入混沌狀態(tài)。其方程式為：

Tent映射定義為：

2.2 Lyapunov指數(shù)對比及最佳μ值

Lyapunov指數(shù)表示映像中相鄰點相互分離的快慢或奇異吸引子中軌道對初始條件的敏感依賴。Lyapunov指數(shù)定義為：

圖1為根據(jù)式（4）求得的上述三種映射Lyapunov指數(shù)隨參數(shù)μ（α）變化的曲線。

Figure 1 Three mapping systems Lyapunov exponent spectrum with different aandμ圖1 不同α、μ值下，三種映射系統(tǒng)對應(yīng)的Lyapunov指數(shù)譜（α、μ均等分1 000點，初值x1 ＝0.4，迭代2 000點）

計算得知，在相同條件下，復(fù)合映射的最大Lyapunov指數(shù)為0.829 6，比Logistic映射的最大Lyapunov指數(shù)（0.629 5）和Tent映射的最大Lyapunov指數(shù)（0.577 6）都要大。而且當(dāng)μ＝2時由式（3）確定的復(fù)合映射Lyapunov指數(shù)達到最大值，具有更好的初值敏感性，混沌特性明顯，從而使其局部搜索能力較單一混沌映射要強。復(fù)合混沌映射方程式為：

2.3 復(fù)合混沌搜索策略

不失一般性，設(shè)有一個n維優(yōu)化問題：min σ＝f（X），X ＝ （x1，x2，…，xn），xj是其第j 維決策變量且xmin，j＜xj＜xmax，j，復(fù)合混沌搜索的具體步驟如下。

步驟4 根據(jù)所求優(yōu)化問題的目標(biāo)函數(shù)σ＝f（X）評價決策變量的優(yōu)劣。如果優(yōu)于，即f（X（k＋1））＜f（X（k）），則輸出，，…，）作為復(fù)合混沌局部搜索結(jié)果；否則，令k＝k＋1，返回步驟2。

作為局部搜索技術(shù)的混沌搜索策略［6］，采用對初值更具敏感性和軌跡遍歷性的復(fù)合混沌搜索局部極值，能夠提高搜索精度和速度，避免長時間尋優(yōu)陷入局部極值的問題。

3 基于復(fù)合混沌搜索及改進人工魚群行為的混合算法

3.1 基本人工魚群算法

人工魚群算法是在對動物群體智能行為研究的基礎(chǔ)上提出的一種新型仿生優(yōu)化算法，根據(jù)“水域中魚生存數(shù)目最多的地方一般就是本水域中富含營養(yǎng)物質(zhì)最多的地方”這一特點來模仿魚群的覓食、聚群、追尾和隨機四種基本行為而實現(xiàn)尋優(yōu)，主要通過模擬魚類的基本行為，采用自上而下的尋優(yōu)模式從構(gòu)造個體的底層行為開始，利用魚群中各個體的局部尋優(yōu)，達到全局最優(yōu)值在群體中突現(xiàn)出來的目的。算法的人工魚模型有五個基本參數(shù)變量：人工魚總數(shù)N、移動最大步長step、人工魚視野visual、嘗試次數(shù)try＿number和擁擠度因子δ；函數(shù)部分包括人工魚所在位置食物濃度、人工魚行為函數(shù)和評價函數(shù)。

人工魚群算法在優(yōu)化過程中跳出局部極值區(qū)域、實現(xiàn)全局極值尋優(yōu)的原理為：在人工魚覓食行為中，較少的嘗試次數(shù)提供了更多隨機游動的機會，使魚跳出局部極值的領(lǐng)域；擁擠度因子限制魚聚群的規(guī)模，使較優(yōu)的地方聚集更多人工魚來廣泛尋優(yōu)；聚群和追尾行為能夠使陷于局部極值的人工魚向大部分趨向全局最優(yōu)值的魚方向聚集，或者向處于更優(yōu)的全局極值的魚方向追隨，從而逃離局部極值。在基本人工魚群算法中，覓食行為奠定了算法收斂的基礎(chǔ)，聚群行為增強了算法收斂的穩(wěn)定性，追尾行為則增強了收斂的速度和全局性，行為分析過程為人工魚群算法的速度效率和穩(wěn)定性提供了保障［7］。

3.2 人工魚群反饋－吞食策略的提出

為了記錄最優(yōu)人工魚的狀態(tài)，人工魚群算法引入了公告牌。通過人工魚自身狀態(tài)與公告牌狀態(tài)的比較，使得公告牌記錄歷史最優(yōu)值。同時，公告牌記錄的最優(yōu)狀態(tài)也可以反饋給人工魚用來指導(dǎo)下一步行動［8］。定義反饋行為：人工魚以一定概率向公告牌記錄的最優(yōu)狀態(tài)游動。魚群算法在尋優(yōu)過程中，首先執(zhí)行覓食、追尾和聚群行為，假若這三種行為均不能找到比當(dāng)前更優(yōu)的狀態(tài)，則人工魚執(zhí)行隨機行為?？紤]到在優(yōu)化后期人工魚聚集在全局最優(yōu)附近時，隨機行為的執(zhí)行會降低算法的優(yōu)化精度和優(yōu)化效率，規(guī)定：人工魚以反饋概率Pfb執(zhí)行隨機行為，以概率 （1－Pfb）執(zhí)行反饋行為，且Pfb隨優(yōu)化過程線性減小，即Pfb＝αPfb，α為Pfb的衰減因子。保證在優(yōu)化前期，隨機行為有更多機會執(zhí)行，而后期的反饋行為則有更多機會執(zhí)行。

人工魚群算法的收斂速度正比于人工魚數(shù)量，隨個體增多收斂越快，但因需要更多存儲空間，造成算法復(fù)雜度增加。因為在人工魚群算法中目標(biāo)函數(shù)值很低，弱小的人工魚對算法的收斂速度和全局尋優(yōu)能力影響很小，根據(jù)自然界中弱小的魚會被大魚吞食的現(xiàn)象，在此引入吞食行為：經(jīng)過若干次迭代后，將目標(biāo)函數(shù)值較低的人工魚以一定比例淘汰掉，釋放其所占空間，此后迭代將舍去這些人工魚。

綜上，人工魚的反饋－吞食策略描述為：每次迭代，當(dāng)人工魚執(zhí)行覓食、追尾和聚群行為后，其狀態(tài)均不優(yōu)于當(dāng)前狀態(tài)時，排列所有人工魚的適應(yīng)度值，將較小適應(yīng)度值的人工魚以（1－Pfb）比例淘汰掉，剩下的人工魚以概率Pfb執(zhí)行隨機行為，以概率（1－Pfb）執(zhí)行反饋行為，優(yōu)化過程中Pfb＝αPfb線性減小。該策略使得在優(yōu)化前期，淘汰少量的弱小人工魚，在降低算法復(fù)雜度的同時防止收斂速度變緩，且保證有更多機會執(zhí)行隨機行為；在優(yōu)化后期，淘汰的弱小人工魚增多，加快算法的收斂，且保證反饋行為有更多機會執(zhí)行。

3.3 混合算法的具體步驟

混沌作為一種有效防止優(yōu)化算法陷入局部最優(yōu)的機制，將第2節(jié)提出的復(fù)合混沌搜索引入人工魚群算法中。人工魚群算法執(zhí)行全局尋優(yōu)搜索，而復(fù)合混沌搜索則在此結(jié)果的基礎(chǔ)上實行局部搜索。改進人工魚引入反饋－吞食行為，使得魚群算法復(fù)雜度降低、收斂效率提高?；谝陨蟽牲c思路，由復(fù)合混沌－人工魚群構(gòu)造的混合算法能夠避免人工魚長時間呆在局部最優(yōu)值附近，減少算法復(fù)雜度，從而提高人工魚群算法的全局收斂性和尋優(yōu)效率，算法的收斂精度和收斂效率增強［9］。

基于復(fù)合混沌搜索和改進人工魚群行為的混合算法具體步驟描述如下：

步驟1 算法初始化，包括人工魚的位置、種群規(guī)模total、步長step、視野visual、反饋概率Pfb、反饋概率衰減因子α；

步驟2 計算所有人工魚的適應(yīng)度值，將最優(yōu)的人工魚記入公告牌；

步驟3 人工魚執(zhí)行覓食行為、追尾行為和聚群行為，對執(zhí)行所得結(jié)果進行評價，如果執(zhí)行后的狀態(tài)優(yōu)于當(dāng)前狀態(tài)，則人工魚向此優(yōu)良狀態(tài)的方向前進一步，繼而轉(zhuǎn)到步驟5；

步驟4 按適應(yīng)度值大小排列所有人工魚，以（1－Pfb）比例淘汰掉較低值的人工魚，產(chǎn)生一個隨機數(shù)rand（），若rand（）＜Pfb，剩余人工魚執(zhí)行隨機行為，否則執(zhí)行反饋行為；

步驟5 最優(yōu)人工魚執(zhí)行復(fù)合混沌搜索；

步驟6 更新公告牌；

步驟7 利用式Pfb＝αPfb更新反饋概率；

步驟8 如果算法滿足終止條件，則停止算法運行，輸出最后結(jié)果，否則返回步驟3。

混合算法的流程圖如圖2所示。

4 算法性能的驗證與分析

選取三個標(biāo)準測試函數(shù)（F1，F(xiàn)2，F(xiàn)3）測試混合算法的性能。這些函數(shù)都具有很多局部極值，普通的優(yōu)化算法很難找到全局最優(yōu)值，測試函數(shù)如表1所示，圖3為其三維效果圖。實驗對每個函數(shù)進行30次，每次迭代600代，每個函數(shù)優(yōu)化參數(shù)設(shè)定一致，F(xiàn)1、F2、F3函數(shù)收斂閾值分別為820、3 564、3。實驗結(jié)果如表2所示。

Figure 2 Diagram of compound chaos－improved artificial fish hybrid algorithm圖1 復(fù)合混沌－改進人工魚群混合算法流程示意圖

由表2實驗結(jié)果可以看出，本文的混合算法無論是收斂精度、收斂速度還是到達收斂閾值所需要的平均迭代收斂次數(shù)，均優(yōu)于基本人工魚群算法。

由表2的驗證實驗，三個測試函數(shù)的收斂曲線如圖4～圖6所示，人工魚總數(shù)均為20條，算法迭代600次。

圖4中，兩種算法步長step＝3，視野visual＝12，嘗試次數(shù)try＿number＝3，擁擠度因子δ＝0.11，混合算法反饋概率Pfb＝0.99，衰減因子α＝0.99。由圖4可以看出，混合算法得出的收斂曲線的收斂速度更快，能夠更好地接近全局最優(yōu)值，收斂精度高。

Table 1 Standard test functions表1 標(biāo)準測試函數(shù)

Table 2 Experimental results表2 實驗結(jié)果

圖5中，兩種算法步長step＝0.01，視野visual＝1，嘗試次數(shù)try＿number＝5，擁擠度因子δ＝0.05，混合算法反饋概率Pfb＝0.96，衰減因子α＝0.98。由圖5可以得出，混合算法尋找全局極值點所需的迭代次數(shù)少，收斂效率更高，收斂速度較快。

Figure 5 Convergence curve of test function F2圖5 F2函數(shù)的收斂曲線

Figure 6 Convergence curve of test function F3圖6 F3函數(shù)的收斂曲線

圖6 中，兩種算法步長step＝0.089，視野visual＝10，嘗試次數(shù)try＿number＝3，擁擠度因子δ＝0.15，混合算法反饋概率Pfb＝0.99，衰減因子α＝0.95。從圖6中能夠得出，基本魚群算法易長時間陷入局部極值，而混合算法能穩(wěn)定地跳出局部極值達到全局尋優(yōu)，優(yōu)化能力增強。

圖7～圖9分別給出了兩種算法對F1、F2、F3優(yōu)化實驗中人工魚群的初始分布和最終分布情況。圖中“○”代表人工魚，總數(shù)為20條。

Figure 9 Artificial fish distribution of F3function algorithm圖9 F3函數(shù)優(yōu)化實驗中算法的人工魚分布圖

由圖7可以看出，混合算法使更多的人工魚能夠到達全局最優(yōu)值區(qū)域，提高了尋優(yōu)精度；圖8中混合算法的人工魚較多地跳出局部極值，提高了優(yōu)化效率；圖9混合算法中部分極值點附近均有人工魚聚集，表明算法在找到全局最優(yōu)解的同時能得到部分的次優(yōu)解，增強了算法的優(yōu)化生存能力。

5 結(jié)束語

本文利用常見的兩種混沌映射進行組合，以復(fù)合形式得出的混沌搜索具有更強遍歷性的搜索局部極值能力，使得優(yōu)化問題的全局尋優(yōu)能跳出局部極值得到精確解。在人工魚群算法中引入反饋－吞食行為，該行為策略在降低算法復(fù)雜度的同時保證了尋優(yōu)的收斂精度和效率?；趶?fù)合混沌搜索與改進人工魚群的混合算法，使得以人工魚為解題模型的優(yōu)化問題全局尋優(yōu)能力在算法復(fù)雜度、收斂速度和跳出局部極值方面均有很大提高，可以應(yīng)用到復(fù)雜工程優(yōu)化設(shè)計中，對于通信和信號圖像處理等領(lǐng)域的大規(guī)模數(shù)據(jù)優(yōu)化問題也將同樣起著重要作用。

［1］ Gao Shang，Yang Jing－yu.Swarm intelligence algorithm and its application［M］.Beijing：China Water Power Press，2006.（in Chinese）

［2］ Li Xiao－lei.A new method of intelligence optimization－artificial fish swarm algorithm［D］.Hangzhou：Zhejiang University，2003.（in Chinese）

［3］ Cheng Y M，Jiang M Y，Yuan D F.Novel clustering algorithms based on improved artificial fish swarm algorithm［C］∥Proc of the 6th International Conference on Fuzzy Systems and Knowledge Discovery（FSKD’09），2009：141－145.

［4］ Gao Yu－fang，Zhang Zhan－yu.Chaotic artificial fish swarm algorithm and its application in the irrigation district optimize water distribution［J］.Journal of Agricultural Engineering，2010，27（6）：2084－2086.（in Chinese）

［5］ Yu Si－min.Chaotic systems and chaotic circuits：Principle，design and its application in communications［M］.Xi’an：Xi’an University of Electronic Science and Technology Publishing House，2011.（in Chinese）

［6］ Bucolo M，Caponetto R，F(xiàn)ortuna L，et al.Does chaos work better than noise？［J］.IEEE Circuits and System Magazine，2002，2（3）：4－19.

［7］ Jiang Ming－yan，Yuan Dong－feng.Artificial fish swarm algorithm and its application［M］.Beijing：Science Press，2012：44－48.（in Chinese）

［8］ Zhu K C，Jiang M Y.Quantum artificial fish swarm algorithm［C］∥Proc of the 8th World Congress on Intelligent Control and Automation，2010：1－5.

［9］ Zhu K C，Jiang M Y.An improved artificial fish swarm algorithm based on chaotic search and feedback strategy［C］∥Proc of International Conference on Computational Intelligence and Software Engineering（CISE），2009：1－4.

附中文參考文獻：

［1］ 高尚，楊靜宇.群智能算法及其應(yīng)用［M］.北京：中國水利水電出版社，2006.

［2］ 李曉磊.一種新型的智能優(yōu)化方法——人工魚群算法［D］.杭州：浙江大學(xué)，2003.

［4］ 高玉芳，張展羽.混沌人工魚群算法及其在灌區(qū)優(yōu)化配水中的應(yīng)用［J］.農(nóng)業(yè)工程學(xué)報，2010，27（6）：2084－2086.

［5］ 禹思敏.混沌系統(tǒng)與混沌電路—原理、設(shè)計及其在通信中的應(yīng)用［M］.西安：西安電子科技大學(xué)出版社，2011.

［7］ 江銘炎，袁東風(fēng).人工魚群算法及其應(yīng)用［M］.北京：科學(xué)出版社，2012：44－48.