粒子群优化算法 Particle Swarm Optimization

xiaozongpeng · 发表于 2022-12-29 10:48

1. 起源 Origins

粒子群优化算法（PSO）是一种进化计算技术（evolutionary computation），1995年由 Eberhart 博士和 Kennedy 博士提出，源于对鸟群捕食的行为研究。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。粒子群算法在对动物集群活动行为观察基础上，利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得最优解。
Reynolds 提出了一个行为模型，其中每个 agent 都遵循三个规则：

Separation：如果每个 agent 离得太近，它们都会尝试远离其邻居。
Alignment：每个 agent 都转向其邻居的平均方向。
Cohesion：每个 agent 都试图走向其邻居的平均位置。

Eberhart 和 Kennedy 在一个简化的 Reynolds-like 模拟中包括了一个“roost（栖息地）”，以便：

每个 agent 都被吸引到 roost 的位置。
每个 agent 都“记住”了它离 roost 更近的地方。
每个 agent 与其邻居（最初是所有其他 agents）共享有关其离 roost 最近的位置的信息。

最终，所有agents 都“降落”在 roost。
2. 连续优化 Continuous optimization

连续优化问题可以表述如下：

寻找 X^* \subseteq X \subseteq \mathbb{R}^n 其中：
X^* = \underset{\textbf{x} \in X}{\arg\min} f(\textbf{x}) = \{\textbf{x}^* \in X \colon f(\textbf{x}^*) \le f(\textbf{x}) \quad \forall \textbf{x} \in X\}.
3. 基本算法 The basic algorithm

(1) 创建一个均匀分布在 X 上的 agents（particles）的“群体”；
(2) 根据目标函数评估每个 particle 的位置；
(3) 如果一个 particle 的当前位置优于其之前的最佳位置，则更新位置；
(4) 确定最佳 particle（根据 particle 刚才的最佳位置）；
(5) 根据以下条件更新 particles 的速度：  \textbf{v}_i^{t+1} = \textbf{v}_i^t + \phi_1\textbf{U}_1^t(\textbf{pb}_i^t - \textbf{x}_i^t) + \phi_2\textbf{U}_2^t(\textbf{gb}^t - \textbf{x}_i^t) .
(6) 根据以下条件将 particles 移动到新位置：  \textbf{x}_i^{t+1} = \textbf{x}_i^t + \textbf{v}_i^{t+1} .
(7) 转到第2步，重复进行直到满足停止条件。

\textbf{v}_i^t ：inertia（惯性，粒子的速度）
\phi_1\textbf{U}_1^t(\textbf{pb}_i^t - \textbf{x}_i^t) ：personal influence（个人影响）
\phi_2\textbf{U}_2^t(\textbf{gb}^t - \textbf{x}_i^t) ：social influence（社会影响）
\phi_1 ：cognitive coefficient（认知系数，权衡 particle 自身先前经验的重要性）
\phi_2 ：social coefficient（社会系数，权衡在 swarm 全局学习的重要性）
\textbf{U}_1^t ， \textbf{U}_2^t ：random value parameters with [0,1] range（增加随机性，避免过早收敛）
\textbf{pb} ：personal best
\textbf{gb} ：global best

4. 主要变体 Main variants

几乎所有的修改都在某种程度上改变了速度更新规则。
Different population topologies

每个 particle i 都有邻域 N_i。
\textbf{v}_i^{t+1} = \textbf{v}_i^t + \phi_1\textbf{U}_1^t(\textbf{pb}_i^t - \textbf{x}_i^t) + \phi_2\textbf{U}_2^t(\textbf{lb}_i^t - \textbf{x}_i^t) .

Inertia weight

\textbf{v}_i^{t+1} = \omega\textbf{v}_i^t + \phi_1\textbf{U}_1^t(\textbf{pb}_i^t - \textbf{x}_i^t) + \phi_2\textbf{U}_2^t(\textbf{gb}^t - \textbf{x}_i^t) .
1998年，Yuhui Shi和Russell Eberhart对基本粒子群算法引入了惯性权重（inertia weight） \omega ，并提出动态调整惯性权重以平衡收敛的全局性和收敛速度，该算法被称为标准PSO算法。

Time-decreasing inertia weight

它在1999年由 Shi 和 Eberhart 提出。
Canonical PSO

它是惯性权重变体的特例：
\textbf{v}_i^{t+1} = \chi[\textbf{v}_i^t + \phi_1\textbf{U}_1^t(\textbf{pb}_i^t - \textbf{x}_i^t) + \phi_2\textbf{U}_2^t(\textbf{gb}^t - \textbf{x}_i^t)] .
\chi ：constriction factor（伸缩因子，是固定值）
它在2002年被 Clerc 和Kennedy 提出之后有着极大的影响力。
Fully Informed PSO

一个 particle 被其邻域的每一个 particle 所吸引：
\textbf{v}_i^{t+1} = \chi[\textbf{v}_i^t + \sum_{p_k\in N_i}\phi_k\textbf{U}_k^t(\textbf{pb}_k^t - \textbf{x}_i^t)] .
Other variants

