智能優(yōu)化算法解析第6章

基于群智能的智能優(yōu)化算法6.1蟻群優(yōu)化算法6.2粒子群優(yōu)化算法6.3細(xì)菌覓食優(yōu)化算法主要內(nèi)容CONTENTS6.4浣熊優(yōu)化算法3基于群智能的智能優(yōu)化算法不同生物體在漫長的自然進(jìn)化過程中，形成了各自獨(dú)特的智能行為，這些智能行為啟發(fā)人們設(shè)計高效的優(yōu)化算法，從而推動科學(xué)技術(shù)的發(fā)展和進(jìn)步導(dǎo)讀蟻群優(yōu)化算法：模擬螞蟻尋找從蟻穴到食物源的最短路徑的覓食行為粒子群優(yōu)化算法：模擬鳥類的飛行行為細(xì)菌覓食優(yōu)化算法：模擬大腸桿菌在生存環(huán)境中尋找營養(yǎng)物質(zhì)的覓食行為浣熊優(yōu)化算法：模擬長鼻浣熊捕食綠鬣蜥和逃脫被其它生物捕食的自然行為6.1蟻群優(yōu)化算法56.1.1

算法原理生物學(xué)原理生物學(xué)研究表明，螞蟻在覓食過程中通過路徑上釋放的信息素進(jìn)行交流路徑上的信息素量關(guān)系著螞蟻的移動方向路徑上經(jīng)過的螞蟻越多，其上信息素量越多，被螞蟻選中的概率越大當(dāng)有螞蟻選擇了沒有信息素的路徑，則表示螞蟻發(fā)現(xiàn)了新的路徑短路徑上單位時間內(nèi)經(jīng)過的螞蟻數(shù)量多于長路徑，同樣時間內(nèi)其信息素量的積累會多于長路徑的積累，從而吸引更多的螞蟻到短路徑上正反饋機(jī)制：短路徑上的螞蟻數(shù)量和信息素量越來越多長路徑上的螞蟻數(shù)量和信息素量越來越少66.1.1

算法原理優(yōu)化問題求解原理蟻群優(yōu)化算法正是受到上述螞蟻覓食行為的啟發(fā)而提出，最早用于解決TSP：將

只螞蟻隨機(jī)地放在

個城市上，每只螞蟻根據(jù)各條路徑上的信息素量和問題的啟發(fā)信息決定轉(zhuǎn)移路徑每經(jīng)過

個時刻，每只螞蟻完成一次

個城市的周游，即構(gòu)建完成TSP的一個可行解在每次周游中或者周游結(jié)束后，周游路徑上的信息素量根據(jù)經(jīng)過的螞蟻數(shù)量按照某種規(guī)則進(jìn)行更新當(dāng)一定次數(shù)的周游結(jié)束后，最小長度的周游路徑即為TSP的最優(yōu)解在蟻群優(yōu)化算法中，信息素初始化、路徑轉(zhuǎn)移和信息素更新是三個關(guān)鍵機(jī)制76.1.2

螞蟻系統(tǒng)算法螞蟻系統(tǒng)算法的優(yōu)化機(jī)制初始化機(jī)制：在初始時刻，各條路徑上信息素量相等，并設(shè)置為某一常量

式中，表示初始時刻時城市和城市之間的路徑上的信息素；是一個常數(shù)。螞蟻系統(tǒng)（AntSystem,AS）算法在1991年由意大利科學(xué)家Dorigo等人提出，是第一個蟻群優(yōu)化算法

（6-1）86.1.2

螞蟻系統(tǒng)算法螞蟻系統(tǒng)算法的優(yōu)化機(jī)制路徑轉(zhuǎn)移規(guī)則：每只螞蟻根據(jù)各條路徑上的信息素量和啟發(fā)信息決定下一步要行走的路徑。設(shè)置禁忌表

來螞蟻

所走過的城市；每只螞蟻的禁忌表隨著周游過程動態(tài)調(diào)整，在每輪周游結(jié)束后，會被清空。具體來說，螞蟻根據(jù)下式計算到訪路徑的轉(zhuǎn)移概率，然后根據(jù)輪盤賭原則選擇下一個到訪城市，并將選取的城市記錄在禁忌表式中，各個符號的意義如下：（6-2）96.1.2

螞蟻系統(tǒng)算法螞蟻系統(tǒng)算法的優(yōu)化機(jī)制

表示在

時刻螞蟻

由城市

轉(zhuǎn)向城市

的路徑轉(zhuǎn)移概率

表示螞蟻

下一步允許訪問的城市集合，即信息素因子，表示信息素對路徑選擇的影響程度。

該值越大，代表信息素對路徑選擇的影響越大，意味著螞蟻更傾向于選擇其它螞蟻經(jīng)過的路徑

啟發(fā)因子，表示啟發(fā)信息對路徑選擇的影響程度。

該值越大，代表啟發(fā)信息對路徑選擇的影響越大，意味著螞蟻更傾向于根據(jù)啟發(fā)信息進(jìn)行路徑選擇

表示在

時刻城市

和城市

之間的路徑

上的信息素量

表示在

時刻城市

和城市

之間的路徑

上的啟發(fā)信息，用來衡量螞蟻從城市

轉(zhuǎn)移到城市

的期望程度，通常定義為：

路徑的長度（6-3）106.1.2

螞蟻系統(tǒng)算法螞蟻系統(tǒng)算法的優(yōu)化機(jī)制信息素更新規(guī)則：有蟻周（Ant-cycle）模型、蟻密（Ant-density）模型和蟻量（Ant-quantity）模型三種信息素更新規(guī)則蟻周模型：螞蟻在每次周游結(jié)束之后，對構(gòu)成可行解的各路徑上的信息素進(jìn)行更新：式中，表示信息素?fù)]發(fā)系數(shù)，則表示信息素殘留因子，用來避免信息素的無限積累；表示周游完成時的

時刻，路徑

上的信息素增量；

表示在

時刻，螞蟻

在路徑

上釋放的信息素量：

