粒子群算法学习

urlyy
  2023-06-24 15:53:48 2023-06-24 15:53:48 创建   2023-06-30 04:22:28 2023-06-30 04:22:28 更新   

粒子群算法是一门新兴算法，此算法与遗传算法有很多相似之处，其收敛于全局最优解的概率很大。

  1. 相较于传统算法计算速度非常快，全局搜索能力也很强：
  2. PSO对于种群大小不十分敏感，所以初始种群设为500-1000，速度影响也不大
  3. 粒子群算法适用于连续函数极值问题，对于非线性、多峰问题均有较强的全局搜索能力。

他的问题主要在于容易产生早熟收敛（尤其是在处理复杂的修峰搜索问题中）、局寻优能力较差等。PSO算法
陷入局最小，主要归咎于种群在搜索空间中多样性的丢失。

  graph TD;
    START[粒子规模和位置和速度的初始化]-->A[计算适应度]
    A-->B[计算个体最优值和群体最优值];
    B-->C[更新速度和更新位置];
    C-->D[更新适应度函数];
    D-->E[更新个体最优值和群体最优值]
    E-->F{满足条件?}
    F-->|N|B
    F-->|Y|G(输出最优解)

假设求解下面函数的最优解

$$
\begin{array}{c}
\min f(x) = \sum_{i=1}^{3}[100(x_{i+1}-x_i^2)^2+(x_i-1)^2] \
x_i \in -30,30
\end{array}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from matplotlib import pyplot as plt
import random
import numpy as np


# 题目给出的函数
def fitness_fun(pos):
    return sum(100*(pos[0][1:] - pos[0][:-1])**2 + (1-pos[0][:-1])**2)


class PSO:
    # 粒子
    class Particle:
      def __init__(self,x_max,v_max,dim):
        # dim维的向量
        self.pos = np.random.uniform(-x_max,x_max,(1,dim))
        self.v = np.random.uniform(-v_max,v_max,(1,dim))
        # 记录一下个体历史最优解
        self.best_pos = np.zeros((1,dim))
        self.best_fitness = fitness_fun(self.pos)

    def __init__(self,x_max,v_max,dim,particle_num,iter_num,tol,c1=2,c2=2,w=1):
        self.x_max = x_max
        self.v_max = v_max
        self.dim = dim
        self.particle_num = particle_num
        self.iter_num = iter_num
        # 循环退出条件
        self.tol=tol
        # 三个超参数，虽然定值可以，但前期c1大、后期c2大更好
        self.c1=c1
        self.c2=c2
        # 惯性权重
        self.w=w
        # 记录全局历史最优解
        self.best_pos = np.zeros((1,dim))
        self.best_fitness = fitness_fun(self.best_pos)
        self.fitness_val_list = []
        self.__particles = [PSO.Particle(x_max,v_max,dim) for i in range(particle_num)]
        # 最优解是求最小值的情况
        self.operator = lambda _new,_old:_new<_old

    def __update_pos(self,p:Particle):
        r1 = np.random.rand()
        r2 = np.random.rand()
        # 更新速度，就是三个向量相加，自己的惯性+朝个体历史最优解+朝全局历史最优解
        p.v = self.w * p.v + self.c1*r1*(p.best_pos - p.pos) + self.c2*r2*(self.best_pos - p.pos)
        # 超出最值的算作最值
        p.v[p.v > self.v_max] = self.v_max
        p.v[p.v < -self.v_max] = -self.v_max
        # 更新位置
        p.pos = p.pos + p.v
        fitness = fitness_fun(p.pos)
        # 更新个体和全局的当前最优解
        if self.operator(fitness,p.best_fitness):
            p.best_fitness = fitness
            p.best_pos = p.pos
        if self.operator(fitness,self.best_fitness):
            self.best_fitness = fitness
            self.best_pos = p.pos


    def run(self):
        for iter in range(self.iter_num):
            for p in self.__particles:
                self.__update_pos(p)
            self.fitness_val_list.append(self.best_fitness)
            if self.operator(self.best_fitness,self.tol):
                break


if __name__ == '__main__':
    pso = PSO(x_max=30, v_max=60,dim=4, particle_num=8, iter_num=7000,  tol=1e-4)
    pso.run()
    print("最优位置:" + str(pso.best_pos))
    print("最优解:" + str(pso.fitness_val_list[-1]))
    plt.plot(range(len(pso.fitness_val_list)), pso.fitness_val_list, alpha=0.5)
    plt.show()
  • w惯性因子，值为非负。w越大，全局寻优能力越强，同时局部寻优能力越弱。动态w可以获得更好的寻优结果。
    • 所以一般一开始w设置较大，取全局搜索。然后越到后面就减少w进行专注的局部搜索。
    • 采用较多的是线性递减权值(LDW)策略，即$w_{t}=(w_{start}-w_{end})(G_k-g)/G_k+w_{end}，G_k是总迭代次数，w_{start}和w_{end}是最初和最后的惯性权值,g应该是当前迭代次数$
  • 粒子群算法的全局版和局部版：全局就是参考了全局最优值，局部就是只考虑了邻域最优值。局部越往后邻域越大，就变为全局的了。全局收敛快但容易陷入全局最优，局部收敛慢但不容易陷入全局最优
  • 至于局部版取邻域的方法，有按照粒子编号和当前领域大小确定、按照粒子的欧式距离取邻域

注意该算法在解决具体问题时需要注意以下几点：

  1. 种群大小m
    m很小很容易陷入局部最优，m很大，pso的优化能力很好，当种群数目增长至一定水平时，再增长将不再有显著的作用。
  2. 权重因子
    对于粒子的速度更新的三部分：
    a. 惯性因子w=1表示基本的粒子群算法，w=0表示失去对粒子本身的速度记忆。
    b. 自我认知部分的学习因子c1=0表示无私型的粒子群算法，只有社会，没有自我，这样会使群体丧失多样性，从而容易导致陷入局部最优而无法跳出。
    c. 社会经验部分的学习因子c2=0表示自我型的粒子群算法，只有自我没有社会，这样导致没有信息的社会共享，算法收敛速度缓慢。
    这三个参数的选择非常重要，如何调整这三个参数使算法避免早熟又可以比较快的收敛，对于解决实际问题意义较大。
  3. 最大速度
    速度限制的作用为：维护算法的探索能力与开发能力的平衡。
    vm较大时，探索能力强，但是粒子容易飞过最优解
    vm较小时，开发能力强，但是容易陷入局部最优解
    vm一般设定为每维变量变化范围的10%~20%
  4. 停止准则
    a. 最大迭代次数
    b. 可以接受的满意解（通过fitness function判断是否满意）
  5. 粒子空间的初始化
    较好地选择粒子的初始化空间，将大大缩短收敛时间．初始化空间根据具体问题的不同而不同，根据具体问题进行设定． 该算法为数不多的关键参数的设置却对算法的精度和效率有
    着显著影响．
  • 标题: 粒子群算法学习
  • 作者: urlyy
  • 创建于 : 2023-06-24 15:53:48
  • 更新于 : 2023-06-30 04:22:28
  • 链接: https://urlyy.github.io/2023/06/24/粒子群算法简单学习/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
此页目录
粒子群算法学习