數(shù)值分析方法 課件 8.5 粒子群算法

數(shù)值分析方法主編

李冬果李林高磊首都醫(yī)科大學(xué)生物醫(yī)學(xué)工程學(xué)院智能醫(yī)學(xué)工程學(xué)學(xué)系面向“四新”人才培養(yǎng)普通高等教育系列教材第八章智能優(yōu)化算法基礎(chǔ)第一節(jié)最優(yōu)化問題和隨機(jī)算法第二節(jié)禁忌搜索算法第三節(jié)模擬退火方法第四節(jié)遺傳算法第五節(jié)粒子群算法

目錄/Contents

8.5粒子群算法在多維連續(xù)空間中搜索最優(yōu)解是一個(gè)非常困難的過程，粒子群算法（particleswarmoptimization,PSO）通過模擬一組粒子的初始狀態(tài)，通過群內(nèi)粒子彼此間的信息共享，不斷迭代的向最優(yōu)解移動來獲取優(yōu)化問題的最優(yōu)解。粒子群算法最早在1995年由Eberhart和Kennedy提出，由于其算法簡明，易于實(shí)現(xiàn)，已經(jīng)在科學(xué)計(jì)算和工程領(lǐng)域得到了廣泛的研究和應(yīng)用。5.1算法原理粒子群算法的靈感來自于對鳥類捕食行為的模擬。假設(shè)一群鳥要在一片區(qū)域中搜索唯一的食物來源，每只鳥都不知道食物所在位置，但卻能知道當(dāng)前位置與食物的距離。如果這些鳥能夠彼此通訊，那么最優(yōu)的搜索策略是，所有的鳥都基于自己搜索的經(jīng)驗(yàn)，向離食物最近的鳥附近去做進(jìn)一步搜索。粒子群算法假設(shè)，優(yōu)化問題的全局最優(yōu)解就是鳥類所追尋的食物所在位置，而每一只鳥（或者稱為粒子）的位置都可以代表著搜索空間中的一個(gè)潛在最優(yōu)解。所有粒子位置都對應(yīng)一個(gè)由被優(yōu)化函數(shù)決定的適應(yīng)值，除此之外，粒子還有一個(gè)速度代表著它的飛行方向和速率。在優(yōu)化過程中，首先通過隨機(jī)初始化每個(gè)粒子的位置和速度，然后通過迭代算法，求得每個(gè)粒子的個(gè)體極值，和所有粒子的全局極值。隨后，每個(gè)粒子都根據(jù)代表自身經(jīng)驗(yàn)的個(gè)體極值，和代表群體經(jīng)驗(yàn)的全局極值來調(diào)整自己的搜索策略，更新下一步的位置和速度。當(dāng)這個(gè)過程不斷迭代進(jìn)行，粒子群將越來越接近全局最優(yōu)解。5.2算法設(shè)計(jì)

5.3算法實(shí)現(xiàn)粒子群算法的實(shí)現(xiàn)步驟如下：步驟1

確定粒子群規(guī)模，適應(yīng)度函數(shù)，隨機(jī)初始化每個(gè)粒子的初始位置和速度；步驟2

為每個(gè)粒子計(jì)算適應(yīng)度；步驟3

更新每個(gè)微粒的個(gè)體最優(yōu)位置以及粒子群的全局最優(yōu)位置；步驟4

根據(jù)粒子群迭代公式，計(jì)算每個(gè)粒子的新位置和新速度；步驟5

如果達(dá)到停止條件，則輸出當(dāng)前的全局最優(yōu)位置，否則返回步驟2，開始下一次循環(huán)。

（2）鄰域拓?fù)浣Y(jié)構(gòu)。在基本粒子群優(yōu)化算法迭代公式中，“社會部分”是通過比較粒子位置與全局最優(yōu)位置來得到的，這里也可以將全局最優(yōu)位置替換為“局部最優(yōu)”位置，即通過粒子位置與其鄰域內(nèi)最優(yōu)位置進(jìn)行比較來迭代更新粒子的運(yùn)動速度。因此可以通過定義粒子的“鄰域”來修正迭代公式。常見的鄰域拓?fù)浣Y(jié)構(gòu)包括：星型結(jié)構(gòu)，即每個(gè)粒子的鄰域是整個(gè)粒子群，迭代過程受全局最優(yōu)值的影響；環(huán)形結(jié)構(gòu)，即每個(gè)粒子只受與其最接近的兩個(gè)近鄰粒子的影響；齒形結(jié)構(gòu)，需要先定義一個(gè)中心粒子，在每次迭代中，中心粒子向全局最優(yōu)方向移動，而其他粒子則通過中心粒子的位置計(jì)算迭代公式中的“社會部分”。目前的研究顯示，星型結(jié)構(gòu)算法收斂快，但容易陷入局部最優(yōu)，環(huán)形結(jié)構(gòu)收斂慢，但更可能找到全局最優(yōu)。

（4）收斂性問題。粒子群優(yōu)化算法的收斂性問題是其理論研究中的熱點(diǎn)問題，由于粒子群算法中包含有隨機(jī)因子，是一個(gè)隨機(jī)系統(tǒng)，其收斂問題的研究困難很大。目前的一些研究顯