周游路徑長度一個常數(shù)，表示信息素強(qiáng)度（6-4）（6-5）116.1.2

螞蟻系統(tǒng)算法螞蟻系統(tǒng)算法的優(yōu)化機(jī)制信息素更新規(guī)則：有蟻周（Ant-cycle）模型、蟻密（Ant-density）模型和蟻量（Ant-quantity）模型三種信息素更新規(guī)則蟻密和蟻量模型：在周游過程中，每移動一步對構(gòu)成就對相應(yīng)路徑上的信息素進(jìn)行更新：式中，表示移動一步之后的

時刻，路徑

上的信息素增量；

表示在

時刻，螞蟻

在路徑

上釋放的信息素量。（6-6）126.1.2

螞蟻系統(tǒng)算法螞蟻系統(tǒng)算法的優(yōu)化機(jī)制信息素更新規(guī)則：有蟻周（Ant-cycle）模型、蟻密（Ant-density）模型和蟻量（Ant-quantity）模型三種信息素更新規(guī)則蟻密和蟻量模型：在周游過程中，每移動一步對構(gòu)成就對相應(yīng)路徑上的信息素進(jìn)行更新：蟻密和蟻量模型釋放信息素的方式分別為：

常數(shù)，表示信息素強(qiáng)度（6-7）（6-8）136.1.2

螞蟻系統(tǒng)算法螞蟻系統(tǒng)算法的實現(xiàn)過程

146.1.3

蟻群系統(tǒng)算法蟻群系統(tǒng)算法的優(yōu)化機(jī)制

AS算法的路徑選擇規(guī)則有很大的隨機(jī)性，導(dǎo)致其只適合于求解城市數(shù)目較少的小規(guī)模TSP，在大規(guī)模TSP上收斂速度比較慢AS算法的信息素更新規(guī)則會使少數(shù)路徑上的信息素量過多，導(dǎo)致其易停滯到一條局部最優(yōu)路徑上為了克服上述兩個問題，Dorigo等人提出了蟻群系統(tǒng)（AntColonySystem，ACS）算法，該算法提出了不同的路徑轉(zhuǎn)移規(guī)則和信息素更新規(guī)則156.1.3

蟻群系統(tǒng)算法蟻群系統(tǒng)算法的優(yōu)化機(jī)制

當(dāng)時，螞蟻選擇信息量最大的路徑，完全利用已有信息確定下一個到訪城市，有利于在局部范圍內(nèi)搜索優(yōu)異解；當(dāng)時，

螞蟻根據(jù)路徑選擇概率確定下一個到訪城市，有一定的機(jī)會探索新路徑，有利于在全局范圍內(nèi)搜索優(yōu)異解。（6-9）路徑轉(zhuǎn)移規(guī)則：每只螞蟻根據(jù)下式選擇下一個到訪城市進(jìn)行路徑轉(zhuǎn)移

式中，是根據(jù)AS算法的路徑轉(zhuǎn)移規(guī)則得到的下一個尚未訪問的城市；

是一個調(diào)控信息素和啟發(fā)信息發(fā)揮作用的影響因子；

是一個選擇路徑轉(zhuǎn)移方式的閾值；是區(qū)間

的一個隨機(jī)數(shù)。兼顧局部利用和全局勘探的搜索平衡166.1.3

蟻群系統(tǒng)算法蟻群系統(tǒng)算法的優(yōu)化機(jī)制（6-10）信息素全局更新規(guī)則：每次周游中，所有螞蟻完成解的構(gòu)建之后利用全局最優(yōu)解或者本次周游中發(fā)現(xiàn)的最優(yōu)解更新信息素，具體如下面兩個式子：

（6-11）其中，表示全局信息素?fù)]發(fā)系數(shù)；表示全局最優(yōu)解或者本次周游中發(fā)現(xiàn)的最優(yōu)解所對應(yīng)的周游路徑長度。176.1.3

蟻群系統(tǒng)算法蟻群系統(tǒng)算法的優(yōu)化機(jī)制信息素局部更新規(guī)則：每次周游中，螞蟻每移動一步就按照下式對經(jīng)過的路徑進(jìn)行信息素局部更新：

（6-12）式中，表示局部信息素?fù)]發(fā)系數(shù)信息素的局部更新規(guī)則通過對螞蟻經(jīng)過的每條路徑進(jìn)行信息素的及時更新，可以有效地避免在一次迭代中所有螞蟻都利用同樣的信息素進(jìn)行路徑選擇而導(dǎo)致易收斂到局部最優(yōu)路徑的問題。186.1.3

蟻群系統(tǒng)算法蟻群系統(tǒng)算法的實現(xiàn)過程196.1.4

最大-最小螞蟻系統(tǒng)算法最大-最小螞蟻系統(tǒng)算法的優(yōu)化機(jī)制

針對AS算法的信息素更新機(jī)制會使少數(shù)路徑上的信息素量過多而導(dǎo)致易停滯到局部最優(yōu)路徑上的問題，Stutzle等人提出了最大-最小螞蟻系統(tǒng)（MMAS）算法MMAS算法采用了ACS算法的路徑轉(zhuǎn)移規(guī)則，但在信息素的設(shè)置和更新方面有一些不同的設(shè)計信息素限制規(guī)則：MMAS算法將路徑上的信息素量限制在

范圍內(nèi)既可以防止某些路徑上信息素量過多而導(dǎo)致停滯到局部最優(yōu)路徑，也可以有效避免某些路徑上信息素量過小而沒有機(jī)會被選擇。在周游過程中，當(dāng)路徑上的信息素量小于

時，被重置為

；當(dāng)路徑上的信息素量大于

時，被重置為

。206.1.4

最大-最小螞蟻系統(tǒng)算法最大-最小螞蟻系統(tǒng)算法的優(yōu)化機(jī)制

信息素初始化規(guī)則：MMAS算法將各路徑上的信息素初始化為最大值

