标准粒子群优化算法的马尔科夫链分析

Analysis of Standard Particle Swarm Optimization Algorithm Based on Markov Chain

根据粒子群优化(Particle swarm optimization,PSO)算法的差分模型定义粒子状态序列和群体状态序列,并分析其马尔科夫性质,证明了粒子及种群的最优状态集的封闭性,以及计算粒子一步转移概率;进一步基于全概率公式和马氏链的性质,推导了群体状态转到最优状态集的转移概率;根据该转移概率,对PSO算法的惯性权重ω和加速度因子c进行了讨论和解释,研究了算法早熟收敛和发散等问题,最后分析表明标准PSO算法以一定概率收敛到全局最优.

According to the proposed particle swarm optimization （PSO） difference model in this paper, the state sequence of a single particle and swarm state sequence are defined first, and their Markov property are analyzed, after that, it is demonstrated that the set of optimal states are closed set. Moreover, the one-step transition probability of a particle is calculated. Considering the complete probability formula and the Markov properties, the transition probability to the optimal set is deduced. According to the derived conclusion, the inertia weight ω and accelerate factor c of PSO are discussed. Finally, the premature convergence and divergent problem are explained, furthermore, it is proved that the standard PSO algorithm reaches the global optimum in probability.