群体智能：用Python编码和可视化粒子群优化

2023-01-28 14:12 946 阅读 ID：732
磐创AI
磐创AI
主页

如果你正在训练一个具有随机梯度下降和反向传播的深度学习模型，并且无法摆脱局部极小值，那么本文可能会帮助你找到解决问题的替代方法。

群体是一组媒介或有机体；群体智能可以定义为群体的社会行为，其中自主个体以分散和自我组织的方式相互作用。个体之间的交互提高了关于环境的经验知识，并使群体达到最佳状态。

我们可以在自然界中观察到这种智力。例如，已知蚂蚁能找到从蚁群到食物来源的最短路径。

一开始，个体探索往返目的地的不同方向。当找到一条有利的路径时，蚂蚁会在路径上标记信息素，信息素是蚂蚁沉积在地面上的化学物质。当更多的蚂蚁走同一条路时，信息素会加强，吸引更多的蚂蚁。因此，大多数蚂蚁都会跟随并收敛到最短的路径。

有一些模仿群体智能的自然启发算法。蚁群算法（ACO）源自蚂蚁。人工蜂群（ABC）的灵感来自蜂巢周围蜂群的蜜蜂。这篇文章是关于粒子群优化（PSO）的，这是由鸟群和鱼群暗示的。

PSO最初是由詹姆斯·肯尼迪（James Kennedy）和罗素·埃伯哈特（Russell Eberhart）于1995年提出的。他们假设信息的社会共享将为群体提供优势。

当资源的分布超出预期时，鱼类学校的个别成员可以从其他成员的发现和经验中获益，而不是争夺食物。关键词是“社会互动”。社会行为提高了个体的适应能力；因此，群体中出现了智能。个体的适应性与集体智力是相互关联的。

PSO算法简单。粒子是搜索空间中的许多简单实体。我们创建了一个粒子群，并用问题的目标函数测量它们的个体适合度。然后根据粒子的个体最佳位置和迄今为止粒子群的最佳位置，将粒子从当前位置移动到下一个位置。通过迭代这些移动，群在几代之后逐渐达到目标函数的最优点。

一些符号：

  • 粒子数量：i
  • 维度数量：n
  • 适应度函数：f(x_i)
  • 粒子：x_i = (x_i1, x_i2, …, x_in)
  • 当前速度：v_i = (v_i1, v_i2, …, v_in)
  • 单个粒子的最佳：p_i = (p_i1, p_i2, …, p_in)
  • 全局粒子的最佳值：p_g = (p_g1, p_g2, …, p_gn)
  • 惯性分量：w * v_i(t)
  • 认知成分：c_1 * r_1 * (p_i - x_i(t))
  • 社会成分：c_2 * r_2 * (g_i - x_i(t))
  • 速度调节：v_i(t+1) <- Inertia+Cognitive+Social
  • 位置调整：x_i(t+1) <- x_i(t)+v_i(t+1)

速度调整受三个因素影响：先前的速度（惯性分量）、单个粒子的最佳位置（认知分量）和群的最佳位置。

速度是一个运动粒子向给定方向运动的速度。粒子在每个方向上的移动都受这些权重的影响。

系数w称为惯性权重，惯性权重是使粒子保持与前一代相同方向运动的力。c1和c2是恒定加速度值，其中，[1]在原始算法中应用了c1=c2。r1和r2表示超参数，它们会引起一些随机扰动。这些参数值的值越大，粒子的移动越灵敏。

我们还假设在我们的例子中，适应度函数是用于最小化问题的。因此，当f（x_i）<f（p_i）时，单个粒子的最佳位置p_i被x_i覆盖。

PSO算法如下：

1.初始化粒子填充数组x_i

2.开始循环

3.对于每个粒子，使用适应度函数f（xi）

4.将当前适合度值与其最佳p_i进行比较。用当前值x_i替换最佳值如果它比最好的好。

5.检查群的最佳粒子并将最佳数组分配给全局最佳pg。

