人工智能第12章群智能課件

1、人工智能第十二章 群智能第1頁，共73頁。12.1 群智能概述12.2 蟻群算法12.3 粒子群優(yōu)化算法12.4 其他群智能優(yōu)化算法第2頁，共73頁。群智能（Swarm Intelligence，SI）優(yōu)化算法通過模擬自然界中的昆蟲、鳥群、魚群等“社會性”生物群體的行為特征，利用群體性生物能夠不斷學習自身經(jīng)驗與其他個體經(jīng)驗的特性，在尋優(yōu)過程中不斷獲取和積累尋優(yōu)空間的知識，自適應(yīng)地進行搜索尋優(yōu)，從而得到最優(yōu)解或準有解。群智能優(yōu)化算法作為一種新興的演化計算技術(shù)，具有較強的自學習性、自適應(yīng)性、自組織性等智能特征，算法結(jié)構(gòu)簡單、收斂速度快、全局收斂性好，在旅行商問題、圖著色問題、車間調(diào)度問題、數(shù)據(jù)聚類

2、問題等領(lǐng)域得到廣泛的應(yīng)用，與進化算法和人工神經(jīng)網(wǎng)絡(luò)并稱為人工智能領(lǐng)域的三駕馬車。12.1 群智能概述第3頁，共73頁。自然界中的群體生物，具有驚人的完成復雜行為的能力，群智能優(yōu)化算法則是國內(nèi)外研究學者受到群體生物的社會行為啟發(fā)而提出。其中提出時間最早、應(yīng)用最為廣泛的群智能優(yōu)化算法主要是模擬螞蟻覓食行為的蟻群算法（Ant Colony Optimization，ACO）和模擬鳥類覓食行為的粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）。 12.1.1 群智能優(yōu)化算法定義鳥群通過協(xié)作進行捕食房間偏僻角落里的蛋糕總會先被螞蟻發(fā)現(xiàn)魚聚集成群可以有效的逃避捕食者第4頁，

3、共73頁。群智能優(yōu)化算法主要源于對自然界中群體生物覓食等行為的模擬，每個具有經(jīng)驗和智慧的個體通過相互作用機制形成強大的群體智慧來解決復雜問題。其主要算法流程如下。將尋優(yōu)過程模擬成生物個體的覓食等行為過程，用搜索空間中的點模擬自然界中的生物個體；將求解問題的目標函數(shù)量化為生物個體對環(huán)境的適應(yīng)能力；將生物個體覓食等行為過程類比為傳統(tǒng)尋優(yōu)方法用較優(yōu)的可行解取代較差可行解的迭代過程，從而演化成為一種具有“生成+檢驗”特征的迭代搜索算法，是一種求解極值問題的自適應(yīng)人工智能技術(shù)。群智能主要算法流程第5頁，共73頁。12.1.2 群智能優(yōu)化算法原理自然界中的昆蟲、鳥群、魚群等一些生物具有群體性的行為特征，計

4、算機圖形學家雷諾茲（C. Reynolds）認為以群落形式生存的生物在覓食時一般遵循以下三個規(guī)則。1）分隔規(guī)則：盡可能避免與周邊生物個體距離太近，造成擁擠；2）對準規(guī)則：盡可能與周邊生物個體的平均移動方向保持一致，向目標方向移動；3）內(nèi)聚規(guī)則：盡可能向周邊生物個體的中心移動。第6頁，共73頁。上述規(guī)則中，分隔規(guī)則體現(xiàn)出生物的個體信息特征，即個體根據(jù)自身當前狀態(tài)進行決策；對準規(guī)則和內(nèi)聚規(guī)則體現(xiàn)生物的群體信息特征，即個體根據(jù)群體狀態(tài)進行決策。除個體信息與群體信息特征，生物行為還具有適應(yīng)性、盲目性、自治性、突現(xiàn)性、并行性等特征。群智能優(yōu)化算法就是利用雷諾茲模型模擬整個生物群體的行為，算法在迭代過程中

