DocumentCode :
2328967
Title :
A hybrid genetic algorithm and inver over approach for the travelling salesman problem
Author :
Arshad, Shakeel ; Yang, Shengxiang
Author_Institution :
Dept. of Comput. Sci., Univ. of Leicester, Leicester, UK
fYear :
2010
fDate :
18-23 July 2010
Firstpage :
1
Lastpage :
8
Abstract :
This paper proposes a two-phase hybrid approach for the travelling salesman problem (TSP). The first phase is based on a sequence based genetic algorithm (SBGA) with an embedded local search scheme. Within the SBGA, a memory is introduced to store good sequences (sub-tours) extracted from previous good solutions and the stored sequences are used to guide the generation of offspring via local search during the evolution of the population. Additionally, we also apply some techniques to adapt the key parameters based on whether the best individual of the population improves or not and maintain the diversity. After SBGA finishes, the hybrid approach enters the second phase, where the inver over (IO) operator, which is a state-of-the-art algorithm for the TSP, is used to further improve the solution quality of the population. Experiments are carried out to investigate the performance of the proposed hybrid approach in comparison with several relevant algorithms on a set of benchmark TSP instances. The experimental results show that the proposed hybrid approach is efficient in finding good quality solutions for the test TSPs.
Keywords :
genetic algorithms; search problems; travelling salesman problems; embedded local search scheme; hybrid genetic algorithm; inver over approach; sequence based genetic algorithm; travelling salesman problem; Benchmark testing; Bioinformatics; Cities and towns; Convergence; Genomics; Optimization; Traveling salesman problems;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Evolutionary Computation (CEC), 2010 IEEE Congress on
Conference_Location :
Barcelona
Print_ISBN :
978-1-4244-6909-3
Type :
conf
DOI :
10.1109/CEC.2010.5586216
Filename :
5586216
Link To Document :
بازگشت