狼群算法

狼群算法是基於狼群群體智慧型,模擬狼群捕食行為及其獵物分配方式,抽象出遊走、召喚、圍攻3種智慧型行為以及“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機制,提出一種新的群體智慧型算法。

基本介紹

• 中文名：狼群算法

基本信息

算法採用基於人工狼主體的自下而上的設計方法和基 於職責分工的協作式搜尋路徑結構。如圖1所示,通過狼群個體對獵物氣味、環境信息的探知、人工狼相互間信息的共享和互動以及人工狼基於自身職責的個體行為決策最終實現了狼群捕獵的全過程。

狼群捕獵模型

狼群系統分析

嚴酷的生活環境和千百年的進化,造就了狼群嚴密的組織系統及其精妙的協作捕獵方式。從成吉思汗時期蒙古鐵騎的“狼群戰法”到納粹德軍將領鄧尼茨猖狂一時的“狼 群潛艇戰術”,再到美軍研究的電子對抗利器-“狼群攻擊系統”,都無不彰顯出狼群群體智慧的巨大魅力。狼過著群居生活且都有其明確的社會分工,它們團結協作為狼群的生存與發展承擔著各自的責任。

頭狼:頭狼始終是狼群中最具智慧和最兇猛的,是在 “弱肉強食、勝者為王”式的殘酷競爭中產生的首領。它不 斷地根據狼群所感知到的信息進行決策,負責整個狼群的 指揮和把關維護,既要避免狼群陷入危險境地又要指揮狼 群以期儘快地捕獲獵物。

探狼:尋找獵物時,狼群不會全體出動而是派出少數精 銳的探狼在獵物的可能活動範圍內遊獵,根據空氣中獵物 留下的氣味進行自主決策,氣味越濃表明狼離獵物越近,探 狼始終就朝著氣味最濃的方向搜尋。

猛狼:一旦探狼發現獵物蹤跡,就會立即向頭狼報告, 頭狼視情通過嚎叫召喚周圍的猛狼來對獵物進行圍攻。周 圍的猛狼聞聲則會自發地朝著該探狼的方向奔襲,向獵物 進一步逼近。

獵物分配規則:捕獲獵物後,狼群並不是平均分配獵物,而是按“論功行賞、由強到弱”的方式分配,即先將獵物分配給最先發現、捕到獵物的強壯的狼,而後再分配給弱小的狼。儘管這種近乎殘酷的食物分配方式會使得少數弱狼由於食物缺乏而餓死,但此規則可保證有能力捕到獵物的狼獲得充足的食物進而保持其強健的體質,在下次捕獵時仍可順利地捕到獵物,從而維持著狼群主體的延續和發展。

算法內容

一些定義


設狼群的獵場空間為一個 N×D 的歐式空間,其中 N 為狼群中人工狼總數,D 為待尋優的變數數。某一人工狼 i 的狀態可表示為Xi = (xi1 ,xi2 ,... ,xiD ),其中 xid 為第i 匹人工狼在欲尋優的第 d (d = 1 ,2 ,... ,D )維變數空 間 中 所 處 位 置;人工狼所感知到的獵物氣味濃度為Y=f(X),其中Y就是目標函式值;人工狼p 和q 之間的距離定義為其狀態向量間的 Manhatan距離,當然 d=1 也可依據具體問題選用其他的距離度量。另外,由於實際中極大與極小值問題之間可相互轉換,為論述方便以下皆以極大值問題進行討論。

智慧型行為和規則的描述

頭狼、探狼和猛狼間的默契配合成就了狼群近乎完美的捕獵行動,而“由強到弱”的獵物分配又促使狼群向最有可能再次捕獲到獵物的方向繁衍發展。將狼群的整個捕獵活動抽象為3種智慧型行為(即遊走行為、召喚行為、圍攻行 為)以及“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機制。

(1)頭狼產生規則。初始解空間中,具有最優目標函式值的人工狼即為頭狼;在疊代過程中,將每次疊代後最優 狼的目標函式值與前一代中頭狼的值進行比較,若更優則 對頭狼位置進行更新,若此時存在多匹的情況,則隨機選一匹成為頭狼。頭狼不執行3種智慧型行為而直接進入下次迭 代,直到它被其他更強的人工狼所替代。

(2)遊走行為。將解空間中除頭狼外最佳的S_num 匹人工狼視為探狼,在解空間中搜尋獵物,S_num 隨機取[n/ (α + 1 ) ,n / α ]之間的整數 ,α為探狼比例因子。探狼 i 首先感知空氣中的獵物氣味,即計算該探狼當前位置的獵物氣味濃度Yi。若Yi 大於頭狼所感知的獵物氣味濃度Ylead,表明獵物離探狼i已相對較近且該探狼最有可能捕獲獵物。於是Ylead =Yi ,探狼 i 替代頭狼並發起召喚行為;若Yi < Y lead ,則探狼先自主決策 ,即探狼向h個方向分別前進一步(此時的步長稱為遊走步長stepa)並記錄每前進一步後所感知的獵物氣味濃度後退回原位置,則向第p(p=1,2,..., h)個方向前進後探狼i在第d維空間中所處的位置為|| （2）

式中,為第k代群體頭狼在第d維空間中的位置。 式(2)由2部分組成,前者為人工狼當前位置,體現狼的圍獵基礎;後者表示人工狼逐漸向頭狼位置聚集的趨勢,體現頭狼對狼群的指揮。

