【优化算法】粒子群优化算法简介

这里是引用

1. 简介

人工智能是计算机科学的一个大领域&＃xff0c;它模拟计算机中的智能行为。在此基础上&＃xff0c;提出了一种基于元启发式&＃xff08; metaheuristic&＃xff09;的粒子群优化算法来模拟鸟类觅食、鱼群移动等。这种算法能够模拟群体的行为&＃xff0c;以便迭代地优化数值问题。例如&＃xff0c;它可以被分类为像蚁群算法、人工蜂群算法和细菌觅食这样的群体智能算法。

J. Kennedy 和 R.Eberhart 在1995年提出的粒子群优化&＃xff08;Particle Swarm Optimization&＃xff0c;PSO&＃xff09;变得非常流行&＃xff0c;它是一种基于随机优化&＃xff08;Stochastic Optimization&＃xff09;的强大算法&＃xff0c;受鸟群中的规则启发&＃xff0c;连续优化过程允许多目标和更多的变化。该方法包括不断寻找最佳解&＃xff0c;以每次迭代计算的一定速度移动粒子&＃xff08;在这种情况下表示为位置 $(x\&＃xff0c;y)$&＃xff09;。每个粒子的运动都有其自身的影响&＃xff0c;最著名的位置也是空间搜索中最著名的位置。最终期望的结果是粒子群收敛到最优解。重要的是要提到粒子群算法不使用梯度下降&＃xff0c;所以它可以用于非线性问题&＃xff0c;只要它不要求问题必须是可微的。

C&＃43;&＃43;/Python代码可参考该仓库。

2. 涌现复杂性

涌现复杂性&＃xff08;Emergent Complexity&＃xff09;是一种现象&＃xff0c;描述了大群体的各个组成部分如何以相同但更简单的规则一起工作&＃xff0c;以创建多样而复杂的系统。有一些自然的复杂行为可以作为涌现的例子。例如&＃xff0c;蚂蚁本能地相互交流&＃xff0c;以建立一个活的桥梁&＃xff0c;在寻找食物来源时最小化交换距离&＃xff08;Video&＃xff09;。鸟类相互跟随&＃xff0c;形成更大的群体&＃xff0c;这增加了它们发现捕食者和食物来源的可能性。不像通常的复杂性&＃xff08;complexity&＃xff09;概念&＃xff0c;它不一定有用&＃xff0c;自然复杂性&＃xff08;natural complexity&＃xff09;是一百万年自然选择过程的结果&＃xff0c;在这个过程中&＃xff0c;能源的使用是增加生存机会的最重要因素。因此&＃xff0c;如果同一个问题有两个解决方案&＃xff0c;更简单、需要更少能量的方法将因自然选择而存在。这就是为什么大自然建议的解决方案会很简单&＃xff0c;但仍然能有效地尽可能减少动物的能量消耗。因此&＃xff0c;科学家们分别观察了一群欧椋鸟&＃xff08;starlings&＃xff0c;八哥&＃x1f638;&＃xff09;中的每只鸟&＃xff0c;发现它们中的每只都采取简单的行动来形成复杂的结构。

• 每只鸟都有自己的位置和速度&＃xff1b;
• 每只鸟都有自己的视野&＃xff0c;可以跟随周围的鸟。这只鸟完全不知道超出此范围的动作。
• 如果有任何鸟类发现食物&＃xff0c;则该群中的所有鸟类都将趋向该方向。

3. 鸟群智能建模

在自然界中&＃xff0c;在一个数值问题中&＃xff0c;任何boid&＃xff08;类似鸟的物体&＃xff09;的可观察到的邻近区域都被限制在一定的范围内。因此&＃xff0c;它可以收敛到一些局部极小值&＃xff08;minima&＃xff09;或鞍点&＃xff08;saddle point&＃xff09;&＃xff0c;其中梯度&＃xff08;在该情况下对应的是速度&＃xff09;将为0。然而&＃xff0c;拥有一个以上的boid可以让鸟群中的所有鸟关注到误差函数的更大范围&＃xff0c;并且如果它们中的任何一只在误差方面看到了更好的位置&＃xff0c;就不会陷入局部极小值。对上述原则进行数学建模&＃xff0c;使群体找到误差函数的全局最小值。

• 每个boid都有自己的位置和速度。我们可以把速度看作误差函数的偏导数的向量。
• 每个boid都记录了它所经历过的最佳位置&＃xff0c;这在一定程度上影响了boid的当前速度。
• 这将是整群鸟见过的最好的位置。因此&＃xff0c;它会以预定的速率影响所有boid的速度。

通过使用上述规则&＃xff0c;我们可以轻松得出将驱动每个boid的数学方程式。

在以上等式中&＃xff1a;

• $w$&＃xff1a;表示惯性&＃xff0c;决定了boid的当前速度对 $\Delta V$ 的影响程度&＃xff1b;
• c1,c2c_1, c_2c1​,c2​&＃xff1a;定义了boid和swarm的最佳记录位置&＃xff08;best-recorded position&＃xff09;将如何分别影响 $\Delta V$&＃xff1b;

