python实现粒子群算法

粒子群算法

粒子群算法源于复杂适应系统(Complex Adaptive System,CAS)。CAS理论于1994年正式提出,CAS中的成员称为主体。比如研究鸟群系统,每个鸟在这个系统中就称为主体。主体有适应性,它能够与环境及其他的主体进行交流,并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括:新层次的产生(小鸟的出生);分化和多样性的出现(鸟群中的鸟分成许多小的群);新的主题的出现(鸟寻找食物过程中,不断发现新的食物)。

PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中,粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。
在找到这两个最优值后,粒子通过下面的公式来更新自己的速度和位置。

i 表示第 i 个粒子, d 表示粒子的第 d 个维度。r1, r2 表示两个位于 [0, 1] 的随机数(对于一个粒子的不同维度,r1, r2 的值不同)。pbest[i] 是指粒子取得最高(低)适应度时的位置,gbest[i] 指的是整个系统取得最高(低)适应度时的位置。

实践

我们用 PSO 算法求解如下函数的最小值

可以在空间画出图像

下图是使用 5 个粒子的收敛情况

可以看到,fitness 在第 12 轮就几乎收敛到 -10.0。

下面是完整代码

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

INF = 1e5

def plot_cost_func():
  """画出适应度函数"""
  fig = plt.figure()
  ax = Axes3D(fig)
  X = np.arange(-4, 4, 0.25)
  Y = np.arange(-4, 4, 0.25)
  X, Y = np.meshgrid(X, Y)
  Z = (X**2 + Y**2) - 10
  ax.plot_surface(X, Y, Z, rstride=1, cstride=1, cmap='rainbow')
  plt.show()

def fitness(x):
  return x[0]**2 + x[1]**2 - 10

class PSOSolver(object):
  def __init__(self, n_iter, weight=0.5, c1=2, c2=2, n_particle=5):
    self.n_iter = n_iter
    self.weight = weight
    self.c1 = c1
    self.c2 = c2
    self.n_particle = n_particle
    self.gbest = np.random.rand(2)
    # gbest 对应的函数值
    self.gbest_fit = fitness(self.gbest)
    # 将位置初始化到 [-5, 5]
    self.location = 10 * np.random.rand(n_particle, 2) - 5
    # 将速度初始化到 [-1, 1]
    self.velocity = 2 * np.random.rand(n_particle, 2) - 1
    self.pbest_fit = np.tile(INF, n_particle)
    self.pbest = np.zeros((n_particle, 2))
    # 记录每一步的最优值
    self.best_fitness = []

  def new_velocity(self, i):
    r = np.random.rand(2, 2)
    v = self.velocity[i]
    x = self.location[i]
    pbest = self.pbest[i]
    return self.weight * v + self.c1 * r[0] * (pbest - x) + \
        self.c2 * r[1] * (self.gbest - x)

  def solve(self):
    for it in range(self.n_iter):
      for i in range(self.n_particle):
        v = self.new_velocity(i)
        x = self.location[i] + v
        fit_i = fitness(x)
        if fit_i < self.pbest_fit[i]:
          self.pbest_fit[i] = fit_i
          self.pbest[i] = x
          if fit_i < self.gbest_fit:
            self.gbest_fit = fit_i
            self.gbest = x
        self.velocity[i] = v
        self.location[i] = x
      self.best_fitness.append(self.gbest_fit)

if __name__ == '__main__':
  plot_cost_func()
  n_iter = 20
  s = PSOSolver(n_iter)
  s.solve()
  print(s.gbest_fit)
  plt.title("Fitness Curve")
  plt.xlabel("iter")
  plt.ylabel("fitness")
  plt.plot(np.arange(n_iter), np.array(s.best_fitness))
  plt.show()

以上就是python实现粒子群算法的详细内容,更多关于python 粒子群算法的资料请关注我们其它相关文章!

时间: 2020-10-13

python em算法的实现