奔襲途中,若猛狼i感知到的獵物氣味濃度Yi>Ylead, 則 Ylead =Yi ,該猛狼 轉化為頭狼並發起召喚行為;若Yi < Y lead ,則猛狼i繼續奔襲直到其與頭狼s之間 的距離d is小於dnear時加入到對獵物的攻擊行列,即轉入圍攻行為。設待尋優的第d個變數的取值範圍為[mind ,maxd ],則判定距離dnear可由式(3)估算得到

式中,w為距離判定因子,其不同取值將影響算法的收斂速度 ,一般而言w增大 會加速算法收斂,但w過大會使得人工狼很難進入圍攻行為,缺乏對獵物的精細搜尋。

召喚行為體現了狼群的信息傳遞與共享機制,並融入了社會認知觀點,通過狼群中其他個體對群體優秀者的“追隨”與“回響”,充分顯示出算法的社會性和智慧型性。

(4)圍攻行為。經過奔襲的猛狼已離獵物較近,這時猛狼要聯合探狼對獵物進行緊密地圍攻以期將其捕獲。這裡將離獵物最近的狼,即頭狼的位置視為獵物的移動位置。具體地,對於第k代狼群,設獵物在第d維空間中的位置為, 則狼 群的圍攻行為可用方程 (4 )表示


||（4）

式中,λ為[ - 1 ,1 ]間均勻分布的隨機數;stepc為人工狼i執行圍攻行為時的攻擊步長。若實施圍攻行為後人工狼感知到的獵物氣味濃度大於其原位置狀態所感知的獵物氣味濃度,則更新此人工狼的位置,若不然,人工狼位置不變。

設待尋優第d個變數的取值範圍為[mind ,maxd ],則3種智慧型行為中所涉及到 遊走步長stepa、奔襲步長stepb、攻擊步長stepc在第d維空間中的步長存在如下關係:

(5)“強者生存”的狼群更新機制。獵物按照“由強到弱”的原則進行分配,導致弱小的狼會被餓死。即在算法中去除目標函式值最差的R匹人工狼,同時隨機產生R匹人工狼。R越大則新產生的人工狼越多,有利於維護狼群個體的多樣性,但若R過大算法就趨近於隨機搜尋;若R過小,則不利於維護狼群的個體多樣性,算法開闢新的解空間的能力減弱。由於實際捕獵中捕獲獵物的大小、數量是有差別的,進而導致了不等數量的弱狼餓死。因此,這裡R取 [n/(2×β),n/β]之間的隨機整數,β為群體更新比例因子 。

算法描述




狼群算法的具體步驟如下。

步驟1 數值初始化。初始化狼群中人工狼位置 Xi及其數目N ,最大疊代次數kmax ,探狼比例因子α,最大遊走次數Tmax,距離判定因子w,步長因子S,更新比例因子β。

步驟2 選取最優人工狼為頭狼,除頭狼外最佳的S _num匹人工狼為探狼並執行遊走行為,直到某隻探狼i偵察到的獵物氣味濃度Yi大於頭狼所感知的獵物氣味濃度Ylead或達到最大遊走次數Tmax ,則轉步驟3。

步驟3 人工猛狼據式(2)向獵物奔襲,若途中猛狼感知的獵物氣味濃度Y i > Ylead 則Y lead = Y i ,替代頭狼並發起召喚行為;若Yi <Ylead ,則人工猛狼繼續 奔襲直到dis ≤dnear , 轉步驟4。

流程圖

步驟4 按式(4)對參與圍攻行為的人工狼的位置進行更新,執行圍攻行為。

步驟5 按“勝者為王”的頭狼產生規則對頭狼位置進行更新;再按照“強者生存”的狼群更新機制進行群體更新。

步驟6 判斷是否達到最佳化精度要求或最大疊代次數kmax ,若達到則輸出頭狼的位置,即所求問題的最優解 ,否則轉步驟2。

套用

求解0-1背包問題


狼群算法(wolf pack algorithm,WPA)源於狼群在捕食及其獵物分配中所體現的群體智慧型,已被成功套用於複雜函式求解。在此基礎上,通過定義運動運算元,對人工狼位置、步長和智慧型行為重新進行二進制編碼設計,提出了一種解決離散空間組合最佳化問題的二進制狼群算法(binary wolf pack algorithm,BWPA)。該算法保留了狼群算法基於職責分工的協作式搜尋特性,選取離散空間的經典問題——0-1背包問題進行仿真實驗,具體通過10組經典的背包問題算例和BWPA算法與經典的二進制粒子群算法、貪婪遺傳算法、量子遺傳算法在求解3組高維背包問題時的對比計算,例證了算法具有相對更好的穩定性和全局尋優能力。

求解多維背包問題

針對多維背包問題特點,設計了試探裝載式的修復機制有效修復和改進人工狼群中的不可行解,改進了傳統基於大懲罰參數的目標函式,減小了由於懲罰參數過大而導致算法陷入局部最優的風險;並受狼群的繁衍方式的啟發,在二進制狼群算法的基礎上提出了求解多維背包問題的改進二進制狼群算法(improve binary wolf pack algorithm,IBWPA)

水電站水庫最佳化調度中的套用

對狼群算法中的圍攻算法進行了改進,給出了水電站水庫最佳化調度問題的狼群算法設計及求解步驟。基於水電站水庫最佳化調度實例,對狼群算法的敏感參數奔襲步長進行了模擬計算和分析,給出了奔襲步長的有效取值範圍。實例計算結果表明,狼群算法是一種求解水電站水庫最佳化調度問題的有效方法。