w,c1,c2,learningRatew, c_1, c_2, learningRatew,c1​,c2​,learningRate 是在优化过程中应微调的超参数。

粒子群优化算法伪代码&＃xff1a;

其中&＃xff1a;

• Vi(k&＃43;1)V_i(k&＃43;1)Vi​(k&＃43;1) 是下一个迭代速度&＃xff1b;
• $W$ 是惯性参数。该参数影响最后速度值给定的运动传播。
• C1,C2C_1, C_2C1​,C2​ 是加速度系数。 C1C_1C1​ 赋予个体最佳值的重要性&＃xff0c;而 C2C_2C2​ 则代表群体最佳值的重要性。
• PiP_iPi​是个体最佳位置&＃xff0c;PgP_gPg​ 是群体最佳位置。在方程式中&＃xff0c;衡量了每个参数到粒子实际位置的距离。
• rand1rand_1rand1​ 和 rand2rand_2rand2​ 是随机数&＃xff0c;其中 $0\le rand\le 1$&＃xff0c;它们控制每个值的影响&＃xff1a;群体和个体&＃xff0c;如下所示。
  

4. 代码实现

使用Python来实现对群体智能背&＃xff08;swarm intelligence&＃xff09;后的数学理论进行了讨论和建模。为了测试算法&＃xff0c;Rastrigin函数将被用作误差函数&＃xff0c;这是优化问题中最具挑战性的函数之一。在平面上有很多余弦振荡会引入无数的局部极小值&＃xff0c;在这些极小值中&＃xff0c;boid会卡住。&＃xff08;图自&＃xff1a;Source&＃xff09;

import numpy as npdef error(current_pos):x &＃61; current_pos[0]y &＃61; current_pos[1]return (x ** 2 - 10 * np.cos(2 * np.pi * x)) &＃43; \(y ** 2 - 10 * np.cos(2 * np.pi * y)) &＃43; 20def grad_error(current_pos):x &＃61; current_pos[0]y &＃61; current_pos[1]return np.array([2 * x &＃43; 10 * 2 * np.pi * x * np.sin(2 * np.pi * x),2 * y &＃43; 10 * 2 * np.pi * y * np.sin(2 * np.pi * y)])


如上所述&＃xff0c;每个boid都将具有位置&＃xff0c;速度&＃xff0c;误差&＃xff0c;最佳位置和已知误差&＃xff08;best-known error&＃xff09;。我们还应该编写一个setter函数来在需要时修改参数。

class Particle:def __init__(self, dim, minx, maxx):self.position &＃61; np.random.uniform(low&＃61;minx, high&＃61;maxx, size&＃61;dim)self.velocity &＃61; np.random.uniform(low&＃61;minx, high&＃61;maxx, size&＃61;dim)self.best_part_pos &＃61; self.position.copy()self.error &＃61; error(self.position)self.best_part_err &＃61; self.error.copy()def setPos(self, pos):self.position &＃61; posself.error &＃61; error(pos)if self.error < self.best_part_err:self.best_part_err &＃61; self.errorself.best_part_pos &＃61; pos


粒子群算法类将由误差函数表面上的移动粒子列表组成。要初始化函数&＃xff0c;需要函数的维数、boids的数量以及纪元的数量。

class PSO:w &＃61; 0.729c1 &＃61; 1.49445c2 &＃61; 1.49445lr &＃61; 0.01def __init__(self, dims, numOfBoids, numOfEpochs):self.swarm_list &＃61; [self.Particle(dims, -500, 500) for i in range(numOfBoids)]self.numOfEpochs &＃61; numOfEpochsself.best_swarm_position &＃61; np.random.uniform(low&＃61;-500, high&＃61;500, size&＃61;dims)self.best_swarm_error &＃61; 1e80 # Set high value to best swarm error


最后&＃xff0c;编写代码来找到最佳优化误差函数的位置。首先&＃xff0c;在每个时期&＃xff0c;每个粒子都被逐个挑选并优化其位置。一旦粒子的位置更新&＃xff0c;“如果”语句检查它是否是粒子群的最佳位置。

def optimize(self):for i in range(self.numOfEpochs):for j in range(len(self.swarm_list)):current_particle &＃61; self.swarm_list[j] # get current particleVcurr &＃61; grad_error(current_particle.position) # calculate current velocity of the particledeltaV &＃61; self.w * Vcurr \&＃43; self.c1 * (current_particle.best_part_pos - current_particle.position) \&＃43; self.c2 * (self.best_swarm_position - current_particle.position) # calculate delta Vnew_position &＃61; self.swarm_list[j].position - self.lr * deltaV # calculate the new positionself.swarm_list[j].setPos(new_position) # update the position of particleif error(new_position) < self.best_swarm_error: # check the position if it&＃39;s best for swarmself.best_swarm_position &＃61; new_positionself.best_swarm_error &＃61; error(new_position)print(&＃39;Epoch: {0} | Best position: [{1},{2}] | Best known error: {3}&＃39;.format(i,self.best_swarm_position[0],self.best_swarm_position[1],self.best_swarm_error))

