(最新)智能優(yōu)化算法簡(jiǎn)介課件

1、 智能優(yōu)化算法智能優(yōu)化算法簡(jiǎn)介遺傳算法簡(jiǎn)介基本遺傳算法改進(jìn)的遺傳算法遺傳算法軟件計(jì)算7.1遺傳算法1智能優(yōu)化算法簡(jiǎn)介一、 傳統(tǒng)優(yōu)化算法的步驟及局限性 1 步驟： （1）選擇一個(gè)初始解， （2）向改進(jìn)方向移動(dòng)判斷停止準(zhǔn)則是否滿足，若 滿足停止，否則轉(zhuǎn)下一步。 （3）向改進(jìn)方向移動(dòng)，得新的解，轉(zhuǎn)回第2步。 2 局限性： （1）單點(diǎn)運(yùn)算方式限制了計(jì)算效率的提高 （2）向改進(jìn)方向移動(dòng)限制了跳出局部最優(yōu)的能力 （3）停止條件僅是局部最優(yōu)的條件 （4）對(duì)目標(biāo)函數(shù)，約束條件的要求限制了算法的應(yīng)用2智能優(yōu)化算法簡(jiǎn)介 二、智能優(yōu)化算法的產(chǎn)生與發(fā)展 1 最優(yōu)化方法的新的需求 （1）對(duì)目標(biāo)函數(shù)，約束函數(shù)的要求更為寬

2、松 （2）計(jì)算效率比理論上的最優(yōu)性更重要 （3）算法隨時(shí)終止都能得到較好的解 （4）對(duì)優(yōu)化模型中數(shù)據(jù)質(zhì)量要求更加寬松。 2 智能算法及代表人物 1975年，Holland提出遺傳算法(Genetic Algorithms) 1977年，Glover提出禁忌算法(Tabu Search) 1983年，Kirkpatrick提出模擬退火算法 （Simulated Annealing） 90年代初，Dorigo提出蟻群算法 (Ant Colony Optimization) 1995年，Kennedy,Eberhart提出的粒子群算法(Particle Swarm) 1999年，Linhares 提

3、出的捕食搜索(Predatory Search) 3智能優(yōu)化算法簡(jiǎn)介三、如何學(xué)習(xí)研究智能優(yōu)化算法 1 應(yīng)用智能優(yōu)化方法解決各類問(wèn)題是重點(diǎn) 2 智能算法的改進(jìn)有很大的空間 3 多種算法結(jié)合是一種很好的途徑 4 不提倡刻意追求理論成果 5 算法性能的測(cè)試是一項(xiàng)要下真功夫的工作 6 創(chuàng)造出新算法 4遺傳算法簡(jiǎn)介 一、遺傳算法原理（ 7.1.1） 遺傳算法是根據(jù)問(wèn)題的目標(biāo)函數(shù)構(gòu)造的 一個(gè)適值函數(shù)，對(duì)一個(gè)由多個(gè)解（每個(gè)解對(duì) 應(yīng)一個(gè)染色體）構(gòu)成的種群進(jìn)行評(píng)估、遺傳 運(yùn)算、經(jīng)多代繁殖，獲得適應(yīng)值最好的個(gè)體 作為問(wèn)題的最優(yōu)解。 5遺傳算法簡(jiǎn)介 二、遺傳算法技術(shù)問(wèn)題（7.1.2）遺傳算法的主要問(wèn)題是算法如何實(shí)現(xiàn)

4、的技術(shù)問(wèn)題。歸結(jié)起來(lái)有如下一些因素： 1 解的編碼和解碼 解的編碼是遺傳算法的最基礎(chǔ)工作，只有在編碼之后才可能有其他的計(jì)算。算法的 最后一個(gè)工作則是通過(guò)解碼得到問(wèn)題的一個(gè)解。 2 初始群體的選取 在計(jì)算開(kāi)始時(shí)，需要產(chǎn)生一些待優(yōu)化問(wèn)題的可能解，稱為初始群體，初始群體可用 隨機(jī)方式產(chǎn)生，也可用用其他的一下啟發(fā)式算法或經(jīng)驗(yàn)選擇，主要針對(duì)實(shí)際問(wèn)題而定。 3 群體規(guī)模的確定， 常取個(gè)體編碼長(zhǎng)度數(shù)的一個(gè)線性倍數(shù)。當(dāng)多個(gè)進(jìn)化代沒(méi)有改變解的性能，可擴(kuò)大群體的規(guī)模。若解的改進(jìn)已經(jīng)非常好時(shí)，就可以減少群體規(guī)模，使計(jì)算速度加快。 4 適應(yīng)函數(shù)的確定 簡(jiǎn)單適應(yīng)函數(shù) 目標(biāo)函數(shù)的簡(jiǎn)單變形，構(gòu)造簡(jiǎn)單，與目標(biāo)函數(shù)直接相關(guān)，缺