5、不斷利用個體最優(yōu)值與群體最優(yōu)值進行尋優(yōu)搜索，完成個體信息與群體信息的交互。在群智能優(yōu)化算法中，個體最優(yōu)值的隨機性使得算法搜索方向具有多樣性，能夠避免算法收斂過早陷入局部最優(yōu)；群體最優(yōu)值能夠把握全局尋優(yōu)方向，提高算法的全局尋優(yōu)能力，及時收斂。第7頁，共73頁。12.1.3 群智能優(yōu)化算法特點群智能優(yōu)化算法主要用來求解一些復雜的、難以用傳統(tǒng)算法解決的問題。與傳統(tǒng)優(yōu)化算法不同，群智能優(yōu)化算法是一種概率搜索算法，具有以下幾個特點。具有較強的魯棒性，群體中相互作用的個體是分布式的，沒有直接的控制中心，不會因少數(shù)個體出現(xiàn)故障而影響對問題的求解。結(jié)構(gòu)簡單，易于實現(xiàn)，每個個體只能感知局部信息，個體遵循的規(guī)則簡

6、單。易于擴充，開銷較少。具有自組織性，群體表現(xiàn)出的智能復雜行為由簡單個體交互而來。第8頁，共73頁。12.2 蟻群算法蟻群算法，又稱為螞蟻算法，1992年多里戈（M. Dorigo）受自然界中真實蟻群的群體覓食行為啟發(fā)提出，是最早的群智能優(yōu)化算法，起初被用來求解旅行商（Total Suspended Particulate，TSP）問題。第9頁，共73頁。12.2.1 蟻群算法概述螞蟻是一種社會性生物，在尋找食物時，會在經(jīng)過的路徑上釋放一種信息素，一定范圍內(nèi)的螞蟻能夠感覺到這種信息素，并移動到信息素濃度高的方向，因此蟻群通過螞蟻個體的交互能夠表現(xiàn)出復雜的行為特征。蟻群的群體性行為能夠看作是一種

7、正反饋現(xiàn)象，因此蟻群行為又可以被理解成增強型學習系統(tǒng)（Reinforcement Learning System）。第10頁，共73頁。12.2.2 蟻群算法的數(shù)學模型蟻群優(yōu)化算法的第一個應(yīng)用是著名的旅行商問題。旅行商問題闡明 蟻群系統(tǒng)模型旅行商問題（Traveling Salesman Problem，TSP）：在尋求單一旅行者由起點出發(fā)，通過所有給定的需求點之后，最后再回到原點的最小路徑成本。螞蟻搜索食物的過程 ：通過個體之間的信息交流與相互協(xié)作最終找到從蟻穴到食物源的最短路徑。第11頁，共73頁。符號表示 m 是蟻群中螞蟻的數(shù)量； 表示結(jié)點i（城市）和結(jié)點j（城市）之間的距離； 表示t時

8、刻在ij連線上殘留的信息素，初始時刻，各條路徑上 的信息素相等，螞蟻k在運動過程中，根據(jù)各條路徑上的信息 素決定轉(zhuǎn)移方向。 稱為啟發(fā)信息函數(shù)，等于距離的倒數(shù)； 表示在t時刻螞蟻 k 選擇從結(jié)點 （城市）i 轉(zhuǎn)移到結(jié)點（城 市） j的概率，也稱為隨機比例規(guī)則。第12頁，共73頁。信息素 共同決定局部啟發(fā)信息 表示螞蟻k下一步允許選擇的城市 記錄螞蟻k當前所走過的城市 是信息素啟發(fā)式因子，表示軌跡的相對重要性 表示期望啟發(fā)式因子，表示能見度的相對重要程度第13頁，共73頁。 值越大該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，該狀態(tài)轉(zhuǎn)移概率越接近于貪婪規(guī)則。當 = 0時不再考慮信息素水平，算法就成為有多重