''' 数据集:伪造数据集(两个高斯分布混合) 数据集长度:1000 ------------------------------ 运行结果: ---------------------------- the Parameters set is: alpha0:0.3, mu0:0.7, sigmod0:-2.0, alpha1:0.5, mu1:0.5, sigmod1:1.0 ---------------------------- the Parameters predict is: al

python3实现单目标粒子群算法

本文实例为大家分享了python3单目标粒子群算法的具体代码,供大家参考,具体内容如下 关于PSO的基本知识......就说一下算法流程 1) 初始化粒子群: 随机设置各粒子的位置和速度,默认粒子的初始位置为粒子最优位置,并根据所有粒子最优位置,选取群体最优位置. 2) 判断是否达到迭代次数: 若没有达到,则跳转到步骤3).否则,直接输出结果. 3) 更新所有粒子的位置和速度: 4) 计算各粒子的适应度值. 将粒子当前位置的适应度值与粒子最优位置的适应度值进行比较,决定是否更新粒子最优位置:将所

python 决策树算法的实现

''' 数据集:Mnist 训练集数量:60000 测试集数量:10000 ------------------------------ 运行结果:ID3(未剪枝) 正确率:85.9% 运行时长:356s ''' import time import numpy as np def loadData(fileName): ''' 加载文件 :param fileName:要加载的文件路径 :return: 数据集和标签集 ''' # 存放数据及标记 dataArr = []; labelArr

python 如何实现遗传算法

1.基本概念 遗传算法(GA)是最早由美国Holland教授提出的一种基于自然界的"适者生存,优胜劣汰"基本法则的智能搜索算法.该法则很好地诠释了生物进化的自然选择过程.遗传算法也是借鉴该基本法则,通过基于种群的思想,将问题的解通过编码的方式转化为种群中的个体,并让这些个体不断地通过选择.交叉和变异算子模拟生物的进化过程,然后利用"优胜劣汰"法则选择种群中适应性较强的个体构成子种群,然后让子种群重复类似的进化过程,直到找到问题的最优解或者到达一定的进化(运算)时间.

Python编程实现粒子群算法(PSO)详解

1 原理 粒子群算法是群智能一种,是基于对鸟群觅食行为的研究和模拟而来的.假设在鸟群觅食范围,只在一个地方有食物,所有鸟儿看不到食物(不知道食物的具体位置),但是能闻到食物的味道(能知道食物距离自己位置).最好的策略就是结合自己的经验在距离鸟群中距离食物最近的区域搜索. 利用粒子群算法解决实际问题本质上就是利用粒子群算法求解函数的最值.因此需要事先把实际问题抽象为一个数学函数,称之为适应度函数.在粒子群算法中,每只鸟都可以看成是问题的一个解,这里我们通常把鸟称之为粒子,每个粒子都拥有: 位置,可

Python实现七个基本算法的实例代码

1.顺序查找 当数据存储在诸如列表的集合中时,我们说这些数据具有线性或顺序关系. 每个数据元素都存储在相对于其他数据元素的位置. 由于这些索引值是有序的,我们可以按顺序访问它们. 这个过程产实现的搜索即为顺序查找. 顺序查找原理剖析:从列表中的第一个元素开始,我们按照基本的顺序排序,简单地从一个元素移动到另一个元素,直到找到我们正在寻找的元素或遍历完整个列表.如果我们遍历完整个列表,则说明正在搜索的元素不存在. 代码实现:该函数需要一个列表和我们正在寻找的元素作为参数,并返回一个是否存在的布尔值

Python 实现国产SM3加密算法的示例代码

SM3是中华人民共和国政府采用的一种密码散列函数标准,由国家密码管理局于2010年12月17日发布.主要用于报告文件数字签名及验证. Python3代码如下: from math import ceil ############################################################################## # # 国产SM3加密算法 # #####################################################

python 密码学示例——理解哈希(Hash)算法

Hash 是密码学安全性的基石,它引入了单向函数(one-way function)和指纹(fingerprint)的概念.即: 对于任意输入,都可以产生相同的.唯一的输出值 输出值中不包含输入值的任何线索 一.保密性(confidentiality)与完整性(integrity) 简单来说,信息的保密性确保除授权人员以外的任何人都无法读取该消息,信息的完整性则确保除授权人员以外的任何人都无法修改该消息. 很多时候一段加密的消息无法被他人读取和理解(保密性),并不意味着该密文不会在传播过程中被截

Python实现EM算法实例代码

EM算法实例 通过实例可以快速了解EM算法的基本思想,具体推导请点文末链接.图a是让我们预热的,图b是EM算法的实例. 这是一个抛硬币的例子,H表示正面向上,T表示反面向上,参数θ表示正面朝上的概率.硬币有两个,A和B,硬币是有偏的.本次实验总共做了5组,每组随机选一个硬币,连续抛10次.如果知道每次抛的是哪个硬币,那么计算参数θ就非常简单了,如 下图所示: 如果不知道每次抛的是哪个硬币呢?那么,我们就需要用EM算法,基本步骤为:   1.给θ_AθA​和θ_BθB​一个初始值:   2.(E-

python 贪心算法的实现

贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关. 基本思路 思想 贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解.每一步只考虑一个数据,他的选取应该满足局部优化的条件.若

python冒泡排序算法的实现代码

1.算法描述:(1)共循环 n-1 次(2)每次循环中,如果 前面的数大于后面的数,就交换(3)设置一个标签,如果上次没有交换,就说明这个是已经好了的. 2.python冒泡排序代码 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- def bubble(l):    flag = True    for i in range(len(l)-1, 0, -1):        if flag:             flag = False

python插入排序算法的实现代码

1.算法:设有一组关键字{ K 1 , K 2 ,-, K n }:排序开始就认为 K 1 是一个有序序列:让 K 2 插入上述表长为 1 的有序序列,使之成为一个表长为 2 的有序序列:然后让 K 3 插入上述表长为 2 的有序序列,使之成为一个表长为 3 的有序序列:依次类推,最后让 K n 插入上述表长为 n-1 的有序序列,得一个表长为 n 的有序序列. 2.python插入排序代码 复制代码 代码如下: def insertion_sort(list2):    for i in ra

Python贪心算法实例小结

本文实例讲述了Python贪心算法.分享给大家供大家参考,具体如下: 1. 找零钱问题:假设只有 1 分. 2 分.五分. 1 角.二角. 五角. 1元的硬币.在超市结账 时,如果 需要找零钱, 收银员希望将最少的硬币数找给顾客.那么,给定 需要找的零钱数目,如何求得最少的硬币数呢? # -*- coding:utf-8 -*- def main(): d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存储每种硬币面值 d_num = [] # 存储每种硬币的数量 s

基于ID3决策树算法的实现(Python版)

实例如下: # -*- coding:utf-8 -*- from numpy import * import numpy as np import pandas as pd from math import log import operator #计算数据集的香农熵 def calcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} #给所有可能分类创建字典 for featVec in dataSet: currentLa

应用OpenCV和Python进行SIFT算法的实现详解

应用OpenCV和Python进行SIFT算法的实现 如下图为进行测试的gakki101和gakki102,分别验证基于BFmatcher.FlannBasedMatcher等的SIFT算法,对比其优劣.为体现出匹配效果对于旋转特性的优势,将图gakki101做成具有旋转特性的效果. 基于BFmatcher的SIFT实现 BFmatcher(Brute-Force Matching)暴力匹配,应用BFMatcher.knnMatch( )函数来进行核心的匹配,knnMatch(k-nearest

python常用排序算法的实现代码

这篇文章主要介绍了python常用排序算法的实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 排序是计算机语言需要实现的基本算法之一,有序的数据结构会带来效率上的极大提升. 1.插入排序 插入排序默认当前被插入的序列是有序的,新元素插入到应该插入的位置,使得新序列仍然有序. def insertion_sort(old_list): n=len(old_list) k=0 for i in range(1,n): temp=old_lis

python Canny边缘检测算法的实现

图像边缘信息主要集中在高频段,通常说图像锐化或检测边缘,实质就是高频滤波.我们知道微分运算是求信号的变化率,具有加强高频分量的作用.在空域运算中来说,对图像的锐化就是计算微分.对于数字图像的离散信号,微分运算就变成计算差分或梯度.图像处理中有多种边缘检测(梯度)算子,常用的包括普通一阶差分,Robert算子(交叉差分),Sobel算子等等,是基于寻找梯度强度.拉普拉斯算子(二阶差分)是基于过零点检测.通过计算梯度,设置阀值,得到边缘图像. Canny边缘检测算子是一种多级检测算法.1986年由J