最近發(fā)展起來的新算法第1頁，共51頁，2023年，2月20日，星期五2第八章最近發(fā)展起來的新算法一.我們的工作：群落選址算法(CLA)二.捕食搜索算法(PS)三.其他新算法第2頁，共51頁，2023年，2月20日，星期五3一.我們的工作：群落選址算法

ColonyLocationAlgorithm(CLA)CLA的產(chǎn)生：汪定偉2004WangDingwei.Colonylocationalgorithmforassignmentproblems[J],JournalofControlTheoryandApplications,2004,2(2):111-116.

WangDingwei.Colonylocationalgorithmforcombinatorialoptimization[A],Proc.IEEE.Conf.onSystems,Man&Cybernetics[C],PiscatawayNJ:IEEEServiceCenter,2004,1903-1909.

基本思想模擬植物群落形成機制－－土地含有的適于植物生長營養(yǎng)成分；不同物種間對生存資源的競爭；人工干預(yù)手段——施肥策略。第3頁，共51頁，2023年，2月20日，星期五4CLA養(yǎng)分函數(shù)Nij(t):在

t時刻，土地j對群落i的養(yǎng)分。加上時間t，是因為施肥可以改變肥力。第4頁，共51頁，2023年，2月20日，星期五5CLA生長率與衰亡率生長率：

r是平均生長率，是所有土地對i的平均肥力（行均值）第5頁，共51頁，2023年，2月20日，星期五6衰亡率：是土地j對所有群落的肥力的均值。（列均值）CLA第6頁，共51頁，2023年，2月20日，星期五7CLA群落比例與歸一化設(shè)xij(t)是群落i

在土地j

上的比例；生長過程帶來比例的和不是1。行、列歸一化，反復(fù)進行。第7頁，共51頁，2023年，2月20日，星期五8生長過程CLA第8頁，共51頁，2023年，2月20日，星期五9CLA解的構(gòu)成與評估xij(t)不是解。以xij(t)為概率，在每塊土地上產(chǎn)生一個群落，問題是要保證一個群落不能同時在兩塊土地上—解的合法性。其實很簡單，按隨機順序，在剩余群落中選。第9頁，共51頁，2023年，2月20日，星期五10CLA施肥過程若S(k*)是最好解；或者第10頁，共51頁，2023年，2月20日，星期五11CLA解的信息熵的計算解的信息熵：第11頁，共51頁，2023年，2月20日，星期五12CLA停止判據(jù)停止準則的計算：第12頁，共51頁，2023年，2月20日，星期五13CLA流程Step1:輸入數(shù)據(jù)和參數(shù)Step2:產(chǎn)生初始群落比例Step3:停止準則判斷Step4:生長和衰亡過程Step5:解的構(gòu)成與評估Step6:選取最優(yōu)解Step7:施肥Step8:結(jié)果輸出第13頁，共51頁，2023年，2月20日，星期五14指派問題的計算結(jié)果第14頁，共51頁，2023年，2月20日，星期五15第15頁，共51頁，2023年，2月20日，星期五16第16頁，共51頁，2023年，2月20日，星期五17CLATSP的計算結(jié)果全國33城市的TSP計算結(jié)果好于文獻的結(jié)果，但TSP.Lab測試題的計算結(jié)果不好。工作還需要繼續(xù)進行。第17頁，共51頁，2023年，2月20日，星期五18CLAQAP的計算結(jié)果自己編的題目計算結(jié)果不錯但對大規(guī)模問題計算效果不好，還需要做很多工作。包括養(yǎng)分函數(shù)的設(shè)置方法都還是問題。第18頁，共51頁，2023年，2月20日，星期五19PredatorySearchAlgorithm捕食搜索算法的基本思想：模仿動物的捕食策略（廣域與鄰域有效結(jié)合起來）。二.捕食搜索算法（PS）第19頁，共51頁，2023年，2月20日，星期五20AlexandreLinhares在1998提出來的一種用于解決組合優(yōu)化問題的模擬動物捕食行為的空間搜索策略。把捕食搜索策略分別應(yīng)用于解決旅行商問題（TSP）和超大規(guī)模集成電路設(shè)計（VLSI）問題，都取得了較好效果

捕食搜索算法——產(chǎn)生第20頁，共51頁，2023年，2月20日，星期五21

