復(fù)合混沌人工魚群混合算法的改進(jìn)及性能研究＊－

易新兵，楊 凱

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

1 引言

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

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

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

混沌運(yùn)動(dòng)具有遍歷性、隨機(jī)性等特性，能在一定范圍內(nèi)按其自身規(guī)律不重復(fù)地遍歷所有狀態(tài)［5］，其軌跡對(duì)初始值極其敏感，由確定性的迭代公式產(chǎn)生。基于此特征的混沌映射可以作為一種局部搜索方法來(lái)提高其他優(yōu)化算法的全局搜索能力，并能夠避免算法陷入局部極值。

2.1 復(fù)合混沌映射

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

Logistic映射定義為：

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

Tent映射定義為：

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

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

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

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

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

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

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

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

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

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

3.1 基本人工魚群算法

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

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

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

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

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

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

3.3 混合算法的具體步驟

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

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

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

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

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

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

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

步驟6 更新公告牌；

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

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

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

4 算法性能的驗(yàn)證與分析

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

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

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

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

圖4中，兩種算法步長(zhǎng)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)準(zhǔn)測(cè)試函數(shù)

Table 2 Experimental results表2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

［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.

附中文參考文獻(xiàn)：

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

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

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

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

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