The Effects of Parameter Settings on the Performance of Genetic Algorithm through Experimental Design and Statistical Analysis

Abstract:

Genetic algorithm (GA) is a meta-heuristic inspired by the efficiency of natural selection in biological evolution. It is one of the most widely used optimization procedure which has successfully been applied on a variety of complex combinatorial problems. The main drawback of GA, however, is its several tuning variables which need to be correctly set. The performance of GA largely depends on the proper selection of its parameters values; including crossover mechanism, probability of crossover, population size and mutation rate and selection percent. The objective of this research is to evaluate the effects of tuning parameters on the performance of genetic algorithm using the data collected as per Central Composite Design (CCD) matrix. To gather the required data, the proposed approach is implemented on a well-known travelling salesman problem with 48 cities. Then, regression modeling has been employed to relate GA variables settings to its performance characteristic. Analysis of Variance (ANOVA) results indicate that the function can properly represent the relationship between GA important variables and its performance measure (solution quality).

• Periodical: Advanced Materials Research (Volumes 433-440)
• Pages: 5994-5999
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.433-440.5994
• Online since: January 2012
• Authors: Farhad Kolahan, Marziyeh Hassani Doughabadi
• Keywords: ANOVA, Design of Experiment (DOE), Genetic Algorithm (GA), Regression Modeling

References

[1] C. Moon, J. Kim, G. Choi, Y. Seo, An efficient genetic algorithm for the traveling salesman problem with precedence constraints, European Journal of Operational Research 140, 2002, p.606–617.

DOI: 10.1016/s0377-2217(01)00227-2

[2] F. Liu, G. Zeng, Study of genetic algorithm with reinforcement learning to solve the TSP, Expert Systems with Applications 36, 2009, p.6995–7001.

DOI: 10.1016/j.eswa.2008.08.026

[3] O. Ghrayeb and N. Phojanamongkolkij, A study of optimizing the performance of genetic algorithms using design-of-experiments in job-shop scheduling application, International Journal of Industrial Engineering-theory Applications and Practice 12, 2005, pp.37-44.

[4] M. Kaya, The effects of two new crossover operators on genetic algorithm performance, " Applied Soft Computing, "in press, (2010).

[5] M. Albayrak and N. Allahverdi, Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms, " Expert Systems with Applications, "in press, (2010).

DOI: 10.1016/j.eswa.2010.07.006

[6] P. Pongcharoen, W. Chainate and P. Thapatsuwan, Exploration of Genetic Parameters and Operators through Travelling Salesman Problem, Science Asia 33, 2007, pp.215-222.

[7] E. Alfaro-Cid, E.W. McGookin, D.J. Murray-Smith, A comparative study of genetic operators for controller parameter optimization, Control Engineering Practice, vol. 17, 2009, p.185– 197.

DOI: 10.1016/j.conengprac.2008.06.001

[8] G. Laporte, The traveling salesman problem: An overview of exact and approximate algorithms, European Journal of Operational Research, vol. 59 (2) , 1992, pp.231-247.

DOI: 10.1016/0377-2217(92)90138-y

[9] S. Chatterjee, C. Carrera, L. A. Lynch, Genetic algorithms and traveling salesman problems, European Journal of Operational Research, vol. 93 (3), 1996, pp.490-510.

DOI: 10.1016/0377-2217(95)00077-1

[10] www. iwr. uniheidelberg. de/iwr/comopt/soft/ TSPLIB95/TSPLIB. html.

[11] C. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Wesley: Addison, (1989).

[12] L. H. Randy, Haupt Sue Ellen, Practical Genetic Algorithm, JOHN WILEY & SONS, (2004).

[13] D.C. Montgomery, Design and analysis of experiments – fifth edition, JOHN WILEY & SONS, (2001).

[14] F. Kolahan, M. M. Bagheri, Modeling and prediction of process parameters in Submerged Arc Welding by Genetic Algorithm, Proc. of the 37th International Conference on Computers and Industrial Engineerin, October 20-23, 2007, Alexandria, Egypt.