【优化算法】粒子群优化算法简介[通俗易懂]

【优化算法】粒子群优化算法简介[通俗易懂]粒子群优化算法(ParticleSwarmOptimization,PSO)简介。

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

这里是引用



1. 简介

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

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

C++/Python代码可参考该仓库

2. 涌现复杂性

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

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

3. 鸟群智能建模

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

在这里插入图片描述


f(x)= x²+y² 的函数图像

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

通过使用上述规则,我们可以轻松得出将驱动每个boid的数学方程式。
在这里插入图片描述


计算Delta V的向量表示

在这里插入图片描述
在以上等式中:

  • w w w:表示惯性,决定了boid的当前速度对 Δ V \Delta V ΔV 的影响程度;
  • c 1 , c 2 c_1, c_2 c1,c2:定义了boid和swarm的最佳记录位置(best-recorded position)将如何分别影响 Δ V \Delta V Δ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 是在优化过程中应微调的超参数。


粒子群优化算法伪代码:
在这里插入图片描述
其中:

  • V i ( k + 1 ) V_i(k+1) Vi(k+1) 是下一个迭代速度;
  • W W W 是惯性参数。该参数影响最后速度值给定的运动传播。
  • C 1 , C 2 C_1, C_2 C1,C2 是加速度系数。 C 1 C_1 C1 赋予个体最佳值的重要性,而 C 2 C_2 C2 则代表群体最佳值的重要性。
  • P i P_i Pi是个体最佳位置, P g P_g Pg 是群体最佳位置。在方程式中,衡量了每个参数到粒子实际位置的距离。
  • r a n d 1 rand_1 rand1 r a n d 2 rand_2 rand2 是随机数,其中 0 ≤ r a n d ≤ 1 0≤rand≤1 0rand1,它们控制每个值的影响:群体和个体,如下所示。
    在这里插入图片描述

4. 代码实现

使用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()

5. Conclusion

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


参考资料

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/183238.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 计算机专业的男生喜欢你,【男生这十个反应说明他喜欢你】_男人的10个表现说明他喜欢上了你…

    计算机专业的男生喜欢你,【男生这十个反应说明他喜欢你】_男人的10个表现说明他喜欢上了你…[onlylady乐活健康情感]男人是一种奇怪动物.和他看不上的女人说话时,他表现得十分自然大方,仿佛兄弟.和他看上的女人说话时,则表现得有点扭捏.1、和女人说话时,不太敢正面女人,而是常常温柔地瞟女人.男人是一种奇怪动物.和他看不上的女人说话时,他表现得十分自然大方,仿佛兄弟.和他看上的女人说话时,则表现得有点扭捏.并非缺乏正面女人的勇气,而是心底不由自主的害羞在作祟.对了,还有一种伴发症…

  • 强大的nginx反向代理异步传输模式(原理)[通俗易懂]

    强大的nginx反向代理异步传输模式(原理)[通俗易懂]sudone.com在nginx的反向代理介绍中,提到了异步传输模式并提到它可以减少后端连接数和压力,这是为何?下面就来讲解下传统的代理(apache/squid)的同步传输和nginx的异步传输的差异。看图:         squid同步传输:浏览器发起请求,而后请求会立刻被转到后台,于是在浏览器和后台之间就建立了一个通道。在请求发起直到请求完成,这条通道都是一直存在的。nginx异步传输:浏…

  • PyTorch—torchvision.models导入预训练模型—残差网络代码讲解

    PyTorch—torchvision.models导入预训练模型—残差网络代码讲解PyTorch框架中torchvision模块下有:torchvision.datasets、torchvision.models、torchvision.transforms这3个子包。关于详情请参考官网:http://pytorch.org/docs/master/torchvision/index.html。具体代码可以参考github:https://github.com/pytorc…

  • for循环break和continue[通俗易懂]

    for循环break和continue[通俗易懂]for循环像while循环一样,for可以完成循环的功能。在Python中for循环可以遍历任何序列的项目,如一个列表或者一个字符串等。for循环的格式for临时变量in列表或者字符串等:循环满足条件时执行的代码demo1name=‘itheima’forxinname:print(x)运行结果如下:itheimademo2name=‘h…

  • 实验室仪器管理系统_实验室设备管理系统代码

    实验室仪器管理系统_实验室设备管理系统代码实验室设备管理系统主要包括:实验室设备信息的管理模块,实验室设备信息的浏览查询模块,设备事故记录模块,设备资料管理模块设备的损坏管理模块,设备损坏信息浏览查询,设备类别设置,系统用户的管理。通过本系统,可以更加有效的管理学生实验室设备信息开发技术:php,mysql,apache课题名称:实验室设备管理系统1)系统简介每学年要对实验室设备使用情况进行统计、更新。其中:(1)对于已彻底损坏的做报废处理,同时详细记录有关信息。(2)对于由严重问题(故障)的要及时修理,并记录修理日期、设备名、编号

    2022年10月13日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号