1、,$,人工魚群算法,組員：,主講人：,2020/7/28,AFSA的特點(diǎn),只需要比較目標(biāo)函數(shù)值，對目標(biāo)函數(shù)的性質(zhì)要求不高； 對初值的要求不高，初值隨機(jī)產(chǎn)生或設(shè)定為固定值均可以； 對參數(shù)設(shè)定的要求不高，有較大的容許范圍； 具備并行處理的能力，尋優(yōu)速度較快； 具備全局尋優(yōu)的能力，能夠快速跳出局部極值點(diǎn)。,2020/7/28,AFSA的不足之處,容易收斂于局部最優(yōu) 解精度不夠高 保持探索與開發(fā)平衡的能力較差 算法運(yùn)行后期搜索的盲目性較大 算法后期收斂速度慢，易陷入局部最優(yōu),2020/7/28,改進(jìn)思路,一、基于算法參數(shù)的改進(jìn) 二、基于魚群行為的改進(jìn) 三、高階行為模式 四、混合優(yōu)化算法,2020/7/

2、28,一、基于算法參數(shù)的改進(jìn),算法參數(shù)： 1.視野visual 2.步長step 3.人工魚總數(shù)N 4.嘗試次數(shù)try number 5.擁擠度因子,2020/7/28,1、基于視野的改進(jìn):,在人工魚群算法的初始階段，每條人工魚以一個(gè)大的視野尋找解，這樣能擴(kuò)大尋優(yōu)的范圍。隨著算法的運(yùn)行，魚群的視野范圍將適當(dāng)?shù)臏p小以加快收斂的速度。改變視野的變化函數(shù)定義為： 其中 是衰減因子，且 (0,1)。這里必須解釋的一點(diǎn)是魚群視野在聚群行為和追尾行為中仍然保持不變，僅在覓食行為中變換。,2020/7/28,2.基于步長的改進(jìn),2.1 Wang Cuiru 等提出的改進(jìn)方法的基本思路就是將人工魚群算法的實(shí)際

3、步長改為參數(shù)定義域內(nèi)的隨機(jī)數(shù)，以保證更好的全局搜索能力。 2.2 王西鄧等提出了兩種對步長進(jìn)行改進(jìn)的魚群算法：一種是移動(dòng)步長縮減策略，另一種是移動(dòng)步長動(dòng)態(tài)調(diào)整策略。 2.3王宗利等提出的利用評價(jià)函數(shù)的步長改進(jìn)算法。,2020/7/28,2.2.1移動(dòng)步長縮減策略,算法在完成一次魚群演化后，根據(jù)函數(shù)最優(yōu)適應(yīng)值的變化情況更新最適應(yīng)值保持次數(shù)keep Times 0 最優(yōu)適應(yīng)值已更新 Keep Times = Keep times +1 最優(yōu)適應(yīng)值不變 根據(jù)最優(yōu)適應(yīng)值保持次數(shù)對人工魚的移動(dòng)步長進(jìn)行更新: M_step keep Times 1且m_step M_step= M_step 其他 其中為

4、步長縮減因子，T為給定的常數(shù)，:為給定的移動(dòng)步長最小值。,2020/7/28,2.2.2移動(dòng)步長動(dòng)態(tài)調(diào)整策略,為了保證迭代能夠到達(dá)最大值，必須要求移動(dòng)步長大于0。因此有: 其中 為一個(gè)預(yù)定義的小的正數(shù) 算法在完成一次魚群演化后，根據(jù)函數(shù)最優(yōu)適應(yīng)值的變化情況更新最優(yōu)適應(yīng)值的更新次數(shù)change Times， change Times +0 最優(yōu)適應(yīng)值未更新 Change Times= Change Times +1 最優(yōu)適應(yīng)值已更新,2020/7/28,2.2.2移動(dòng)步長動(dòng)態(tài)調(diào)整策略,每經(jīng)過n次魚群演化，根據(jù)最優(yōu)適應(yīng)值在最近10n次迭代中的更新次數(shù)對人工魚的移動(dòng)步長進(jìn)行更新: 其中， 為步長縮減

5、因子，取0.85； 為給定的移動(dòng)步長最小值。并將change Times恢復(fù)為0: Change Times 0 進(jìn)行下一次移動(dòng)步長的自動(dòng)調(diào)整準(zhǔn)備。,2020/7/28,2.3基于評價(jià)函數(shù)的步長改進(jìn)算法,設(shè)當(dāng)前人工魚狀態(tài)X i, 在可視范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)X j, 如果食物濃度Yj Yi, 即X j 處的食物濃度較X i 大很多, 可以認(rèn)為X j 處的營養(yǎng)物質(zhì)較為豐富, X i 應(yīng)該向X j 移動(dòng)一大步。基本人工魚群算法中, 移動(dòng)步長隨機(jī)而定, 在改進(jìn)的人工魚群算法中, 評價(jià)函數(shù)： (其中Ymax為初始狀態(tài)適應(yīng)值函數(shù)的最大值, Ymin為初始狀態(tài)適應(yīng)值函數(shù)的最小值)狀態(tài)X i 與狀態(tài)X j

