# 0 賽題思路

（賽題出來(lái)以后第一時(shí)間在CSDN分享）

https://blog.csdn.net/dc_sinor?type=blog

1 什么是粒子群算法？

粒子群算法（Particle Swarm Optimization,PSO）是一種模仿鳥(niǎo)群、魚(yú)群覓食行為發(fā)展起來(lái)的一種進(jìn)化算法。其概念簡(jiǎn)單易于編程實(shí)現(xiàn)且運(yùn)行效率高、參數(shù)相對(duì)較少，應(yīng)用非常廣泛。粒子群算法于1995年提出，距今（2019）已有24年歷史。
　　
　　粒子群算法中每一個(gè)粒子的位置代表了待求問(wèn)題的一個(gè)候選解。每一個(gè)粒子的位置在空間內(nèi)的好壞由該粒子的位置在待求問(wèn)題中的適應(yīng)度值決定。每一個(gè)粒子在下一代的位置有其在這一代的位置與其自身的速度矢量決定，其速度決定了粒子每次飛行的方向和距離。在飛行過(guò)程中，粒子會(huì)記錄下自己所到過(guò)的最優(yōu)位置 Ｐ，群體也會(huì)更新群體所到過(guò)的最優(yōu)位置Ｇ 。粒子的飛行速度則由其當(dāng)前位置、粒子自身所到過(guò)的最優(yōu)位置、群體所到過(guò)的最優(yōu)位置以及粒子此時(shí)的速度共同決定。

2 舉個(gè)例子

在一個(gè)湖中有兩個(gè)人他們之間可以通信，并且可以探測(cè)到自己所在位置的最低點(diǎn)。初始位置如上圖所示，由于右邊比較深，因此左邊的人會(huì)往右邊移動(dòng)一下小船。

現(xiàn)在左邊比較深，因此右邊的人會(huì)往左邊移動(dòng)一下小船

一直重復(fù)該過(guò)程，最后兩個(gè)小船會(huì)相遇

得到一個(gè)局部的最優(yōu)解
將每個(gè)個(gè)體表示為粒子。每個(gè)個(gè)體在某一時(shí)刻的位置表示為，x(t),方向表示為v(t)

p（t）為在t時(shí)刻x個(gè)體的自己的最優(yōu)解，g(t)為在t時(shí)刻所有個(gè)體的最優(yōu)解，v(t)為個(gè)體在t時(shí)刻的方向，x(t)為個(gè)體在t時(shí)刻的位置

下一個(gè)位置為上圖所示由x,p,g共同決定了

種群中的粒子通過(guò)不斷地向自身和種群的歷史信息進(jìn)行學(xué)習(xí)，從而可以找到問(wèn)題的最優(yōu)解。

3 還是一個(gè)例子

粒子群算法是根據(jù)鳥(niǎo)群覓食行為衍生出的算法。現(xiàn)在，我們的主角換成是一群鳥(niǎo)。

小鳥(niǎo)們的目標(biāo)很簡(jiǎn)單，要在這一帶找到食物最充足的位置安家、休養(yǎng)生息。它們?cè)谶@個(gè)地方的搜索策略如下：
　　1． 每只鳥(niǎo)隨機(jī)找一個(gè)地方，評(píng)估這個(gè)地方的食物量。
　　2． 所有的鳥(niǎo)一起開(kāi)會(huì)，選出食物量最多的地方作為安家的候選點(diǎn)G。
　　3． 每只鳥(niǎo)回顧自己的旅程，記住自己曾經(jīng)去過(guò)的食物量最多的地方P。
　　4． 每只鳥(niǎo)為了找到食物量更多的地方，于是向著G飛行，但是呢，不知是出于選擇困難癥還是對(duì)P的留戀，或者是對(duì)G的不信任，小鳥(niǎo)向G飛行時(shí)，時(shí)不時(shí)也向P飛行，其實(shí)它自己也不知道到底是向G飛行的多還是向P飛行的多。
　　5． 又到了開(kāi)會(huì)的時(shí)間，如果小鳥(niǎo)們決定停止尋找，那么它們會(huì)選擇當(dāng)前的G來(lái)安家；否則繼續(xù)2->3->4->5來(lái)尋找它們的棲息地。

上圖描述的策略4的情況，一只鳥(niǎo)在點(diǎn)A處，點(diǎn)G是鳥(niǎo)群們找到過(guò)的食物最多的位置，點(diǎn)P是它自己去過(guò)的食物最多的地點(diǎn)。V是它現(xiàn)在的飛行速度（速度是矢量，有方向和大小)，現(xiàn)在它決定向著P和G飛行，但是這是一只佛系鳥(niǎo)，具體飛多少隨緣。如果沒(méi)有速度V，它應(yīng)該飛到B點(diǎn)，有了速度V的影響，它的合速度最終使它飛到了點(diǎn)C，這里是它的下一個(gè)目的地。如果C比P好那么C就成了下一次的P，如果C比G好，那么就成了下一次的G。