5、點(diǎn)是可能使算法在迭代過(guò)程中出現(xiàn)收斂到一些目標(biāo)值近似的不同染色體而難以區(qū)別。 加速適應(yīng)函數(shù) 有非線性加速適應(yīng)函數(shù)，線性加速適應(yīng)函數(shù)等。它們的思想是希望開(kāi)始時(shí)每一個(gè)狀態(tài)有較大的選取性，隨著計(jì)算的步步進(jìn)行，逐漸拉開(kāi)目標(biāo)值不同對(duì)應(yīng)狀態(tài)的檔次。 排序適應(yīng)函數(shù) 為了避開(kāi)對(duì)目標(biāo)函數(shù)進(jìn)行線性、非線性等加速適應(yīng)函數(shù)的早熟可能，使每一代當(dāng)前最好的解以最大的概率遺傳。6遺傳算法簡(jiǎn)介三、遺傳算法特點(diǎn) 1 特點(diǎn) （1）遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象。 （2）遺傳算法直接以適應(yīng)度作為搜索信息，無(wú)需導(dǎo)數(shù)等其它輔助信息。 （3）遺傳算法使用多個(gè)點(diǎn)的搜索信息，具有隱含并行性。 （4）遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)

6、則。 2 應(yīng)用領(lǐng)域 （1）函數(shù)優(yōu)化 （2）組合優(yōu)化 （3）生產(chǎn)調(diào)度 （4）自動(dòng)控制 （5） 機(jī)器人學(xué) （6）圖象處理 7基本遺傳算法(7.1.3) 一、 基本遺傳算法的構(gòu)成要素 1 染色體編碼方法。 2 個(gè)體適應(yīng)度評(píng)價(jià)。 3 遺傳算子。基本遺傳算法使用下述三種遺傳算子 選擇運(yùn)算使用比例選擇算子； 交叉運(yùn)算使用單點(diǎn)交叉算子； 變異運(yùn)算使用基本位變異算子或均勻變異算子。 4 基本遺傳算法的運(yùn)行參數(shù)?；具z傳算法有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定： M：群體大小，即群體中所合個(gè)體的數(shù)量，一般取為201000。 T：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取為l00一500。 Pc: 交叉概率，般取為0.4一0.99

7、。 Pm: 變異概率，一般取為0.0001一0.1.8基本遺傳算法(7.1.3)二 、基本遺傳算法描述 1 基本遺傳算法的形式化定義基本遺傳算法可定義為一個(gè)8元組，這些參數(shù)合理的取值大小或取值范圍。9基本遺傳算法(7.1.3)二 、基本遺傳算法描述 2 遺傳算法的基本操作舉例 （1）產(chǎn)生 初始種群 括號(hào)中的數(shù)值為目標(biāo)函數(shù)值10基本遺傳算法(7.1.3) 2 遺傳算法的基本操作舉例（2）遺傳運(yùn)算 選擇運(yùn)算（輪盤(pán)賭） 11基本遺傳算法(7.1.3) 2 遺傳算法的基本操作舉例（2）遺傳運(yùn)算 選擇運(yùn)算（輪盤(pán)賭）由計(jì)算機(jī)產(chǎn)生隨機(jī)數(shù)來(lái)實(shí)現(xiàn) 假設(shè)產(chǎn)生隨機(jī)數(shù)序列為0.070221，0.545929，0.78

8、4567，0.44693，0.507893，0.291198，0.71634，0.27290l，0.37l 435，0.854641。將該隨機(jī)序列與計(jì)算獲得的累積概率比較，則依次序號(hào)為1，8，9，6，7，5，8，4，6，10個(gè)體被選中。顯然適應(yīng)度高的個(gè)體被選中的概率大。而且可能被選中；而適應(yīng)度低的個(gè)體則很有可能破淘汰。在第一次生存競(jìng)爭(zhēng)考驗(yàn)中，序號(hào)為2的個(gè)體(0101111001)和3的個(gè)體(0000000101)被淘汰，代之以適應(yīng)度較高的個(gè)體8和6。12基本遺傳算法(7.1.3) 2 遺傳算法的基本操作舉例（2）遺傳運(yùn)算 交叉運(yùn)算 以單點(diǎn)交叉為例，任意挑選經(jīng)過(guò)選擇操作后種群中兩個(gè)個(gè)體作為交叉對(duì)

9、象，即兩個(gè)父?jìng)€(gè)體經(jīng)過(guò)染色體交換重組產(chǎn)生兩個(gè)子個(gè)體，如下圖，隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)位置，父?jìng)€(gè)體l和父?jìng)€(gè)體2在交叉點(diǎn)位置之有的部分基因碼互換，形成子個(gè)體1和子個(gè)體2。類似地完成其他個(gè)體的交叉操作13基本遺傳算法(7.1.3) 2 遺傳算法的基本操作舉例（2）遺傳運(yùn)算 變異算子 如圖所示采用翻轉(zhuǎn)，對(duì)于個(gè)體1001110100產(chǎn)生變異， 以小概率決定第4個(gè)遺傳因子翻轉(zhuǎn)，即將1換為0。14遺傳算法的進(jìn)化過(guò)程15大變異遺傳算法(7.1.4) 一、 大變異遺傳原理 在遺傳算法中，變異操作可以使算法避免“早熟”。但是，為了保證算法的穩(wěn)定性，變異操作的變異概率通常取值很小，所以算法一旦出現(xiàn)“早熟”，單靠傳統(tǒng)的變異操

