Need of Optimizing for Optimum Solution for TSP by applying Knowledge Augmentation in Genetic Algorithm using OX, PMX, CX Crossover Operators

Poonam Punia , Surender Jangra

Abstract


In modern era of computer science and operational research several researches are made on large data set through various traditional methodologies and newer technologies and methods. The biggest challenge is to find best optimum solution for a particular problem in order to bring out efficient and time saving results. Genetic Algorithms plays a vital role when we are dealing with large data set and random number in order to find best optimal solution. In our study GA’s are used as common practice. The cycle of genetic algorithm goes through various phases namely selecting initial population, finding out best fittest population, applying crossover strategy, selection and mutation. Three crossover techniques of GA’s order crossover OX, cycle crossover, partially mapped crossover PMX are compared and contrast with change in existing techniques in order to produce more efficient results. We have chosen one of most common and widely used problems that are traveling salesman problem TSP for these crossover operators by introducing knowledge augmentation in these crossover techniques. The feasibility study includes finding out best optimum solution for traveling salesman by using above three techniques of crossover that is order crossover OX, cycle crossover, partially mapped crossover, PMX using knowledge augmentation. By using knowledge augmentation results are compared with existing output of these crossover techniques. The goal of work is to improve performances for finding shortest path in TSP by using knowledge augmentation. Genetic algorithms are popular due to their large diversity in efficient execution of large data sets. Unlike in evolutionary algorithms GA’s are well enough to produce efficient results. 


Full Text:

PDF

References


Ahmed, H. Zakir,Genetic Algorithm for Traveling Salesman Problem using Sequential Constructive Crossover Operator, International Journal of Biometrics & Bioinformatics (IJBB) Volume (3): Issue (6)

Davis, L. D., ed. (1991),Handbook of Genetic Algorithms. Van Nostrand Reinhold.

Goldberg, D. E. (1989a),Genetic Algorithms in Search, Optimization, & Machine Learning.Addison−Wesley.

Goldberg, D. E. (1989b),Genetic Algorithms in Search Optimization & Machine Learning, Addison-Wesley, Reading, MA.

Holland, J. H. (1975/1992).Adaptation in Natural & Artificial Systems. Cambridge, MA:MIT Press. Second edition (1992). (First edition, University of Michigan Press,1975).

Lin, Guangming & Yao, xin (1997), Analyzing crossover operator by search step size, Canberra, Act, Australia 2600: Computational Intelligence Group, School of Computer Science university College, The University of South Wales,and Australian Defense Force Academy.

Oliver, I.M. & Smith, D. J. and Holland J.R.C, (1987),A Study of Permutation Crossover Operators on Travelling Salesman Problem”.In J.J.

Rasheed, Khaled (1999), Guided Crossover: A New Operator For Genetic Algorithm Based Optimization, New Brunswick, NJ08903, USA:Computer Science Department, Rutgers University

Vahdati, Gohar. et.al (n.d), A New Approach to Solve Traveling Salesman Problem Using Genetic Algorithm Based on Heuristic Crossover & Mutation Operator.

OTHER SOURCES

Bonomi, E. & Lutton J-L,The N-city travelling salesman problem: statistical mechanism & Metropolis Algorithm, SIAM Review Vol. 26(4), pp. 551-559 (Oct 1984).

Potvin, Jean-Yves (n.d), Genetic Algorithms for Traveling Salesman Problem: Montréal (Québec)Canada H3C 3J7, Centre de Recherche Sur Les Transports University de Montréal.

Riolo, R. L. (1992), Survival of fittest bits. Scientific American, 267, no. 1: 114–116.

S.N. Sivanandam & S. N. Deepa. (2007), Introduction to Genetic Algorithms, Springer, ISBN 9783540731894.

Takahashi, Ryouei.(n.d), Solving Traveling Salesman Problem through Genetic Algorithms with Changing Crossover Operators , Japan: Hachinohe Institute of Technology.


Refbacks

  • There are currently no refbacks.