运行PSO并观察算法的性能。

pso &＃61; PSO(dims&＃61;2, numOfBoids&＃61;30, numOfEpochs&＃61;500)
pso.optimize()


...
Epoch: 27 | Best position: [2.1199768747964054,-1.1332450655810595] | Best known error: 11.792438949384607
Epoch: 28 | Best position: [2.1199768747964054,-1.1332450655810595] | Best known error: 11.792438949384607
Epoch: 29 | Best position: [2.1199768747964054,-1.1332450655810595] | Best known error: 11.792438949384607
Epoch: 30 | Best position: [2.1199768747964054,-1.1332450655810595] | Best known error: 11.792438949384607
Epoch: 31 | Best position: [2.1199768747964054,-1.1332450655810595] | Best known error: 11.792438949384607
Epoch: 32 | Best position: [1.0839903018536725,-1.1678886593978168] | Best known error: 8.966098069909691

从下面的等高线图可以很容易地看出&＃xff0c;swarm只需要几个纪元就能收敛到Rastrigin函数的全局最小值。要获得创建轮廓可视化的代码以及过程的错误时期图&＃xff0c;可以参考&＃xff1a;T. Ahadli, Particle Swarm Optimization C&＃43;&＃43;/Python Project Codes。

完整代码


"""
Copyright © 2020 Tarlan Ahadli
"""import numpy as np
import matplotlib.pyplot as pltdef error(current_pos):x &＃61; current_pos[0]y &＃61; current_pos[1]return (x ** 2 - 10 * np.cos(2 * np.pi * x)) &＃43; \(y ** 2 - 10 * np.cos(2 * np.pi * y)) &＃43; 20def grad_error(current_pos):x &＃61; current_pos[0]y &＃61; current_pos[1]return np.array([2 * x &＃43; 10 * 2 * np.pi * x * np.sin(2 * np.pi * x),2 * y &＃43; 10 * 2 * np.pi * y * np.sin(2 * np.pi * y)])class PSO:class Particle:def __init__(self, dim, minx, maxx):self.position &＃61; np.random.uniform(low&＃61;minx, high&＃61;maxx, size&＃61;dim)self.velocity &＃61; np.random.uniform(low&＃61;minx, high&＃61;maxx, size&＃61;dim)self.best_part_pos &＃61; self.position.copy()self.error &＃61; error(self.position)self.best_part_err &＃61; self.error.copy()def setPos(self, pos):self.position &＃61; posself.error &＃61; error(pos)if self.error < self.best_part_err:self.best_part_err &＃61; self.errorself.best_part_pos &＃61; posw &＃61; 0.729c1 &＃61; 1.49445c2 &＃61; 1.49445lr &＃61; 0.01def __init__(self, dims, numOfBoids, numOfEpochs):self.swarm_list &＃61; [self.Particle(dims, -500, 500) for i in range(numOfBoids)]self.numOfEpochs &＃61; numOfEpochsself.best_swarm_position &＃61; np.random.uniform(low&＃61;-500, high&＃61;500, size&＃61;dims)self.best_swarm_error &＃61; 1e80 # Set high value to best swarm errordef optimize(self):for i in range(self.numOfEpochs):for j in range(len(self.swarm_list)):current_particle &＃61; self.swarm_list[j] # get current particleVcurr &＃61; grad_error(current_particle.position) # calculate current velocity of the particledeltaV &＃61; self.w * Vcurr \&＃43; self.c1 * (current_particle.best_part_pos - current_particle.position) \&＃43; self.c2 * (self.best_swarm_position - current_particle.position) # calculate delta Vnew_position &＃61; self.swarm_list[j].position - self.lr * deltaV # calculate the new positionself.swarm_list[j].setPos(new_position) # update the position of particleif error(new_position) < self.best_swarm_error: # check the position if it&＃39;s best for swarmself.best_swarm_position &＃61; new_positionself.best_swarm_error &＃61; error(new_position)print(&＃39;Epoch: {0} | Best position: [{1},{2}] | Best known error: {3}&＃39;.format(i,self.best_swarm_position[0],self.best_swarm_position[1],self.best_swarm_error))pso &＃61; PSO(dims&＃61;2, numOfBoids&＃61;30, numOfEpochs&＃61;500)
pso.optimize()

5. Conclusion

总而言之&＃xff0c;粒子群优化&＃xff08;Particle Swarm Optimization&＃xff09;模拟了鸟或鱼群的集体行为。它受益于自然界解决自身优化问题的方式&＃xff0c;以最大限度地减少能量使用。自然的设计和原理在计算机科学问题上有很多出色的实际应用。

参考资料

Nature-Inspired Optimization Algorithms: Particle Swarm Optimization Using Python
Implementing the Particle Swarm Optimization (PSO) Algorithm in Python