10、作需很多代才能得到不同于其他個(gè)體的新個(gè)體。 大變異操作的思路是：當(dāng)某代中所有個(gè)體集中在一起時(shí)，我們以一個(gè)遠(yuǎn)大于通常的變異概率的概率進(jìn)行變異操作，它能夠產(chǎn)生多個(gè)新個(gè)體，從而使得種群脫離”早熟”。16大變異遺傳算法(7.1.4) 一、 大變異遺傳算法的原理當(dāng)某一代的最大適應(yīng)度 與平均適應(yīng)度 滿足 其中 ，被稱為密集因子，表征個(gè)體集中的程度。大變異操作要求有兩個(gè)參數(shù)是： 密集因子和大變異概率。密集因子用來(lái)決定大變異操作在整個(gè)優(yōu)化過(guò)程中所占的比重，其數(shù)值越接近0.5時(shí)大變異操作被調(diào)用的越頻繁。大變異概率越大，含大變異操作的遺傳算法的穩(wěn)定性就越好，但是，這是以犧牲收斂速度為代價(jià)的，當(dāng)其數(shù)值等于0.5時(shí)，

11、大變異操作就近似為隨機(jī)搜索。17大變異遺傳算法(7.1.4) 二、 大變異遺傳算法的步驟 1 隨機(jī)產(chǎn)生初始種群，種群個(gè)體數(shù)目事先給定，每個(gè)個(gè)體表示為染色體的基因編碼； 2計(jì)算個(gè)體的適應(yīng)度，并判斷是否符合優(yōu)化準(zhǔn)則，若符合，輸出最佳個(gè)體及其代表的最優(yōu)解，并結(jié)束計(jì)算，否則轉(zhuǎn)3； 3依據(jù)適應(yīng)度選擇再生個(gè)體，適應(yīng)的高的個(gè)體被選中的概率高，適應(yīng)的低的個(gè)體可能被淘汰； 4對(duì)選擇出再生個(gè)體按一定的交叉概率和交叉方法生成新個(gè)體； 5如果當(dāng)代最大適應(yīng)度與平均適應(yīng)度滿足時(shí)，進(jìn)行大變異操作，否則進(jìn)行普通變異操作。 6 由交叉和變異產(chǎn)生新一代的種群，返回2。18自適應(yīng)遺傳算法(7.1.5) 一、 自適應(yīng)遺傳算法的原理

12、Srinvivas等提出一種自適應(yīng)遺傳算法，交叉概率和變異概率能夠隨適應(yīng)度自動(dòng)改變。當(dāng)種群個(gè)體適應(yīng)度趨于一致或者趨于局部最優(yōu)時(shí)，使交叉概率和變異概率二者增加、而當(dāng)群體適應(yīng)度比較分散時(shí)，使交叉概率和變異概率減少。 同時(shí)，對(duì)于適應(yīng)值高于群體平均適應(yīng)值的個(gè)體，對(duì)應(yīng)于較低的交叉概率和變異概率，使該個(gè)體得以保護(hù)進(jìn)入下一代；而低于平均適應(yīng)值的個(gè)體，相對(duì)于較高的交叉概率和變異概率，使該個(gè)體被淘汰。因此，自適應(yīng)遺傳算法能過(guò)提供相對(duì)某個(gè)解的最佳交叉概率和變異概率。19自適應(yīng)遺傳算法(7.1.5) 一、 自適應(yīng)遺傳算法的原理 Srinvivas等提出一種自適應(yīng)遺傳算法，交叉概率和變異概率能夠隨適應(yīng)度自動(dòng)改變。當(dāng)種

13、群個(gè)體適應(yīng)度趨于一致或者趨于局部最優(yōu)時(shí)，使交叉概率和變異概率二者增加、而當(dāng)群體適應(yīng)度比較分散時(shí)，使交叉概率和變異概率減少。 同時(shí)，對(duì)于適應(yīng)值高于群體平均適應(yīng)值的個(gè)體，對(duì)應(yīng)于較低的交叉概率和變異概率，使該個(gè)體得以保護(hù)進(jìn)入下一代；而低于平均適應(yīng)值的個(gè)體，相對(duì)于較高的交叉概率和變異概率，使該個(gè)體被淘汰。因此，自適應(yīng)遺傳算法能過(guò)提供相對(duì)某個(gè)解的最佳交叉概率和變異概率。20自適應(yīng)遺傳算法(7.1.5)一、 自適應(yīng)遺傳算法的原理 自適應(yīng)遺傳算法中交叉概率和變異概率的計(jì)算公式如下：21自適應(yīng)遺傳算法(7.1.5) 二、 自適應(yīng)遺傳算法的步驟 1 隨機(jī)產(chǎn)生初始種群，種群個(gè)體數(shù)目事先給定，每個(gè)個(gè)體表示為染色體的

