|
| Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator
|
|
Full
text: |
 PDF(138.5KB) |
|
|
Source |
International Journal of Biometrics and Bioinformatics (IJBB) |
|
Table of Contents |
|
|
Download
Complete Issue PDF(305.47KB) |
|
Volume: 3 Issue: 6 |
| |
Pages: 96-105 |
|
Publication
Date: January 2010 |
|
ISSN
(Online): 1985-2347 |
|
|
|
|
|
Pages |
96 - 105 |
|
Author(s) |
|
|
|
Published
Date |
02-03-2010 |
|
Publisher |
CSC
Journals, Kuala Lumpur,
Malaysia |
|
ADDITIONAL
INFORMATION |
| Keywords Abstract References Cited by Related Articles Collaborative
Colleague |
| |
|
| |
KEYWORDS: Traveling salesman problem, NP-complete, Genetic algorithm, Sequential constructive crossover |
|
|
| |
|
|
| This Manuscript is indexed in the following databases/websites:- |
|
| 1. Directory of Open Access Journals (DOAJ) |
| 2. Free-Books-Online |
| 3. PDFCAST |
| 4. Docstoc |
| 5. Scribd |
| 6. ScientificCommons |
| 7. Google Scholar |
| 8. WorldCat |
| 9. ResearchGATE |
| 10. refSeek |
| 11. Academic Index |
| 12. Bielefeld Academic Search Engine (BASE) |
| 13. iSEEK |
| 14. Socol@r |
| |
|
| |
|
|
| This paper develops a new crossover operator, Sequential Constructive crossover (SCX), for a genetic algorithm that generates high quality solutions to the Traveling Salesman Problem (TSP). The sequential constructive crossover operator constructs an offspring from a pair of parents using better edges on the basis of their values that may be present in the parents' structure maintaining the sequence of nodes in the parent chromosomes. The efficiency of the SCX is compared as against some existing crossover operators; namely, edge recombination crossover (ERX) and generalized N-point crossover (GNX) for some benchmark TSPLIB instances. Experimental results show that the new crossover operator is better than the ERX and GNX. |
| |
|
| |
|
| |
| 1 |
C.H. Papadimitriou and K. Steglitz. “Combinatorial Optimization: Algorithms and Complexity”. Prentice Hall of India Private Limited, India, 1997.
|
|
|
| 2 |
C.P. Ravikumar. "Solving Large-scale Travelling Salesperson Problems on Parallel Machines”. Microprocessors and Microsystems 16(3), pp. 149-158, 1992.
|
|
|
| 3 |
R.G. Bland and D.F. Shallcross. "Large Travelling Salesman Problems arising form Experiments in X-ray Crystallography: A Preliminary Report on Computation". Operations Research Letters 8, pp. 125-128, 1989.
|
|
|
| 4 |
D.E. Goldberg and R. Lingle. “Alleles, Loci and the Travelling Salesman Problem”. In J.J. Grefenstette (ed.) Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications. Lawrence Erlbaum Associates, Hilladale, NJ, 1985.
|
|
|
| 5 |
L. Davis. “Job-shop Scheduling with Genetic Algorithms”. Proceedings of an International Conference on Genetic Algorithms and Their Applications, pp. 136-140, 1985.
|
|
|
| 6 |
I.M. Oliver, D. J. Smith and J.R.C. Holland. “A Study of Permutation Crossover Operators on the Travelling Salesman Problem”. In J.J. Grefenstette (ed.). Genetic Algorithms and Their Applications: Proceedings of the 2nd International Conference on Genetic Algorithms. Lawrence Erlbaum Associates, Hilladale, NJ, 1987.
|
|
|
| 7 |
D. Whitley, T. Starkweather and D. Shaner. “The Traveling Salesman and Sequence Scheduling: Quality Solutions using Genetic Edge Recombination”. In L. Davis (Ed.) Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, pp. 350-372, 1991.
|
|
|
| 8 |
N.J. Radcliffe and P.D. Surry. “Formae and variance of fitness”. In D. Whitley and M. Vose (Eds.) Foundations of Genetic Algorithms 3. Morgan Kaufmann, San Mateo, CA, pp. 51-72, 1995.
|
|
|
| 9 |
P. Poon and J. Carter. “Genetic algorithm crossover operations for ordering applications”. Computers and Operations Research 22, pp. 135–47, 1995.
|
|
|
| 10 |
I. Choi, S. Kim and H. Kim. "A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem". Computers & Operations Research 30, pp. 773 – 786, 2003.
|
|
|
| 11 |
C. Moon, J. Kim, G. Choi and Y. Seo. "An efficient genetic algorithm for the traveling salesman problem with precedence constraints". European Journal of Operational Research 140, pp. 606- 617, 2002.
|
|
|
| 12 |
D.E. Goldberg. "Genetic Algorithms in Search, Optimization, and Machine Learning". Addison- Wesley, New York, 1989.
|
|
|
| 13 |
K. Deb. “Optimization For Engineering Design: Algorithms And Examples”. Prentice Hall Of India Pvt. Ltd., New Delhi, India, 1995.
|
|
|
| 14 |
Z.H. Ahmed. "A sequential Constructive Sampling and Related approaches to Combinatorial Optimization". PhD Thesis, Tezpur University, India, 2000.
|
|
|
| 15 |
Z.H. Ahmed and S.N.N. Pandit. “The travelling salesman problem with precedence constraints”. Opsearch 38, pp. 299-318, 2001.
|
|
|
| 16 |
TSPLIB, http://www.iwr.uni-heidelberg.de/iwr/comopt/software/TSPLIB95/
|
|
|
| |
|
| |
|
| |
| |
|
| |
|
| |
| |
|
| |
|
| |
|
| Zakir H. Ahmed : Colleagues
|
|
