Research On Application Of Evolutionary Computation Algorithms For Routing Optimization

The main contents of this dissertation are the application of evolutionary computation on routing optimization. The algorithms this dissertation involved are Genetic Algorithm and Particle Swarm Optimization, and the routing optimization problems this dissertation discussed are Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP).There are four aspects in the domain of evolutionary computing: Genetic Algorithm(GA), Evolution Strategies(ES), Evolutionary Programming(EP), and Genetic Programming(GP). In the recent years, Particle Swarm Optimization (PSO) and memetic algorithm are included in the frame of evolutionary computing. Although not the classic branches of evolutionary computing, these algorithms has been developed fast, and been applied well in many fields, and become the important parts of the frame of evolutionary computation.Genetic Algorithm is studied best and applied most broadly among the evolutionary algorithms. Genetic Algorithm (GA) was first proposed by Holland in 1975. GA evolves from a chromosome population created randomly. The chromosomes with higher fitness are selected with higher probability to go through a crossover and mutation procedure, and produce some children that are different from their parents, but inherit some genetic factors from them. After a predefined number of generation, the evolvement stops.Particle Swarm Optimization is a new developed algorithm in recent years. Particle Swarm Optimization was firstly proposed by Kennedy and Eberhart in 1995, and it is an evolutionary algorithm based on iterations. Particle swarm optimization mainly considered the two domains: artificial life, PSO was inspired by the process of searching food of bird flock and fish school, especially Swarm Theory, on the other hand, evolutionary computation, especially has ties to genetic algorithm and evolutionary programming. In the description of PSO, the Swarm is made up of a certain number of particles, at each iteration, all the particles search the global optima in the n-dimensional space. The position and velocity of each particle are updated by certain formulas. In the searching process, each particle is influenced by the three factors: the current velocity of the particle, the best history experience of the particle and the global best experience of all the particles.The traveling salesman problem can be described as follows: one salesman wants to sell his items for the n cities. He wants to choose one tour which visits all the city once and only once, and finally go back to the starting city. The object is to find a minimal length tour. TSP can be described from the view of graph theory: In the graph G = (V, E), V is the set of nodes, or cities, E is the set of edges, E= {(a, b): a, b V}. The Euclidean distance between a and b is Dab , supposing that Dab = Dba . The object of TSP is to find a minimal length closed tour that visits each city once and only once, and the closed tour is also called Hamiltonian Cycle.Particle Swarm Optimization, as a novel evolutionary computing technique, has succeeded in many continuous problems, but research on discrete problems especially routing optimization problem has been done little. In this dissertation, a modified Particle Swarm Optimization (PSO) algorithm was proposed to solve TSP, which is a well-known NP-hard problem. Fuzzy Matrices were used to represent the position and velocity of the particles in PSO and the operators in the original PSO formulas were redefined. Then the algorithm was tested with concrete examples in TSPLIB, experiment shows that the algorithm can achieve good results.Fuzzy Discrete PSO is suitable for the TSP of small size, but when the number of the cities is large, the time and space complexity will increase dramatically. Based on the above consideration, we proposed a fast Particle Swarm Optimization. The algorithm searched in the Cartesian continuous space, constructed a mapping from continuous space to discrete permutation space of TSP, thus to implement the space transformation. Moreover, lo...