An Efficient Genetic Algorithm for Numerical Function Optimization with Two New Crossover Operators

Full Text (PDF, 642KB), PP.42-55

Views: 0 Downloads: 0

Author(s)

Abid Hussain 1,* Yousaf Shad Muhammad 1 Muhammad Nauman Sajid 2

1. Department of Statistics, Quaid-i-Azam University, Islamabad, Pakistan

2. Department of Software Engineering, Foundation University, Islamabad, Pakistan

* Corresponding author.

DOI: https://doi.org/10.5815/ijmsc.2018.04.04

Received: 20 Apr. 2018 / Revised: 5 Jun. 2018 / Accepted: 19 Jul. 2018 / Published: 8 Nov. 2018

Index Terms

Genetic algorithms, Crossover operators, Benchmark functions, Comparison

Abstract

Selection criteria, crossover and mutation are three main operators of genetic algorithm’s performance. A lot of work has been done on these operators, but the crossover operator has a vital role in the operation of genetic algorithms. In literature, multiple crossover operators already exist with varying impact on the final results. In this article, we propose two new crossover operators for the genetic algorithms. One of them is based on the natural concept of crossover i.e. the upcoming offspring takes one bit from a parent and next from other parent and continuously takes bits till last one. The other proposed scheme is the extension of two-point crossover with the concept of multiplication rule. These operators are applied for eight benchmark problems in parallel with some traditional crossover operators. Empirical studies show a remarkable performance of the proposed crossover operators.

Cite This Paper

Abid Hussain, Yousaf Shad Muhammad, Muhammad Nauman Sajid,"An Efficient Genetic Algorithm for Numerical Function Optimization with Two New Crossover Operators", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.4, No.4, pp.42-55, 2018. DOI: 10.5815/ijmsc.2018.04.04

Reference

[1]Holland, J.H. Adaptation in Natural and Artificial Systems. Ann Arbor, MI, USA: University of Michigan Press; 1975.

[2]Goldberg, D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Boston, MA, USA: Addison-Wesley Longman Publishing; 1989.

[3]Datta, D. Unit commitment problem with ramp rate constraint using a binary-real- coded genetic algorithm. Appl Soft Comput. 2013; 13:3873-3883.

[4]Dudek, G. Genetic algorithm with binary representation of generating unit start-up and shut-down times for the unit commitment problem. Expert Syst Appl. 2013; 40:6080-6086.

[5]Sun, L., Zhang, Y., Jiang, C. A matrix real-coded genetic algorithm to the unit commitment problem. Electr Pow Syst Res. 2006; 76:716-728.

[6]Dudek, G. Unit commitment by genetic algorithm with specialized search operators. Electr Pow Syst Res. 2004; 72:299-308.

[7]Swarup, K., Yamashiro, S. Unit commitment solution methodology using genetic algorithm. IEEE T Power Syst. 2002; 17:87-91.

[8]Dang, C., Li, M. A floating-point genetic algorithm for solving the unit commitment problem. Eur J Oper Res. 2007; 181:1370-1395.

[9]Pavez-Lazo, B., Soto-Cartes, J. A deterministic annular crossover genetic algorithm optimization for the unit commitment problem. Expert Syst Appl. 2011; 38:6523-6529.

[10]Bukhari, S.B., Ahmad, A., Raza, S.A., Siddique, M.N. A ring crossover genetic algorithm for the unit commitment problem. Turk J Elec Eng & Comp Sci. 2016; 24:3862-3876.

[11]Kohshori, M.S., Zeynolabedini, D., Liri, M.S., Jadidi, L. Multi Population Hybrid Genetic Algorithms for University Course Timetabling Problem. International Journal of Information Technology and Computer Science. 2012; 4(6):1-11.

[12]Caruana, R.A., Eshelman, L.J., Schaffer, J.D. Representation and hidden bias II: Eliminating defining length bias in genetic search via shuffle crossover. In: Proceedings of the 11th International Joint Conference on Artificial intelligence. 1989; 750-755.

[13]Spears, W.M., Anand, V. A study of crossover operators in genetic programming. In: International Symposium on Methodologies for Intelligent Systems; Springer, Berlin, Heidelberg. 1991;409-418.

[14]Picek, S., Golub, M. Comparison of a crossover operator in binary-coded genetic algorithms. WSEAS Trans. Comput. 2010; 9:1064-1073.