6.计算速度v_i（t+1）并更新x_i的粒子（t+1）

7.如果满足标准，则退出循环。

8.结束循环

让我们将算法转换为Python代码。为了可视化粒子的运动，我们可以将粒子的维度简化为2，x和y。

1.导入库

import random
import numpy as np
from matplotlib import pyplot as plt
from matplotlib import animation

2.定义适应度函数

我们使用函数：f(x,y)=(x-2y+3)^2+(2x+y-8)^2。此函数的全局最小值为0。所有粒子都应该从随机点移动到x和y坐标的最佳位置，此处的值接近0。

# Fitness function
# We assume the problem can be expressed by the following equation: 
# f(x1,x2)=(x1+2*-x2+3)^2 + (2*x1+x2-8)^2
# The objective is to find a minimum which is 0

def fitness_function(x1,x2):
  f1=x1+2*-x2+3
  f2=2*x1+x2-8
  z = f1**2+f2**2
  return z

3.更新速度

我们应用r1、r2和w的随机值。c1和c2在0.1时的值较小。可以安排惯性值，从0.9开始，逐渐减少到0.4。

在我们的例子中，我们生成了最小0.5和最大1的正态分布，并根据[3]的实验，在每一代随机选择一个值。

def update_velocity(particle, velocity, pbest, gbest, w_min=0.5, max=1.0, c=0.1):

  # Initialise new velocity array
  num_particle = len(particle)
  new_velocity = np.array([0.0 for i in range(num_particle)])

  # Randomly generate r1, r2 and inertia weight from normal distribution
  r1 = random.uniform(0,max)
  r2 = random.uniform(0,max)
  w = random.uniform(w_min,max)
  c1 = c
  c2 = c

  # Calculate new velocity
  for i in range(num_particle):
    new_velocity[i] = w*velocity[i] + c1*r1*(pbest[i]-particle[i])+c2*r2*(gbest[i]-particle[i])
  return new_velocity

4.更新位置

如算法所述，新位置是当前位置和速度的总和。

def update_position(particle, velocity):
  # Move particles by adding velocity
  new_particle = particle + velocity
  return new_particle

5.PSO的主要功能

首先，我们初始化粒子，它们的最佳位置、速度和适应度。我们还根据粒子的初始位置设置全局最佳位置。然后我们一代一代地循环。当算法达到最大生成次数或成功标准时应停止。在我们的例子中，它是指平均适合度值超过特定值。

def pso_2d(population, dimension, position_min, position_max, generation, fitness_criterion):
  # Initialisation
  # Population
  particles = [[random.uniform(position_min, position_max) for j in range(dimension)] for i in range(population)]

  # Particle's best position
  pbest_position = particles

  # Fitness
  pbest_fitness = [fitness_function(p[0],p[1]) for p in particles]

  # Index of the best particle
  gbest_index = np.argmin(pbest_fitness)

  # Global best particle position
  gbest_position = pbest_position[gbest_index]

  # Velocity (starting from 0 speed)
  velocity = [[0.0 for j in range(dimension)] for i in range(population)]

  # Loop for the number of generation
  for t in range(generation):

    # Stop if the average fitness value reached a predefined success criterion
    if np.average(pbest_fitness) <= fitness_criterion:
      break
    else:
      for n in range(population):

        # Update the velocity of each particle
        velocity[n] = update_velocity(particles[n], velocity[n], pbest_position[n], gbest_position)

        # Move the particles to new position
        particles[n] = update_position(particles[n], velocity[n])

    # Calculate the fitness value
    pbest_fitness = [fitness_function(p[0],p[1]) for p in particles]

    # Find the index of the best particle
    gbest_index = np.argmin(pbest_fitness)

    # Update the position of the best particle
    gbest_position = pbest_position[gbest_index]

  # Print the results
  print('Global Best Position: ', gbest_position)
  print('Best Fitness Value: ', min(pbest_fitness))
  print('Average Particle Best Fitness Value: ', np.average(pbest_fitness))
  print('Number of Generation: ', t)