14、基因編碼； 2 計(jì)算個(gè)體的適應(yīng)度，并判斷是否符合優(yōu)化準(zhǔn)則，若符合，輸出最佳個(gè)體及其代表的最優(yōu)解，并結(jié)束計(jì)算，否則轉(zhuǎn)3； 3 依據(jù)適應(yīng)度選擇再生個(gè)體，適應(yīng)的高的個(gè)體被選中的概率高，適應(yīng)的低的個(gè)體可能被淘汰； 4 按照下式(I)確定交叉概率，并通過(guò)交叉生成新個(gè)體； 5 按照式(II)確定變異概率，并通過(guò)變異生成新個(gè)體； 6由交叉和變異產(chǎn)生新一代的種群，返回2。.22遺傳算法的軟件實(shí)現(xiàn)一、基本遺傳算法的Matlab實(shí)現(xiàn) 1 計(jì)算函數(shù)的格式 函數(shù)：myGA。 功能：用基本遺傳算法解一維無(wú)約束極值問(wèn)題 調(diào)用格式：xv,fv=myGA(fitness,a,b,NP,NG,Pc,Pm,eps) 其中：fit

15、ness：待優(yōu)化的目標(biāo)函數(shù)； a：自變量下界；b：自變量上界； NP：種群大?。籒G：最大進(jìn)化代數(shù)； Pc：交叉概率；Pm：變異概率； eps:：自變量離散精度； xv：目標(biāo)函數(shù)取最大值時(shí)的自變量取值； fv：目標(biāo)函數(shù)的最大值。23遺傳算法的軟件計(jì)算一、基本遺傳算法的Matlab實(shí)現(xiàn) 2 舉例 例7-1 用基本遺傳算法計(jì)算下面函數(shù)的最大值 種群個(gè)體數(shù)目50，最大進(jìn)化代數(shù)100，離散精度0.01， 交叉概率0.9，變異概率0.04。 解：首先建立目標(biāo)函數(shù)文件fitness.m function F=fitness(x) F=x3-60*x2+900*x+100; 在命令框中輸入調(diào)用遺傳算法函數(shù)

16、xv,fv=myGA(fitness,0,30,50,100,0.9,0.04,0.01)所得結(jié)果 xv= 8.8242 fv=4.0991e+003 該問(wèn)題的精確最大值點(diǎn)為xv=10，最大值為fv=4100。24遺傳算法的軟件計(jì)算二、大變異遺傳算法的Matlab實(shí)現(xiàn) 1 計(jì)算函數(shù)格式 函數(shù)：GMGA。 功能：用大變異遺傳算法解一維無(wú)約束極值問(wèn)題 調(diào)用格式：xv,fv=GMGA(fitness,a,b,NP,NG,Pc,Pm, alpha,Pbm, eps) 其中：fitness：待優(yōu)化的目標(biāo)函數(shù)；a：自變量下界； b：自變量上界；NP：種群大??；NG：最大進(jìn)化代數(shù)； Pc：交叉概率； Pm：

17、變異概率；alpha,：密集因子； Pbm：大變異概率； eps:：自變量離散精度； xv：目標(biāo)函數(shù)取最大值時(shí)的自變量取值； fv：目標(biāo)函數(shù)的最大值。25遺傳算法的軟件計(jì)算二、大變異遺傳算法的Matlab實(shí)現(xiàn) 2 舉例 例7-2 用大變異遺傳算法求函數(shù) 的最大值，個(gè)體數(shù)目取50，最大進(jìn)化代數(shù)500，交叉概率取0.9， 變異概率取0.03，密集因子取0.6，大變異概率取0.2 ，離散精度取0.01。解：首先建立目標(biāo)函數(shù)文件fitness.mFunction F = fitness(x)F =x2-10*cos(2*pi*x)+10;在命令框中輸入調(diào)用大變異遺傳算法函數(shù) xv,fv=GMGA(fi

18、tness,0,4,50,500,0.9,0.03,0.6,0.2,0.01)運(yùn)算結(jié)果xv = 3.5068fv = 32.2887最大值點(diǎn)為x=3.5178, 最大值為f=32.3124。用大變異算法得到的結(jié)果較好。 26遺傳算法的軟件計(jì)算三、自適應(yīng)遺傳算法的Matlab實(shí)現(xiàn) 1 計(jì)算函數(shù)格式 函數(shù)：AdapGA。 功能：用自適應(yīng)遺傳算法解一維無(wú)約束極值問(wèn)題 調(diào)用格式：xv,fv=AdapGA(fitness,a,b,NP,NG,Pc1, Pc 2,Pm1, Pm2, eps) 其中：fitness：待優(yōu)化的目標(biāo)函數(shù)；a：自變量下界； b：自變量上界；NP：種群大??；NG：最大進(jìn)化代數(shù)； P

