基于約束優(yōu)化問題的人工魚群算法及其改進

孫王杰，盧月亮，孫書貝，鞏曉悅

(1.吉林化工學院理學院，吉林吉林132022;2.吉林化工學院信息與控制工程學院，吉林吉林132022)

隨著應用和需求的不斷擴展，出現(xiàn)了一些新穎的優(yōu)化算法，如人工神經(jīng)網(wǎng)絡、混沌、遺傳算法、模擬退火、禁忌搜索等等.這些算法都是通過模擬或揭示某些自然現(xiàn)象或過程而得到發(fā)展的.在這期間群智能優(yōu)化算法也得到了較快發(fā)展，如粒子群算法、蟻群算法等等.2002年，李曉磊博士通過研究魚群的行為特點提出了一種新型的群智能優(yōu)化算法-人工魚群算法［1］.人工魚根據(jù)環(huán)境的狀態(tài)通過它的四種行為來尋找最優(yōu)解［2］，其中4種行為分別是覓食行為、追尾行為、聚群行為和隨機行為［3］.

本文改進了人工魚的覓食行為，將人工魚群算法與罰函數(shù)的理論結(jié)合來解決約束優(yōu)化問題.另外引入了吞噬行為以便加快收斂速度，得到更優(yōu)的適應度值.仿真結(jié)果表明改進的人工魚群算法在解決約束優(yōu)化問題時，具有收斂速度快、適應度值優(yōu)、全局尋優(yōu)性能強等優(yōu)點，比基本人工魚群算法具有更好的性能.

1 人工魚群算法

1.1 人工魚群算法簡介

人工魚(artificial fish，AF)是真實魚的一個虛擬實體，用來進行問題的分析和說明.通過模擬魚類的四種行為:覓食行為、聚群行為、追尾行為和隨機行為，來使魚類活動在周圍的環(huán)境.這些行為可以在不同的情況下相互轉(zhuǎn)換.

算法采用面對對象的技術(shù)重構(gòu)人工魚的模型，將人工魚封裝成變量和函數(shù)兩部分.變量部分包括人工魚的總數(shù)N/人工魚的個體的狀態(tài)X=(x1，x2，…，xn)［其中 xi(i=1，2，…，n)］為欲尋求的變量、人工魚群移動的最大步長Step、人工魚群的視野Visual、嘗試次數(shù)Try_number、擁擠度因子 δ、人工魚個體 i，j之間的距離 di，j=Xi－Xj.

函數(shù)部分包括人工魚當前所在位置的食物濃度Y=f(X)(Y為目標函數(shù)值)、人工魚的各種行為函數(shù)［覓食行為 Prey()、聚群行為Swarm()、追尾行為 Follow()、隨機行為Move().及行為評價函數(shù)Evaluate()］.通過這種封裝，人工魚的狀態(tài)可以被其他同伴所感知.

在尋優(yōu)過程中，人工魚是通過Visual來確定視野范圍.當在視野范圍內(nèi)如果尋找到比現(xiàn)在食物濃度高的位置時，人工魚將移動到那一位置.

其中X代表當前尋優(yōu)的人工魚，XV代表在當前人工魚X的Visual內(nèi)尋找到的下一點，Step是人工魚的步長，Rand()是0到1上的隨機數(shù).

準確地來講，人工魚是通過它的四種行為在其Visual內(nèi)尋找下一位置的.這四種行為分別是覓食行為、追尾行為、聚群行為和隨機行為.

1.1.1 覓食行為

這是人工魚的一種基本行動，也就是趨向食物的一種活動，一般我們認為它是通過視覺或味覺來感知水中的食物量或濃度進而來選擇趨向的.

行為描述:設人工魚i當前狀態(tài)為Xi，在其感知范圍內(nèi)隨機選擇一個狀態(tài)Xj

式中，Rand()是一個介于0和1之間的隨機數(shù)，如果在求極大值問題中，Yi＜Yj(或求極小值Yj＜Yi)，則向該方向前進一步

反之，再重新隨機選擇狀態(tài)Xj，判斷是否滿足前進條件，反復嘗試Try_number次后，若仍不滿足前進條件，則隨機一定一步

1.1.2 聚群行為

魚在游動過程中會自然的聚集成群，這也是為了保證群體的生存和躲避危害而形成的一種生活習性.

