A New Evolutionary Estimation of Distribution Algorithm Based on Learning Automata
Subject Areas : electrical and computer engineeringAbstract :
In order to overcome the poor behaviors of genetic algorithms in some problems other classes of evolutionary algorithms have been recently developed by researchers. Although these algorithms do not have the simplicity of classic genetic algorithms but they are superior to genetic algorithms. The Probabilistic Model Building Genetic Algorithms or Estimation of Distribution Algorithms (EDAs) is one of these classes which is recently developed. In this paper we introduce a new estimation of distribution algorithm based on Learning Automata. The proposed algorithm is a model based search optimization method that uses a set of learning automata as a probabilistic model of the population of solutions in the search space. The proposed algorithm is a simple algorithm which has produced good results for the optimization problems considered in this problem.
References:
[1] S. Baluja and R. Caruana, "Removing the genetics from the standard genetic algorithm", in Proc. of ICML’95, pp. 38-46, Morgan Kaufmann Publishers, Palo Alto, CA, 1995.
[2] H. Mühlenbein and G. Paaß, "From recombination of genes to the estimation of distributions I. binary parameters", Lecture Notes in Computer Science 1411: Parallel Problem Solving from Nature-PPSN IV, pp. 178-187, 1996.
[3] S. Baluja and S. Davies, "Using optimal dependency trees for combinatorial optimization: learning the structure of search space", Technical Report CMU-CS-97-107, Carnegie Mellon University,Pittsburgh, Pennsylvania, 1997.
[4] S. Baluja, "Population based incremental learning: a method for integrating genetic search based function optimization and competitive learning", Technical Report CMU-CS-94-163, Carnegie Mellon University, Pittsburgh, Pennsylvania, 1994.
[5] J. S. De Bonet, C. L. Isbell, and P. Viola, "MIMIC: finding optima by estimating probability densities", In Proc. of NIPS’97, pp. 424– 431, MIT Press, Cambridge, MA, 1997.
[6] G. R. Harik, F. G. Lobo, and D. E. Goldberg, "The compact genetic algorithm", IEEE Trans. on Evolutionary Computing, vol. 3, no. 4, pp. 287–297, Nov. 1999.
[7] H. Mühlenbein and T. Mahnig, "The factorized distribution algorithm for additively decomposed functions", in Proc. of the 1999 Congress on Evolutionary Computation, IEEE Press, pp. 752-759,1999.
[8] H. Mühlenbein, "The equation for response to selection and its use for prediction", Evolutionary Computation, vol. 5, no. 3, pp. 303- 346, Fall 1998.
[9] H. Mühlenbein and M. Pelikan, The Bivariate Marginal Distribution Algorithm, Advances in Soft Computing-Engineering Design and Manufacturing, pp. 521-535, 1999.
[10] M. Pelikan, D. E. Goldberg, and F. Lobo, "A survey of optimization by building and using probabilistic model", Illinois Genetic Algorithm Report, No. 99018, Illinois University, Illinois, USA, Sep. 1999.
[11] M. Pelikan, D. E. Goldberg, and E. Cant-Paz, "Linkage problem, distribution estimation and Bayesian networks", Evolutionary Computation, vol. 8, no. 3, pp. 311-340, Sep. 2000.
[12] H. Mühlenbein and T. Mahnig, Evolutionary Algorithms: From Recombination to Search Distributions, Theoretical Aspects of Evolutionary Computing, Springer Publication, 2001.
[13] G. Harik, "Linkage learning via probabilistic modeling in the ECGA", Illinois Genetic Algorithm Report, no. 99010, Illinois University, Illinois, USA, 1999.
[14] M. N. Howell, T. J. Gordon, and F. V. Brandao, "Genetic learning automata for function optimization", IEEE Trans. on Systems, Man, and Cybernetics-Part B: Cybernetics, vol. 32, no. 6, pp. 804-815,Dec. 2002.
[15] M. Munetomi, Y. Takai, and Y. Sato, "stGA: An application of genetic algorithm to stochastic learning automata", Syst., Computer. Jpn., vol 27, pp. 67-78, Sep. 1996.
[16] P. Larranaga, R. Etxeberria, J. A. Lozano, and J. M. Pena, "Optimization by learning and simulation of Bayesian and Gaussian networks", Technical Report EHU-KZAA-IK-4/99, Department of Computer Science and Artificial Intelligence, University of Basque Country, Dec. 1999.
[17] D. Heckerman, "A tutorial on learning with Bayesian networks", Technical Report, MSR-TR-95-06, Advanced Technology Division, Microsoft Cooperation, Redmond, WA, Nov. 1996.
[18] G. Syswerda, "Simulated crossover in genetic algorithms", in Proc. Second Workshop on Foundation of Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo California, pp. 239-255, 1993.
[19] N. Monmarch´e, E. Ramat, G. Dromel, M. Slimane, and G. Venturini, "On the similarities between AS, BSC and PBIL:toward the birth of a new Meta-heuristic", Technical Report 215,Laboratoire d’Informatique, Universit´e de Tours, 1999.
[20] G. Rosenberg, and A. Salomaa (Editors), Handbook of Formal Language, Springer-Verlag, Berlin, 1993.
[21] B. J. Oommen and M. Agache, "Continuous and discredited pursuit learning schemes: various algorithms and their comparison", IEEE Trans. on Systems, Man, and Cybernetics—Part B: Cybernetics, vol.31, no. 3, pp. 277-287, Jun. 2001.
[22] M. A. L. Thathachar and P. S. Sastry, "Estimator algorithms for learning automata", Proc. Platinum Jubilee Conferences on Systems and Signal Processing, Electrical Eng. Department, Indian Institute of Science, Bangalore, India, Dec. 1986.
[23] K. S. Narendra and M. A. L. Thathachar, Learning Automata: An Introduction, Printice-Hall Inc, 1989.
[24] R. Rastegar and M. R. Meybodi, "LAEDA: a new evolutionary algorithm using learning automata", Accepted in 10th Annual International Computer Society of Iran Computer Conference CSICC2004, Sharif university, Tehran, Iran, 2004.
[1] S. Baluja and R. Caruana, "Removing the genetics from the standard genetic algorithm", in Proc. of ICML’95, pp. 38-46, Morgan Kaufmann Publishers, Palo Alto, CA, 1995.
[2] H. Mühlenbein and G. Paaß, "From recombination of genes to the estimation of distributions I. binary parameters", Lecture Notes in Computer Science 1411: Parallel Problem Solving from Nature-PPSN IV, pp. 178-187, 1996.
[3] S. Baluja and S. Davies, "Using optimal dependency trees for combinatorial optimization: learning the structure of search space", Technical Report CMU-CS-97-107, Carnegie Mellon University,Pittsburgh, Pennsylvania, 1997.
[4] S. Baluja, "Population based incremental learning: a method for integrating genetic search based function optimization and competitive learning", Technical Report CMU-CS-94-163, Carnegie Mellon University, Pittsburgh, Pennsylvania, 1994.
[5] J. S. De Bonet, C. L. Isbell, and P. Viola, "MIMIC: finding optima by estimating probability densities", In Proc. of NIPS’97, pp. 424– 431, MIT Press, Cambridge, MA, 1997.
[6] G. R. Harik, F. G. Lobo, and D. E. Goldberg, "The compact genetic algorithm", IEEE Trans. on Evolutionary Computing, vol. 3, no. 4, pp. 287–297, Nov. 1999.
[7] H. Mühlenbein and T. Mahnig, "The factorized distribution algorithm for additively decomposed functions", in Proc. of the 1999 Congress on Evolutionary Computation, IEEE Press, pp. 752-759,1999.
[8] H. Mühlenbein, "The equation for response to selection and its use for prediction", Evolutionary Computation, vol. 5, no. 3, pp. 303- 346, Fall 1998.
[9] H. Mühlenbein and M. Pelikan, The Bivariate Marginal Distribution Algorithm, Advances in Soft Computing-Engineering Design and Manufacturing, pp. 521-535, 1999.
[10] M. Pelikan, D. E. Goldberg, and F. Lobo, "A survey of optimization by building and using probabilistic model", Illinois Genetic Algorithm Report, No. 99018, Illinois University, Illinois, USA, Sep. 1999.
[11] M. Pelikan, D. E. Goldberg, and E. Cant-Paz, "Linkage problem, distribution estimation and Bayesian networks", Evolutionary Computation, vol. 8, no. 3, pp. 311-340, Sep. 2000.
[12] H. Mühlenbein and T. Mahnig, Evolutionary Algorithms: From Recombination to Search Distributions, Theoretical Aspects of Evolutionary Computing, Springer Publication, 2001.
[13] G. Harik, "Linkage learning via probabilistic modeling in the ECGA", Illinois Genetic Algorithm Report, no. 99010, Illinois University, Illinois, USA, 1999.
[14] M. N. Howell, T. J. Gordon, and F. V. Brandao, "Genetic learning automata for function optimization", IEEE Trans. on Systems, Man, and Cybernetics-Part B: Cybernetics, vol. 32, no. 6, pp. 804-815,Dec. 2002.
[15] M. Munetomi, Y. Takai, and Y. Sato, "stGA: An application of genetic algorithm to stochastic learning automata", Syst., Computer. Jpn., vol 27, pp. 67-78, Sep. 1996.
[16] P. Larranaga, R. Etxeberria, J. A. Lozano, and J. M. Pena, "Optimization by learning and simulation of Bayesian and Gaussian networks", Technical Report EHU-KZAA-IK-4/99, Department of Computer Science and Artificial Intelligence, University of Basque Country, Dec. 1999.
[17] D. Heckerman, "A tutorial on learning with Bayesian networks", Technical Report, MSR-TR-95-06, Advanced Technology Division, Microsoft Cooperation, Redmond, WA, Nov. 1996.
[18] G. Syswerda, "Simulated crossover in genetic algorithms", in Proc. Second Workshop on Foundation of Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo California, pp. 239-255, 1993.
[19] N. Monmarch´e, E. Ramat, G. Dromel, M. Slimane, and G. Venturini, "On the similarities between AS, BSC and PBIL:toward the birth of a new Meta-heuristic", Technical Report 215,Laboratoire d’Informatique, Universit´e de Tours, 1999.
[20] G. Rosenberg, and A. Salomaa (Editors), Handbook of Formal Language, Springer-Verlag, Berlin, 1993.
[21] B. J. Oommen and M. Agache, "Continuous and discredited pursuit learning schemes: various algorithms and their comparison", IEEE Trans. on Systems, Man, and Cybernetics—Part B: Cybernetics, vol.31, no. 3, pp. 277-287, Jun. 2001.
[22] M. A. L. Thathachar and P. S. Sastry, "Estimator algorithms for learning automata", Proc. Platinum Jubilee Conferences on Systems and Signal Processing, Electrical Eng. Department, Indian Institute of Science, Bangalore, India, Dec. 1986.
[23] K. S. Narendra and M. A. L. Thathachar, Learning Automata: An Introduction, Printice-Hall Inc, 1989.
[24] R. Rastegar and M. R. Meybodi, "LAEDA: a new evolutionary algorithm using learning automata", Accepted in 10th Annual International Computer Society of Iran Computer Conference CSICC2004, Sharif university, Tehran, Iran, 2004.