9、起點的隨機貪婪算法。當 = 0時算法就成為純粹的正反饋的啟發(fā)式算法。第14頁，共73頁。1-表示信息素殘留因子，常數(shù) 為信息素揮發(fā)因子， 表示路徑上信息素的損耗程度； 的大小關(guān)系到算法的全局搜索能力和收斂速度。螞蟻完成一次循環(huán)，各路徑上信息素濃度揮發(fā)規(guī)則為： 蟻群的信息素濃度更新規(guī)則為： 根據(jù)信息素更新策略不同，多里戈提出了3種基本蟻群算法模型。第15頁，共73頁。1、蟻周系統(tǒng)（Ant-cycle System）單只螞蟻所訪問路徑上的信息素濃度更新規(guī)則為： Q 為常數(shù)Lk 為優(yōu)化問題的目標函數(shù)值，表示第k只螞蟻在本次循環(huán)中所走路徑的長度。第16頁，共73頁。2、蟻量系統(tǒng)（Ant-quantit

10、y System） 3、 蟻密系統(tǒng)（Ant-density System） 第17頁，共73頁。蟻圈系統(tǒng)利用的是全局信息 ，即螞蟻完成一個循環(huán)后，更新所有路徑上的信息。蟻量系統(tǒng)利用的是局部信息 ，即螞蟻每走一步都要更新殘留信息素的濃度。蟻密系統(tǒng)利用的是局部信息 ，即螞蟻每走一步都要更新殘留信息素的濃度。三種模型比較效果最好，通常作為蟻群優(yōu)化算法的基本模型。第18頁，共73頁。設(shè)置參數(shù),初始化信息素濃度While（不滿足條件時）dofor蟻群中的每只螞蟻for每個解構(gòu)造步驟(直到構(gòu)造出完整的可行解)1）螞蟻按照信息素及啟發(fā)因子構(gòu)造下一步問題的解；2）進行信息素局部更新。(可選)end foren

11、d for1）以已獲得的解為起點進行局部搜索；(可選)2）根據(jù)已獲得的解的質(zhì)量進行全局信息素更新。end Whileend 蟻群算法流程第19頁，共73頁。12.2.3 蟻群算法的改進為提高蟻群算法性能，諸多研究學者對蟻群算法進行了改進，其中主要包括螞蟻-Q系統(tǒng)（Ant-Q System）、蟻群系統(tǒng)（Ant Colony System, ACS）、最大-最小螞蟻系統(tǒng)（Max-Min Ant System，MMAS）、自適應(yīng)蟻群算法。第20頁，共73頁。螞蟻-Q系統(tǒng)1995年，意大利學者盧卡（M. Luca）、甘巴德拉（L. M. Gambardella）、多里戈在ACO算法的基礎(chǔ)上，進行了創(chuàng)新

12、，提出了螞蟻-Q系統(tǒng)。在解構(gòu)造過程中提出了偽隨機比例狀態(tài)遷移規(guī)則；信息素局部更新規(guī)則引入強化學習中的Q學習機制；在信息素的全局更新中采用了精英策略。第21頁，共73頁。其概率分布計算、AQ值更新規(guī)則分別為：其中：第22頁，共73頁。1996年，甘巴德拉和多里戈又在Ant-Q算法的基礎(chǔ)上提出了蟻群系統(tǒng)，蟻群系統(tǒng)是Ant-Q算法的一種特例。其主要創(chuàng)新如下：蟻群系統(tǒng)相比ACO算法，蟻群系統(tǒng)中的螞蟻在下一步移動之前，增加一次隨機實驗，將選擇情況分成“利用已知信息”和“探索”兩類。提出了精英策略（Elitist Strategy）。設(shè)置精英螞蟻數(shù)目的最優(yōu)范圍：若低于該范圍，增加精英螞蟻數(shù)目，以便能夠較快