，這樣有利于螞蟻在周游早期階段探索更多可能的路徑，擴(kuò)大搜索范圍信息素更新規(guī)則：MMAS算法在所有螞蟻完成周游之后對最優(yōu)解上的路徑進(jìn)行信息素更新式中，表示在本次周游完成時的

時刻，發(fā)現(xiàn)最優(yōu)解的螞蟻在路徑

上釋放的信息量；表示本次周游中發(fā)現(xiàn)的最短路徑長度。（6-13）（6-14）216.1.4

最大-最小螞蟻系統(tǒng)算法最大-最小螞蟻系統(tǒng)算法的優(yōu)化機(jī)制

信息素平滑規(guī)則：為了進(jìn)一步消除某些路徑上信息素過多而易導(dǎo)致的搜索停滯問題，MMAS算法采用了一個信息素平滑規(guī)則：

式中，

是一個反映以前信息素保持程度的參數(shù)，

時完全保留以前的信息素，

時完全消除以前的信息素。（6-15）226.1.4

最大-最小螞蟻系統(tǒng)算法最大-最小螞蟻系統(tǒng)算法的實現(xiàn)過程

236.1.4

典型問題求解案例例題

例題6-1假設(shè)某公司要在全國八個省份推銷某商品。請利用蟻周模型版本的AS算法為該公司設(shè)計一條周游八個省會城市一次并回到起點省會城市的最短路線。八個省會城市及其坐標(biāo)如表6-1所示：表6-1八個省會城市及其二維坐標(biāo)246.1.4

典型問題求解案例求解過程

編寫Matlab主程序main.m如下：%讀取存儲8個城市坐標(biāo)的cite.csv文件，獲取8個城市坐標(biāo)filename='city8.csv';opts=detectImportOptions(filename);City=readtable(filename,opts);C=[City.x,City.y];Cname=City.city;%城市名稱%設(shè)置求解參數(shù)m=30;%螞蟻個數(shù)alpha=2;%信息素因子beta=4;%啟發(fā)因子rho=0.02;%信息素?fù)]發(fā)系數(shù)tau0=1/(34*160);%信息素初始值Tmax=200;%最大迭代次數(shù)Q=0.01;%信息素強(qiáng)度%調(diào)用AS算法求解該TSP[Shortest_Route,Shortest_Length]=AS(C,m,alpha,beta,rho,tau0,Tmax,Q);Draw_AS(C,Shortest_Route,Shortest_Length,'AS');%繪制最優(yōu)路徑和收斂曲線

256.1.4

典型問題求解案例求解過程

AS算法得到的最短周游路徑AS算法的收斂曲線266.1.5前沿進(jìn)展進(jìn)展概述自1991年被提出，ACO算法已經(jīng)經(jīng)過三十多年的發(fā)展，但依舊是目前求解路徑規(guī)劃、車間調(diào)度等離散優(yōu)化問題最有效的方法之一研究人員一直在探索如何更好地克服ACO算法固有的收斂速度慢、易停滯在局部最優(yōu)的缺陷提高ACO算法性能的最受關(guān)注的研究方向：改進(jìn)路徑轉(zhuǎn)移規(guī)則、信息素更新規(guī)則以及啟發(fā)信息設(shè)定規(guī)則例如，2021年，研究人員針對室內(nèi)機(jī)器人路徑規(guī)劃問題，提出了一個自適應(yīng)的蟻群優(yōu)化算法。該算法有三方面創(chuàng)新：1）采用了一種自適應(yīng)的啟發(fā)信息更新規(guī)則；2）在路徑轉(zhuǎn)移規(guī)則中，引入了障礙排除因素和角度指導(dǎo)因素；3）利用多個目標(biāo)評估下的最優(yōu)解和最壞解更新信息素。6.2粒子群優(yōu)化算法286.2.1

算法原理生物學(xué)原理自然界中，鳥群能一致地朝一個方向飛行、又突然同時轉(zhuǎn)向、分散、聚集Reynolds在1987年提出Boid模型來模擬鳥群飛行，指出了鳥類飛行的基本準(zhǔn)則：1）避免與鄰近個體碰撞；2）向個體目標(biāo)靠近；3）向群體中心聚集Boyd和Richerson在研究人類的決策過程時，發(fā)現(xiàn)人類在做決策時會綜合兩種信息，一種是根據(jù)自己的嘗試和經(jīng)歷積累的自身經(jīng)驗，另一種是了解了其他人的行為后，得到的他人經(jīng)驗296.2.1

