PSO粒子群算法的Python实现 | Build Knowledge Together

嘿嘿，前一阵参加的一个建模比赛，在队友的带领下拿了一个二等奖。其中用到了粒子群优化算法，趁这个机会讲解一下。

0. 背景

粒子群优化（Particle Swarm Optimization, PSO），又称粒子群算法，由 J. Kennedy 和 R. C. Eberhart 等于 1995 年开发的一种演化计算技术。粒子群算法的灵感来源于鸟类的捕食行为：鸟群中的每个个体在搜捕食物的过程中，互相传递、共享位置信息，从而找到该区域内的最大食物源，并使得整个种群聚集在该食物源周围。PSO 算法是基于群体的，根据对环境的适应度将群体中的个体移动到目标的区域，PSO 将每个个体看作是维搜索空间中的一个的微粒，在搜索空间中以一定的速度飞行（探索），这个速度根据它本身几周围粒子的反馈而调整。动态调整方程为：

其中表示更新速度，为自身权重因子，和为学习因子，为种群的评估值，为个体 i 当前的最优值(pbest), 为当前的全局最优值(gbest).

1. 算法流程

PSO算法的核心即为利用种群中的个体对信息的共享从而在求解范围内找到最优解。PSO算法的基本流程如下图所示：

初始化一群粒子（种群大小为 m），并随机化每个粒子的位置和速度；
评价每个微粒的适应度（目标函数）；
对每个微粒，将它当前迭代的适应值和 pbest 作比较，如果较好，则将其作为当前 pbest 并记录位置；
对每个微粒，将它的适应值和 gbest 作比较，如果较好，则将其作为当前 gbest 并记录位置；
根据公式变化微粒的速度和位置；
回到（2）进入下一次迭代直到迭代结束。

2. 代码实现

import random
from abc import abstractmethod
from typing import List

import numpy as np


class PSO:

    def __init__(self, epochs, pop_size, var_num, bound: List[List]):
        self.epochs = epochs
        self.pop_size = pop_size
        self.var_num = var_num
        self.bound = bound

        self.pop_x = np.zeros((self.pop_size, self.var_num))  # res
        self.pop_v = np.zeros((self.pop_size, self.var_num))  # v

        # self.p_best = np.random.uniform(self.pop_size, self.var_num)
        self.p_best = np.zeros((self.pop_size, self.var_num))
        self.g_best = np.zeros((1, var_num))

        tmp = float("-inf")
        for i in range(self.pop_size):
            for j in range(self.var_num):
                self.pop_x[i][j] = random.uniform(self.bound[0][j], self.bound[1][j])
                self.pop_v[i][j] = random.uniform(0, 1)
            self.p_best[i] = self.pop_x[i]  # 储存最优的个体
            fit = self.evaluate(self.p_best[i])
            if fit > tmp:
                self.g_best = self.p_best[i]
                temp = fit

    @abstractmethod
    def evaluate(self, vals):
        return vals

    def _update_func(self, w, c1, c2, xi, vi, pi, pg):
        return w * vi + \
               c1 * random.uniform(0, 1) * (pi - xi) + \
               c2 * random.uniform(0, 1) * (pg - xi)

    def update(self):
        c1 = 2  # 学习因子，一般为2
        c2 = 2
        w = 0.4  # 自身权重因子
        for i in range(self.pop_size):
            # 更新速度
            self.pop_v[i] = self._update_func(w, c1, c2, self.pop_x[i], self.pop_v[i], self.p_best[i], self.g_best)
            # 更新位置
            self.pop_x[i] = self.pop_x[i] + self.pop_v[i]
            # 越界保护
            for j in range(self.var_num):
                if self.pop_x[i][j] < self.bound[0][j]:
                    self.pop_x[i][j] = self.bound[0][j]
                if self.pop_x[i][j] > self.bound[1][j]:
                    self.pop_x[i][j] = self.bound[1][j]
            # 更新p_best和g_best
            if self.evaluate(self.pop_x[i]) > self.evaluate(self.p_best[i]):
                self.p_best[i] = self.pop_x[i]
            if self.evaluate(self.pop_x[i]) > self.evaluate(self.g_best):
                self.g_best = self.pop_x[i]

    def run(self):
        hist = []
        self.ng_best = np.zeros((1, self.var_num))[0]
        for gen in range(self.epochs):
            self.update()
            print('############ Generation {} ############'.format(str(gen + 1)))
            if self.evaluate(self.g_best) > self.evaluate(self.ng_best):
                self.ng_best = self.g_best.copy()
            print('最好的位置：{}'.format(self.ng_best))
            print('最大的函数值：{}'.format(self.evaluate(self.ng_best)))
            hist.append(self.ng_best)
        return hist

3. 应用实例

假设现有问题：求解。那目标函数可以写为

import math
    
    class SqrtTwo(PSO):
        def evaluate(self, vals):
            return 1 - math.fabs(vals[0] ** 2 - 2)


    ans = SqrtTwo(epochs=100, pop_size=100, var_num=1, bound=[[1], [2]])
    hist = ans.run()
    print("---- End of (successful) Searching ----")

运行结果

############ Generation 1 ############
最好的位置：[1.41131529]
最大的函数值：0.9918108382688424
############ Generation 2 ############
最好的位置：[1.41131529]
最大的函数值：0.9918108382688424
############ Generation 3 ############
最好的位置：[1.41446544]
最大的函数值：0.9992875061077915
...
...
...
############ Generation 99 ############
最好的位置：[1.41421356]
最大的函数值：0.9999999999999996
############ Generation 100 ############
最好的位置：[1.41421356]
最大的函数值：0.9999999999999996

训练曲线

4. 参考资料

粒子群优化-维基百科
Python手把手构建粒子群算法（PSO）实现最优化搜索-代码参考