改进的粒子群优化算法

3.2　改进的粒子群优化算法

参考文献［94］基于统计物理提出了动力学演化算法(Dynamical Evolutionary Algorithm)，它通过驱动所有的个体运动和进化来保持种群的多样性;参考文献［41］从热力学和模拟退火算法得到启发，提出了一种基于自由能极小原理的热力学遗传算法(Thermodynamical Genetic Algorithm)，采用温度和熵的概念来系统地控制种群多样性;参考文献［42］根据统计物理的粒子输运理论中粒子相空间能量最小原理和熵增法提出了一类粒子动力学演化算法。受此启发，本书作者把统计物理中的分子运动论引入到基本粒子群优化算法中来设计一种新颖的粒子群优化算法————基于分子运动论的粒子群优化算法^［95-96］，算法中的粒子除了具有速度和位置属性之外，还增加了一个加速度属性，算法中还定义了群质心的概念。下面类比于统计物理和热力学中的质心和加速度的概念，给出基于分子运动论的粒子群优化算法中群质心和加速度的定义。

定义3.1　群质心指种群所有粒子的质量集中于此的一个假想点。在一个N维空间中，群质心计算公式为

其中，X_i表示种群中粒子i的坐标;m_i表示种群中粒子i的质量，可以把m_i看成是粒子i的权重，实际处理时可以令m_i等于粒子i的适应值，在本章中假设各粒子的质量相等且为1，公式(3.1)简化为

定义3.2　由于分子间距离的变化，当F在斥力和引力之间转换时，F的大小和方向也会随之变化，根据牛顿第二定律

加速度a的大小和方向也会随之改变。忽略a的大小，只考虑它的方向，当分子力F呈现为引力时a=1，当分子力F呈现为斥力时a=－1。

根据定义3.2重新定义了粒子的速度更新公式，此时公式(2.1)变更为

其中，a_i表示粒子i的加速度。初始化时所有粒子的加速度a_i都默认设置为1，随着算法的迭代进行，根据粒子i与群质心之间的距离(为便于描叙用d(X_cen，X_i)来表示粒子i与群质心之间的距离)，时刻调整a_i(具体的调整规则见算法流程)。当d(X_cen，X_i)小于某个阈值d_l时，粒子与群质心之间的分子力表现为斥力，驱使粒子远离群质心以保持种群的多样性，且有利于算法的全局搜索;当d(X_cen，X_i)大于某个阈值d_h时，为了保证算法的收敛、加强算法的局部搜索能力，分子力表现为引力，吸引粒子朝着群质心飞行。

根据以上的分析和定义，可以发现分子的热运动和MPSO算法之间有诸多相似之处，它们之间的对应关系如表3.1所示。

表3.1　MPSO算法与分子运动论的相似关系

MPSO算法的流程如下。

Step1:初始化种群粒子(群体规模为M)，包括位置、速度和加速度。Step2:评价每个粒子的适应值。

Step3:更新粒子的当前最优解和种群当前的最优解。

Step4:如果算法收敛准则满足或达到最大迭代次数，执行Step7，否则执行Step5。

Step5:

Step6:未满足结束条件则转Step2。

Step7:输出算法所找到的全局最优解，算法结束。

参考文献［38］受生物学中细菌趋化性的启发提出了具有吸引和排斥两种阶段的粒子群优化算法(Particle Swarm Optimization Based on Bacterial Chemotaxis，简称PSOBC)。参考文献［97］为了保持种群的多样性也提出了一种具有吸引和排斥两种状态的粒子群优化算法(Attractive and Repulsive PSO，简称ARPSO)。本章的MPSO算法，PSOBC算法和ARPSO算法的相同点在于三种算法都具有吸引和排斥两个阶段;不同点是PSOBC算法和ARPSO算法要求所有粒子同时处于吸引或者同时处于排斥阶段，本章的MPSO算法可以使一部分粒子处于吸引状态，而另外一部分粒子处于排斥状态。因此MPSO算法能更有效地平衡全局和局部搜索能力，并具有更好的性能，下一小节的实验结果证实了这点。