混合蛙跳算法的Markov模型及其收敛性分析

The Markov Model of Shuffled Frog Leaping Algorithm and Its Convergence Analysis

本文就混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)建立了Markov链数学分析模型,详细分析了该Markov链的性质,证明青蛙族群状态序列是齐次Markov链.在此基础上,通过分析族群状态序列的转移过程,指出序列必将进入最优状态集.同时证明混合蛙跳算法满足随机搜索算法全局收敛的两个条件,能够保证全局收敛.

The Markov chain model for the shuffled frog leaping algorithm（SFLA） was established.It was shown that the frog memeplex state sequence containing both the frog states and the current local and the global optimal frog states constructs a homogeneous Markov chain.The transition process of the frog memeplex state sequence was analyzed,and the conclusion that sequence will eventually converges to the optimal state set was drawn.Furthermore,it was proved that the shuffled frog leaping algorithm ensures global convergence as it meets the global convergence criterions of random search algorithms.