DESIGN AND APPLICATIONS OF GENETIC ALGORITHM FOR THE TRAVELLING SALESMAN PROBLEM

Abstract

In most real world optimization problems it is often desired to determine a global optimal solution rather than a local optimal solution. Determining the global optimal solution of an optimization problem is generally more difficult as compared to the problem of determining a local optimal solution. However because of the practical necessity the search for the point of global optimum often becomes necessary. Conventional computing paradigms usually face difficulty in dealing with such real life problems. Natural systems have emerged over millennia to solve such problems. They have inspired several natural computing paradigms that can be used where conventional computing techniques perform unsatisfactorily. Genetic Algorithm (GA) is one of the most effective and popular natural computing technique which takes its inspiration from Darwin's theory of evolution "Survival of the Fittest". GA has undergone many changes since its introduction. As researchers have learned about the technique, they have derived new versions, developed new applications, and published theoretical studies of the effects of the various operators, parameters and aspects of the algorithm. One such important part of GA family is Permutation Coded Genetic Algorithm (PCGA). This Thesis is computationally dominant and interdisciplinary in nature which aims to improve the efficiency and reliability of PCGAs and their application to the Travelling Salesman Problem. The main contribution of this Thesis is the development of new PCGAs by proposing five new operators -three variations of order crossover operators and two combined mutation operators for Permutation Coded Genetic Algorithms to determine global optimal solutions. Firstly, three new variations of order crossover operators are proposed and their performance is evaluated over the existing two basic variants. These are implemented on a set of benchmark test problems taken from TSPLIB. The analysis of results based on the numerical and graphical analysis indicate that the new variations of the order crossover proposed in this chapter have a definite supremacy over the existing variants for TSP. Next, the minimum cost, time and distance of a tour that connects all 13 zonal and 8 special wereda cities of the south Ethiopian regional state is determined by modeling the problem as a Travelling Salesman problem and solving it by Genetic Algorithm. In order to make sure that the new minimum distance, cost and time is reasonable, two existing and three new variants of order crossover operator are applied. Four TSPLIB benchmark problems are also tested. Introduction of the problem, case study of SNNPR state, Encoding, Initial population Generation and Selection operator are discussed. After application two combined mutation operators have been developed to increase the performance of Genetic Algorithm that helps to find the minimum cost in the known Travelling Salesman problem (TSP). In order to do this the combined mutation operators which are named as Inverted Exchange and Inverted Displacement are compared with four existing mutation operators. The crossover operator used here is the order crossover using two of its existing and three of its new variations. In general six mutation operators, ten benchmark test problems from the TSPLIB and five variations of order crossover are used. Based on the numerical and graphical analysis it is indicated that the Inverted Displacement has a definite supremacy over the existing four mutations except for few instances considered here. A variant of partially mapped crossover (VPMX) is also designed using cut point positions and is tested for its performance with the existing partially mapped crossover (PMX). In order to test the performance, two mutation operators are used. These mutation operators are inverted displacement and inversion mutations. Partially mapped crossover (PMX) with inversion and with inverted displacement and a variant of partially mapped crossover (VPMX) with inversion and with inverted displacement are programmed and implemented on a set of ten benchmark problems taken from the Travelling salesman problem library (TSPLIB). The results indicate that the designed variant of PMX is superior by showing a better performance in eight instances in combination with the inverted displacement mutation. In two instances PMX has obtained a better result. One is PMX with inversion mutation and the other is PMX with inverted displacement mutation. Finally, it is tried to solve the Travelling Salesman Problem (TSP) on Indian railways. Metropolitan city railway stations that are connected to each other are considered. The fourth variation of order crossover (0X4) proposed in previous chapter of this Thesis with Inversion mutation and Inverted Displacement mutation are used. These are found to be superior in chapter two of this Thesis. These are programmed in C++ and implemented on the distance, cost and time data obtained from the Indian railways. The minimum and maximum distances of travel, costs of travel and time taken to cover the stations are evaluated. According to the analysis of results that is based on numerical and graphical analysis it is concluded that the sequence of choosing railway stations is very crucial. This is observed by the big difference between the minimum and maximum distance, cost and time of travel evaluated. Especially the difference between the minimum and maximum results of distance travelled and time taken to cover the tours is almost double. ii