Solving Traveling Salesman Problem And The Ant Colony Algorithm For Nonlinear Equations

Traveling salesman problem(TSP) and nonlinear equations are two kinds of important problems with widely applications.TSP is a typical NP-hard combination optimization problem.It has been widely applied to many fields,such as transport,circuit board line,physical distribution and so on.Especially,it is also a typical testing case for effectiveness of the ant colony algorithm. Nonlinear equations are important problems in science and engineering fields,such as numerical weather prediction,the exploration of petroleum geology,the calculation of biochemistry,control field and orbit design.In particular,the Kuhn-Tucker conditions of constrained optimization problems are asymmetrical nonlinear equations.Thus how to solve them is significant in both theory and application.There are many methods for solving TSP,yet traditional methods are difficult to solve the optimizations because the computing time is increased with problem scale.With the rising of evolutionary algorithm,such as genetic algorithms(GA),ant colony algorithms(ACA) and particle swarm optimization(PSO),people begin to use them to solve TSP.Among them,ACA derived from the foraging behavior of real ants of nature has shown strong search abilities for solving TSP because of positive feedback mechanism,stronger robustness,good distributed computing and combination with other algorithms easily.In Chapter 2,started from TSP,we introduce basic situation of ACA, including the development background,basic theory and procedure,complexity,convergence and its properties,In Chapter 3,for the symmetric TSP,we analyze the Ant Colony System(ACS) and ant colony genetic algorithm(ACSGA) on basis of the existing methods.To avoid local optimization, we first introduce cross operator.Then we introduce candidate list and 2-exchang strategy to speed up the convergence and improve the solution accuracy,and an improved ACA for solving TSP is supposed.The simulation results show that the proposed method avoids local optimization and has some improvement in executive efficiency and solution quality.The traditional Newton method is still the widest methods for solving nonlinear equations,yet its strong dependence of initial value limits the application.In recent years,evolutionary algorithms such as genetic algorithm have been shown particular property for solving nonlinear equations with large complexity and various states because of its abilities of global research and fast convergence. For asymmetrical nonlinear equations,we summarize the recent methods,and analyze a kind of ACA for solving unconstrained optimization problem in Chapter 4.Since the experiments indicate that the method for solving unconstrained optimization problem has strongly convergent speed and good precision,we extend to solve nonlinear equations.To do this,we first transform it into an equivalent unconstraint optimization problem,and then the quasi Newton method is introduced to speed up local research,and the parameters are used by dynamic and self-adaptive mechanism to improve the stability.Finally,quasi Newton ant colony algorithm is proposed.The experiment data show that the new algorithm is feasible and effective.Compared with the quasi Newton methods and ACA,the solution accuracy of new algorithm is not only improved,but also the convergent reliability is increased.