13、的發(fā)現(xiàn)最優(yōu)路徑；若高于該范圍，精英螞蟻會在搜索初期迫使尋優(yōu)過程停留在次優(yōu)解附近，降低算法性能。第23頁，共73頁。其中狀態(tài)轉(zhuǎn)移規(guī)則為： 其中，Sk表示螞蟻k所選中的下一個結(jié)點；q是一個隨機變量，為設(shè)定閾值。第24頁，共73頁。1997年，德國學者施蒂茨勒（T. Stutzle）提出了最大-最小螞蟻系統(tǒng)。其主要創(chuàng)新如下：最大-最小螞蟻系統(tǒng)為了避免算法收斂過早，陷入局部最優(yōu)，將各條路徑的信息素濃度限制到min,max區(qū)間范圍內(nèi)。采用了平滑機制，路徑上信息素濃度的增加與max和當前濃度(i, j)之差成正比，即其中，0 1。第25頁，共73頁。自適應(yīng)蟻群算法自適應(yīng)蟻群算法能夠根據(jù)搜索結(jié)果進行信息素濃

14、度更新，如果算法陷入局部最優(yōu)，自適應(yīng)調(diào)整陷入局部最優(yōu)的螞蟻所經(jīng)過路徑中的信息素和信息素強度Q，使得算法能夠較快的跳出局部最優(yōu)，避免算法“早熟”，同時自適應(yīng)蟻群算法限定所有路徑上的信息素范圍，有利于提高算法全局搜索能力。第26頁，共73頁。蟻群算法最早被用來解決旅行商問題，隨后陸續(xù)被用于解決圖著色問題、二次分配問題、大規(guī)模集成電路設(shè)計、通訊網(wǎng)絡(luò)中的路由問題以及負載平衡問題、車輛調(diào)度問題、數(shù)據(jù)聚類問題、武器攻擊目標分配和優(yōu)化問題、區(qū)域性無線電頻率自動分配問題等。12.2.3 蟻群算法的應(yīng)用示例旅行商問題描述如下：假設(shè)為一個加權(quán)圖，為頂點集，為邊集。為頂點i到頂點j的距離，其中且，同時。 第27頁，

15、共73頁。經(jīng)典TSP的數(shù)學模型為： 是圖s的頂點數(shù)。第28頁，共73頁。實際問題可以描述為：一行人要去27個城市旅行，其中城市坐標如表所示，該人從一城市出發(fā)，使用蟻群算法計算，應(yīng)如何選擇行進路線，以使總的行程最短。城市123456789行值304639177 712 488326238196312列值312315244399535556229104790城市101112131415161718行值386107562788381332715918161列值570970756491676695678179370城市192021222324252627行值7806763292634295073944

16、39935列值212578838931908367643201240第29頁，共73頁。應(yīng)用基本蟻群算法進行建模，可計算得出行程最短路徑為：城市19城市4城市2城市24城市26城市8城市7城市3城市18城市1城市5城市10城市6城市25城市14城市15城市9城市21城市22城市11城市23城市12城市16城市20城市13城市27城市17。第30頁，共73頁。12.3 粒子群優(yōu)化算法粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）源于對鳥群社會系統(tǒng)的研究，由美國普渡大學的埃伯哈特（J. Eberhart）和肯尼迪（R. Kennedy）于1995年提出。其核心思想

17、是利用個體的信息共享促使群體在問題解空間從無序進行有序演化，最終得到問題的最優(yōu)解。第31頁，共73頁?？捎萌缦陆?jīng)典描述直觀理解粒子群優(yōu)化算法：設(shè)想這么一個場景：一群鳥在尋找食物，在遠處有一片玉米地，所有的鳥都不知道玉米地到底在哪里，但是它們知道自己當前的位置距離玉米地有多遠。那么找到玉米地的最優(yōu)策略就是搜尋目前距離玉米地最近的鳥群的所在區(qū)域。粒子群優(yōu)化算法就是從鳥群食物的覓食行為中得到啟示，從而構(gòu)建形成的一種優(yōu)化方法。12.3.1 粒子群優(yōu)化算法基本思想第32頁，共73頁。粒子群優(yōu)化算法將每個問題的解類比為搜索空間中的一只鳥，稱之為“粒子”，問題的最優(yōu)解對應(yīng)為鳥群要尋找的“玉米地”。每個粒子設(shè)

