1 原理
粒子群算法是群智能一種承二，是基于對鳥群覓食行為的研究和模擬而來的淋淀。假設(shè)在鳥群覓食范圍瘟芝，只在一個地方有食物易桃，所有鳥兒看不到食物（不知道食物的具體位置），但是能聞到食物的味道（能知道食物距離自己位置）锌俱。最好的策略就是結(jié)合自己的經(jīng)驗在距離鳥群中距離食物最近的區(qū)域搜索晤郑。
利用粒子群算法解決實際問題本質(zhì)上就是利用粒子群算法求解函數(shù)的最值。因此需要事先把實際問題抽象為一個數(shù)學(xué)函數(shù)贸宏，稱之為適應(yīng)度函數(shù)造寝。在粒子群算法中，每只鳥都可以看成是問題的一個解吭练，這里我們通常把鳥稱之為粒子诫龙，每個粒子都擁有：
- 位置，可以理解函數(shù)的自變量的值鲫咽；
- 經(jīng)驗签赃，也即是自身經(jīng)歷過的距離食物最近的位置谷异；
- 速度，可以理解為自變量的變化值锦聊；
- 適應(yīng)度歹嘹，距離食物的位置，也就是函數(shù)值括丁。
粒子群算法的過程
- 初始化荞下。包括根據(jù)給定的粒子個數(shù)，初始化粒子史飞，包括初始化一下的值：
- 位置：解空間內(nèi)的隨機值尖昏；
- 經(jīng)驗：與初始位置相等；
- 速度：0构资；
- 適應(yīng)度：根據(jù)位置抽诉，帶入適應(yīng)度函數(shù)，得到適應(yīng)度值吐绵。
- 更新迹淌。包括兩部分：
-
粒子自身信息：包括根據(jù)下面的公式更新粒子的速度、位置己单，根據(jù)適應(yīng)度函數(shù)更新適應(yīng)度唉窃，然后和用更新后的適應(yīng)度和自身經(jīng)驗進(jìn)行比較，如果新的適應(yīng)度由于經(jīng)驗的適應(yīng)度纹笼，就利用當(dāng)前位置更新經(jīng)驗纹份；
速度更新公式
位置更新公式
上面公式中：i表示粒子編號；t表示時刻廷痘，反映在迭代次數(shù)上蔓涧；w是慣性權(quán)重，一般設(shè)置在0.4左右笋额；c表示學(xué)習(xí)因子元暴，一般都取值為2；Xpbest表示的是粒子i的經(jīng)驗兄猩，也即是粒子i所到過最佳位置茉盏；Xgbest代表的是全局最優(yōu)粒子的位置；r是0到1之間的隨機值厦滤。
- 種群信息：把當(dāng)前適應(yīng)度和全局最優(yōu)位置的適應(yīng)度進(jìn)行比較援岩，如果當(dāng)前適應(yīng)度優(yōu)于全局最優(yōu)的適應(yīng)度，那么久用當(dāng)前粒子替換群居最優(yōu)掏导。
- 判斷結(jié)束條件。結(jié)束條件包括最大迭代次數(shù)和適應(yīng)度的閾值羽峰。
2 代碼
- 實驗環(huán)境為python 2.7.11趟咆。
- 這個代碼最初是用于求解一維最大熵分割圖像問題的添瓷，因此是求解函數(shù)最大值，如果需要求解最小值值纱，把代碼中的大于號全部改成小于號就可以了鳞贷。
首先需要解決的是粒子的存儲，我第一反應(yīng)是利用結(jié)構(gòu)體來存儲虐唠，但是python并沒有相應(yīng)的數(shù)據(jù)結(jié)構(gòu)搀愧，所以我選擇用一個類來表示粒子結(jié)構(gòu)，該類的一個對象就是一個粒子疆偿，上代碼：
class bird:
"""
speed:速度
position:位置
fit:適應(yīng)度
lbestposition:經(jīng)歷的最佳位置
lbestfit:經(jīng)歷的最佳的適應(yīng)度值
"""
def __init__(self, speed, position, fit, lBestPosition, lBestFit):
self.speed = speed
self.position = position
self.fit = fit
self.lBestFit = lBestPosition
self.lBestPosition = lPestFit
接下來就是粒子群算法的主干部分咱筛，用一個類來封裝，代碼：
import random
class PSO:
"""
fitFunc:適應(yīng)度函數(shù)
birdNum:種群規(guī)模
w:慣性權(quán)重
c1,c2:個體學(xué)習(xí)因子杆故，社會學(xué)習(xí)因子
solutionSpace:解空間迅箩，列表類型：[最小值，最大值]
"""
def __init__(self, fitFunc, birdNum, w, c1, c2, solutionSpace):
self.fitFunc = fitFunc
self.w = w
self.c1 = c1
self.c2 = c2
self.birds, self.best = self.initbirds(birdNum, solutionSpace)
def initbirds(self, size, solutionSpace):
birds = []
for i in range(size):
position = random.uniform(solutionSpace[0], solutionSpace[1])
speed = 0
fit = self.fitFunc(position)
birds.append(bird(speed, position, fit, position, fit))
best = birds[0]
for bird in birds:
if bird.fit > best.fit:
best = bird
return birds,best
def updateBirds(self):
for bird in self.birds:
# 更新速度
bird.speed = self.w * bird.speed + self.c1 * random.random() * (bird.lBestPosition - bird.position) + self.c2 * random.random() * (self.best.position - bird.position)
# 更新位置
bird.position = bird.position + bird.speed
# 跟新適應(yīng)度
bird.fit = self.fitFunc(bird.position)
# 查看是否需要更新經(jīng)驗最優(yōu)
if bird.fit > bird.lBestFit:
bird.lBestFit = bird.fit
bird.lBestPosition = bird.position
def solve(self, maxIter):
# 只考慮了最大迭代次數(shù)处铛，如需考慮閾值饲趋，添加判斷語句就好
for i in range(maxIter):
# 更新粒子
self.updateBirds()
for bird in self.birds:
# 查看是否需要更新全局最優(yōu)
if bird.fit > self.best.fit:
self.best = bird
有了以上代碼，只需要自定義適應(yīng)度函數(shù)fitFunc就可以進(jìn)行求解撤蟆，但是需要注意的是只適用于求解** 一維問題 **奕塑。
