粒子群优化算法PSO

参考：

（1）https://www.cnblogs.com/csguo/p/7521441.html
（2）https://blog.csdn.net/daaikuaichuan/article/details/81382794
（3）https://blog.csdn.net/myarrow/article/details/51507671
（4）https://zhuanlan.zhihu.com/p/192870518
（5）https://blog.csdn.net/qq_18822147/article/details/108301279

一、算法思想：

粒子群算法最早是由两名美国的科学家基于群鸟觅食，寻找最佳觅食区域的过程所提出来的，作为一种智能算法，PSO模拟的就是最佳决策的过程，鸟群觅食类似于人类的决策过程，想想在你做出选择之前，是不是会受到自己的经验（局部最优）以及周围人的经历（全局最优）的影响？同样的道理，群鸟在觅食的过程当中，每一只鸟的初始位置都处于随机状态，当然也不知道最佳的觅食点在何处，并且每只鸟的飞行方向也是随机的。可以认为，在觅食的初期，鸟群的运动轨迹都是杂乱无章的，随着时间的推移，处于随机位置的鸟类通过群内的相互学习、共享觅食信息，每一只鸟在每一次的觅食过程中结合自己的经验和同伴传送的信息估计目前所处的位置能够找到食物有多大的价值。基于这样的搜索方式，粒子群算法（Particle Swarm Optimization, PSO）应运而生。

二、算法流程：

v_i: 粒子i的速度（d维，d >= 1）。

pos_i: 粒子i的位置（d维，d >= 1）。

w: 惯性因子，非负数，值越大，全局搜索能力越强，局部搜索能力越弱。可根据具体问题进行调试。

c1, c2: 学习因子，通常c1 = c2 = 2。

rand(): (0, 1)之间的随机数。

fitness: 粒子i的适应值，用来度量位置的优劣，计算方法根据具体问题设置。

pbest_i: 粒子i的个体最优位置。

gbest: 全局最优位置

（1）初始化粒子群：选取粒子个数（一般为20~40个，个数越多，越容易找到全局最优解，但计算时间相应增加），随机初始化粒子的位置和速度。

（2）将粒子的初始位置作为其个体最优位置，计算每个粒子的适应值，比较后得到全局最优位置。

（3）迭代更新粒子的速度，位置，个体最优位置和全局最优位置，直至满足迭代次数或终止条件。

v_i = w x v_i + c1 x rand() x (pbest_i- pos_i) + c2 x rand() x (gbest - pos_i)

pos_i= pos_i+ v_i

三、测试

测试函数：Griewank函数

其中，x_i∈[-600, 600]

最小值为0，在(0, 0, ..., 0)取到

import numpy as np
import random
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

#函数三维图像
fig = plt.figure()
ax3 = plt.axes(projection='3d')

x = np.linspace(-8, 8, 100)
y = x

x, y = np.meshgrid(x, y)
z = (x ** 2) / 4000 + (y ** 2) / 4000 - np.cos(x) * np.cos(y / np.sqrt(2)) + 1

ax3.plot_surface(x, y, z, cmap = 'rainbow')
plt.show()

inf = 0x3f3f3f3f
#粒子群个数
n = 200
#粒子维度
d = 2
#迭代次数
iters = 50
#位置范围
pos_min = -600
pos_max = 600
#速度范围（在本问题中速度范围如何设置似乎对结果没有什么影响）
v_min = -1000
v_max = 1000
#粒子群位置
pos = [] 
#粒子群速度
v = [] 
#粒子最优位置
pbest = []
#粒子群最优位置
gbest = []

#测试函数Griewank
def fitness(p):
    
    y1 = 0
    y2 = 1
    for i in range(len(p)):
        
        y1 += (p[i] ** 2) / 4000    
        y2 *= np.cos(p[i] / np.sqrt(i + 1))
        
    y = y1 - y2 + 1
    return y

def init():
    
    global inf
    f_min_value = inf
    f_min_index = 0
    
    global n, d
    for i in range(n):
        
        global pos, pos_min, pos_max
        pos.append([random.uniform(pos_min, pos_max) for j in range(d)])
        
        global v, v_min, v_max
        v.append([random.uniform(v_min, v_max) for j in range(d)])
        
        global pbest
        pbest.append(pos[i])
        
        f = fitness(pos[i])
        if f < f_min_value:
            f_min_value = f
            f_min_index = i
            
    global gbest
    gbest = pos[f_min_index]
    
def PSO():
    
    global iters
    for i in range(iters):
        
        for j in range(n):
            
            global pos, v, pbest, gbest
            t_pos = np.array(pos[j])
            t_v = np.array(v[j])
            t_pbest = np.array(pbest[j])
            t_gbest = np.array(gbest)
            
            t_v = (0.5 * t_v + 2 * random.random() * (t_pbest - t_pos) + 
                  2 * random.random() * (t_gbest - t_pos))
            t_pos = t_pos + t_v
            
            global v_min, v_max
            t_v = np.clip(t_v, v_min, v_max)
            v[j] = list(t_v)
            
            global pos_min, pos_max
            t_pos = np.clip(t_pos, pos_min, pos_max)
            pos[j] = list(t_pos)
         
        for j in range(n):
            
            if fitness(pos[j]) < fitness(pbest[j]):
                pbest[j] = pos[j]
                
            if fitness(pos[j]) < fitness(gbest):
                gbest = pos[j]
                
        print('i:{}, gbest:{}, fitness:{}'.format(i, gbest, fitness(gbest)))
    
init()
PSO()

粒子群优化算法PSO

相关

标签