with dynamic neighborhood topologies
with enhanced diversity
with different velocity update rules
with components from other approches
for discrete optimization problems
...

5. 参数设置 Parameter selection

考虑一个 one-particle one-dimensional particle swarm。那么这个 particle 的速度更新规则为  \textbf{v}^{t+1} = a\textbf{v}^t + b_1\textbf{U}_1^t(\textbf{pb}^t - \textbf{x}^t) + b_2\textbf{U}_2^t(\textbf{gb}^t - \textbf{x}^t) .
令
E[U_*^t(0, 1)] = \frac{1}{2}, \\ b = \frac{b_1+b_2}{2}, \\ pb^{t+1} = pb^{t+1}, gb^{t+1} = gb^{t}, \\ r = \frac{b_1}{b_1+b_2}pb^{t} + \frac{b_1}{b_1+b_2}gb^{t}.
那么  v^{t+1} = av^t + b(r - x^t)  该系统将根据a，b的值以不同的方式运行：

一些例子：

选择特定变体或参数集时要考虑：

问题的特征（“模态”、搜索范围、维度等）
可用搜索时间（wall clock time或function evaluations）
定义满意的解的solution quality threshold

6. 实例 Example

import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm我们选取Eggholder Function
f(\textbf{x}) = -(x_2+47)\sin(\sqrt{\left|\frac{x_1}{2} + (x_2 + 47)\right|}) - x_1\sin(\sqrt{\left|x_1 - (x_2 + 47)\right|}) .
x_i\in[-512, 512], for all i = 1, 2.
Global minimum：
f(\textbf{x}^*) = -959.6407 , at \textbf{x}^* = (512, 404.2319).
def eggholder(x):
f = -(x[1] + 47) * np.sin(np.sqrt(abs(x[0] / 2 + (x[1] + 47)))) - x[0] * np.sin(
      np.sqrt(abs(x[0] - (x[1] + 47))))
return f

x = np.mgrid[-512:512:512j, -512:512:512j]
ax = plt.subplot(111, projection=&#34;3d&#34;)
ax.set_title(&#34;Eggholder Function&#34;)
ax.plot_surface(x[0], x[1], eggholder(x), rstride=1, cstride=1, cmap=cm.jet)

plt.show()

class Particle:
def __init__(self, pos_max, vel_max):
      self.pos_max = pos_max
      self.vel_max = vel_max

      self.pos = np.random.uniform(-pos_max, pos_max, 2)
      self.pb = self.pos
      self.pb_value = eggholder(self.pb)
      self.vel = np.random.uniform(-vel_max, vel_max, 2)

def get_pos(self):
      return self.pos

def get_pb(self):
      return self.pb

def get_pb_value(self):
      return self.pb_value

def get_vel(self):
      return self.vel

def set_pos(self, pos):
      self.pos = pos

def set_pb(self):
      pos_value = eggholder(self.pos)
      if pos_value < self.pb_value:
         self.pb = self.pos
         self.pb_value = pos_value

def set_vel(self, vel):
      self.vel = vel
class PSO:
def __init__(self, population, vel_max, pos_max, phi_1, phi_2, iter_num):
      self.population = population
      self.vel_max = vel_max
      self.pos_max = pos_max
      self.phi_1 = phi_1
      self.phi_2 = phi_2
      self.iter_num = iter_num
      self.w = np.linspace(.4, .9, iter_num)
      self.w = np.flipud(self.w)

      self.gb = 0
      self.gb_value = 0
      self.gb_values = np.ones(iter_num)

      self.particles = [Particle(pos_max, vel_max) for i in range(population)]

def evaluate(self, particles):
      for p in particles:
         p.set_pb()
         if self.gb_value > p.get_pb_value():
            self.gb_value = p.get_pb_value()
            self.gb = p.get_pb()

def update_vel(self, particles, w):
      for p in particles:
         new_vel = w * p.get_vel() + self.phi_1 * np.random.random() * (
                  p.get_pb() - p.get_pos()) + self.phi_2 * np.random.random() * (self.gb - p.get_pos())
         new_vel[new_vel > self.vel_max] = self.vel_max
         new_vel[new_vel < -self.vel_max] = -self.vel_max
         p.set_vel(new_vel)

def update_pos(self, particles):
      for p in particles:
         new_pos = p.get_pos() + p.get_vel()
         new_pos[new_pos > self.pos_max] = self.pos_max
         new_pos[new_pos < -self.pos_max] = -self.pos_max
         p.set_pos(new_pos)

def update(self):
      for i in range(self.iter_num):
         self.evaluate(self.particles)
         self.update_vel(self.particles, self.w)
         self.update_pos(self.particles)
         self.gb_values = self.gb_value

      plt.plot(range(self.iter_num), self.gb_values)
      plt.show()

      return self.gb, self.gb_value
p = PSO(population=100, vel_max=50.0, pos_max=512.0, phi_1=1.4995,
      phi_2=1.4995, iter_num=100)
p.update()

(array([512. , 404.23180522]), -959.6406627208507)

		自动登录	找回密码
密码			立即注册

粒子群优化算法 Particle Swarm Optimization

本帖子中包含更多资源