19、c1：交叉常數(shù)1；Pc2：交叉常數(shù)2； Pm1：變異常數(shù)1；Pm2：變異常數(shù)2； eps:：自變量離散精度； xv：目標(biāo)函數(shù)取最大值時(shí)的自變量取值； fv：目標(biāo)函數(shù)的最大值。27遺傳算法的軟件計(jì)算三、自適應(yīng)遺傳算法的Matlab實(shí)現(xiàn) 2 舉例 例7-3 用自適應(yīng)遺傳算法求函數(shù) 的最大值，個(gè)體數(shù)目取50，最大進(jìn)化代數(shù)500，交叉概率k1取0.5， k2取0.9，變異概率k3取0.02，k4取0.05，離散精度取0.01。解：首先建立目標(biāo)函數(shù)文件fitness.mFunction F = fitness(x)F =x2-10*cos(2*pi*x)+10;在命令框中輸入調(diào)用自適應(yīng)遺傳算法函數(shù) xv

20、,fv=AdapGA(fitness,0,4,50,500,0.5,0.9,0.02,0.05, 0.01)運(yùn)算結(jié)果xv = 3.5147fv = 32.3105與例7-2相比自適應(yīng)遺傳算法所求結(jié)果更好。 28遺傳算法的應(yīng)用舉例文獻(xiàn)1 一種改進(jìn)的遺傳優(yōu)化策略在電動(dòng)機(jī)故障診斷中的應(yīng)用 文獻(xiàn)2 基于遺傳算法的熱管多目?jī)?yōu)化設(shè)計(jì)29粒子群算法簡(jiǎn)介基本粒子群算法改進(jìn)的粒子群算法粒子群算法軟件計(jì)算粒子群算法應(yīng)用7.2 粒子群算法30粒子群算法簡(jiǎn)介 一、粒子群算法原理粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是Eberhart和kennedy博士發(fā)明。源于對(duì)鳥(niǎo)群捕食的行

21、為研究，PSO同遺傳算法類似，是一種基于迭代的優(yōu)化工具。系統(tǒng)初始化為一組隨機(jī)解，通過(guò)迭代搜索尋最優(yōu)值。在PSO算法中，每個(gè)優(yōu)化問(wèn)題的解都是搜索空間中的一只鳥(niǎo)，被抽象為沒(méi)有質(zhì)量和體積的微粒，并將其延伸到N維空間，離子i在N維空間中的位置表示為一個(gè)矢量，每個(gè)粒子的飛行速度也為一個(gè)矢量，所有粒子都有一個(gè)被優(yōu)化的函數(shù)決定的適應(yīng)值(fitness)，每個(gè)粒子還有一個(gè)決定他們飛翔的方向和距離。粒子們知道到目前為止發(fā)現(xiàn)的最好位置（pbest）和現(xiàn)在的位置，這個(gè)可以看做是粒子自己的飛行經(jīng)驗(yàn)，除此之外，每個(gè)粒子還知道目前為止所有粒子發(fā)現(xiàn)的最好位置（gbest, gbest是pbest中最好值），著可以看做是粒子

22、同伴的經(jīng)驗(yàn)。粒子是通過(guò)自己的經(jīng)驗(yàn)和同伴中最好的經(jīng)驗(yàn)來(lái)決定下一步的運(yùn)動(dòng)。 31粒子群算法簡(jiǎn)介 二、粒子群算法技術(shù)問(wèn)題粒子群算法的性能很大程度取決于算法的控制參數(shù)，粒子數(shù)、最大速度、學(xué)習(xí)因子、慣性權(quán)重等，各個(gè)參數(shù)的選取原則如下：1 粒子數(shù)：粒子數(shù)的多少根據(jù)問(wèn)題的復(fù)雜度自行決定。對(duì)于一般的優(yōu)化問(wèn)題取20至40個(gè)；對(duì)比較簡(jiǎn)單的問(wèn)題10個(gè)粒子就可以；對(duì)于比較復(fù)雜的或特定的問(wèn)題，粒子數(shù)可取100以上。2 粒子的維度：由優(yōu)化問(wèn)題決定；為解的維度，3 粒子的范圍：由優(yōu)化問(wèn)題決定，每一維可設(shè)定不同的范圍；4 最大速度： 決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離，通常設(shè)定為粒子的范圍寬度；5 學(xué)習(xí)因子：學(xué)習(xí)因子使粒子具