6、處的食物濃度之差為& Yij = Yj - Yi, 如果& Yij & Y, 則向Xj 方向移動(dòng)3step的距離。如果& Yij & Y, 則向X j 方向移動(dòng)一步。,2020/7/28,3.基于視野和步長的改進(jìn),取決于人工魚當(dāng)前所在的狀態(tài)和視野中視點(diǎn)感知的狀態(tài)的自適應(yīng)步長的改進(jìn)策略： 對于人工魚的當(dāng)前狀態(tài) 和所探索的下一個(gè)狀態(tài) 其表示如下：,2020/7/28,4.基于步長和擁擠度因子的改進(jìn),對步長和擁擠度因子進(jìn)行適時(shí)的自行調(diào)整，以達(dá)到提高收斂精度的目的。在該算法中，運(yùn)用最優(yōu)適應(yīng)值變化率K和變化方差作為是否進(jìn)行參數(shù)變化的衡量標(biāo)準(zhǔn)。定義如下：,2020/7/28,4.基于步長和擁擠度因子的改進(jìn)

7、,根據(jù)以上兩個(gè)判別準(zhǔn)則，對步長和擁擠度因子作調(diào)整，表達(dá)式如下： 其中f(Step)表示按一定規(guī)則對步長進(jìn)行調(diào)整；f( )表示對擁擠度因子作相應(yīng)調(diào)整；，表示評價(jià)系數(shù)，根據(jù)具體問題給出不同的值，用來控制變步長的速度和迭代的進(jìn)程。,2020/7/28,5.引入新參數(shù)（改變參數(shù)）,自適應(yīng)人工魚群算法：視步系數(shù)=步長/視野 基本思想是： 1）每次迭代后，人工魚都將自身的位置信息及食物濃度寫入并更新公告板。 2）人工魚根據(jù)魚群的狀態(tài)智能地獲取視野visual。 3）確定一個(gè)視步系數(shù)a（0a1），把step=avisual 作為人工魚的最大步長。 4）忽略擁擠的因素，在執(zhí)行追尾行為和聚群行為時(shí)，只要視野范圍

8、內(nèi)的最優(yōu)人工魚和中心位置優(yōu)于當(dāng)前位置，就以rand（）step 向其移動(dòng)。,2020/7/28,5.引入新參數(shù)（改變參數(shù)）,根據(jù)視野方式不同，分為四種（AAFSA1-4）： 1）AAFSA1:基于平均距離的自適應(yīng)人工魚群算法 即每次迭代前，每條人工魚都要對其他人工魚到自身的距離進(jìn)行測算，并計(jì)算出平均值，把它作為自身的視野visual。 2）AAFSA2:基于最優(yōu)人工魚的自適應(yīng)人工魚群算法 即在每次迭代前，每條人工魚都要測算出到當(dāng)前最優(yōu)人工魚的距離，并把它作為自身的視野visual1。,2020/7/28,5.引入新參數(shù),3）AAFSA3:基于最優(yōu)人工魚和最近人工魚的半復(fù)合自適應(yīng)人工魚群算法 在

9、AAFSA2 的基礎(chǔ)上，對覓食行為做如下改進(jìn)：人工魚測算出到離自身最近的人工魚的距離，并把它作為覓食行為的視野（visual）進(jìn)行搜索，隨機(jī)確定一點(diǎn)，如比自身位置優(yōu)，則以visual2rand（）向該點(diǎn)動(dòng)一步；反之，則繼續(xù)搜索，直至達(dá)到規(guī)定的嘗試次數(shù)。 如仍未找到，則執(zhí)行隨機(jī)行為。用visual2rand（）而不用visual2arand（）。,2020/7/28,5.引入新參數(shù),4）AAFSA4:基于最優(yōu)人工魚和最近人工魚的復(fù)合自適應(yīng)人工魚群算法 把AAFSA2 和AAFSA3 相結(jié)合，得到了另一種改進(jìn)覓食行為的方法。,2020/7/28,二、基于魚群行為的改進(jìn),1.基于基本魚群行為的改進(jìn)