算法原理優(yōu)化問題求解原理受到鳥類和人類等生物群體行為的啟發(fā)，1995年Kennedy和Eberhart合作提出(ParticleSwarmOptimization,PSO）算法鳥群中每個個體被抽象為沒有質(zhì)量和體積但有位置和速度的飛行粒子開始階段，每個粒子的位置和速度被隨機(jī)初始化為與解空間同維度的向量每個粒子的位置代表解空間中的一個可行解，在解空間中以一定的速度飛行，粒子的飛行過程即解的搜索過程每個粒子的優(yōu)劣根據(jù)適應(yīng)函數(shù)進(jìn)行評價，通常優(yōu)化問題的目標(biāo)函數(shù)被設(shè)置為適應(yīng)函數(shù)，每個粒子的目標(biāo)函數(shù)值稱為其適應(yīng)度在飛行中，粒子的飛行速度根據(jù)自身的飛行經(jīng)驗（即自身歷史最優(yōu)位置）和同伴的飛行經(jīng)驗（整個種群的歷史最優(yōu)位置或者一定范圍內(nèi)鄰居的最優(yōu)位置）進(jìn)行動態(tài)調(diào)整隨著粒子的飛行，粒子的位置隨之變動來尋找優(yōu)化問題的最優(yōu)解306.2.2

基本粒子群優(yōu)化算法基本粒子群優(yōu)化算法的優(yōu)化機(jī)制Kennedy和Eberhart在1995年提出了首個粒子群優(yōu)化算法，通常稱為基本PSO（BasicPSO，BPSO）算法

速度和位置更新規(guī)則：假設(shè)優(yōu)化問題的解空間為

維，粒子群中含有

個粒子，每個粒子的位置和速度在優(yōu)化過程開始時都被隨機(jī)初始化為一個

維向量。下面首先給出相關(guān)的標(biāo)記方法：

表示第個粒子的速度

表示第個粒子的位置

表示第

個粒子的個體歷史最優(yōu)位置

表示整個粒子群的最優(yōu)位置316.2.2

基本粒子群優(yōu)化算法基本粒子群優(yōu)化算法的優(yōu)化機(jī)制

第

次迭代時，第

個粒子的速度和位置的更新規(guī)則分別為：式中，和是[0,1]內(nèi)均勻分布的隨機(jī)數(shù)；和分別是粒子向個體歷史最優(yōu)位置和種群歷史最優(yōu)位置學(xué)習(xí)的因子。

（6-19）（6-20）326.2.2

基本粒子群優(yōu)化算法基本粒子群優(yōu)化算法的優(yōu)化機(jī)制

速度更新規(guī)則包括三部分：1)粒子當(dāng)前速度：粒子的運(yùn)動慣性，刻畫粒子的自我學(xué)習(xí)能力，提供粒子在解空間內(nèi)進(jìn)行搜索的源動力2）粒子的自我認(rèn)知：粒子對自身經(jīng)驗的思考和學(xué)習(xí)，刻畫粒子向自身經(jīng)驗學(xué)習(xí)的能力。它鼓勵粒子飛向自身曾經(jīng)發(fā)現(xiàn)的最優(yōu)位置，發(fā)揮著局部利用的作用3）粒子的社會認(rèn)知：粒子對社會經(jīng)驗的思考和學(xué)習(xí)，刻畫粒子向整個種群學(xué)習(xí)的能力。它鼓勵粒子飛向種群發(fā)現(xiàn)的最優(yōu)位置，體現(xiàn)了粒子間信息的共享與群體協(xié)作，發(fā)揮著全局勘探的作用336.2.2

基本粒子群優(yōu)化算法基本粒子群優(yōu)化算法的重要參數(shù)分析

最大速度：影響算法的局部利用和全局勘探的搜索平衡，太大容易

使粒子錯過優(yōu)異解，太小容易使粒子陷入局部最優(yōu)解

，通常將最大速度

設(shè)置為

具體來說，當(dāng)某粒子的速度向量

中某一維超過相應(yīng)維度的解空間邊界時，按照下式進(jìn)行設(shè)定：學(xué)習(xí)因子和：這兩個參數(shù)同樣關(guān)系著算法的局部利用和全局勘探的搜索。若學(xué)習(xí)因子過小，容易引起粒子在最優(yōu)解附近徘徊；而若學(xué)習(xí)因子過大，容易導(dǎo)致粒子錯過最優(yōu)解。（6-21）346.2.2

基本粒子群優(yōu)化算法基本粒子群優(yōu)化算法的實現(xiàn)過程

356.2.3

標(biāo)準(zhǔn)粒子群優(yōu)化算法標(biāo)準(zhǔn)粒子群優(yōu)化算法的優(yōu)化機(jī)制

SPSO算法有易陷入局部最優(yōu)的缺陷1998年，Shi和Eberhart提出基于慣性權(quán)重（InetiaWeight）的粒子群優(yōu)化算法之后，PSO的研究大多以帶有慣性權(quán)重的PSO算法為對象進(jìn)行分析、擴(kuò)展和應(yīng)用，因此通常將其稱為標(biāo)準(zhǔn)PSO（StandardPSO，SPSO）算法在第

次迭代時，第

個粒子的速度和位置的更新公式分別為：

（6-23）（6-24）366.2.3

標(biāo)準(zhǔn)粒子群優(yōu)化算法標(biāo)準(zhǔn)粒子群優(yōu)化算法的重要參數(shù)分析

與BPSO相比，SPSO引入了一個新參數(shù)——慣性權(quán)重

，減弱了最大速度

對算法性能的影響，可以更好地平衡算法的全局勘探和局部利用的能力較大的慣性權(quán)重有利于提高種群的多樣性，幫助增強(qiáng)全局勘探能力；較小的慣性權(quán)重有利于提高算法的局部利用能力，幫助加快算法的收斂速度粒子飛行軌跡示意圖376.2.3

標(biāo)準(zhǔn)粒子群優(yōu)化算法標(biāo)準(zhǔn)粒子群優(yōu)化算法的重要參數(shù)分析

下面給出三種常見的慣性權(quán)重設(shè)置方法：1）常數(shù)權(quán)重：

，其中

表示一個常數(shù)2）隨機(jī)權(quán)重：3）基于迭代次數(shù)的慣性遞減權(quán)重：式中，表示當(dāng)前迭代次數(shù)；表示最大迭代次數(shù)；表示最大慣性權(quán)重；

表示最小慣性權(quán)重386.2.4

多目標(biāo)粒子群優(yōu)化算法多目標(biāo)優(yōu)化相關(guān)概念

緒論中給出了多目標(biāo)優(yōu)化的一般數(shù)學(xué)模型定義定義6.1

可行解：對于某個

，如果

滿足式（1-15）中給出的

個不等式約束、式（1-16）中給出的

個等式約束以及式（1-17）中給出的邊界約束，則稱

為多目標(biāo)優(yōu)化問題的一個可行解。定義6.2

可行解集合：所有可行解組成的集合稱為可行解集，記為

（1-14）（1-15）（1-16）（1-17）396.2.4

多目標(biāo)粒子群優(yōu)化算法多目標(biāo)優(yōu)化相關(guān)概念

定義6.3帕累托（Pareto）占優(yōu)：和是多目標(biāo)優(yōu)化問題的兩個可行解，稱帕累托占優(yōu)或支配，若滿足如下條件：

與的這種帕累托占優(yōu)關(guān)系通常記作，其中稱為帕累托占優(yōu)解或非支配解（6-26）406.2.4

多目標(biāo)粒子群優(yōu)化算法多目標(biāo)優(yōu)化相關(guān)概念