23、有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力，從而向群體內(nèi)或鄰域內(nèi)最近點(diǎn)靠近，通常取為2，也可以相等，取值范圍0到4。6 慣性權(quán)重：決定了對(duì)粒子當(dāng)前速度繼承的多少，適合的選擇可以使粒子具有均衡的探索能力和開(kāi)發(fā)能力，慣性權(quán)重的取法一般有常數(shù)法、線性遞減法、自適應(yīng)法等 32粒子群算法簡(jiǎn)介三、粒子群算法的特點(diǎn)及應(yīng)用領(lǐng)域 1 特點(diǎn) （1）粒子群算法以決策變量的編碼作為運(yùn)算對(duì)象。 （2）粒子群算法直接以適應(yīng)度作為搜索信息，無(wú)需導(dǎo)數(shù)等其它輔助信息。 （3）粒子群算法使用多個(gè)點(diǎn)的搜索信息，具有隱含并行性。 （4）粒子群算法使用概率搜索技術(shù)，而非確定性規(guī)則。 2 應(yīng)用領(lǐng)域 （1）函數(shù)優(yōu)化 （2）組合優(yōu)化 （3）生產(chǎn)

24、調(diào)度 （4）自動(dòng)控制 （5） 機(jī)器人學(xué) （6）圖象處理 33基本粒子群算法(7.2.1) 一、 基本粒子群算法的構(gòu)成要素 1 粒子數(shù) 2 最大速度 3 學(xué)習(xí)因子 4 慣性權(quán)重34基本粒子群算法(7.2.1)二 、基本粒子群算法步驟 1 隨機(jī)初始化種群中各種微粒的位置和速度； 2 評(píng)價(jià)每個(gè)微粒的適應(yīng)度,將當(dāng)前各微粒的位置和適應(yīng)值存儲(chǔ)在各微粒的pbest中,將所有pbest中適應(yīng)值最優(yōu)個(gè)體的位置和適應(yīng)值存于gbest中； 3 用下面的式子更新粒子的速度和位移； 4 對(duì)每個(gè)微粒子;將其適應(yīng)值與其經(jīng)歷過(guò)的最好位置作比較,如果較好,則將其作為當(dāng)前的最好位置； 5 比較當(dāng)前所有pbest和gbes的值，更

25、新gbes； 6 若滿足停止條件（通常為預(yù)設(shè)的運(yùn)算精度或迭代步數(shù)），搜索停止，輸出結(jié)果，否則返回3，繼續(xù)搜索。35二階粒子群算法(7.2.2)一、 二階粒子群算法原理 在標(biāo)準(zhǔn)PSO算法中，微粒的飛行速度僅僅是微粒當(dāng)前位置的函數(shù)，而二階粒子群算法中微粒飛行速度的變化與微粒位置的變化有關(guān)，其速度更新公式為：36二階粒子群算法(7.2.2)二 、二階粒子群算法步驟 1 隨機(jī)初始化種群中各種微粒的位置和速度； 2 評(píng)價(jià)每個(gè)微粒的適應(yīng)度,將當(dāng)前各微粒的位置和適應(yīng)值存儲(chǔ)在各微粒的pbest中,將所有pbest中適應(yīng)值最優(yōu)個(gè)體的位置和適應(yīng)值存于gbest中； 3 用下面的式子更新粒子的速度和位移； 4 對(duì)每

26、個(gè)微粒子;將其適應(yīng)值與其經(jīng)歷過(guò)的最好位置作比較,如果較好,則將其作為當(dāng)前的最好位置； 5 比較當(dāng)前所有pbest和gbes的值，更新gbes； 6 若滿足停止條件（通常為預(yù)設(shè)的運(yùn)算精度或迭代步數(shù)），搜索停止，輸出結(jié)果，否則返回3，繼續(xù)搜索。37基于選擇的粒子群算法(7.2.3)一、 基于選擇的粒子群算法原理 將遺傳算法中的選擇機(jī)理與粒子群算法相結(jié)合就 得到基于選擇的粒子群算法。 基本思想：每次迭代過(guò)程將整個(gè)粒子群按適應(yīng)值排序,用群體最好的一半的粒子的速度和位置替換最差的一半的位置和速度,同時(shí)保留原來(lái)每個(gè)個(gè)體所記憶的歷史最優(yōu)值。38基于選擇的粒子群算法(7.2.3)二 、基于選擇的粒子群算法步驟

27、 1 隨機(jī)初始化種群中各種微粒的位置和速度； 2 評(píng)價(jià)每個(gè)微粒的適應(yīng)度,將當(dāng)前各微粒的位置和適應(yīng)值存儲(chǔ)在各微粒的pbest中,將所有pbest中適應(yīng)值最優(yōu)個(gè)體的位置和適應(yīng)值存于gbest中； 3 用下面的式子更新粒子的速度和位移； 4 對(duì)每個(gè)微粒子;將其適應(yīng)值與其經(jīng)歷過(guò)的最好位置作比較,如果較好,則將其作為當(dāng)前的最好位置； 5 比較當(dāng)前所有pbest和gbes的值，更新gbes； 6將整個(gè)粒子群按適應(yīng)值排序，用群體中最好的一半的粒子的速度和位置替換最差的一半的位置和速度，保持pbest和gbest不變。 7 若滿足停止條件（通常為預(yù)設(shè)的運(yùn)算精度或迭代步數(shù)），搜索停止，輸出結(jié)果，否則返回3，繼續(xù)

