关键词: 先进计算, 组合优化, 人工鱼群算法, 全局收敛性, 有限Markov链

Abstract: 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.

Key words: advanced computation, combinatorial optimization, artificial fish swarm algorithm, global convergence, finite Markov chain