An Improved Genetic Algorithm For Solving Complementarity Problems

With the development of science and technology,the research of intelligent algorithm develops rapidly.Considerting that most of the intelligent algorithms simulate the natural process,there are some defects more or less.In order to improve its performance,many hybrid algorithms emerge.The hybrid algorithm which combines genetic algorithm and traditional algorithm is one of them.L-M(Levenberg Marquardt)algorithm is a traditional algorithm for solving optimization problems.It has simple structure and wide application range.Some scholars use it to construct hybrid genetic algorithm to solve nonlinear equations and function optimization problems.As an optimization problem,the complementarity problem can be transformed into a system of nonlinear equations,and then into an optimization problem.Therefore,this paper mainly studies how to use L-M algorithm to improve genetic algorithm for solving complementarity problem.The research process and the improvement direction of genetic algorithm are introduced in the first chapter.The method of equivalent transformation of complementarity problem is discussed in the second chapter.The operation flow of genetic algorithm and L-M algorithm is described in this chapter.We use genetic algorithm,L-M algorithm and improved L-M algorithm to carry out numerical experiments from Chapter 3 to Chapter 5.In addition,three different types of numerical examples are selected to introduce the process of solving the exact solution and transforming it into equivalent nonlinear equations.With the help of Sheffield's genetic algorithm toolbox,the general genetic algorithm is simplified to the minimum genetic algorithm,and numerical experiments are carried out to make the calculation result more accurate.According to the types of complementarity problems,the calculation method of Jacobian matrix in the general L-M algorithm is modified,and then different initial values are selected for numerical experiments,which reflect the influence of the selection of initial values on the number of iterations of L-M algorithm.L-M algorithm is introduced into genetic algorithm,there are two methods to improve the genetic algorithm.One method is to introduce L-M algorithm to optimize the individual population after mutation operation,and to change part of the populationgenerated after mutation to all of the optimization replacement in reference [1];the other method is to use the result obtained after a certain number of iterations of genetic algorithm as the initial value,and to use the non-linear optimization method in reference [2]for local optimization,and to change it to acquisition L-M algorithm is used for local optimization.The results of numerical experiments show that the two improved methods are effective.The improved genetic algorithm reduces the population size and the number of iterations accordingly,which not only overcomes the disadvantage of the difficulty in selecting the initial value of L-M algorithm,but also speeds up the convergence speed of the genetic algorithm,and improves the accuracy of the calculation results.Through comparative analysis,it is found that the first method is more applicable than the second method.The first improved method can be used to get high precision results regardless of dimension and sparse matrix.For solving the horizontal linear complementarity problem,the second improved method is more efficient than the first.