ICTACT Journal on Soft Computing

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Crossover Operators in Genetic Algorithms:A Review


Affiliations
1 Department of Information Technology, Walchand College of Engineering, India
2 Department of Master of Computer Applications, Government College of Engineering, Karad, India
     

   Subscribe/Renew Journal


The performance of Genetic Algorithm (GA) depends on various operators. Crossover operator is one of them. Crossover operators are mainly classified as application dependent crossover operators and application independent crossover operators. Effect of crossover operators in GA is application as well as encoding dependent. This paper will help researchers in selecting appropriate crossover operator for better results. The paper contains description about classical standard crossover operators, binary crossover operators, and application dependant crossover operators. Each crossover operator has its own advantages and disadvantages under various circumstances. This paper reviews the crossover operators proposed and experimented by various researchers.

Keywords

Evolutionary Algorithm, Genetic Algorithm, Crossover, Genetic Operators.
Subscription Login to verify subscription
User
Notifications
Font Size

  • Tomasz Dominik Gwiazda, “Genetic Algorithms Reference”, Volume –I, Poland: Tomasz Gwiazda, 2006

  • David E. Goldberg and Robert Lingle Jr., “Alleles, loci and the traveling salesman problem”, Proceedings of the 1st International Conference on Genetic Algorithms, pp. 154-159, 1985.

  • I. M. Oliver, D. J. Smith, and J. R. C. Holland, “A study of permutation crossover operators on the TSP”, Proceedings of the 2nd International Conference on Genetic Algorithms on Genetic Algorithms and their Application, pp. 224-230, 1987.

  • Lawrence Davis, “Applying adaptive algorithms to epistatic domains”, Proceedings of the 9th international joint conference on Artificial Intelligence, Vol. 1, pp. 162-164, 1985.

  • Gilbert Syswerda, “Schedule optimization using genetic algorithms”, Handbook of Genetic Algorithms, pp. 332-349, New York: Van Nostrand Reinhold, 1991.

  • H. Muhlenbein, “Parallel genetic algorithms, population genetics and combinatorial optimization”, Proceedings of Workshop on Parallel Processing: Logic, Organization and Technology, pp. 398-406, 1991.

  • P. Larranaga, C. M. H. Kuijpers, M. Poza, and R. H. Murga, “Optimal Decomposition of Bayesian Networks by Genetic Algorithms”, Internal Report, EHU-KZAA-IKT-3-94, Department of Computer Science and Artificial Intelligence, University of the Basque Country, 1994.

  • L. Darrell Whitley, Timothy Starkweather and D’Ann Fuquay, “Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator”, Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 133-140, 1989.

  • John J. Grefenstette, Rajeev Gopal, Brian J. Rosmaita and Dirk Van Gucht, “Genetic Algorithms for the Traveling Salesman Problem”, Proceedings of the 1st International Conference on Genetic Algorithms, pp. 160-168, 1985.

  • J. Grefenstette, “Incorporating Problem Specific Knowledge into Genetic Algorithms”, In L. Davis (ed.) “Genetic Algorithms and Simulated Annealing”, Morgan Kaufmann, pp. 42-60, 1987.

  • Sengoku, H., Yoshihara, I., “A Fast TSP Solution using Genetic Algorithm (Japanese)”, Proceedings of 46th National Convention of Information Processing Society of Japan, 1993.

  • Liang-Jie Zhang, Mao Zhi-Hong and Li Yan-Da, “Mathematical Analysis of Crossover Operator in Genetic Algorithms and its Improved Strategy”, Proceedings of IEEE International Conference on Evolutionary Computation, pp. 412-417, 1995.

  • Shengxiang Yang, “Adaptive Non-Uniform Crossover Based on Statistics for Genetic Algorithms”, Proceedings of the Genetic and Evolutionary Computation Conference, pp. 650-657, 2002.

  • Yoshida Junichi, Miki Mitsunori, Hiryasu Tomoyuki and Sakata Yoshinobu, “New Crossover Scheme for Parallel Distributed Genetic Algorithms ” Proceedings of the IASTED International Conference on Parallel and Distributed Computing And Systems, Vol. 1, No. 6-9, pp. 145-150, 2000.

  • S. Shigeyoshi Tsutsui, “Multi-parent recombination in genetic algorithms with search space boundary extension by mirroring”, Parallel Problem Solving from Nature – PPSN V, Lecture Notes in Computer Science, Vol. 1498, pp. 428-437, 2006.

  • S. Tsutsui and A. Ghosh, “A study on the effect of multi-parent recombination in real coded genetic algorithms”, Proceedings of IEEE World Congress on Computational Intelligence, pp. 828-833, 1998.

  • Chuan-Kang Ting and Chun-Cheng Chen, “The Effects of Supermajority on Multi-Parent Crossover”, IEEE Congress on Evolutionary Computation, pp. 4524-4530, 2007.

  • S. Tsutsui, M. Yamamura and T. Higuchi. “Multi-parent recombination with simplex crossover in real coded genetic algorithms”, Proceedings of the Genetic and Evolutionary Computation Conference, Vol. 1, pp. 657-664, 1999.

  • Chuan-Kang Ting, “On the convergence of multi-parent genetic algorithms”, IEEE Congress on Evolutionary Computation, Vol. 1, pp. 396-403, 2005.

  • Chuan-Kang Ting, “On the mean convergence time of multi-parent genetic algorithms without selection”, Proceedings of the 8th European Conference on Advances in Artificial Life, Vol. 3630, pp. 403-412, 2005.

  • A. E. Eiben, “Multiparent Recombination”, Handbook of Evolutionary Computation, Institute of Physics Publishing and Oxford University Press, 1997.

  • A. E. Eiben and C.H.M. van Kemenade, “Diagonal crossover in genetic algorithms for numerical optimization”, Journal of Control and Cybernetics, Vol. 26, No. 3, pp. 447-465, 1997.

  • A.E. Eiben, C.H.M. van Kemenade and J.N. Kok. “Orgy in the Computer: Multi-parent reproduction in genetic algorithms”, Proceedings of the 3rd European Conference on Artificial Life, pp. 934-945, 1995.

  • Kalyan Deb, S. Karthik and Tatsuya Okabe, “Self-Adaptive Simulated Binary Crossover for Real-Parameter Optimization”, Genetic and Evolutionary Computation Conference, pp. 1187-1194, 2007.

  • H. Kita, I. Ono and S. Kobayashi, “Multi-parental extension of the unimodal normal distribution crossover for real-coded genetic algorithms”, Proceedings of the Congress on Evolutionary Computation, Vol. 2, pp. 1581-1588, 1999.

  • Inki Hong, Andrew B. Kahng and Byung Ro Moon, “Exploiting Synergies of Multiple Crossovers: Initial Studies”, Proceedings of IEEE International Conference on Evolutionary Computation, Vol. 1, 1995.

  • Harpal Maini, Kishan Mehrotra, Chilukuri Mohan and Sanjay Ranka, “Knowledge-Based Nonuniform Crossover”, Proceedings of the 1st IEEE Conference on World Congress on Computational Intelligence Evolutionary Computation, pp. 22-271, 1994.

  • Patrik D'haeseleer, “Context Preserving Crossover in Genetic Programming”, Proceedings of the 1st IEEE Conference on World Congress on Computational Intelligence Evolutionary Computation, Vol. 1, pp. 256-261, 1994.

  • P. J. Bentley and J. P. Wakefield, “Hierarchical Crossover in Genetic Algorithms”, Proceedings of the 1st On-line Workshop on Soft Computing, 1996.

  • Chilkuri K. Mohan, “Selective crossover: towards fitter offspring”, Proceedings of the ACM symposium on Applied Computing, pp. 374-378, 1998.

  • Goutam Chakraborty and Basabi Chakraborty, “Rank and Proximity Based Crossover (RPC) to Improve Convergence in Genetic Search”, IEEE Congress on Evolutionary Computation, Vol. 2, pp. 1311-1316, 2005.

  • Yuichi Nagata, “Criteria for designing crossovers for TSP”, IEEE Congress on Evolutionary Computation, Vol. 2, pp. 1465-1472, 2004.

  • Mengjie Zhang, Xiaoying Gao and Weijun Lou, “Looseness Controlled Crossover in GP for Object Recognition”, IEEE Congress on Evolutionary Computation, pp.1285-1292, 2006.

  • Alberto Moraglio, Julian Togelius and Simon Lucas, “Product Geometric Crossover for the Sudoku Puzzle”, IEEE Congress on Evolutionary Computation, pp. 470-476, 2006.

  • Yourim Yoon, YongHyuk Kim, Alberto Moraglio and Byung Ro Moon, “Quotient Geometric Crossovers”, Technical Report, CSM-467, Department of Computer Science, University of Essex, 2007.

  • Takuya Ito, Hitoshi Iba and Satoshi Sato, “Depth-Dependent Crossover for Genetic Programming”, Proceedings IEEE World Congress on Computational Intelligence Evolutionary Computation, pp. 775-780, 1995.

  • Alberto Moraglio, Yong-Hyuk Kim, Yourim Yoon and Byung-Ro Moon, “Geometric Crossovers for Multiway Graph Partitioning”, Evolutionary Computation, Vol. 15, No. 4, pp. 445-474, 2007.

  • Zbigniew Kokosiński, Marcin Kołodziej and Krzysztof Kwarciany, “Parallel Genetic Algorithm for Graph Coloring Problem”, Computational Science - ICCS 2004, Vol. 3036, pp. 215-222, 2004.

  • Jong De Jong and Kenneth Alan, “An Analysis of the Behavior of a class of Genetic Adaptive Systems”, PhD Thesis, University of Michigan, 1975.

  • Donald E. Brown, Christopher L. Huntley and Andrew R. Spillane, “A Parallel Genetic Heuristic for the Quadratic Assignment Problem”, Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 406-415, 1989.

  • Andrew L. Tuson, “The Implementation of a Genetic Algorithm for the Scheduling and Topology Optimisation of Chemical Flowshops”, Technical Report TRGA94-01, Physical Chemistry Laboratory, Oxford University, 1994.

  • H. Muhlenbein, M. Gorges-Schleuter, and O. Kramer, “Evolution Algorithms in Combinatorial Optimization”, Parallel Computing, Vol. 7, No. 1, pp. 65-85, 1988.

  • Sushil. J. Louis and Gregory J. E. Rawlins, “Designer Genetic Algorithms: Genetic Algorithms in Structure Design”, Proceedings of the 4th International Conference on Genetic Algorithms, pp. 53-60, 1991.

  • Laura Barbulescu, Adele E. Howe, L. Darrell Whitley and Mark Roberts, “Understanding Algorithm Performance on an Oversubscribed Scheduling Application”, Journal of Artificial Intelligence Research, Vol. 27, pp. 577-615, 2006.

  • Kengo Katayama and Hiroyuki Narihisa, “An Efficient Hybrid Genetic Algorithm for the Traveling Salesman Problem”, Electronics and Communications in Japan, Vol. 84, No. 2, pp. 76-83, 2001.

  • Sushil J. Louis, Xiangying Yin and Zhen Ya Yuan, “Multiple Vehicle Routing With Time Windows Using Genetic Algorithms”, Proceedings of the Congress on Evolutionary Computation, 1999.

  • Yam Ling Chan, “A Genetic Algorithm Shell for Iterative Timetabling”, M.S. Thesis, Department of Computer Science. RMIT University, 1994.

  • George G. Mitchell, “Evolutionary Computation Applied to Combinatorial Optimisation Problems,” Ph.D. Thesis, School of Electronic Engineering, Dublin City University, 2007.


Abstract Views: 461

PDF Views: 2




  • Crossover Operators in Genetic Algorithms:A Review

Abstract Views: 461  |  PDF Views: 2

Authors

A. J. Umbarkar
Department of Information Technology, Walchand College of Engineering, India
P. D. Sheth
Department of Master of Computer Applications, Government College of Engineering, Karad, India

Abstract


The performance of Genetic Algorithm (GA) depends on various operators. Crossover operator is one of them. Crossover operators are mainly classified as application dependent crossover operators and application independent crossover operators. Effect of crossover operators in GA is application as well as encoding dependent. This paper will help researchers in selecting appropriate crossover operator for better results. The paper contains description about classical standard crossover operators, binary crossover operators, and application dependant crossover operators. Each crossover operator has its own advantages and disadvantages under various circumstances. This paper reviews the crossover operators proposed and experimented by various researchers.

Keywords


Evolutionary Algorithm, Genetic Algorithm, Crossover, Genetic Operators.

References