A Dynamical System Based Study On Model Analysis And Design Of Evolutionary Algorithms

As a simple and straightforward optimization method,evolutionary algorithms(EAs)have been widely developed and applied since it was proposed.Since the new century,the emergence of complex problems has also presented great challenges for the study of evolutionary algorithms.At the same time,many different evolutionary algorithms have emerged,such as the Cuckoo Bird algorithm,the Grey Wolf algorithm,and so on.The inherent thought of these algorithms is to learn from the theoretical techniques of other disciplines to study the algorithm design and problem-solving methods.These algorithms simulate the evolution law of nature and human society,which have a strong natural physical background.Therefore,investigation on model design and algorithm analysis of evolutionary algorithms based on the discipline of natural physics,especially mathematics and physics,is a natural trend in the study of evolutionary algorithms.In this paper,the dynamical system and stability analysis theory with a deep mathematical foundation are introduced into the modeling and analysis of evolutionary algorithms,and the dynamical models of evolutionary algorithms are established.On this basis,the theoretical analyses of evolutionary algorithms are carried out,and according to the conclusion of theoretical studies,some algorithm design improvement strategies are proposed.The main contents of this paper are as follows:(1)The elastodynamic model and relaxation time model of the simulated annealing algorithm are established.Then,the convergence and time complexity of the simulated annealing algorithm are analyzed.The simulated annealing algorithm originates from the annealing process of metals in physics,and it has a strong physical background.Firstly,we regard the Metropolis rule,which is the most crucial rule in the algorithm,as a damped vibration process,and then establish the elastodynamic model of the algorithm.Though the model,the two-stage process of undamped and damped vibration characterizing the operation mechanism of the algorithm is analyzed.Then,based on the stability analysis theory,we analyze the local and global convergence of the algorithm.Furthermore,by deriving ideas from statistical physics and transport theory of inhomogeneous gases,we establish the relaxation time model of the algorithm,and analyze the time complexity of the algorithm.Therefore,according to the difference equation,the dynamic Markov chain setting strategy of the simulated annealing algorithm is proposed.Experiments verify the effectiveness of the proposed dynamical system model and the efficiency of the improved strategy.(2)The aerodynamical model of the population evolutionary algorithms,namely the wave model,is established.And the convergence and optimization mechanism of the evolutionary algorithm are analyzed.Based on the applied of the dynamical system model method to the simulated annealing algorithm,the dynamical system analysis method is further extended to the population evolutionary algorithms.By drawing an analogy between the population of an evolutionary algorithm and a gas system,we first build wave models of evolutionary algorithms based on aerodynamics theory.Then,we solve the models' linear and quasi-linear hyperbolic equations analytically,yielding wave solutions.These describe the propagation of the particle density wave,which is composed of leftward and rightward waves.The sparse wave and compressed wave which characterize the exploration and exploitation of the evolutionary algorithms are obtained by the characteristic theory.We then demonstrated the convergence of evolutionary algorithms by analyzing the mechanism underlying the leftward wave,and discussed population diversity by analyzing the rightward wave.Experiments verify the applicability of the proposed wave model.(3)Based on the wave model of evolutionary algorithms,an experimental method to estimate the convergence speed of evolutionary algorithms is proposed.First,based on the wave model,we analyze the volumetric elasticity coefficient of the evolutionary algorithm,which can describe the motion ability of the evolutionary operation to drive the particle system in the evolutionary algorithms.Then we derive the population's density wave velocity equation based on the momentum conservation equation and verify the effectiveness of the method through experiments.On this basis,considering the fluctuation characteristics of the wave model,the propagation speed of the wave crest actually represents the convergence rate of the evolutionary population.We derive the experimental convergence speed method of the evolutionary algorithm based on the propagation of the wave crest.Then,according to the trend of convergence rate,we give an experimental stopping criterion for evolutionary algorithm.To confirm these theoretical and experimental results,we conduct experiments that apply particle swarm algorithm(PSO)to common benchmark problems,showing that the experimental and theoretical results agree.(4)The dynamical model of particle swarm optimization(PSO)is established,and two improved strategies of PSO are proposed.According to the similarity between the oscillation search of particle swarm optimization(PSO)and the overshoot problem of the PID control model,an automatic control dynamical model of PSO is established.Then,by analyzing the dynamical process of the PID automatic control model,we analyze the overshoot problem of the particle swarm optimization algorithm.Experiments show that when the current search direction is the same as the historical search direction,the overshoot phenomenon will be caused by the oscillating search.Therefore,to alleviate the overshoot problem of particle swarm optimization,we propose two strategies to adjust the search direction of particle swarm optimization.One strategy is to introduce the change of search direction into the search process and construct the improved PID control strategy of particle swarm optimization(PBS-PSO).The other strategy is to propose an improved integration separation strategy(ISPSO)by analyzing the construction process of historical momentum direction and current search direction.The experimental results show that the two improved strategies of particle swarm optimization based on the PID automatic control model are efficient and robust.