定義6.4

Pareto最優(yōu)解：一個可行解

被稱為Pareto最優(yōu)解(ParetoOptimalSolution)，當(dāng)且僅當(dāng)它滿足如下條件：定義6.5Pareto最優(yōu)解集：所有Pareto最優(yōu)解的集合稱為Pareto最優(yōu)解集(ParetoOptimalSolutionSet，PS)，定義如下：定義6.6Pareto前沿面：

Pareto最優(yōu)解集

中所有Pareto最優(yōu)解對應(yīng)的目標(biāo)向量組成的曲面稱為Pareto前沿面（ParetoFront，PF），其定義如下：（6-27）（6-28）（6-29）416.2.4

多目標(biāo)粒子群優(yōu)化算法多目標(biāo)粒子群優(yōu)化算法的優(yōu)化機(jī)制

Cello等學(xué)者在2004年將其拓展到求解多目標(biāo)連續(xù)優(yōu)化問題上，提出了經(jīng)典的多目標(biāo)粒子群優(yōu)化(Multi-objectiveParticleSwarmOptimization，MOPSO)算法多目標(biāo)優(yōu)化問題求解的目標(biāo)是一個分布均勻的Pareto最優(yōu)解集MOPSO利用Pareto支配關(guān)系來評價粒子之間的優(yōu)劣MOPSO根據(jù)每個粒子的個體歷史最優(yōu)位置和種群歷史最優(yōu)位置進(jìn)行速度和位置的更新MOPSO使用一個基于自適應(yīng)網(wǎng)格的外部存檔集來保存每次迭代中發(fā)現(xiàn)的非支配解，并利用一個變異策略引入隨機(jī)擾動來避免算法陷入局部最優(yōu)426.2.4

多目標(biāo)粒子群優(yōu)化算法多目標(biāo)粒子群優(yōu)化算法的速度和位置更新機(jī)制

MOPSO算法的速度和位置更新公式和SPSO算法的速度和位置更新公式一樣，如式（6-22）和式（6-23）所示不過，由于多目標(biāo)優(yōu)化問題不存在唯一的最優(yōu)解，MOPSO算法中個體歷史最優(yōu)位置和整個種群的歷史最優(yōu)位置的確定方法有所不同個體歷史最優(yōu)位置：若粒子的當(dāng)前位置支配它的個體歷史最優(yōu)位置，則用粒子的當(dāng)前位置來更新它的個體歷史最優(yōu)位置若粒子的當(dāng)前位置被它的歷史最優(yōu)位置支配，則粒子的個體歷史最優(yōu)位置不變?nèi)袅Ｗ拥漠?dāng)前位置和其個體歷史最優(yōu)位置互不支配，則從二者中隨機(jī)選擇一個作為粒子的個體歷史最優(yōu)位置436.2.4

多目標(biāo)粒子群優(yōu)化算法多目標(biāo)粒子群優(yōu)化算法的速度和位置更新機(jī)制

種群歷史最優(yōu)位置：為了保證搜索的均勻性，MOPSO算法會對目標(biāo)空間進(jìn)行網(wǎng)格劃分，并根據(jù)下述方法選擇種群歷史最優(yōu)位置：首先設(shè)定一個大于1的固定數(shù)值

，使用該固定數(shù)值除以個體所屬小超立方體內(nèi)含有非支配解的數(shù)量然后以此為依據(jù)，根據(jù)輪盤賭原則選定一個小超立方體，并從中隨機(jī)選擇一個粒子的位置作為種群歷史最優(yōu)位置446.2.4

多目標(biāo)粒子群優(yōu)化算法基于自適應(yīng)網(wǎng)格的外部存檔集

MOPSO算法采用外部存檔集來保存每次迭代中發(fā)現(xiàn)的非支配解，而外部存檔集采用自適應(yīng)網(wǎng)格策略來維護(hù)非支配解的多樣性。基于自適應(yīng)網(wǎng)格的外部存檔集建立：外部存檔集中非支配解集記為AP，目標(biāo)空間中每個維度上網(wǎng)格的劃分?jǐn)?shù)為

，根據(jù)

對外部存檔集所在的目標(biāo)空間進(jìn)行網(wǎng)格劃分網(wǎng)格在第

個維度上的下邊界和上邊界的計算方法分別為式中，和

分別表示外部存檔集中所有非支配集在第

個維度上的最小值和最大值（6-30）（6-31）456.2.4

多目標(biāo)粒子群優(yōu)化算法基于自適應(yīng)網(wǎng)格的外部存檔集

基于自適應(yīng)網(wǎng)格的外部存檔集建立：第

個維度上小超立方體的寬度

的計算方法如下式所示：（6-32）第

個目標(biāo)維度上的網(wǎng)格設(shè)置466.2.4

多目標(biāo)粒子群優(yōu)化算法基于自適應(yīng)網(wǎng)格的外部存檔集

基于自適應(yīng)網(wǎng)格的外部存檔集建立：當(dāng)對外部存檔集所在的目標(biāo)空間的所有維度都進(jìn)行上述網(wǎng)格設(shè)置后，外部存檔集的網(wǎng)格就建立好了，每個網(wǎng)格小區(qū)域稱為一個小超立方體每個小超立方體內(nèi)含有的非支配解的數(shù)量稱為小超立方體的密度在劃分好的網(wǎng)格空間內(nèi)，每個非支配解都擁有自己的網(wǎng)格坐標(biāo)，計算方法如式（6-33）所示：式中，表示非支配解在第個目標(biāo)上的網(wǎng)格坐標(biāo)；表示非支配解在第個目標(biāo)上的函數(shù)值；表示向下取整函數(shù)。當(dāng)某個即將進(jìn)入外部存檔集中的新非支配解在目標(biāo)空間的某個維度上超出網(wǎng)格空間的邊界，需重新劃分網(wǎng)格。（6-33）476.2.4

多目標(biāo)粒子群優(yōu)化算法基于自適應(yīng)網(wǎng)格的外部存檔集更新

