Variance as a Stopping Criterion for Genetic Algorithms with Elitist Model

• Autorzy: Bhandari D. , Murthy C.A. , Pal S.K.
• Języki publikacji: EN

Abstrakty

EN

Genetic Algorithm (GA) has now become one of the leading mechanisms in providing solution to complex optimization problems. Although widely used, there are very few theoretical guidelines for determining when to stop the algorithm. This article establishes theoretically that the variance of the best fitness values obtained in the iterations can be considered as a measure to decide the termination criterion of a GA with elitist model (EGA). The criterion automatically takes into account the inherent characteristics of the objective function. Implementation issues of the proposed stopping criterion are explained. Its difference with some other stopping criteria is also critically analyzed.

Słowa kluczowe

EN

Genetic Algorithm with Elitist Model; stopping criterion; Markov chains; variance

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 120, nr 2
• Strony: 145--164
• Opis fizyczny: Bibliogr. 21 poz., tab., wykr.

Twórcy

autor

Bhandari D.

autor

Murthy C.A.

autor

Pal S.K.

• Center for Soft Computing Research Indian Statistical Institute Kolkata 700108, India,

Bibliografia

• [1] Aytug, H., Koehler, G. J.: New stopping criteria for Genetic Algorithms, European Journal of Operational Research, 126, 2000, 662-674.
• [2] Bhandari, D., Murthy, C. A., Pal, S. K.: Genetic Algorithms with Elitist Model and its Convergence, International Journal of Pattern recognition and Artificial Intelligence, 10(6), 1996, 731-747.
• [3] Davis, T. E., Principe, C. J.: A simulated annealing like convergence theory for the simple genetic algorithm, Proceedings of 4th int. conf. on genetic algorithms, Morgan Kaufmann, Los Altos, CA, 1991.
• [4] Dejong, K. A.: An analysis of the behaviour of a class of genetic adaptive systems, Ph.D. Thesis, Department of Computer and Communication Science, Univ. of Michigan, Ann Arbor, 1975.
• [5] Feller, W.: An Introduction to Probability Theory and its Applications (Vol. I), Wiley Eastern Pvt. Ltd., New Delhi, 1972.
• [6] Goldberg, D. E.: Genetic Algorithms: Search,Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989.
• [7] Greenhalgh, D., Marshall, S.: Convergence Criteria for Genetic Algorithms, SIAM Journal on Computing, 30(1), 2000, 269-282.
• [8] Jain, B. J., Pohlheim, H., Wegener, J.: On Termination Criteria of Evolutionary Algorithms, GECCO 2001 - Proceedings of the Genetic and Evolutionary Computation Conference., Morgan Kauffmann, San Francisco, CA, 2001.
• [9] Kallel, L., Naudts, B., Rogers, A., Eds.: Theoretical aspects of evolutionary computing, Springer, Heidelberg, Heidelberg, 2001.
• [10] Maity, S. P., Kundu, M. K.: Genetic algorithms for optimality of data hiding in digital images, Soft Computing, 13(4), 2009, 361-373.
• [11] Michalewicz, Z.: Genetic Algorithms + Data Structure = Evolution programs, Springer Verlag, 1992.
• [12] Munteanu, C., Rosa, A.: Gray-Scale Image Enhancement as an Automatic Process Driven by Evolution, IEEE Transactions on Systems, Man and Cybernetics-Part B: Cybernetics, 34(2), 2004, 1292-1298.
• [13] Murthy, C. A., Bhandari, D., Pal, S. K.: _-Optimal Stopping Time for Genetic Algorithms, Fundamenta Informaticae, 35(1-4), 1998, 91-111.
• [14] Nix, A. E., Vose, M. D.: Modeling genetic algorithms with markov chains, Annals of Mathematics and Artificial Intelligence, 5, 1992, 79-88.
• [15] Pal, S. K., Bhandari, D.: Selection of optimal set of weights in a layered network using Genetic algorithms, Information Sciences, 80(3-4), 1994, 213-234.
• [16] Pal, S. K., Bhandari, D., Kundu, M. K.: Genetic algorithms for optimal image enhancement, Pattern Recognition Letters, 15, 1994, 261-271.
• [17] Pal, S. K., Ghosh, A., Kundu, M. K., Eds.: Soft Computing for Image Processing, Physica Verlag, Heidelberg, 2000.
• [18] Rudolph, G.: Convergence analysis of canonical genetic algorithm, IEEE Transactions on Neural networks, 5(1), 1994, 96-101.
• [19] Safe, M., Carballido, J. A., Ponzoni, I., Brignole, N. B.: On stopping criteria for genetic algorithms, Proc. of Advances in artificial intelligenceSBIA 2004, 17th Brazilian symposium on artificial intelligence (A. L. C. Bazzan, S. Labidi, Eds.), Springer, Berlin, 2004.
• [20] Suzuki, J.: A Markov chain analysis on a genetic algorithm, IEEE Transactions on Systems, Man and Cybernetics, 25(4), 1995, 655-659.
• [21] Vose, M. D.: Modeling simple genetic algorithms, Foundations of genetic algorithms II (D. Whitley, Ed.), Morgan Kaufmann Publishers, 1993.