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

2023-01-28 14:12 498 阅读 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