外部存檔集是一個保留每次迭代中發(fā)現(xiàn)的非支配個體的精英留存機(jī)制，對其進(jìn)行合理更新能夠有效地指導(dǎo)整個種群的進(jìn)化外部存檔集更新示意圖486.2.4

多目標(biāo)粒子群優(yōu)化算法基于自適應(yīng)網(wǎng)格的外部存檔集更新

基于自適應(yīng)網(wǎng)格的外部存檔集的更新可以分為如下五種情況：1）當(dāng)外部存檔集為空時，則直接接受新的非支配解，如（a）所示2）當(dāng)新非支配解被外部存檔集中的某些解支配時，則不允許新非支配解進(jìn)入外部存檔集，如（b）所示3）當(dāng)新支配解與外部存檔集中所有解都互不支配時，則接受新非支配解進(jìn)入外部存檔集，并計算其網(wǎng)格坐標(biāo)，進(jìn)入相應(yīng)小超立方體，如（c）所示4）當(dāng)新非支配解支配外部存檔集中某些解時，則接受非新支配解，計算其網(wǎng)格坐標(biāo)，進(jìn)入相應(yīng)小超立方體，并將外部存檔集中被其支配的解刪除，如（e）所示5）當(dāng)外部存檔集中的非支配解數(shù)量已達(dá)到額定數(shù)量，并且新非支配解與外部存檔集中所有解互不支配時，則隨機(jī)刪除密度最大的小超立方體內(nèi)的非支配解，如（e）所示496.2.4

多目標(biāo)粒子群優(yōu)化算法變異策略

引入隨機(jī)擾動，能有效地避免種群陷入局部最優(yōu)，具體實現(xiàn)過程如下：1）

首先根據(jù)設(shè)定的變異率

計算當(dāng)前迭代的擾亂因子

：2）然后依據(jù)變異率

決定粒子是否執(zhí)行變異策略。若粒子需要執(zhí)行變異策略，則隨機(jī)生成[0,1]內(nèi)的一個隨機(jī)數(shù)，若該隨機(jī)數(shù)大于擾亂因子

，則粒子的位置保持不變，否則隨機(jī)選出粒子的某個決策變量

，并按照下式計算其變異范圍：

其中，和分別表示決策變量的取值上界和取值下界。3）最后粒子的決策變量

通過在

內(nèi)進(jìn)行隨機(jī)取值來完成變異。（6-34）（6-35）506.2.4

多目標(biāo)粒子群優(yōu)化算法多目標(biāo)粒子群優(yōu)化算法的流程

516.2.5

典型問題求解案例例題

例題6-2

利用PSO算法求解經(jīng)典的二維Rosenbrock函數(shù)優(yōu)化問題：二維Rosenbrock函數(shù)的全局曲面：最優(yōu)解為：最優(yōu)目標(biāo)函數(shù)值為：

二維Rosenbrock函數(shù)的全局曲面：526.2.5

典型問題求解案例求解過程

編寫Matlab主程序main.m如下：c1=2;%自我認(rèn)知學(xué)習(xí)因子c2=2;%社會認(rèn)知學(xué)習(xí)因子w=1;%慣性權(quán)重vmax=30;%最大飛行速度popSize=50;%種群規(guī)模gen=150;%最大迭代次數(shù)dim=2;%決策變量數(shù)量%設(shè)置Rosenbrock函數(shù)優(yōu)化任務(wù)Task.dims=dim;Task.fnc=@(x)Rosenbrock(x);Task.Lb=-30*ones(1,n);Task.Ub=30*ones(1,n);[Convergence_curve,gBest,gBestfit]=PSO(Task,popSize,gen,Lb,Ub,c1,c2,w,vmax);%利用PSO算法求解draw(Convergence_curve,gBest,gBestfit);%繪制收斂曲線536.2.5

典型問題求解案例求解過程

BPSO的收斂曲線

SPSO的收斂曲線（）

BPSO找到的最優(yōu)解為：最優(yōu)目標(biāo)函數(shù)值為：

SPSO找到的最優(yōu)解為：最優(yōu)目標(biāo)函數(shù)值為：

546.2.5

典型問題求解案例例題

例題6-3利用MOPSO算法求解如下經(jīng)典的三目標(biāo)DTLZ2函數(shù)優(yōu)化問題：式中，，，且，，碼6-1【代碼解析】MOPSO的求解代碼556.2.6前沿進(jìn)展進(jìn)展概述PSO算法是首個用于求解單目標(biāo)連續(xù)優(yōu)化問題的群智能優(yōu)化算法PSO算法具有原理簡單、參數(shù)少、收斂速度快等優(yōu)勢，已經(jīng)被廣泛應(yīng)用于各個領(lǐng)域中，是迄今為止最成功的群智能優(yōu)化算法之一自1995年提出之后的近三十年間，為了更好地求解各種優(yōu)化問題，研究人員一直對PSO算法進(jìn)行持續(xù)的研究和探索PSO近年來在不同類型的復(fù)雜多目標(biāo)優(yōu)化問題求解上備受青睞：1）

2023年，文獻(xiàn)[39]提出帶有自調(diào)整策略的多模態(tài)多目標(biāo)粒子群優(yōu)化算法2）

2024年，文獻(xiàn)[46]提出數(shù)據(jù)驅(qū)動的魯棒多模態(tài)多目標(biāo)粒子群優(yōu)化算法3）

2023年，文獻(xiàn)[47]提出基于種群合作的大規(guī)模多目標(biāo)粒子群優(yōu)化算法4）

2024年，文獻(xiàn)[49]提出基于柔性排序的大規(guī)模多目標(biāo)粒子群優(yōu)化算法5）

2023年，文獻(xiàn)[50]提出基于網(wǎng)格分類代理輔助的昂貴多目標(biāo)粒子群優(yōu)化算法566.2.6前沿進(jìn)展進(jìn)展概述PSO的衍生算法：例如，2023年文獻(xiàn)[45]提出了一個基于隨機(jī)對比連接策略的粒子群優(yōu)化算法在每次迭代，首先為每個粒子隨機(jī)選擇