算法流程

算法實(shí)現(xiàn)

這里學(xué)長(zhǎng)用python來(lái)給大家演示使用粒子群解函數(shù)最優(yōu)解

import numpy as np
import matplotlib.pyplot as plt
import random# 定義“粒子”類(lèi)
class parti(object):def __init__(self, v, x):self.v = v                    # 粒子當(dāng)前速度self.x = x                    # 粒子當(dāng)前位置self.pbest = x                # 粒子歷史最優(yōu)位置class PSO(object):def __init__(self, interval, tab='min', partisNum=10, iterMax=1000, w=1, c1=2, c2=2):self.interval = interval                                            # 給定狀態(tài)空間 - 即待求解空間self.tab = tab.strip()                                              # 求解最大值還是最小值的標(biāo)簽: 'min' - 最小值；'max' - 最大值self.iterMax = iterMax                                              # 迭代求解次數(shù)self.w = w                                                          # 慣性因子self.c1, self.c2 = c1, c2                                           # 學(xué)習(xí)因子self.v_max = (interval[1] - interval[0]) * 0.1                      # 設(shè)置最大遷移速度#####################################################################self.partis_list, self.gbest = self.initPartis(partisNum)                 # 完成粒子群的初始化，并提取群體歷史最優(yōu)位置self.x_seeds = np.array(list(parti_.x for parti_ in self.partis_list))    # 提取粒子群的種子狀態(tài) ###self.solve()                                                              # 完成主體的求解過(guò)程self.display()                                                            # 數(shù)據(jù)可視化展示def initPartis(self, partisNum):partis_list = list()for i in range(partisNum):v_seed = random.uniform(-self.v_max, self.v_max)x_seed = random.uniform(*self.interval)partis_list.append(parti(v_seed, x_seed))temp = 'find_' + self.tabif hasattr(self, temp):                                             # 采用反射方法提取對(duì)應(yīng)的函數(shù)gbest = getattr(self, temp)(partis_list)else:exit('>>>tab標(biāo)簽傳參有誤："min"|"max"<<<')return partis_list, gbestdef solve(self):for i in range(self.iterMax):for parti_c in self.partis_list:f1 = self.func(parti_c.x)# 更新粒子速度，并限制在最大遷移速度之內(nèi)parti_c.v = self.w * parti_c.v + self.c1 * random.random() * (parti_c.pbest - parti_c.x) + self.c2 * random.random() * (self.gbest - parti_c.x)if parti_c.v > self.v_max: parti_c.v = self.v_maxelif parti_c.v < -self.v_max: parti_c.v = -self.v_max# 更新粒子位置，并限制在待解空間之內(nèi)if self.interval[0] <= parti_c.x + parti_c.v <=self.interval[1]:parti_c.x = parti_c.x + parti_c.velse:parti_c.x = parti_c.x - parti_c.vf2 = self.func(parti_c.x)getattr(self, 'deal_'+self.tab)(f1, f2, parti_c)             # 更新粒子歷史最優(yōu)位置與群體歷史最優(yōu)位置def func(self, x):                                                       # 狀態(tài)產(chǎn)生函數(shù) - 即待求解函數(shù)value = np.sin(x**2) * (x**2 - 5*x)return valuedef find_min(self, partis_list):                                         # 按狀態(tài)函數(shù)最小值找到粒子群初始化的歷史最優(yōu)位置parti = min(partis_list, key=lambda parti: self.func(parti.pbest))return parti.pbestdef find_max(self, partis_list):parti = max(partis_list, key=lambda parti: self.func(parti.pbest))   # 按狀態(tài)函數(shù)最大值找到粒子群初始化的歷史最優(yōu)位置return parti.pbestdef deal_min(self, f1, f2, parti_):if f2 < f1:                          # 更新粒子歷史最優(yōu)位置parti_.pbest = parti_.xif f2 < self.func(self.gbest):self.gbest = parti_.x            # 更新群體歷史最優(yōu)位置def deal_max(self, f1, f2, parti_):if f2 > f1:                          # 更新粒子歷史最優(yōu)位置parti_.pbest = parti_.xif f2 > self.func(self.gbest):self.gbest = parti_.x            # 更新群體歷史最優(yōu)位置def display(self):print('solution: {}'.format(self.gbest))plt.figure(figsize=(8, 4))x = np.linspace(self.interval[0], self.interval[1], 300)y = self.func(x)plt.plot(x, y, 'g-', label='function')plt.plot(self.x_seeds, self.func(self.x_seeds), 'b.', label='seeds')plt.plot(self.gbest, self.func(self.gbest), 'r*', label='solution')plt.xlabel('x')plt.ylabel('f(x)')plt.title('solution = {}'.format(self.gbest))plt.legend()plt.savefig('PSO.png', dpi=500)plt.show()plt.close()if __name__ == '__main__':PSO([-9, 5], 'max')

效果

建模資料

資料分享: 最強(qiáng)建模資料