IJPAM: Volume 115, No. 4 (2017)

Title

GENETIC ALGORITHM ADOPTING IMMIGRATION
OPERATOR TO SOLVE THE ASYMMETRIC
TRAVELING SALESMAN PROBLEM

Authors

Chakir Tajani$^1$, Otman Abdoun$^2$, Ahmed Idrissi Lahjouji$^3$
$^{1,2}$Department of Mathematics
Polydisciplinary Faculty of Larache
Abdelmalek Essaadi University, MOROCCO
$^3$Department of Mathematics and Informatics
Faculty of Sciences of Meknes
Moulay Ismail University
MOROCCO

Abstract

In this work, we are interested in improving the performance of genetic algorithm (GA) to solve the Asymmetric Traveling Salesman Problem (ATSP). Several approaches have been developed with genetic algorithms based on the adaptation and improvement of different standard genetic operators. We proposes a new GA adopting immigration strategies to maitain diversity and to perform more the genetic algorithm. Experimental results on series of standard instances of ATSP show that the proposed structured memory immigration scheme in GA effectively improves the performance of GAs.

History

Received: February 18, 2017
Revised: May 8, 2017
Published: August 10, 2017

AMS Classification, Key Words

AMS Subject Classification: 80M50, 90C27, 90B06
Key Words and Phrases: asymmetric traveling salesman problem, genetic algorithm, optimization problem, immigration operator

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
G. Dantzig, D. Fulkerson and S. Johnson, Solutions of a large-scale traveling-salesman problem, Journal of the Operations Research Society of America, 2 (1954), 393-410.

2
M. R. Garey and D.S. Jonhson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman (1979).

3
K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic, Eur. J. of Oper. Res., 126 (2000), 106-130.

4
I. M. Oliver, D. J. Smith and JRC. Holland, A study of permutation crossover operators on the traveling salesman problem, In Proc. of the second international conference on genetic algorithms (ICGA'87) Cambridge, MA: Massachusetts Institute of Technology (1987).

5
D. Goldberg, Genetic Algorithm in Search, Optimization, and Machine Learning, Addison Wesley (1989).

6
J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge, MA (1992).

7
L. Davis, D. Orvosh, A. Cox and Y. Qiu, A Genetic Algorithm for Survivable Network Design, ICGA (1993), 408-415.

8
Z. Michalewicz, Genetic algorithms + data structures = evolution programs, Berlin: Springer ( 1992).

9
O. Abdoun, C. Tajani and J. Abouchabaka, Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem Analyzing, Int. J. of Emer. Sci., 2 (2012), 61-77.

10
O. Abdoun, J. Abouchabaka, A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem, Int. J. of Comp. Appl., 31 (2011), 49-57.

11
V. A. Cicirello, Non-wrapping order crossover: An order preserving crossover operator that respects absolute position, GECCO, (2006), 1125-1131.

12
O. Abdoun, C. Tajani and J. Abouchabaka, Hybridizing PSM and RSM Operator for Solving NP-Complete Problems: Application to Traveling Salesman Problem, Int. J. of Comp. Sci. Iss., 9 (2012), 374-378.

13
L. N. Xing, Y. WuChen, K. WeiYang, F. Hou, X. ShiShen and H. PingCai, A hybrid approach combining an improved genetic algorithm and optimization strategies for the asymmetric traveling salesman problem, Eng. Appl. of Art. Intel., 21 (2008), 1370-1380.

14
J. Grefenstette, Genetic algorithms for changing environments, Parallel Problem Solving from Nature II, (1992), 137-144.

15
Asymmetric Traveling Salesman Problem Data, https://www2.iwr.uni heidelberg.de/groups/com opt/software/TSPLIB95/atsp/ 2011.

How to Cite?

DOI: 10.12732/ijpam.v115i4.13 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2017
Volume: 115
Issue: 4
Pages: 801 - 812


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).