10、1.1改進(jìn)的覓食行為 1.2改進(jìn)的聚群行為 1.3改進(jìn)的追尾行為 2.基于新增魚群行為的改進(jìn) 2.1逃逸行為 2.2繁殖行為,2020/7/28,三、高階行為模式,將人工魚以前的行為和經(jīng)驗(yàn)也封裝在對象內(nèi)部，并對其采取一定的參考和學(xué)習(xí)，以達(dá)到提高算法的效率的目的。 如: class Artificial fish public float AF_Xn /AFs position float last AF_Xn /AFs last position float evergood_AF_Xn / the ever good position of AF ； 這樣，人工魚就記憶著曾經(jīng)的最好狀態(tài)和上一

11、次的狀態(tài)，從而為下一次的行為作出更加合理的行為評價(jià)。,2020/7/28,四、混合優(yōu)化算法,算法在優(yōu)化過程初期雖然具有較快的收斂品質(zhì)，但在后期卻往往收斂較慢，或者無法達(dá)到要求的精度，因此，與其他算法相結(jié)合，在合適的時(shí)候與它們互相切換，實(shí)現(xiàn)各算法之間的優(yōu)缺點(diǎn)互補(bǔ)，也是一種解決問題的常用方法。,2020/7/28,四、混合優(yōu)化方法,李曉磊針對復(fù)雜大系統(tǒng)的優(yōu)化問題中方程數(shù)多、變量維數(shù)高等特點(diǎn)，描述了一種基于分解協(xié)調(diào)思想的人工魚群優(yōu)化算法。并以換熱器系統(tǒng)為例進(jìn)行了計(jì)算，結(jié)果表明，該算法具有較好的收斂性、初值不敏感性和參數(shù)不敏感性等特點(diǎn)。 Xiaojuan Shan等提出了一種改進(jìn)的人工魚群算法，引入禁

12、忌表，增強(qiáng)了人工魚群算法的全局尋優(yōu)和鄰域搜索能力，避免限于局部最優(yōu)解。實(shí)驗(yàn)結(jié)果顯示改進(jìn)的算法具有較好的全局尋優(yōu)能力。 李亮等構(gòu)造了一種兩點(diǎn)禁忌尋優(yōu)算子以避免尋優(yōu)過程中的迂回搜索，并用它模擬魚群中單條魚的追尋歷史最優(yōu)魚、追尾、群聚三種行為，采用遺傳算法中非均勻變異算子模擬單條魚的覓食行為，魚群中各個(gè)體通過這四種行為進(jìn)行交流、合作從而形成了一種禁忌魚群算法。將該算法應(yīng)用于兩個(gè)復(fù)雜土坡的最小安全系數(shù)搜索中，并同基本魚群算法的計(jì)算結(jié)果進(jìn)行了比較，結(jié)果證明禁忌魚群算法具有搜索高效、適于約束優(yōu)化問題求解等特點(diǎn)。,2020/7/28,四、混合優(yōu)化方法,張梅鳳等在分析人工魚群算法存在不足的基礎(chǔ)上，提出了基于變

13、異算子與模擬退火混合的人工魚群優(yōu)化算法。該算法保持了人工魚群算法簡單、易實(shí)現(xiàn)的特點(diǎn)，克服了人工魚漫無目的隨機(jī)游動(dòng)或在非全局極值點(diǎn)的大量聚集，顯著提高了算法的運(yùn)行效率和求解質(zhì)量。通過函數(shù)和實(shí)例測試驗(yàn)證，表明了該算法是可行和有效的。 黃光球等通過引入網(wǎng)格劃分策略和禁忌搜索算法，對基本人工魚群算法進(jìn)行了改進(jìn)，減少了迂回搜索的無用計(jì)算，同時(shí)也使人工魚可以在解空間內(nèi)進(jìn)行更為全面的搜索，提高了搜索效率，加快了系統(tǒng)滿意解域的確定；通過對變量空間進(jìn)行網(wǎng)格劃分，提供了獲取系統(tǒng)最優(yōu)解的方法，而且加強(qiáng)了對魚群公告板信息的使用。實(shí)驗(yàn)表明，與基本人工魚群算法相比，該方法具有明顯的優(yōu)越性。 高德芳等提出了融合魚群算法及蟻群算法的優(yōu)化模型求解方法，并以鐵路客車內(nèi)裝模塊化配置設(shè)計(jì)為應(yīng)用，驗(yàn)證了該求解方法的可行性和有效性。,2020/7/28,四、混合優(yōu)化方法,宋志宇等根據(jù)混沌(CHAOS)的遍歷性和隨機(jī)性等特點(diǎn)，將混沌系統(tǒng)和人工魚群算法相結(jié)合形成了一種新的融合優(yōu)化算法-混沌人工