[15]Adeli, H., Cheng, N.T. Integrated genetic algorithm for optimization of space structures. J AEROSPACE ENG. 1993; 6:315-328.

[16]Adeli, H., Cheng, N.T. Augmented Lagrangian genetic algorithm for structural optimization. J AEROSPACE ENG. 1994; 7:104-118.

[17]Adeli, H., Cheng, N.T. Concurrent genetic algorithms for optimization of large structures. J AEROSPACE ENG. 1994; 7:276-296.

[18]Wu, S.J., Chow, P.T. Steady-state genetic algorithms for discrete optimization of trusses. COMPUT STRUCT. 1995; 56:979-991.

[19]Jenkins, W.M. On the application of natural algorithms to structural design optimization. ENG STRUCT. 1997; 19:302-308.

[20]DeJong, K.A., Spears, W.M. An analysis of the interacting roles of population size and crossover in genetic algorithms. In: International Conference on Parallel Problem solving from Nature; Springer, Berlin, Heidelberg. 1990; 38-47.

[21]Syswerda, G. Uniform crossover in genetic algorithms. In: Proceedings of the 3rd International Conference on Genetic Algorithms. 1989; 2-9.

[22]Hasanc¸ebi, O., Erbatur, F. Evaluation of crossover techniques in genetic algorithm based optimum structural design. COMPUT STRUCT. 2000; 78:435-448.

[23]Zaharie, D. Influence of crossover on the behavior of differential evolution algorithms. APPL SOFT COMPUT. 2009; 9:1126-1138.

[24]Khan, I.H. Assessing Different Crossover Operators for Traveling Salesman Problem. International Journal of Intelligent Systems and Applications. 2015; 7(11):19-25.

[25]Kellegoz, T., Toklu, B., Wilson, J. Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem. Applied Mathematics and Computation. 2008; 199:590-598.

[26]Reeves, C.R. Genetic algorithms. In Handbook of Metaheuristics, pp. 109-139. Springer, Boston, MA; 2010.

[27]Back, T. Evolutionary algorithms in theory and practice. New York, Oxford university press; 1996.

[28]Beasley, D., Bull, D.R., Martin, R.R. An overview of genetic algorithms: Part 2, research topics. University computing. 1993; 15:170-181.

[29]Kaya, M. The effects of two new crossover operators on genetic algorithm performance. Applied Soft Computing. 2011; 11:881-890.

[30]Hussain, A., Muhammad, Y.S., Nawaz, A. Optimization through genetic algorithm with a new and efficient crossover operator, International Journal of Advances in Mathematics. 2018; 1:1-14.

[31]Srinivas, M., Patnaik, L.M. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics. 24, (1994) 656-667.

[32]Ortiz-Boyer, D., Hervas-Martinez, C., Garcia-Pedrajas, N. CIXL2: A Crossover Operator for Evolutionary Algorithms Based on Population Features. J. Artif. Intell. Res. (JAIR). 2005; 24:1-48.

[33]Friedman, J.H. An overview of predictive learning and function approximation. In From Statistics to Neural Networks. Springer, Berlin, Heidelberg. 1994; 1-61.

[34]Deb, K. Genetic algorithms in multimodal function optimization. PhD diss., Clearinghouse for Genetic Algorithms, Department of Engineering Mechanics, University of Alabama; 1989.

[35]Himmelblau, D.M. Applied nonlinear programming. McGraw-Hill Companies; 1972.

[36]Li, X., Engelbrecht, A., Epitropakis, M. Benchmark functions for CEC’2013 special session and competition on niching methods for multimodal function optimization, Tech. rep., RMIT University; 2013.

[37]Michalewicz, Z. Genetic Algorithms + Data Structures= Evolution Programs. 3rd ed. London, UK: Springer-Verlag; 1996.

[38]Goldstein, A.A., Price, J.F. On descent from local minima. MATH COMPUT. 1971; 25:569574.

[39]Easom, E.E. A survey of global optimization techniques. PhD, University of Louisville, Kentucky, United States; 1990.

[40]DeJong, K.A. Analysis of the behavior of a class of genetic adaptive Systems. PhD, Dept.Computer and Communication Sciences, University of Michigan, Ann Arbor; 1975.