A Reliable Approach for Terminating the GA Optimization Method

Iranian Journal of Numerical Analysis and Optimization

مقاله 4، دوره 7، شماره 1 - شماره پیاپی 11، تیر 2017، صفحه 83-106   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.v7i1.48652

نویسندگان

L. lotfi Katooli؛ A. shahsavand^*

Department of Chemical Engineering, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran

چکیده

Genetic algorithm (GA) has been extensively used in recent decades to solve many optimization problems in various fields of science and engineering. In most cases, the number of iterations is the only criterion which is used to stop the GA. In practice, this criterion will lead to prolong execution times to ensure proper solution. A novel approach is presented in this article as the approximate number of decisive iterations (ANDI ) which can be used to successfully terminate the GA optimization method with minimum execution time. Two simple correlations are presented which relate the new parameter (ANDI ) with approximate degrees of freedom (Adf ) of the merit function at hand. For complex merit functions, a linear smoother (such as Regularization network) can be used to estimate the required Adf. Four illustrative case studies are used to successfully validate the proposed approach by effectively finding the optimum point by using to the presented correlation. The linear correlation is more preferable because it is much simpler to use and the horizontal axis represents the approximate (not exact) degrees of freedom. It was also clearly shown that the Regularization Networks can successfully filter out the noise and mimic the true hyper-surface underlying a bunch of noisy data set.

کلیدواژه‌ها

Genetic algorithm؛ Termination criterion؛ Approximate degrees of freedom؛ Approximate number of decisive iteration؛ Linear smoother con- cept؛ Regularization Networks

مراجع

1. Aytug, H., Bhattacharrya, S. and Koehler, G.J. A Markov chain analysis of genetic algorithms with power of 2 cardinality alphabets, Eur. J. Oper. Res. 96 (1996), 195-201.

2. Aytug, H. and Koehler, G.J. Stopping Criteria for Finite Lenght Genetic Algorithms, Informs Jo. Comput. 8 (1996), 183-191.

3. Bagley, J.D. The behavior of adaptive systems which employ genetic and correlation algorithms. Ph.D. Thesis, University of Michigan, 1967.

4. Bergamaschi, P.R., Saramago, S.F.P. and Coelho, L.S. Comparative study of SQP and metaheuristics for robotic manipulator design, Appl. Numer. Math. 58 (2008), 13961412.

5. Bhandari, D., Murthy, C.A. and Pal, S.K. Variance as a Stopping Criterion for Genetic Algorithms with Elitist Model, Fundamenta Informaticae. 120 (2012), 145-164.

6. Cavicchio, D.J. Adaptive Search using Simulated Evolution, Ph.D. Thesis, University of Michigan, 1970.

7. Conway, B.A. A Survey of Methods Available for the Numerical Optimization of Continuous Dynamic Systems, J. Optim. Theory Appl. 152 (2012), 271306.

8. Elliott, L., Ingham, D.B., Kyne, A.G., Mera, N.S., Pourkashanian, M. and Wilson, C.W. Genetic algorithms for optimisation of chemical kinetics reaction mechanisms, Prog. Energ. Combust. 30 (2004), 297328.

9. Fleming, P.J. and Purshouse, R.C. Evolutionary algorithms in control systems engineering: a survey, Control Eng. Pract. 10 (2002), 12231241.

10. Gen, M. and Cheng, R. Genetic Algorithms amd engineering Design. New York, John Wiley and Sons, 2000.

11. Greenhalgh, D. and Marshall, S. Convergence Criteria for Genetic Algorithms, SIAM J. Comput. 30(1) (2000), 269282.

12. Golub, G.H., Van Loan, C.G., Matrix Computations, third ed., Johns Hopkins UniversityPress, Baltimore, 1996.

13. Hastie, T.J. and Tibshirani, R.J., Generalized Additive Models, London, Chapman and Hall, 1990.

14. Hedar, A.R., Ong, B.T. and Fukushima, M. Genetic Algorithms with Automatic Accelerated Termination, Technical Report, 2007.

15. Holland, J.H. Outline for a Logical Theory of Adaptive Systems, J. ACM. 9 (1962), 297-314.

16. Jackson. W.C. and Norgard. J.D. A Hybrid Genetic Algorithm with Boltzmann Convergence Properties, J. Optim. Theory. Appl. 136 (2008), 431-443

17. Kim, J. Genetic algorithm stopping criteria for optimization of construction resource scheduling problems, Construction Management and Economics. 31(1) (2013), 3-19.

18. Kopchenova, N.V. and Maron, I.A. Computatinal Mathematics: worked examples ana problems with elements of theory, Moscow, Mir Publishers, 1975.

19. Kumar. M. and Banka, H. Changing Mutation Operator of Genetic Algorithms for Optimizing Multiple Sequence Alignment, International Journal of Information and Computation Technology. 5(3) (2003), 465-470.

20. Lam, X.B, Kim, Y.S., Hoang, A.D. and Park. C.W. Coupled Aerostructural Design Optimization Using the Kriging Model and Integrated Multiobjective Optimization Algorithm, J. Optim. Theory Appl. 142 (2009), 533556.

21. Meyer, L. and Feng, X. A Fuzzy Stop Criterion for Genetic Algorithms Using Performance Estimation, In: Proceedings of the Third IEEE Conference on Fuzzy Systems, Orlano, FL, IEEE Service Center, pp. 1990-1995, (1994)

22. Michalewicz, Z. Genetic Algorithm+Data Structure =Evolution Programs, New York, Springer-Verlag, 1992.

23. Murthy, C.A., Bhandari, D. and Pal, S.K. Optimal Stopping Time for Genetic Algorithm, Fundamenta Informaticae. 35 (1998), 91-111.

24. Nix, A.E. and Vose, M.D. Modeling genetic algorithms with Markov chains, Ann. Math. Artif. Intel. 5 (1992) 79-88.

25. Ong, B.T. and Fukushima, M. Genetic algorithm with automatic termination and search space rotation, Memetic Comp. 3 (2011), 111-127.

26. Poggio, T. and Girosi, F. Regularization algorithms for learning that are equivalent to multilayer networks, Science. 247 (1990), 978-982.

27. Press, W.H., Teukolsky, S.A., Vetterling, W.T. and Flannery, B.P. Numerical Recipes: The Art of Scientific Computing, Cambridge, Cambridge University Press, 2007.

28. Qu, B.Y., Liang, J.J., Wang, Z.Y., Chen, Q., Suganthan, P.N.: Novel benchmark functions for continuous multimodal optimization with comparative results, Swarm and Evolutionary Computation 26 (2016), 23-34.

29. Rosenberg, R.S. Simulation of genetic populations with biochemical properties, Ph.D. Thesis, University of Michigan, 1967.

30. Rudolph, G. Convergence Analysis of Canonical Genetic Algorithms, IEEE T Neural Networ. 5(1) (1994), 96-101.

31. Shahsavand, A.: An Optimal Radial Basis Function (RBF) Neural Network for Hyper-Surface Reconstruction. Chemistry and Chemical Engineering 16 (2009), 41-53.

32. Sumathi, S., Hamsapriya, T. and Surekha, P. Evolutionary Intelligence An Introduction to Theory and Applications with Matlab, Berlin, SpringerVerlag, 2008.

33. Suzuki, J. A Markov chain analysis on a genetic algorithm, IEEE T. Syst. Man Cyb. 25(4) (1995) 655659.

34. Yuan, S., Skinner, B., Huang, S. and Liu, D. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms, Eur. J. Oper. Res. 228 (2013), 7282.