Research On Coevolutionary Algorithms Based On Balanced Search

With the rapid development of social production,the demand for solving optimization problems is more and more urgent.Evolutionary algorithms have become important tools for solving those problems which can not be solved or can not be effectively solved by deterministic optimization algorithms.In recent years,many evolutionary algorithms including swarm intelligence optimization algorithms have been proposed.However,no free lunch theory has stated that no optimization algorithm can perform better than any other algorithm on all types of optimization problems.And another study has shown that there are some problems that are more difficult for one algorithm,but simpler for another algorithm,and vice versa.Therefore,integration or cooperation of different optimization algorithms and multi-population optimization algorithms that can increase the scope of the algorithm to solve the problem effectively have become promising solutions.Coevolutionary algorithm is an extension of traditional evolutionary algorithm and has great potential to solve the problem of poor performance when using general evolutionary algorithms.This dissertation studies coevolutionary strategies based on evolutionary programming and particle swarm optimization algorithm,and improves these algorithms by means of balancing exploration and exploitation.At the same time,the proposed coevolutionary particle swarm optimization algorithm is used to solve the evolutionary search problem in the feature space.The main research contents and innovations of this dissertation are as follows:(1)Coevolutionary strategy based on Shapley value: Aiming at the difference in the applicability of different mutation operators of evolutionary programming algorithms on different types of problems,a more adaptable coevolutionary programming based on Shapley value is proposed.The coevolutionary strategy takes the mean fitness value of the successful offspring generated by different mutation operators as the benefit,and uses the Shapley value method to allocate "fair" selection probabilities to mutation operators,so that the algorithm can effectively adjust selection probabilities according to the performance of mutation operators.At the same time,in order to balance the exploration and exploitation of evolutionary programming,the average mutation step size is used to update individuals.So as to better explore the search space at the beginning of the evolution process,and better exploit the space at the later stage,to avoid search stagnation caused by the rapid decline of mutation standard deviation.(2)Coevolutionary strategy based on local fitness landscape: Aiming at the problem that the coevolutionary strategy based on Shapley value is sensitive to the fitness value,a coevolutionary strategy based on local fitness landscape roughness is proposed.First,a new calculation method for estimating local landscape roughness based on the local and global optima in the population is proposed.The Lévy mutation operators with different parameters are suitable for solving problems with different landscape characteristics.The algorithm adjusts the parameters of Lévy mutation operators according to the local landscape roughness,so that more individuals use the Lévy mutation operator adapted to the landscape.This strategy makes the algorithm have a good population diversity and mainly completes the exploration task.At the same time,an improved local search step is added to the algorithm to improve the exploitation ability of the algorithm.(3)Coevolutionary strategy based on the change rate of fitness value: Aiming at the difficulty of determining the suitable fitness landscapes for optimization algorithms,a coevolutionary particle swarm optimization algorithm based on the change rate of fitness value is proposed according to the mixed strategy in game theory.The algorithm has strong adaptability and is easy to implement.In the algorithm,the particles in the population are regarded as the players of the game,and the search process is the game process.In the search process,the particles choose different strategies to generate offsprings to play games with other particles.And the selection probabilities of the strategies are dynamically adjusted according to the change rates of the fitness values of particles.In addition,in order to further improve the optimization performance of the algorithm,one of the variant algorithms is improved,so that the algorithm can enhance the exploitation ability while maintaining the exploration ability.In order to balance the exploration and exploitation of the algorithm,the global optimum is added to the velocity update,and the average population velocity is used to guide the update of the particle velocity with the probability of linearly decreasing.(4)Application of coevolutionary particle swarm optimization algorithm to feature selection: The feature selection problem can be regarded as a combinatorial optimization problem.When using the optimization algorithm for feature selection,the performance of the optimization algorithm and the quality of the objective function are the two main factors that affect the performance of the feature subset.The coevolutionary particle swarm optimization algorithm has good optimization performance,so using it to solve the feature selection problem can improve the classification accuracy of feature subset.In addition,in order to make the final feature subset both small in size and high in classification accuracy,an objective function combining distance measurement and information entropy is proposed.The function focuses on both classification accuracy and feature subset size.Using the coevolutionary particle swarm optimization algorithm to solve this objective function,the classification accuracy of the obtained feature subset is high,and the subset size is small and stable.