一些其它粒子組成一個隨機(jī)拓?fù)浣Y(jié)構(gòu)然后，確定比每個粒子優(yōu)異的的支配粒子最后，當(dāng)粒子的支配粒子數(shù)量大于2時，利用其最好支配者和最差支配者進(jìn)行速度和位置更新：式中，

和

分別表示粒子

的最好、最壞支配粒子；

、

和

都是

區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)；

是一個控制參數(shù)，關(guān)系著粒子

向最壞支配粒子

學(xué)習(xí)的程度6.3細(xì)菌覓食優(yōu)化算法主要內(nèi)容CONTENTS6.3.1

算法原理細(xì)菌覓食優(yōu)化(BacterialForagingOptimization,BFO)是2002年提出的一種新型的群智能優(yōu)化算法58基本原理人體腸道內(nèi)大腸桿菌在覓食過程中體現(xiàn)出的智能行為生物學(xué)家的研究表明，菌群覓食營養(yǎng)是通過菌群個體間的相互競爭與協(xié)作共同完成的，其過程主要由趨向、聚集、繁殖、遷徙四種機(jī)制完成將細(xì)菌個體隨機(jī)初始化為

維空間的一個

維向量，表示細(xì)菌所在的位置細(xì)菌的適應(yīng)度與優(yōu)化問題的目標(biāo)函數(shù)值有關(guān)，表示相應(yīng)位置的營養(yǎng)豐富程度執(zhí)行三重嵌套循環(huán)完成優(yōu)化過程：趨向循環(huán)、復(fù)制循環(huán)、遷徙循環(huán)主要內(nèi)容CONTENTS6.3.2

算法描述趨向機(jī)制59細(xì)菌向營養(yǎng)豐富的區(qū)域移動的行為稱為趨向機(jī)制，通過翻轉(zhuǎn)和游泳兩種運(yùn)動實現(xiàn)翻轉(zhuǎn)：變換尋優(yōu)方向的行為游泳：沿著一個方向移動的行為，實現(xiàn)公式為：移動后新解當(dāng)前解移動方向表示第個細(xì)菌在第次趨向、第次復(fù)制、第次遷徙操作時的位置

表示移動步長

表示

維隨機(jī)向量翻轉(zhuǎn)游泳主要內(nèi)容細(xì)菌會首先執(zhí)行翻轉(zhuǎn)運(yùn)動，然后比較移動前后所在區(qū)域內(nèi)營養(yǎng)的豐富程度。如果移動后所在區(qū)域的營養(yǎng)更加豐富，細(xì)菌會繼續(xù)沿著該方向移動，直到營養(yǎng)變得匱乏或者已經(jīng)在同一方向上移動了足夠多的步數(shù)為止CONTENTS6.3.2

算法描述趨向機(jī)制60具體過程：細(xì)菌首先執(zhí)行翻轉(zhuǎn)運(yùn)動，然后比較移動前后所在區(qū)域內(nèi)營養(yǎng)的豐富程度。如果移動后所在區(qū)域的營養(yǎng)更加豐富，細(xì)菌會繼續(xù)沿著該方向移動，直到營養(yǎng)變得匱乏或者已經(jīng)在同一方向上移動了足夠多的步數(shù)為止主要內(nèi)容細(xì)菌會首先執(zhí)行翻轉(zhuǎn)運(yùn)動，然后比較移動前后所在區(qū)域內(nèi)營養(yǎng)的豐富程度。如果移動后所在區(qū)域的營養(yǎng)更加豐富，細(xì)菌會繼續(xù)沿著該方向移動，直到營養(yǎng)變得匱乏或者已經(jīng)在同一方向上移動了足夠多的步數(shù)為止CONTENTS6.3.2

算法描述聚集機(jī)制61細(xì)菌覓食過程中，會收到其它個體發(fā)出的吸引信號和排斥信號。吸引信號引誘細(xì)菌個體游向群體中心，排斥信號保證細(xì)菌個體之間保持在一定的安全距離之內(nèi)。細(xì)菌個體之間這種吸引和排斥的相互作用通過下式計算：

表示種群中所有其它細(xì)菌對細(xì)菌

的吸引力和排斥力的合力；

表示所有細(xì)菌個體在第

次趨向、第

次復(fù)制，第

次遷徙操作時的位置集合細(xì)菌個數(shù)吸引力擴(kuò)散率吸引力釋放量排斥力釋放量排斥力擴(kuò)散率BFO中一個可選機(jī)制

無聚集機(jī)制適應(yīng)度為

有聚集機(jī)制適應(yīng)度為主要內(nèi)容細(xì)菌會首先執(zhí)行翻轉(zhuǎn)運(yùn)動，然后比較移動前后所在區(qū)域內(nèi)營養(yǎng)的豐富程度。如果移動后所在區(qū)域的營養(yǎng)更加豐富，細(xì)菌會繼續(xù)沿著該方向移動，直到營養(yǎng)變得匱乏或者已經(jīng)在同一方向上移動了足夠多的步數(shù)為止CONTENTS6.3.2

算法描述復(fù)制機(jī)制62隨著營養(yǎng)的吸收，細(xì)菌會逐漸變長。在適當(dāng)?shù)臏囟葪l件下，吸收充足營養(yǎng)的細(xì)菌個體會對自身進(jìn)行復(fù)制，即每個細(xì)菌個體分裂為兩個完全相同的細(xì)菌個體，而營養(yǎng)匱乏的細(xì)菌個體會消亡具體過程：每經(jīng)過

次趨向操作，菌群發(fā)生一次復(fù)制過程。一半數(shù)量的健康度高的細(xì)菌進(jìn)行自我復(fù)制，另一半數(shù)量的細(xì)菌死亡健康度定義：次趨向操作目標(biāo)函數(shù)值總和主要內(nèi)容細(xì)菌會首先執(zhí)行翻轉(zhuǎn)運(yùn)動，然后比較移動前后所在區(qū)域內(nèi)營養(yǎng)的豐富程度。如果移動后所在區(qū)域的營養(yǎng)更加豐富，細(xì)菌會繼續(xù)沿著該方向移動，直到營養(yǎng)變得匱乏或者已經(jīng)在同一方向上移動了足夠多的步數(shù)為止CONTENTS6.3.2

