A Hybrid Genetic Algorithm For Nonlinear Equations Based On Quasi-Newton Method And Genetic Algorithm

Solving nonlinear equations problem is one of the most basic problems in modern mathematics. Traditional numerical algorithms have fast convergence property , and need much calculation on Hessian matrix . In general , these algorithms have local convergence , that is to say , their convergence is related to the initial point , so they often fails to solve some non-linear equations because of the local convergence , and have low validity. In recent years, people try to introduce some algorithm with large scale convergence to solve non-linear equations, and have some new break-throughs .Based on the thought above,this paper propose the following Hybrid Genetic Algorithm (HGA) for solving non-linear equations , which utilizes the principle of the Genetic Algorithm (GA ), combined the quasi-Newton method . The calculation process of HGA algorithm is as follows:Step 1.Produce initial parent population randomly and calculate their fitness.Step2.Repeat the following Step3-Step7 , until meeting theend condition .Step3.Choose two individuals in the population with probability Pc ,and carry on encodes , crossover, decodes operation, put all the parent and offspring into the subgeneration population;Step4.Carry on encodes, mutation , decodes operation with probability Pm to each individual in subgeneration population, and put all the parent and offspring into the subgeneration population;Step5.Search each individual in subgeneration population with probability Pn for quasi-Newton operator , and put the new produced value into the subgeneration population taking the place of parents;Step6.Calculate fitness of each individual;Step7.Preserve better solution at present, and with the set scale of population, choose the subgeneration population for the next reproduction (Bred the fittest, eliminate the unfit );Step8.Output the result of searching, stop .We use BFGS formula as quasi-Newton operator in HGA as follows : V J p(k)Tq(k)p(k)Tq(k)The operator of crossover , mutation and selection in HGA have function of macroscopical search , that deals with a largescale search , while the quasi-Newton operator has function of local search,and deals with a small circle search and problem of accelerating of search.HGA have well combined their own advantages of GA and Quasi-Newton method, so HGA possess group searching and global convergence of GA, and have local strong searching ability of quasi-Newton method with upper convergent rate and precision. HGA overcome the shortcoming of GA's poor local searching ability ,and when GA comes to it's real solution, the convergence rate of GA is so slow as to result in " premature convergence " and low precision, and HGA effectively solve sensitivity to initial point of quasi-Newton method.Because the state of HGA is in only related to the individual's gene, so we can think every element of state space S is a binary coded integer. Projection 7Tk{i) is the kth binary code of i state , that's to say,it's the kth individual of population. So, HGA can be regarded as a random array in S. The genetic operators in HGA have no relations with generation, so HGA is a homogeneous Markov chain. The transformation matrix P of HGA can be expressed by product of three random matrix C ? M and S, where C ? M and S are the transformation matrix caused by crossover , variation and selection operator.Lemmal Let pc ï¿¡ [0,1] is crossover probability of SGA iVm ï¿¡ [051] is variation probability of SGA, adopt the roulette wheel...