18、定一個初始位置和速度向量，根據(jù)目標函數(shù)計算當前所在位置的適應(yīng)度值（Fitness Value），可以將其理解為距離“玉米地”的距離。粒子在迭代過程中，根據(jù)自身的“經(jīng)驗”和群體中的最優(yōu)粒子的“經(jīng)驗”進行學習，從而確定下一次迭代時飛行的方向和速度。通過逐步迭代，整個群體逐步趨于最優(yōu)解。第33頁，共73頁。在n 維連續(xù)搜索空間中，對粒子群中的第i (i=1, 2, , m)個粒子進行定義： ：表示搜索空間中粒子的當前位置。 ：表示該粒子至今所獲得的具有最優(yōu)適應(yīng)度 的位置。 ：表示該粒子的搜索方向。12.3.2 粒子群優(yōu)化算法基本框架 ：表示每個粒子經(jīng)歷過的最優(yōu)位置（Pbest）。 ：群體經(jīng)歷過的最優(yōu)

19、位置（Gbest）。第34頁，共73頁。c1 ，c2 是速度因子，均為非負值；r1 和 r2 為0, 1 范圍內(nèi)的隨機數(shù)。早期的粒子群優(yōu)化算法速度和位置向量更新公式如下：；第35頁，共73頁。由于 的更新過于隨機，使得粒子群優(yōu)化算法具有較強的全局尋優(yōu)能力，但是局部尋優(yōu)能力較差。為保證算法具有全局尋優(yōu)能力的同時，提高其局部尋優(yōu)能力。1998年Shi Yuhui和埃伯哈特在算法中引入慣性權(quán)重（Inertia Weight）系數(shù)w，修正了速度向量更新公式：第36頁，共73頁。參數(shù)w取值范圍為0,1，與物理中的慣性相似，w反映了粒子歷史運動狀態(tài)對當前運動的影響。如果w取值較小，歷史運動狀態(tài)對當前運動影

20、響較小，粒子的速度能夠很快的改變；相反，如果w取值較大，雖然提高了搜索空間范圍，但是粒子運動方向不易改變，難于向較優(yōu)位置收斂。因此w設(shè)置較大時，能夠提高算法全局尋優(yōu)能力，w設(shè)置較小時，又能夠加快算法局部尋優(yōu)。實際工程應(yīng)用中w可采取自適應(yīng)取值方式。第37頁，共73頁。粒子群優(yōu)化算法流程procedure PSO for 每個粒子i 初始化每個粒子i，隨機設(shè)置每個粒子的初始位置和速度 計算每個粒子i的目標函數(shù)，Gbest = end for Gbest = minPbesti while not stop for i=1 to m 更新粒子i的速度和位置 if fit() fit(Pbesti)

21、Pbesti = if fit(Pbesti) fit(Gbest) Gbest = Pbesti; end for end while print Gbestend procedure第38頁，共73頁。12.3.3 粒子群優(yōu)化算法參數(shù)分析與改進粒子群優(yōu)化算法中主要參數(shù)如下：種群規(guī)模m種群規(guī)模通常設(shè)置為20-40，可根據(jù)不同問題進行自定義。慣性權(quán)重w慣性權(quán)重能夠保持粒子運動慣性，擴展搜索空間，搜索新的區(qū)域。最大速度Vmax最大速度Vmax決定當前位置與最優(yōu)位置之間的區(qū)域的精度。若Vmax過大，粒子可能跨過最優(yōu)位置；若Vmax過小，粒子無法在局部最優(yōu)值之外進行足夠的探索，易陷入局部最優(yōu)。限制最

