这里是引用
人工智能是计算机科学的一个大领域,它模拟计算机中的智能行为。在此基础上,提出了一种基于元启发式( metaheuristic)的粒子群优化算法来模拟鸟类觅食、鱼群移动等。这种算法能够模拟群体的行为,以便迭代地优化数值问题。例如,它可以被分类为像蚁群算法、人工蜂群算法和细菌觅食这样的群体智能算法。
J. Kennedy 和 R.Eberhart 在1995年提出的粒子群优化(Particle Swarm Optimization,PSO)变得非常流行,它是一种基于随机优化(Stochastic Optimization)的强大算法,受鸟群中的规则启发,连续优化过程允许多目标和更多的变化。该方法包括不断寻找最佳解,以每次迭代计算的一定速度移动粒子(在这种情况下表示为位置 ( x , y ) (x,y) (x,y))。每个粒子的运动都有其自身的影响,最著名的位置也是空间搜索中最著名的位置。最终期望的结果是粒子群收敛到最优解。重要的是要提到粒子群算法不使用梯度下降,所以它可以用于非线性问题,只要它不要求问题必须是可微的。
C++/Python代码可参考该仓库。
涌现复杂性(Emergent Complexity)是一种现象,描述了大群体的各个组成部分如何以相同但更简单的规则一起工作,以创建多样而复杂的系统。有一些自然的复杂行为可以作为涌现的例子。例如,蚂蚁本能地相互交流,以建立一个活的桥梁,在寻找食物来源时最小化交换距离(Video)。鸟类相互跟随,形成更大的群体,这增加了它们发现捕食者和食物来源的可能性。不像通常的复杂性(complexity)概念,它不一定有用,自然复杂性(natural complexity)是一百万年自然选择过程的结果,在这个过程中,能源的使用是增加生存机会的最重要因素。因此,如果同一个问题有两个解决方案,更简单、需要更少能量的方法将因自然选择而存在。这就是为什么大自然建议的解决方案会很简单,但仍然能有效地尽可能减少动物的能量消耗。因此,科学家们分别观察了一群欧椋鸟(starlings,八哥😸)中的每只鸟,发现它们中的每只都采取简单的行动来形成复杂的结构。
在自然界中,在一个数值问题中,任何boid(类似鸟的物体)的可观察到的邻近区域都被限制在一定的范围内。因此,它可以收敛到一些局部极小值(minima)或鞍点(saddle point),其中梯度(在该情况下对应的是速度)将为0。然而,拥有一个以上的boid可以让鸟群中的所有鸟关注到误差函数的更大范围,并且如果它们中的任何一只在误差方面看到了更好的位置,就不会陷入局部极小值。对上述原则进行数学建模,使群体找到误差函数的全局最小值。
f(x)= x²+y² 的函数图像
通过使用上述规则,我们可以轻松得出将驱动每个boid的数学方程式。
计算Delta V的向量表示
在以上等式中:
w , c 1 , c 2 , l e a r n i n g R a t e w, c_1, c_2, learningRate w,c1,c2,learningRate 是在优化过程中应微调的超参数。
粒子群优化算法伪代码:
其中:
使用Python来实现对群体智能背(swarm intelligence)后的数学理论进行了讨论和建模。为了测试算法,Rastrigin函数将被用作误差函数,这是优化问题中最具挑战性的函数之一。在平面上有很多余弦振荡会引入无数的局部极小值,在这些极小值中,boid会卡住。(图自:Source)
import numpy as np
def error(current_pos):
x = current_pos[0]
y = current_pos[1]
return (x ** 2 - 10 * np.cos(2 * np.pi * x)) + \
(y ** 2 - 10 * np.cos(2 * np.pi * y)) + 20
def grad_error(current_pos):
x = current_pos[0]
y = current_pos[1]
return np.array(
[2 * x + 10 * 2 * np.pi * x * np.sin(2 * np.pi * x),
2 * y + 10 * 2 * np.pi * y * np.sin(2 * np.pi * y)])
如上所述,每个boid都将具有位置,速度,误差,最佳位置和已知误差(best-known error)。我们还应该编写一个setter函数来在需要时修改参数。
class Particle:
def __init__(self, dim, minx, maxx):
self.position = np.random.uniform(low=minx, high=maxx, size=dim)
self.velocity = np.random.uniform(low=minx, high=maxx, size=dim)
self.best_part_pos = self.position.copy()
self.error = error(self.position)
self.best_part_err = self.error.copy()
def setPos(self, pos):
self.position = pos
self.error = error(pos)
if self.error < self.best_part_err:
self.best_part_err = self.error
self.best_part_pos = pos
粒子群算法类将由误差函数表面上的移动粒子列表组成。要初始化函数,需要函数的维数、boids的数量以及纪元的数量。
class PSO:
w = 0.729
c1 = 1.49445
c2 = 1.49445
lr = 0.01
def __init__(self, dims, numOfBoids, numOfEpochs):
self.swarm_list = [self.Particle(dims, -500, 500) for i in range(numOfBoids)]
self.numOfEpochs = numOfEpochs
self.best_swarm_position = np.random.uniform(low=-500, high=500, size=dims)
self.best_swarm_error = 1e80 # Set high value to best swarm error
最后,编写代码来找到最佳优化误差函数的位置。首先,在每个时期,每个粒子都被逐个挑选并优化其位置。一旦粒子的位置更新,“如果”语句检查它是否是粒子群的最佳位置。
def optimize(self):
for i in range(self.numOfEpochs):
for j in range(len(self.swarm_list)):
current_particle = self.swarm_list[j] # get current particle
Vcurr = grad_error(current_particle.position) # calculate current velocity of the particle
deltaV = self.w * Vcurr \
+ self.c1 * (current_particle.best_part_pos - current_particle.position) \
+ self.c2 * (self.best_swarm_position - current_particle.position) # calculate delta V
new_position = self.swarm_list[j].position - self.lr * deltaV # calculate the new position
self.swarm_list[j].setPos(new_position) # update the position of particle
if error(new_position) < self.best_swarm_error: # check the position if it's best for swarm
self.best_swarm_position = new_position
self.best_swarm_error = error(new_position)
print('Epoch: {0} | Best position: [{1},{2}] | Best known error: {3}'.format(i,
self.best_swarm_position[0],
self.best_swarm_position[1],
self.best_swarm_error))
运行PSO并观察算法的性能。
pso = PSO(dims=2, numOfBoids=30, numOfEpochs=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
从下面的等高线图可以很容易地看出,swarm只需要几个纪元就能收敛到Rastrigin函数的全局最小值。要获得创建轮廓可视化的代码以及过程的错误时期图,可以参考:T. Ahadli, Particle Swarm Optimization C++/Python Project Codes。
完整代码
""" Copyright © 2020 Tarlan Ahadli """
import numpy as np
import matplotlib.pyplot as plt
def error(current_pos):
x = current_pos[0]
y = current_pos[1]
return (x ** 2 - 10 * np.cos(2 * np.pi * x)) + \
(y ** 2 - 10 * np.cos(2 * np.pi * y)) + 20
def grad_error(current_pos):
x = current_pos[0]
y = current_pos[1]
return np.array(
[2 * x + 10 * 2 * np.pi * x * np.sin(2 * np.pi * x),
2 * y + 10 * 2 * np.pi * y * np.sin(2 * np.pi * y)])
class PSO:
class Particle:
def __init__(self, dim, minx, maxx):
self.position = np.random.uniform(low=minx, high=maxx, size=dim)
self.velocity = np.random.uniform(low=minx, high=maxx, size=dim)
self.best_part_pos = self.position.copy()
self.error = error(self.position)
self.best_part_err = self.error.copy()
def setPos(self, pos):
self.position = pos
self.error = error(pos)
if self.error < self.best_part_err:
self.best_part_err = self.error
self.best_part_pos = pos
w = 0.729
c1 = 1.49445
c2 = 1.49445
lr = 0.01
def __init__(self, dims, numOfBoids, numOfEpochs):
self.swarm_list = [self.Particle(dims, -500, 500) for i in range(numOfBoids)]
self.numOfEpochs = numOfEpochs
self.best_swarm_position = np.random.uniform(low=-500, high=500, size=dims)
self.best_swarm_error = 1e80 # Set high value to best swarm error
def optimize(self):
for i in range(self.numOfEpochs):
for j in range(len(self.swarm_list)):
current_particle = self.swarm_list[j] # get current particle
Vcurr = grad_error(current_particle.position) # calculate current velocity of the particle
deltaV = self.w * Vcurr \
+ self.c1 * (current_particle.best_part_pos - current_particle.position) \
+ self.c2 * (self.best_swarm_position - current_particle.position) # calculate delta V
new_position = self.swarm_list[j].position - self.lr * deltaV # calculate the new position
self.swarm_list[j].setPos(new_position) # update the position of particle
if error(new_position) < self.best_swarm_error: # check the position if it's best for swarm
self.best_swarm_position = new_position
self.best_swarm_error = error(new_position)
print('Epoch: {0} | Best position: [{1},{2}] | Best known error: {3}'.format(i,
self.best_swarm_position[0],
self.best_swarm_position[1],
self.best_swarm_error))
pso = PSO(dims=2, numOfBoids=30, numOfEpochs=500)
pso.optimize()
总而言之,粒子群优化(Particle Swarm Optimization)模拟了鸟或鱼群的集体行为。它受益于自然界解决自身优化问题的方式,以最大限度地减少能量使用。自然的设计和原理在计算机科学问题上有很多出色的实际应用。
Nature-Inspired Optimization Algorithms: Particle Swarm Optimization Using Python Implementing the Particle Swarm Optimization (PSO) Algorithm in Python
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/183238.html原文链接:https://javaforall.cn