如果你正在训练一个具有随机梯度下降和反向传播的深度学习模型,并且无法摆脱局部极小值,那么本文可能会帮助你找到解决问题的替代方法。
群体是一组媒介或有机体;群体智能可以定义为群体的社会行为,其中自主个体以分散和自我组织的方式相互作用。个体之间的交互提高了关于环境的经验知识,并使群体达到最佳状态。
我们可以在自然界中观察到这种智力。例如,已知蚂蚁能找到从蚁群到食物来源的最短路径。
一开始,个体探索往返目的地的不同方向。当找到一条有利的路径时,蚂蚁会在路径上标记信息素,信息素是蚂蚁沉积在地面上的化学物质。当更多的蚂蚁走同一条路时,信息素会加强,吸引更多的蚂蚁。因此,大多数蚂蚁都会跟随并收敛到最短的路径。
有一些模仿群体智能的自然启发算法。蚁群算法(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.
感谢阅读!