6.设置参数值并运行算法

population = 100
dimension = 2
position_min = -100.0
position_max = 100.0
generation = 400
fitness_criterion = 10e-4

我们创建了100个粒子，其中的位置随机放置在x和y坐标处，范围在-100到100之间。由于函数采用x和y，因此粒子的位置是二维的。成功标准为0.001或更低。如果符合标准，该程序应在第400代之前停止。

通过使用上述配置运行算法，我们获得了以下结果：

Global Best Position:  [2.60008033 2.799968  ]
Best Fitness Value:  3.7383573411040855e-08
Average Particle Best Fitness Value:  0.0009671024787191154
Number of Generations:  68

由于其随机性，每次运行程序时，结果都会发生变化。第68代才达到成功标准。最佳粒子到达位置x≈2.6和y≈2.8，其中适应度函数返回全局最小值。

如果我们能够可视化粒子的运动，而不是将结果写在文本中，那将更具洞察力。

7.Matplotlib绘图和动画

# Plotting prepartion
fig = plt.figure(figsize=(10, 10))
ax = fig.add_subplot(111, projection='3d')
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('z')
x = np.linspace(position_min, position_max, 80)
y = np.linspace(position_min, position_max, 80)
X, Y = np.meshgrid(x, y)
Z= fitness_function(X,Y)
ax.plot_wireframe(X, Y, Z, color='r', linewidth=0.2)

# Animation image placeholder
images = []

# Add plot for each generation (within the generation for-loop)
    image = ax.scatter3D([
                          particles[n][0] for n in range(population)],
                         [particles[n][1] for n in range(population)],
                         [fitness_function(particles[n][0],particles[n][1]) for n in range(population)], c='b')
    images.append([image])

# Generate the animation image and save
animated_image = animation.ArtistAnimation(fig, images)
animated_image.save('./pso_simple.gif', writer='pillow')

绘制函数的线框有助于查看全局最小值的位置。下面是同一示例的输出。

在第一代中，粒子是散射的。它们很快地向网格底部移动，看起来算法正在按预期工作。我们可以通过改变适应度函数和超参数（如惯性权重w和认知和社会系数（c1和c2））来进行更多实验，以优化算法。

群体智能（如PSO）是一类元启发式算法，被认为可以在合理的计算时间内找到复杂优化问题的近似最优解。如果我们将该算法应用于训练神经网络，这将特别有用。好处是双重的：全局搜索和并行化。

我们可以将每个粒子转换为表示神经元之间权重的n维数组。正如我们在动画gif中看到的那样，每个粒子都以不同的方向移动。与局部搜索最优点的反向传播学习算法不同，粒子群优化算法可以同时探索多组不同的权重参数，从而有助于避免到达局部最小值的路径。

此外，适应度函数与网络拓扑无关；评估每个粒子适合度的计算可以并行进行。

本文用一个简单的代码探索了粒子群优化算法，以了解其机制。如果你对ML的PSO应用程序感兴趣，我强烈建议你阅读以下关于将机器学习集成到各种元启发式的文章。

https://www.sciencedirect.com/science/article/pii/S0377221721003623

参考文献：

[1] J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proceedings of ICNN’95 — International Conference on Neural Networks.

[2] Poli, R., Kennedy, J. & Blackwell, T. Particle swarm optimization. Swarm Intell 1, 33–57 (2007). https://doi.org/10.1007/s11721-007-0002-0

[3] R. Eberhart and Yuhui Shi, “Particle swarm optimization: Developments, applications and resources,” Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. №01TH8546), Aug. 2002.

感谢阅读！

 收起内容
免责声明：作者保留权利，不代表本站立场。如想了解更多和作者有关的信息可以查看页面右侧作者信息卡片。
    快抢沙发！
      加载更多评论
    反馈
    to-top--btn