28、搜索。39基于交叉的粒子群算法(7.2.4)一、 基于交叉的粒子群算法原理 借鑒遺傳算法中的交叉概念，在每次迭代中，根據(jù)交叉概率選取制定數(shù)量的粒子放入交叉池內(nèi)，池中的粒子隨機(jī)兩輛交叉，產(chǎn)生同樣數(shù)目的子代粒子（child），并用子代粒子替換親代粒子（parent）。子代位置由父代位置進(jìn)行算術(shù)交叉得到：其中 p是0到1之間的隨機(jī)數(shù)。子代的速度由下式計(jì)算或或40基于交叉的粒子群算法(7.2.4)二 、基于交叉的粒子群算法步驟 1 隨機(jī)初始化種群中各種微粒的位置和速度； 2 評(píng)價(jià)每個(gè)微粒的適應(yīng)度,將當(dāng)前各微粒的位置和適應(yīng)值存儲(chǔ)在各微粒的pbest中,將所有pbest中適應(yīng)值最優(yōu)個(gè)體的位置和適應(yīng)值存于g

29、best中； 3 用下面的式子更新粒子的速度和位移； 4 對(duì)每個(gè)微粒子;將其適應(yīng)值與其經(jīng)歷過(guò)的最好位置作比較,如果較好,則將其作為當(dāng)前的最好位置； 41基于交叉的粒子群算法(7.2.4)二 、基于交叉的粒子群算法步驟 5 比較當(dāng)前所有pbest和gbes的值，更新gbes； 6 根據(jù)交叉概率選取指定數(shù)量的粒子放入交叉池內(nèi)，池中的粒子隨機(jī)兩兩交叉產(chǎn)生同樣數(shù)目的子代粒子，子代的位置和速度計(jì)算公式如下： 保持pbest和gbest不變。 7 若滿足停止條件（通常為預(yù)設(shè)的運(yùn)算精度或迭代步數(shù)），搜索停止，輸出結(jié)果，否則返回3，繼續(xù)搜索。42粒子群算法的軟件實(shí)現(xiàn)一、基本粒子群算法的Matlab實(shí)現(xiàn) 1 計(jì)

30、算函數(shù)的格式 函數(shù)：PSO。 功能：用基本粒子群算法求解無(wú)約束極值問(wèn)題。 調(diào)用格式：xv,fv=PSO(fitness,N,c1,c2,w,M,D) 其中：fitness: 待優(yōu)化的目標(biāo)函數(shù); N:粒子數(shù)目; c1:學(xué)習(xí)因子1; c2:學(xué)習(xí)因子2; w:慣性權(quán)重; M:最大迭代次數(shù); D:問(wèn)題的維數(shù); xv:目標(biāo)函數(shù)的最小值點(diǎn); fv:目標(biāo)函數(shù)的最小值。43粒子群算法的軟件計(jì)算一、基本粒子群算法的Matlab實(shí)現(xiàn) 2 舉例 例7-4 采用基本粒子群算法求Sphere Model的最小值。解：首先建立目標(biāo)函數(shù)文件fitness.m，輸入內(nèi)容如下： Function F= fitness(x) F

31、 = 0; for i=1:30 F = F+x(i)2; end 在MATLAB命令窗口中輸入：xv,fv = PSO(fitness,40,2,2,0.5,1000,30)xv,fv = PSO(fitness,40,2,2,0.5,5000,30)xv,fv = PSO(fitness,40,2,2,0.5,10000,30)44粒子群算法的軟件計(jì)算一、基本粒子群算法的Matlab實(shí)現(xiàn) 迭代步數(shù)1000500010000 x10.171159151-0.09655836-0.015987273x20.1420736240.008334669-0.001818132x3-0.1819121

32、030.0186364210.004625648x40.1003362930.1037824360.038768164x5-0.166995445-0.0301029570.007716967x60.0356615090.0060840490.015746696x70.037148320.013657669-0.00238339x80.0457441510.010931290.023852163x9-0.171087980.0429103380.007423934x100.055131632-0.15093465-0.014160336x110.0457441510.076321997-0.0

33、32519146x12-0.171087980.0044026080.006066822x130.0551316320.026024016-0.007677664x140.2564633330.011989153-0.027326272x15-0.1307773830.0166517660.01974572x160.116058331-0.0073606770.014704575表7-1 迭代步數(shù)不同時(shí)粒子群法求解結(jié)果比較表迭代步數(shù)1000500010000 x17-0.098250698-0.038645847-0.037417556x18-0.168572745-0.012203864-0