22、大速度可以有效防止計算溢出、決定問題空間搜索的粒度。迭代次數(shù)Gmax迭代次數(shù)Gmax根據(jù)工程應(yīng)用具體問題決定。第39頁，共73頁。學習因子c1、c2學習因子c1、c2分別控制個體認知分量和群體社會分量相對貢獻的學習率。當c1=0、c2=0時，只有第1部分，粒子保持當前速度飛行，直到達邊界，只能搜索有限的區(qū)域，無法找到最優(yōu)解。w=0時，沒有第1部分，速度沒有記憶性，只取決于粒子當前位置和其歷史最優(yōu)位置。當c1=0時，沒有第2部分，粒子沒有認知能力，只有“社會模型”。在粒子的相互作用下，有能力達到新的搜索空間。但是復雜問題容易陷入局部最優(yōu)。當c2=0時，沒有第3部分，粒子間沒有社會共享信息，只有“

23、認知模型”。個體間沒有交互，群體中所有個體獨立搜索，因此無法得到最優(yōu)解。第40頁，共73頁。粒子群優(yōu)化算法的改進粒子群優(yōu)化算法具有收斂速度快的優(yōu)點，但是在算法運行初期，算法存在精度較低、易發(fā)散等缺點。因此國內(nèi)外諸多研究人員致力于提高粒子群優(yōu)化算法的性能，現(xiàn)階段主要側(cè)重理論研究改進、拓撲結(jié)構(gòu)改進、混合改進算法、參數(shù)優(yōu)化等方面。第41頁，共73頁。粒子群優(yōu)化算法自提出至今，被廣泛的應(yīng)用于神經(jīng)網(wǎng)絡(luò)訓練、機器人、經(jīng)濟、通信、醫(yī)學等多種領(lǐng)域。本節(jié)示例為粒子群優(yōu)化算法在車輛路徑問題（Vehicle Routing Problem，VRP）中的應(yīng)用。12.3.4 粒子群優(yōu)化算法的應(yīng)用示例第42頁，共73頁。

24、假定配送中心最多可以用 輛車對 個客戶進行運輸配送， 表示倉庫。每個車輛載重為 ，每個客戶的需求為 ，客戶i到客戶 j 的運輸成本為 cij（可以是距離，時間，費用等）。定義如下變量：第43頁，共73頁。1、建立車輛路徑問題的數(shù)學模型如下：每輛車的能力約束：保證每個客戶都被服務(wù)：保證客戶是僅被一輛車訪問：保證客戶是僅被一輛車訪問：消除子回路：表示變量的取值范圍：表示變量的取值范圍：第44頁，共73頁。2、編碼與初始種群 對這類組合優(yōu)化問題，編碼方式、初始解的設(shè)置對問題的求解都有很大的影響。 本問題采用常用的自然數(shù)編碼方式。 對于K輛車和L個客戶的問題，用從1到L的自然數(shù)隨機排列來產(chǎn)生一組解 。

25、然后分別用節(jié)約法或者最近插入法構(gòu)造初始解。第45頁，共73頁。粒子群優(yōu)化算法的各個參數(shù)設(shè)置如下：種群規(guī)模p=50 ，迭代次數(shù)Gmax=1000，w的初始值為1，隨著迭代的進行，線性減小到0，c1=c2=1.4 ， 。優(yōu)化結(jié)果及其比較實例PSOGAbestdev(%)bestdev(%)A-n32-k58295.738184.34A-n33-k57056.656741.97A-n34-k58326.948215.52A-n39-k68726.088665.35A-n44-k610168.499915.76A-n46-k79776.899574.7A-n54-k712053.2612033.08A