算法描述遷徙機(jī)制63菌群生活的環(huán)境發(fā)生劇烈變化后，有的個體可能會遷移到新環(huán)境中去尋找營養(yǎng)物質(zhì)具體過程：菌群每完成

次復(fù)制操作，發(fā)生一次遷徙過程。細(xì)菌個體執(zhí)行遷徙過程的規(guī)則如下：預(yù)設(shè)的遷徙概率隨機(jī)產(chǎn)生的新個體主要內(nèi)容細(xì)菌會首先執(zhí)行翻轉(zhuǎn)運(yùn)動，然后比較移動前后所在區(qū)域內(nèi)營養(yǎng)的豐富程度。如果移動后所在區(qū)域的營養(yǎng)更加豐富，細(xì)菌會繼續(xù)沿著該方向移動，直到營養(yǎng)變得匱乏或者已經(jīng)在同一方向上移動了足夠多的步數(shù)為止CONTENTS6.3.2

算法描述BFO實現(xiàn)過程64656.3.3

典型問題求解案例例題

例題6-4利用BFO算法求解經(jīng)典的二維Sphere函數(shù)優(yōu)化問題：二維Sphere函數(shù)的全局曲面：最優(yōu)解為：最優(yōu)目標(biāo)函數(shù)值為：

666.3.3

典型問題求解案例求解過程

編寫Matlab主程序main.m如下：%設(shè)置任務(wù)n=2;Task3.dims=n;Task.fnc=@(x)Sphere(x);Task.Lb=-100*ones(1,n);Task.Ub=100*ones(1,n);%設(shè)置算法參數(shù)Nc=100;%趨向次數(shù)Ns=4;%游泳次數(shù)Nre=4;%復(fù)制次數(shù)Sr=S/2;%每一代細(xì)菌復(fù)制數(shù)量draw(Convergence_curve,gBest,gBestfit);%繪制收斂曲線Ned=2;%驅(qū)散次數(shù)ped=0.25;%遷徙概率flag=0;%flag==0,沒有吸引力和排斥力作用；flag==1,有吸引力和排斥力作用[best_solution,best_fitness,fitness_iter]=BFO(Task,popSize,Nc,Ns,Nre,Sr,Ned,Ped,flag);%調(diào)用BFOdraw(best_solution,best_fitness,fitness_iter);%繪制收斂曲線676.3.3

典型問題求解案例求解過程

BFO的收斂曲線(無相互作用)

BFO的收斂曲線（有相互作用）

最優(yōu)解為：最優(yōu)目標(biāo)函數(shù)值為：

最優(yōu)解為：最優(yōu)目標(biāo)函數(shù)值為：

686.3.4前沿進(jìn)展進(jìn)展概述BFO算法自2002年被提出到如今二十余年時間內(nèi)，研究人員圍繞著算法改進(jìn)和算法應(yīng)用進(jìn)行了廣泛的研究和探索，使BFO算法逐漸成為一種流行的群智能優(yōu)化方法BFO的前沿應(yīng)用

：1）

2017年，文獻(xiàn)[57]拓展BFO算法用于蛋白質(zhì)網(wǎng)絡(luò)功能模塊檢測2）2018年，文獻(xiàn)[58]將BFO算法用于預(yù)測軀體化障礙的嚴(yán)重程度3）

2021年，文獻(xiàn)[59]將BFO算法用于機(jī)器人的運(yùn)動規(guī)劃4）

2023年，文獻(xiàn)[60]將BFO算法用于視頻隱寫領(lǐng)域5）

2024年，文獻(xiàn)[61]使用BFO算法進(jìn)行青光眼眼底圖像的特征選擇696.3.4前沿進(jìn)展進(jìn)展概述BFO的衍生算法BFO存在兩大缺陷：一是細(xì)菌在整個搜索過程中使用了固定的游泳步長，這制約了算法平衡局部利用和全局勘探的能力。二是算法中細(xì)菌個體之間的信息交流能力比較弱，不利于算法收斂。國內(nèi)外學(xué)者紛紛通過不同的方法與技術(shù)彌補(bǔ)上述不足，提出了不少衍生算法例如，

2016年，文獻(xiàn)[54]模擬了細(xì)菌生物的接合行為作為新信息交流機(jī)制，并且提出了一種非均勻自適應(yīng)步長：式中，是[0,1]區(qū)間內(nèi)一個均勻分布的隨機(jī)數(shù)；是算法要執(zhí)行的趨向操作總數(shù)；是細(xì)菌游泳步長變化程度的控制參數(shù)；

是算法當(dāng)前發(fā)現(xiàn)的全局最優(yōu)解；

是細(xì)菌

已經(jīng)執(zhí)行的趨向機(jī)制次數(shù)6.4浣熊優(yōu)化算法主要內(nèi)容CONTENTS6.4.1

算法原理浣熊優(yōu)化算法（CoatiOptimizationAlgorithm，COA）是Dehghani等人在2023年提出的一種求解單目標(biāo)連續(xù)優(yōu)化問題的新型群智能優(yōu)化算法71基本原理COA模擬了長鼻浣熊捕食綠鬣蜥和逃離被其它生物捕食的兩種自然行為長鼻浣熊經(jīng)常需要爬上樹去捕捉它最喜歡的食物之一——綠鬣蜥長鼻浣熊群的捕捉策略為：一部分長鼻浣熊爬上樹，把綠鬣蜥嚇到地上，另一部分在地上的長鼻浣熊迅速攻擊綠鬣蜥長鼻浣熊在捕食綠鬣蜥的過程中，同時有被其它動物捕捉的危險。為了避免被捕食，長鼻浣熊會迅速逃離當(dāng)前位置，并在其附近選擇安全的隱身地點主要