Research in Random Parameters of Genetic Algorithm and Its Application on TSP and Optimization Problems

Mohammed Masoud JAVIDI; Roghiyeh Hoseinpour FARD; Mahdi JAMPOUR

Authors

Mohammed Masoud JAVIDI Department of Computer Science, Shahid Bahonar University of Kerman, Kerman
Roghiyeh Hoseinpour FARD Department of Computer Science, Shahid Bahonar University of Kerman, Kerman
Mahdi JAMPOUR Department of Computer Science, Shahid Bahonar University of Kerman, Kerman

Keywords:

Genetic algorithm, Schaffer, Ackley, Rastrigin, traveling salesman problem

Abstract

In this paper, we consider a variety of random parameters of genetic algorithms based on some benchmark functions and traveling salesman problem (TSP). We have analyzed parameters of the genetic algorithm such as population size, crossover probability and mutation probability. The experiments have shown that we cannot propose a uniform model for the parameters of a genetic algorithm. However increasing of population size can reduce genetic algorithm iterations but crossover probability and also mutation probability strongly depend on benchmark functions.

doi:10.14456/WJST.2015.3

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...

References

CS Danalakshmi and GM Kumar. Optimization of supply chain network using genetic algorithm. J. Manuf. Eng. 2010; 3, 30-5.

IG Tsoulos and A Stavrakoudis. Enhancing PSO methods for global optimization. J. App. Math. Comput. 2010; 216, 2988-3001.

X Liu. The barrier attribute of filled functions. J. Appl. Math. Comput. 2004, 149, 641-9.

M Gaviano. Some General Results on the Convergence of Random Search Algorithms in Minimization Problems. In: LCW Dixon and GP Szegö (eds.). Towards Global Optimization, 1975, p. 149-57.

HA Bremermann. A method for unconstrained global optimization. Math. Biosci. 1970; 9, 1-15.

RA Jarvis. Adaptive global search by the process of competitive evolution. IEEE Trans. Syst. Man Cybern. 1975; 75, 297-311.

WL Price. Global optimization by controlled random search. J. Comput. 1977; 20, 367-70.

S Kirkpatrick, CD Gelatt and MP Vecchi. Optimization by simulated annealing. J. Stor. 1983; 220, 671-80.

PJM van Laarhoven and EHL Aarts. Simulated Annealing: Theory and Applications. Springer, Boston, 1987, p. 1-186.

A Corana, M Marchesi, C Martini and S Ridella. Minimizing multimodal functions of continuous variables with the simulated annealing algorithm. ACM Trans. Math. Software 1987; 13, 262-80.

WL Goffe, GD Ferrier and J Rogers. Global optimization of statistical functions with simulated annealing. J. Econometrics 1994; 60 ,65-100.

D Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Reading, Massachusetts, 1989.

Z Michaelewizc. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1996.

R Storn and K Price. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 1997; 11, 341-59.

MM Ali and LP Fatti. A differential free point generation scheme in the differential evolution algorithm. J. Global Optim. 2006; 35, 551-72.

JH Holland. Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, 1975.

TP Patalia and GR Kulkarni. Behavioral analysis of genetic algorithm for function optimization. In: Proceedings of the IEEE International Conference on Computational Intelligence and Computing Research, Tamil Nadu, India, 2011, p. 1-5

E Eiben, R Hinterding, Z Michalewicz. Parameter control in evolutionary algorithms. IEEE Trans. Evol. Comput. 1999; 3, 124-41.

SN Sivanandam and SN Deepa. Introduction to Genetic Algorithm. Springer, 2008, p. 1-442.

P Bajpai and M Kumar. Genetic algorithm: An approach to solve global optimization problems. J. Comput. Sci. Eng. 2010; 1, 199-206.

D Hua-Fa, L Xiao-Lu and L Xue. An Improved Genetic Algorithm for Combinatorial Optimization. In: Proceedings of the IEEE International Conference on Computer Science and Automation Engineering, Shanghai, China, 2011, p. 58-61.

G Laporte. The vehicle routing problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 1992, 59, 345-58.

A Otman and A Jaafar. A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem. J. Comput. Appl. 2011; 31, 49-57.

G Carpaneto and P Toth. Some new branching and bounding criteria for the asymmetric traveling salesman problem. Manag. Sci. 1980; 26, 736-43.

TSPLIB, Institute of Information, University Heidelberg, Available at: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95, accessed February 2012.