Convergence Analysis On Population Migration Algorithms

Population migration algorithm(PMA) is a new kind of simulated evolutionary algorithm(SEA) proposed recently by Zhou Yonghua and Mao Zongyuan, which simulates the principle of population migration. The procedure of the original algorithm is too long and wordy, and after revised by Xu Zongben, a new PMA is obtained. PMA is different from other SEAs, because it set up the model through simulating the principle in society that people migrate along with economic center and disperse as population pressure increases instead of some optimization groups in nature. The mathematical fundament of various SEAs(including PMA) is generally acknowledged imperfect, especially the convergence problem. A new approach to analysis the convergence of SEAs——Axiomatic Model was developed by Xu Zongben in recent years. This approach is based on the axiomatical description of the simulated evolutionary computation's operation, and, it can analysis directly the convergence of vorious SEAs by utilizing the properties of seletion and evolution operators. As an application, this approach establishes the convergence problem of genetic algorithms(GAs) and evolution strategies(ESs), at the same time, it provide a frame for people to research other SEAs. In this paper, we establish the convergence problem of PMA by applying axiomatic model too. The paper is organized as follows. In chapter 2, we introduce some concepts about SEA, the abstract SEA model and the convergence definition of algorithm. In chapter 3, we describe firstly the evolution of PMA as an abstract stochastic process, and by characterizing axiomatically the properties of the fundamental selection and evolution operators, we conclude that PMA is essentially a kind of SEA. In chapter 4, firstly, we revise the original definition of the properties of selection operator, and by computing the concrete characteristic numbers of all operators, we conlude that PMA cannot converge to the global optimum if it does not adopt the "elitist record strategy" or the strategy that parents are always put into competition with their offsprings("parent-offsprings competition strategy"). Furthermore, using the properties of oprators, we establish that PMA with "parent-offsprings competition strategy" is convergent with probability 1, and also we estimate the convergence rate and computational time complexity, which lays a theoretical foundation for PMA to be used widely, and guides us to set up various parameters. Finally, numerical experiments not only indicate that the PMA is very effective, but also make known that the setup of parameters provided by this paper can improve the convergence rate of PMA effectly.