動物捕食時，在沒有發(fā)現(xiàn)獵物和獵物的跡象時在整個捕食空間沿著一定的方向以很快的速度尋找獵物；一旦發(fā)現(xiàn)獵物或者發(fā)現(xiàn)有獵物的跡象，它們就放慢步伐，在發(fā)現(xiàn)獵物或者有獵物的跡象的附近區(qū)域進行集中的區(qū)域搜索，以找到更多的獵物。在搜尋一段時間沒有找到獵物后，捕食動物將放棄這種集中的區(qū)域，而繼續(xù)在整個捕食空間尋找獵物。動物的這種捕食搜索策略可以概括為以下兩個搜索：

捕食搜索算法——基本原理第21頁，共51頁，2023年，2月20日，星期五22搜索1（全局搜索）：在整個搜索空間進行全面搜索，直到發(fā)現(xiàn)獵物或者有獵物的跡象而轉(zhuǎn)到搜索2進行局域搜索；搜索2（局域搜索）：在獵物或者有獵物的跡象的附近區(qū)域進行集中搜索，直到搜索很多次也沒有找到獵物而放棄局域搜索，轉(zhuǎn)到搜索1進行全局搜索。

捕食搜索算法——基本原理第22頁，共51頁，2023年，2月20日，星期五23動物的捕食策略第23頁，共51頁，2023年，2月20日，星期五24應(yīng)用捕食搜索算法尋優(yōu)時，先在整個搜索空間進行全局搜索，直到找到一個較優(yōu)解；然后在較優(yōu)解附近的區(qū)域進行集中搜索，直到搜索很多次也沒有找到更優(yōu)解，從而放棄局域搜索；然后再在整個搜索空間進行全局搜索。如此循環(huán)，直到找到最優(yōu)解（或近似最優(yōu)解）為止。在捕食搜索算法中，使用限制（restriction）來表征較優(yōu)解的鄰域大小。通過限制的調(diào)節(jié)，實現(xiàn)搜索空間的增大和減小，從而達到探索能力和開發(fā)能力的平衡。

捕食搜索算法——基本原理第24頁，共51頁，2023年，2月20日，星期五25捕食搜索算法——基本原理第25頁，共51頁，2023年，2月20日，星期五26捕食搜索算法——基本概念第26頁，共51頁，2023年，2月20日，星期五27捕食搜索算法——基本概念第27頁，共51頁，2023年，2月20日，星期五28捕食搜索算法——基本概念第28頁，共51頁，2023年，2月20日，星期五29捕食搜索算法——基本概念解空間示意圖第29頁，共51頁，2023年，2月20日，星期五30捕食搜索算法——基本概念第30頁，共51頁，2023年，2月20日，星期五31捕食搜索算法——基本概念第31頁，共51頁，2023年，2月20日，星期五32捕食搜索算法——基本概念第32頁，共51頁，2023年，2月20日，星期五33捕食搜索算法——算法步驟第33頁，共51頁，2023年，2月20日，星期五34捕食搜索算法——算法步驟第34頁，共51頁，2023年，2月20日，星期五35捕食搜索算法——限制的計算第35頁，共51頁，2023年，2月20日，星期五36捕食搜索算法——參數(shù)的設(shè)置第36頁，共51頁，2023年，2月20日，星期五37捕食搜索算法——參數(shù)的設(shè)置第37頁，共51頁，2023年，2月20日，星期五38捕食搜索算法——計算舉例第38頁，共51頁，2023年，2月20日，星期五39捕食搜索算法——計算舉例第39頁，共51頁，2023年，2月20日，星期五40捕食搜索算法——計算舉例第40頁，共51頁，2023年，2月20日，星期五41捕食搜索算法——計算舉例第41頁，共51頁，2023年，2月20日，星期五42捕食搜索算法——計算舉例第42頁，共51頁，2023年，2月20日，星期五43捕食搜索算法——計算舉例第43頁，共51頁，2023年，2月20日，星期五44捕食搜索算法——計算舉例第44頁，共51頁，2023年，2月20日，星期五45捕食搜索算法——計算舉例第45頁，共51頁，2023年，2月20日，星期五46捕食搜索算法——計算舉例第46頁，共51頁，2023年，2月20日，星期五47捕食搜索算法——計算舉例第47頁，共51頁，