34、.061915582x190.0833436250.038583338-0.046837159x200.0988520890.089216026-0.022234846x210.07067315-0.074770647-0.071276469x22-0.2220526430.0072028790.049688358x23-0.0408937950.015707451-0.006258405x240.210061935-0.0290495680.090448281x25-0.1281979520.019223623-0.013524576x260.216501635-0.0202020740.0

35、1044023x27-0.0875019130.007375891-0.040697535x280.060820255-0.036771138-0.00546114x29-0.24635774-0.041702041-0.04696722x30-0.013847313-0.0616090710.010652994函數(shù)極值0.6475372570.078922440.03341558245粒子群算法的軟件計(jì)算一、基本粒子群算法的Matlab實(shí)現(xiàn) 從表7-1的求解結(jié)果可以看出,在其他參數(shù)不變的情況下,一般迭代步數(shù)越大,求得的精度越高,但這并不是絕對(duì)的,因?yàn)镻SO算法本質(zhì)上也是一種隨機(jī)算法,即使用同

36、樣的參數(shù),每次求解也可能得出不同的結(jié)果,同時(shí)如果對(duì)于多峰函數(shù),PSO算法還可能陷入局部最優(yōu)點(diǎn)。 下面再看粒子群規(guī)模對(duì)結(jié)果的影響，學(xué)習(xí)因子都為2，慣性權(quán)重為0.5，迭代步數(shù)都為10000，粒子群規(guī)模分別取50、60和80。在MATLAB命令窗口中輸入：xv,fv = PSO(fitness,50,2,2,0.5,10000,30)xv,fv = PSO(fitness,60,2,2,0.5,10000,30)xv,fv = PSO(fitness,80,2,2,0.5,10000,30)46粒子群算法的軟件計(jì)算一、基本粒子群算法的Matlab實(shí)現(xiàn) 迭代步數(shù)506080 x1-0.01131034

37、60.0074255830.032168404x20.0043878460.0048179140.018358567x3-0.0066672460.0018556090.022236195x40.0059684390.0143353340.011242284x50.00915497-0.001267227-0.020372561x6-0.051987837-0.0054969170.022033454x7-0.0286875740.00010960.052377912x8-0.0177265260.008815249-0.023582598x90.012876614-0.00195790.03

38、170092x100.011624676-0.0015827040.0014189874x11-0.0233624320.034052767-0.013562149x12-0.042501880.015367050.046835547x130.0132199080.0066061990.032128767x14-0.010243719-0.0087775810.040258144x15-0.011879719-0.000378132-0.000129326x16-0.031978858-0.004513022-0.049016752表7-2 種群數(shù)不同時(shí)粒子群法求解結(jié)果比較表 迭代步數(shù)5060

39、80 x17-0.021793246-0.013723932-0.083971611x18-0.014866581-0.0009891410.021355323x190.032450927-0.0036157330.007294525x20-0.025591814-0.005227237-0.027505171x21-0.0091624940.0036420450.030514614x220.053509427-0.007972992-0.006440302x23-0.004734495-0.0059175490.043635763x240.007099750.0127190950.02102

40、1241x25-0.0004611460.0003873220.04026069x26-0.003042356-0.0026208750.016406857x27-0.0052418520.006107442-0.051622937x28-0.009992668-0.07381692-0.021966852x290.01191555-0.0120409020.038647243x300.012901919-0.0024714870.060333511函數(shù)極值0.0141168710.0026933620.03663915347粒子群算法的軟件計(jì)算一、基本粒子群算法的Matlab實(shí)現(xiàn) 從表7-2

41、的求解結(jié)果可以看出，粒子群的規(guī)模不是越大越好，關(guān)鍵是各參數(shù)之間的搭配，搭配好才能求得比較好的結(jié)果。這需要反復(fù)試算。48粒子群算法的軟件實(shí)現(xiàn)二、二階粒子群算法的Matlab實(shí)現(xiàn) 1 計(jì)算函數(shù)的格式 函數(shù)：SecPSO。 功能：用基本粒子群算法求解無(wú)約束極值問(wèn)題。 調(diào)用格式：xv,fv=SecPSO(fitness,N,c1,c2,w,M,D) 其中：fitness: 待優(yōu)化的目標(biāo)函數(shù); N:粒子數(shù)目;、 c1:學(xué)習(xí)因子1; c2:學(xué)習(xí)因子2; w:慣性權(quán)重; M:最大迭代次數(shù); D:問(wèn)題的維數(shù); xv:目標(biāo)函數(shù)的最小值點(diǎn); fv:目標(biāo)函數(shù)的最小值。 49粒子群算法的軟件計(jì)算二、二階粒子群算法的Matlab實(shí)現(xiàn) 2 舉例 例7-5 采用二階粒子群算法實(shí)現(xiàn)求下面函數(shù)的最小值取粒子