计算智能--生物人工智能之粒子群算法

时间:2022-01-17 09:07:37

生物群体智能

     生物群体普遍具有智能行为,这种生物群体所具有的智能我们称为群智能

     可以把群(Swarm)定义为某种具有交互作用的组织或智能体的集合。在这种群体中,个体在结构上很简单,而他们的集体行为可能变得相当复杂。

     个体行为全局群行为之间存在着某种紧密地联系,这些个体的行为构成和支配了群行为,同时,群行为又影响和改变这些个体的自身行为。个体之间的交互在构建群行为中起到重要的作用,它帮助群体改善了对环境的经验知识。

     对不同群的研究得到不同的应用,其中最引人注目的是通过对鸟群和蚁群的研究而建立的粒子群算法蚁群算法

(一)粒子群优化概述 

粒子群优化PSOParticle SwarmOptimization)算法是一种基于群智能的演化计算方法,由Kennedy和Eberhart于1995年提出。该算法源于对鸟类捕食行为的模拟

    设想这样一个场景:一群鸟在随机搜索食物。在这个区域里只有一块食物,所有的鸟都不知道食物在那里,但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域

在搜寻过程中,每只鸟的位置变化是以成功地超越其他个体的社会心理意向为基础的。因此一只鸟的搜寻行为受到其他鸟的搜寻行为的影响

*********特点:(1)个体独立,有个体能动性(2)受团体影响*********

 

PSO从这种模型中得到启示并用于解决优化问题。在PSO中,优化问题的潜在解刻画为搜索空间中的一只鸟,称之为“粒子”。每个粒子都有一个由优化函数决定的适应值和一个决定飞翔方向距离的速度,粒子们追随当前的最优粒子在解空间中搜索。

 

粒子=====》问题集:

鸟所处位置信息(n维向量表达)(问题潜在解)====》求解问题解

速度信息(n维向量)(个体行为)

适应度函数(适应值对应当前位置的好坏)

 

所有的粒子构成粒子群

 

 

PSO 初始化为一群随机粒子(随机解),然后通过迭代找到最优解。

在每一次迭代中,粒子通过跟踪两个“极值”来更新自己的位置。这两个极值分别是:

    ① 粒子本身所找到的最优解,称为个体极值

    ② 整个种群目前找到的最优解,称为全局极值

粒子通过不断学习和更新,最终飞至空间中最优解所在的位置。 

 

第t时刻(第t代)第i个粒子的位置信息:(D维向量)

计算智能--生物人工智能之粒子群算法

截止到第t时刻第i个个体找到的最优解(个体局部最优解):

计算智能--生物人工智能之粒子群算法

截止到第t时刻,整个粒子群的最优解

计算智能--生物人工智能之粒子群算法

第t时刻(第t代)第i个粒子的速度信息:(D维向量)

计算智能--生物人工智能之粒子群算法

第t+1时刻第i个个体速度的计算:

计算智能--生物人工智能之粒子群算法

计算智能--生物人工智能之粒子群算法====》第i个个体:截止到第t时刻的个体位置最优解与第t时刻的位置之差

计算智能--生物人工智能之粒子群算法======》粒子群截止到第t时刻的位置最优解与第i个个体的t时刻位置之差

计算智能--生物人工智能之粒子群算法:0-1之间的权值(由经验给出)

计算智能--生物人工智能之粒子群算法 :第i个体第t时刻的速度

计算智能--生物人工智能之粒子群算法,   计算智能--生物人工智能之粒子群算法:动量

计算智能--生物人工智能之粒子群算法计算智能--生物人工智能之粒子群算法:0-1之间的随机数

第t+1时刻第i个个体的位置计算:

计算智能--生物人工智能之粒子群算法(第t时刻的位置+第t+1时刻的速度)

 

向量表示:

计算智能--生物人工智能之粒子群算法

 

2 粒子群算法过程 (*****)

由于在上述的迭代过程中,Pg是整个粒子群的最优位置,因此上述PSO算法称为全局版PSO。还可以把第i个粒子的近邻搜索到的最优位置作为Pg,此时PSO称为局部版PSO。这里我们只对全局PSO算法过程进行描述。

    具体算法如下:

(1) 随机初始化粒子群,即t=0时随机为每个粒子指定一个位置Xi(0)及速度Vi(0);

(2) 计算每个粒子的适应度值f(Xi(t));保存每个粒子最优值(当前位置),求初始全局最优位置G(0)

(3) 比较每个粒子的当前适应度值f(Xi(t))和个体最优值f(Pi),如果f(Xi(t))>(优于)f(Pi),那么Pi=Xi(t);

(4) 比较每个粒子的当前适应度值f(Xi(t))和全局最优值f(Pg),如果f(Xi(t))> (优于)f(Pg),那么Pg=Xi(t);

(5) 按下列公式更改每个粒子的速度矢量和位置:

计算智能--生物人工智能之粒子群算法

(6) 如果满足终止条件,则输出Pg;否则,t =t+1,转(2)。

 

(PSO算法每次运行的结果都不同)

 

   在PSO算法中并没有太多需要调节的参数,下面列出了这些参数以及经验设置:

粒子数m(种群大小):一般取20-40,其实对于大部分的问题,10个粒子已经足够取得好的结果,对于比较难的问题或者特定类别的问题,粒子数可以取到100或200。

粒子的长度n(空间维数):这是由优化问题决定的,就是问题解的长度。

粒子的坐标范围:由优化问题决定,每一维可设定不同的范围。

学习因子c1c2通常等于2,不过在一些文献中也有其它的取值,但是一般c1c2相等,并且范围在0和4之间。

中止条件:最大循环数以及最小偏差要求,这个中止条件由具体问题确定。

3 粒子群算法与遗传算法比较   

PSO和遗传算法(GeneticAlgorithm,GA)相比:

  相同之处:两者都随机初始化种群,都使用适应度函数来评价系统,并根据适应度值来进行一定的随机搜索,且两个系统都不保证一定找到最优解。

不同之处

(1)PSO 没有遗传操作,如交叉和变异,它根据粒子的速度来决定搜索,操作简单,而且粒子具有记忆功能。

(2)PSO 的信息共享机制也有别于GA。

              在GA中,染色体互相共享信息,所以整个种群的移动是比较均匀的向最优区域移动;在PSO中,只有pgpi提供信息给其他的粒子,这是单向的信息流动。PSO整个搜索更新过程是跟随当前最优解的过程,因而收敛速度相对要快。

(3)GA比较适用于离散问题的求解,而粒子群较适合连续性问题的求解。

PSO依据每个粒子的位置移动生成下一代,GA通过选择,交叉,变异产生下一代