求解组合优化问题的鱼群算法的收敛性证明

摘要

In order to prove global convergence of artificial fish swarm algorithm for solving combinatorial optimization problems, the search space of artificial fish swarm algorithm is defined as discrete space, where each point is just a position state of an artificial fish, its food density is the objective function value at this point. The whole discrete space is divided into a series of non-empty subsets according to different energy levels; all artificial fishes are also divided into a series of non-empty subsets. During preying, swarming or following activity of artificial fishes, each artificial fish' s transition probability from a position to another position can be simply calculated; each position state during moving corresponds to a state of a finite Markov chain, then the stability condition of a reducible stochastic matrix can be satisfied; based on that, the global convergence of artificial fish swarm algorithm is proved.%为了证明求解组合优化问题的人工鱼群算法的全局收敛性,将人工鱼群算法的搜索空间定义为离散空间,其中的每个点即为一个人工鱼的位置状态,其食物浓度即为该点的目标函数值.根据食物浓度大小将整个离散空间集合分为若干个非空子集；将所有人工鱼集合也对应划分为若干个非空子集.在人工鱼的觅食、聚群和追尾过程中,人工鱼从一个位置状态转移到任意一个位置状态的转移概率可以计算出来；人工鱼移动过程中的每个位置状态对应于有限Markov链上的一个状态,且满足可归约随机矩阵的稳定性条件,据此证明了工鱼群算法具有全局收敛性.