26、-n60-k914769.0114104.13A-n69-k912751012437.24A-n80-k10199212.9818716.12第46頁，共73頁。12.4 其他群智能優(yōu)化算法隨著蟻群算法、粒子群優(yōu)化算法的廣泛應(yīng)用，各類群智能優(yōu)化算法蜂擁而至。其中較為典型的幾種包括人工魚群算法（Artificial Fish Swarm Algorithm，AFSA）、細菌覓食算法（Bacterial Foraging Optimization，BFO）、蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）、果蠅優(yōu)化算法（Fruit Fly Optimizatio

27、n Algorithm，F(xiàn)OA）等。群智能優(yōu)化1992年 1995年2002年2003年2005年2007年2011年2014年蟻群算法果蠅優(yōu)化算法狼群算法鴿群優(yōu)化算法人工魚群算法第47頁，共73頁。人工魚群算法（Artificial Fish Swarm Algorithm，AFSA），由李曉磊博士于2001年提出，是一種源于魚群自治行為的群智能優(yōu)化算法，通過構(gòu)造人工魚來模仿魚群的覓食、聚群、追尾和隨機行為，從而實現(xiàn)尋優(yōu)，具有較快的收斂速度，可以用于解決有實時性要求的問題。12.4.1 人工魚群算法人工魚的結(jié)構(gòu)圖第48頁，共73頁。假設(shè)人工魚當前狀態(tài)為X，Visual代表其視野范圍，Xv表示

28、某時刻其視點所在位置。若該位置的狀態(tài)優(yōu)于當前狀態(tài)，向當前位置方向前進一步到達狀態(tài)Xnext；若狀態(tài)Xv比當前狀態(tài)差，繼續(xù)巡視視野內(nèi)的其他位置。巡視的次數(shù)越多，對視野范圍內(nèi)的信息了解越全面，從而能夠全方位立體感知周圍的環(huán)境，有助于對目標問題做出相應(yīng)的判斷和決策。人工魚群算法基本概念人工魚視覺的概念第49頁，共73頁。其中，狀態(tài) ，狀態(tài) ，則該過程可以表示為：式中，rand函數(shù)用來產(chǎn)生0,1之間的隨機數(shù)；Step為移動步長。第50頁，共73頁。人工魚群算法采用面向?qū)ο蟮募夹g(shù)重構(gòu)人工魚的模型，將人工魚封裝成變量和函數(shù)兩部分。其中變量部分包括人工魚的總數(shù)N，人工魚個體的狀態(tài)為待尋優(yōu)的變量），人工魚移動

29、的最大步長Step，人工魚的視野Visual，嘗試次數(shù)Try_number，擁擠度因子，人工魚個體i,j之間的距離 。函數(shù)部分包括人工魚當前所處位置的食物濃度 人工魚的各種行為函數(shù)（覓食行為Prey()、聚群行為Swarm()、追尾行為Follow()、隨機行為Move()以及行為評價函數(shù)Evaluate()）。通過封裝，人工魚的狀態(tài)能夠被其他同伴感知。（Y為目標函數(shù)值）第51頁，共73頁。覓食行為聚群行為追尾行為隨機行為人工魚的四種基本行為算法描述由于魚類不具備復雜邏輯推理能力和綜合判斷能力，它們只能通過簡單行為達到目的。因此通過模擬魚類的四種行為覓食行為、聚群行為、追尾行為和隨機行為來使魚

30、類活動在周圍的環(huán)境。第52頁，共73頁。覓食行為是人工魚趨向食物源的一種基本行為，一般通過視覺或味覺感知水中的食物數(shù)量或濃度，進行趨向選擇。行為描述：設(shè)人工魚i的當前狀態(tài)為Xi，在其感知范圍內(nèi)隨機選擇一個狀態(tài)Xj，則其中，rand是一個0,1之間的隨機數(shù)，在求解問題極大值時，若YiYj，則向Xj方向前進一步：否則，再次隨機選擇狀態(tài)Xj，判斷是否滿足前進條件，若反復嘗試Try_number次后仍不滿足前進條件，則隨機移動一步：覓食行為第53頁，共73頁。這是魚群生存和躲避危害的一種生活習性。在魚群算法中，一般規(guī)定兩條，一是盡量向鄰近伙伴的中心移動，二是避免過分擁擠。行為描述：設(shè)人工魚當前狀態(tài)為X

