Improvement Of Genetic Algorithm And Its Applications In The Traveling Salesman Problem

It has always been a compelling task to develop a universal algorithm that can automatically gains and accumulates the knowledge of a search space during the searching process and then finds an optimal or a sub-optimal solution.Genetic algorithm (GA) is an important branch of evolutionary computing originally invented by Holland in 1975. As it is known, genetic algorithm is inspired by Darwins theory about evolution. GA is an inherently parallel optimization procedure, which utilizes an approach of "survival of the fittest". A basic GA employs selection, crossover and mutation operators. The whole process can be referred to as "reproduction". The main characteristic of the GA is that it is simple, universal and robust. After 20 year's development, GA has been successfully used in a lot of fields such as the traveling salesman problem, scheduling, function optimization, machine learning etc.This dissertation includes two new genetic algorithms. One is genetic algorithm based on gene bank and multiple-searching method for TSP. This algorithm, which combines the idea of gene bank and the multiple-searching method, reconstructs the crossover operator and has a test for several representative traveling salesman problems. The other is a niche adaptive hybrid genetic algorithm for TSP. This improved adaptive hybrid algorithm, which employs the technique of niche and proposes two indexes for variety, avoids premature phenomenon effectively and improves the capability of local search by comparison test of TSP.