Evolutionary Algorithm For Dynamic Multi-objective TSP

In many application areas of scientific management and economic decision making, there are a lot of multi-objective optimization problems. In a specific Traveling Salesman Problem (TSP), often have to consider some goals simultaneously, such as the shortest route, the minimum time, the lowest risk, the minimum cost and many other factors. How to get a fair and reasonable solution is a complicated issue. In real life, a large number of multi-objective optimization problems are time-dependent and the environment of the problems changes with the time. So these optimization problems have not only multi-objective nature, but also dynamic nature.Dynamic multi-objective TSP (DMOTSP), a new research filed of evolutionary computation, is an NP-hard problem which comes from the applications of mobile computing, mobile communications. DMOTSP is a combination of dynamic TSP and multi-objective TSP, which was first proposed as a mathematical model of aerospace communication between ground base, aero base and space base in 2004. It is harder than classical TSP, DTSP and MOTSP and demands to track the dynamic Pareto optimal front in real time. Researching DMOTSP is of great theoretical significance and research value, because it would promote a development in network topology and routing optimization problems such as mobile computing, mobile communications and aerospace communication.The first two chapters introduce the basic knowledge of TSP and genetic algorithm, and the research status for TSP. Chapter 3 to Chapter 5 introduces the author's productions about DMOTSP.There are some important problems of theories which have not been solved or researched yet, such as measuring the degrees of dynamic change and conflict between objectives, evaluating the Pareto set and the algorithms' performance for DMOTSP, the correlation between the degree of conflict between objectives and the number of solutions in the Pareto set.In Chapter 3, the concepts of dynamic degree and conflict degree are first proposed and the problems of measuring the degree of dynamic change and conflict between objectives are investigated. The change of problem's environment is reflected through the change of the cost matrixes with time. And the cost matrixes of all objectives determine the correlation of objectives. So measuring the degree of problem dynamic change and the conflict between objectives is to compare how different between some correlative cost matrixes. Methods for measuring dynamic and conflict degree are proposed, which can be used to compute the degree of dynamic change and conflict between objectives. These works can make a greate contribution to optimization algorithm designing. And an evaluation criterion of the algorithms for DMOTSP called Paretos-Similarity is also proposed, with which can evaluate the Pareto set and algorithms' performance for DMOTSP. Paretos-Similarity can evaluate how much a Pareto set close to the optimal Pareto set, which is from the number of solutions in Pareto set, the best approximate degree of each objective in Pareto set, the average approximate degree of Pareto set and the uniform and diversity of distribution of solutions in Pareto set.In Chapter 4, a dynamic multi-objective evolutionary algorithm for DMOTSP, DMOInver-Over, is proposed, which embraces an effective operator, Inver-Over, for static TSP and dynamic elastic relaxation operators for dynamic TSP. It can track the Pareto front of medium-scale dynamic multi-objective TSP in which the number of cities is between 100 and 200. In experiment, taking CHN144+5 with two objectives for example, the algorithm is tested. From the experiment results, it can be seen that DMOInver-Over solver can get an approximate Pareto optimal set with Inver-Over, dynamic elastic relaxation operators and the rules for generating offspring population can speed up the convergence of algorithms.For multi-objective problems, its difficulties and the Pareto optimal front depend on the conflict degree between objectives. The conflict degree changes with time for dynamic multi-objective problems. A single algorithm can not solve effectively this kind of problems, which is decided by the theorem, NFLTs. In Chapter 5, a new approach to designing algorithm, multi-algorithm co-evolution strategy (MACS), for DMOTSP is proposed. Through multi-algorithm co-evolution, MACS can make these algorithms' performance complemented, avoid the limitations of a single algorithm, accelerate algorithm's convergence, make Pareto set maintain diversity and make Pareto front distribute evenly. In experiment, taking the three-dimensional benchmark problem CHN144+5 with two-objective for example, the results show that MACS can solve DMOTSP effectively with faster convergence, better diversity of Pareto set and more even distribution of Pareto front than single algorithm.