行為描述:在人工魚群算法中對每條人工魚做如下規(guī)定:一是盡量向鄰近伙伴的中心移動;而是避免過分擁擠.

否則執(zhí)行覓食行為.

1.1.3 追尾行為

魚群在游動過程中，當其中的一條與或幾條魚發(fā)現(xiàn)食物時，其鄰近的伙伴會尾隨其快速到達食物點.

行為描述:追尾行為是一種向鄰近的有著最高適應度的人工魚追逐的行為，在尋優(yōu)算法中可以理解為是向附近的最優(yōu)伙伴前進的過程.設人工魚 i當前狀態(tài)為 Xi，搜索當前鄰域內(nèi)(dij＜Visual)的伙伴中Yj為最大值的伙伴Xj.，表明伙伴X的狀態(tài)具有較高的食物j濃度并且周圍不太擁擠，則朝Xj的方向前進一步

否則執(zhí)行覓食行為.

1.1.4 隨機行為

行為描述:

人工魚在視野中隨機選擇一個狀態(tài)，然后向該狀態(tài)移動，其實是覓食行為的一個缺省行為.

這四種行為在不同條件下會相互轉(zhuǎn)換，魚類通過對行為的評價選擇一種當前最優(yōu)的行為進行執(zhí)行，已達到食物濃度更高的位置，這是魚類的生存習慣.

1.2 改進人工魚群算法(IAFSA)

因為基本人工魚群算法存在保持探索與開發(fā)平衡的能力較差、算法運行后期搜索的盲目性較大、尋優(yōu)結(jié)果精度低和運算速度慢等缺點，影響了其搜索質(zhì)量和效率.

1.2.1 改進視野和步長

一般來說，視野和步長的選擇對算法的收斂速度有很大的影響.視野范圍較大有利于搜索全局最優(yōu)值，但是耗費的系統(tǒng)資源比較多.然而視野范圍較小，耗費的系統(tǒng)資源較少，但是全局尋優(yōu)就受到了限制.人工魚群算法是使用自適應視野來尋優(yōu)的［4］.在本文中，我們根據(jù)文獻［4］的理論，引入自適應視野，并引入步長因子，

得到自適應步長.這樣可以根據(jù)迭代次數(shù)改變，視野進行相應的改變，既節(jié)省了系統(tǒng)的資源，又增加了全局的尋優(yōu)能力.

1.2.2 改進覓食行為

執(zhí)行基本人工魚群算法的覓食行為時，人工魚在尋找到比當前位置較優(yōu)的位置時，就向該位置的方向移動一步.但是基本人工魚群算法突顯出的問題是每次覓食行為中Try_number僅僅被執(zhí)行了幾次，這樣大大的削弱了覓食行為的能力.基本覓食行為中人工魚較優(yōu)位置的方向上移動時不能確定移動到的那一位置比當前位置優(yōu)，所以傳統(tǒng)覓食行為既削弱了人工魚的覓食能力，又浪費了系統(tǒng)的大量資源.針對傳統(tǒng)覓食行為的缺點，我們對覓食行為進行改進.在完全執(zhí)行Try_number次數(shù)之后，人工魚直接移動到這一最優(yōu)的位置.

1.2.3 添加吞噬行為

在改進覓食行為以后，我們可以引入吞噬行為來解決覓食行為執(zhí)行時間變長的問題.吞噬行為是仿照自然界中優(yōu)勝劣汰的規(guī)律進行改編的.在執(zhí)行程序幾次迭代后，較優(yōu)的人工魚把最不優(yōu)的人工魚吞噬掉，于是就節(jié)省了不優(yōu)人工魚的尋優(yōu)時間.

2 人工魚群算法求解約束優(yōu)化問題

2.1 約束優(yōu)化問題描述

約束優(yōu)化最小化問題可以表示如下:

這里是x=(x1，…xn)T∈Rn是n維實向量，f(x)為目標函數(shù)，hi(x)為第i個等式的約束，gj(x)是第j個不等式的約束，xk變量在區(qū)間［，表示搜索空間.

2.2 改進的人工魚群算法求解約束函數(shù)優(yōu)化問題

在人工魚群算法中每個人工魚通過探索領域內(nèi)伙伴的變化情況和目標函數(shù)的變化情況等環(huán)境狀態(tài)從而從以上幾種行為中選擇一種執(zhí)行經(jīng)過若干次的迭代搜索最后人工魚將聚集在極值的周圍.算法步驟如下:

Setp1.初始化參數(shù):人工魚總數(shù) M，視野Visual，步長Step，步長因子a，覓食行為的嘗試次數(shù)Try_number，迭代次數(shù)t，人工魚的初始位置等等.

Step2.選出在四種行為中適應度值最優(yōu)的行為并執(zhí)行.在M個人工魚都執(zhí)行行為之后.選出最優(yōu)的人工魚與公告牌上的人工魚進行比較，人工魚優(yōu)于公告牌則將自身所有屬性與公告牌上面的進行替換，反之保留公告牌屬性.

Step3.進行吞噬行為，去掉最不優(yōu)的人工魚.

Step4.經(jīng)過一次迭代之后保留公告牌的屬性，更新人工魚的數(shù)目.

Step5.如不滿足終止條件，返回step.2.

Step6.輸出人工魚的各項參數(shù)及最優(yōu)值的圖.

3 仿真實驗

使用matlab7.0軟件，選取以下2個約束函數(shù)進行測試這些都是帶有非線性約束的目標規(guī)劃問題［5-6］，兩個測試函數(shù)如下所示:

用基本人工魚群和改進的人工魚群測試函數(shù)(9)的結(jié)果如圖1所示

圖1 x1和x2的值

圖1中可以看出，基本AFSA和IAFSA的x1和x2都滿足大于0小于6的約束條件.從圖2和圖3中，我們可以清楚的知道IAFSA滿足C1、C2兩個約束條件的性能較強.圖4中IAFSA的適應度值與文獻［4］中提出的適應度值相等，并且從圖4中我們可以看出改進的人工魚群算法在第3次迭代時就獲得了最優(yōu)適應度值.

圖2 基本AFSA和IAFSA滿足約束條件c1的情況

圖3 基本AFSA和IAFSA滿足約束條件c2的情況

圖4 基本AFSA和IAFSA的適應度值

圖5 x1和x2的值

用基本人工魚群和改進的人工魚群測試函數(shù)(10)的結(jié)果如圖5所示.

圖5 x1和x2的值

圖6 基本AFSA和IAFSA滿足約束條件c1的情況

圖7 基本AFSA和IAFSA滿足約束條件c2的情況

圖8 基本AFSA和IAFSA的適應度值

圖5(a)和5(b)中我們可以看出，基本AFSA和IAFSA的x1和x2都滿足大于0小于10的約束條件.從圖6和圖7中，我們可以清楚的知道IAFSA滿足C1、C2兩個約束條件的性能較強.圖8中基本AFSA和IAFSA的最優(yōu)適應度值都與文獻［10］中提出的適應度值相等，并且從圖8中我們可以看出改進的人工魚群算法在第3次迭代時就獲得了最優(yōu)適應度值.而基本AFSA在第5次迭代才獲得最優(yōu)適應度值.

4 結(jié) 論

人工魚群算法是一種相對新型的群集智能算法該文在描述了人工魚群算法的基本原理的基礎上研究了如何使用該算法解決約束函數(shù)優(yōu)化問題.在基本人工魚群算法的基礎上，改進了人工魚的覓食行為，另外引入了吞噬行為，加快了收斂速度，得到了更優(yōu)的適應度值，具有更快的收斂速度，比基本人工魚群算法具有更好的性能.

［1］ 李曉磊，錢積新.人工魚群算法:自上而下的尋優(yōu)模式［J］.系統(tǒng)工程理論與實踐，2002，2(3):76-82.

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

［3］ 李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式:魚群算法［J］.系統(tǒng)工程理論和實踐，2002，22(11):32-28.

［4］ 王錫淮，鄭曉明，肖建梅.求解約束優(yōu)化問題的人工魚群算法［J］.計算機工程與應用，2007，43(3):40-42.

［5］ Yanbin Gao，Lianwu Guan，Tingjun Wang，et al.Research on the Calibration of FOG Based on AFSA”［J］.IEEE ICMA inter.Con.2013:412-417

［6］ Deb K.An efficient constraint handling method for genetic algorithms［J］.Computer Methods in Applied Mechanics and Engineering，2000，186(2):311-338.

［7］ Dong Ying，Tang Jia-fu，Xu Bao-dong，et al.An application of swarm optimization to nonlinear programming［J］.Computers and Mathematics with Applications，2005，49:1655-1668.