31、i，當前搜索范圍內(nèi)dijVisual，伙伴數(shù)目為 ，中心位置為Xo。若 ，表明伙伴中心食物較多且不存在過分擁擠，則向伙伴中心位置方向前進一步，即否則，執(zhí)行覓食行為。聚集行為第54頁，共73頁。魚群在游動過程中，當其中一條魚或幾條魚發(fā)現(xiàn)食物時，其鄰近的伙伴會尾隨其快速到達食物點。行為描述：設(shè)人工魚i當前狀態(tài)為Xi，當前搜索范圍內(nèi)dij0表示細菌的游動步長單位； 表示細菌翻轉(zhuǎn)運動后隨機改變的角度。 第62頁，共73頁。細菌覓食算法具體步驟算法參數(shù)初始化，包括細菌個數(shù)S、趨化操作次數(shù)Nc、最大游動步數(shù)Ns、繁殖操作次數(shù)Nre、驅(qū)散操作次數(shù)Ned以及細菌個體驅(qū)散概率P、隨機生成單個細菌的位置。種群位置

32、初始化，計算每個細菌初始適應(yīng)度值，j=0，k=0，l=0。驅(qū)散操作循環(huán)l=l+1。繁殖操作循環(huán)k=k+1。趨化操作循環(huán)i=i+1，每個細菌個體進行趨化操作。若jNc，則回到。繁殖操作，適應(yīng)度值排在前S/2的個體進行繁殖，替換適應(yīng)度值較小的另一半細菌。若kNre，則轉(zhuǎn)到。驅(qū)散操作。當細菌i滿足驅(qū)散概率，隨機生成新的細菌替換細菌i。若lNed，則轉(zhuǎn)到；否則，算法結(jié)束，輸出問題最優(yōu)結(jié)果。第63頁，共73頁。12.4.3 混合蛙跳算法混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA），由尤瑟夫（M. M. Eusuff）和蘭西（K. E. Lansey）于2003

33、年提出，是一種全新的后啟發(fā)式群體智能算法，結(jié)合了模因演算MA（Memetic Algorithm）和粒子群優(yōu)化算法2種算法的優(yōu)點，具有高效的計算效率和良好的全局尋優(yōu)能力。第64頁，共73頁?；旌贤芴惴ɑ靖拍罨旌贤芴惴梢悦枋鰹椋涸谝黄臻g區(qū)域內(nèi)生活著一群青蛙，為了尋找食物較多的地方，蛙群首先按照一定的規(guī)則確定每只青蛙的初始位置。隨后，每只青蛙利用個體信息在初始位置附近搜索食物更多的區(qū)域，跳躍完成個體位置更新。主要搜索規(guī)則為，蛙群利用青蛙的自組織性行為，組成多個子種群，子種群中的青蛙個數(shù)基本相同，由子種群中的局部精英個體帶領(lǐng)其他個體進行組團搜索。子種群完成一次搜索后，蛙群中的所有個體進行重新混合分組，繼續(xù)執(zhí)行組團。組團搜索與蛙群混合迭代進行，直至到達食物最豐富的位置。第65頁，共73頁?；旌贤芴惴ɑ玖鞒袒旌贤芴惴ㄊ紫葟目尚杏蛑须S機產(chǎn)生一組初始解，每個解對應(yīng)一只青蛙，形成初始種群；根據(jù)目標函數(shù)，計算每個青蛙的適應(yīng)度值，進行由大到小排列；以一定的規(guī)則將蛙群劃分為一定數(shù)量的子種群，每個子種群進行局部搜索，子種群內(nèi)最差的青蛙根據(jù)更新策略向局部最優(yōu)位置靠近；子種群完成一次局部搜索后，