Title :
Application of multi-step GA to the traveling salesman problem
Author :
Watabe, Hirokazu ; Kawaoka, Tsukasa
Author_Institution :
Dept. of Knowledge Eng. & Comput. Sci., Doshisha Univ., Kyoto, Japan
Abstract :
Although GAs are widely used for optimization problems and often produce good results, there are also problems, such as premature convergence and evolutionary stagnation. The premature convergence caused by a reduction of the diversity and evolutionary stagnation in GAs are observed, and a new genetic algorithm, named multi-step GA (MSGA) is proposed. MSGA narrows the search space to avoid evolutionary stagnation and restarts from the initial population, keeping past results to avoid premature convergence. To evaluate MSGA, traveling salesman problems are considered. As a result, MSGA can avoid premature convergence and evolutionary stagnation and shows higher performance than other conventional GAs
Keywords :
convergence of numerical methods; genetic algorithms; search problems; travelling salesman problems; evolutionary stagnation; multi-step genetic algorithm; optimization; premature convergence; search space; traveling salesman problems; Convergence; Genetic algorithms; Image converters; Intelligent systems; Performance evaluation; Shape; Space exploration; Space technology; Traveling salesman problems;
Conference_Titel :
Knowledge-Based Intelligent Engineering Systems and Allied Technologies, 2000. Proceedings. Fourth International Conference on
Conference_Location :
Brighton
Print_ISBN :
0-7803-6400-7
DOI :
10.1109/KES.2000.884100