يك الگوريتم تكاملي تخمين توزيع جديد با استفاده از اتوماتاي يادگير
الموضوعات :
1 - دانشگاه صنعتی امیرکبیر
الکلمات المفتاحية: الگوريتم تکامليالگوريتم تخمين توزيعاتوماتای يادگير,
ملخص المقالة :
در سالهای اخير رويکرد جديدی به منظور حل مشکلات الگوريتمهای تکاملي به ويژه الگوريتمهای ژنتيکي مورد توجه محققين قرار گرفته است. اين رويکرد مبتني برايجاد مدلهای احتمالاتي از ژنوم‌ها و اجزای سازنده آنها مي‌باشد. تاکنون الگوريتمهای متنوعي بر اين اساس ارائه شده‌اند که اگر چه برخي از سادگي الگوريتمهای ژنتيکي برخوردار نيستند، اما در حل مسائل با موفقيت بيشتری روبرو بوده‌اند. در اين مقاله رهيافت ديگری از اين الگوريتمها را بر اساس اتوماتای يادگير معرفي و مورد بررسي قرار مي‌دهيم. در اين رهيافت مدل احتمالاتي اجزای سازنده مسئله به وسيله اتوماتای يادگير و بر اساس ژنوم‌های نسل توليد شده تخمين زده مي‌شود. الگوريتم پيشنهادی بسيار ساده و برای مسائل مورد بررسي در اين مقاله دارای کارايي خوبي مي‌باشد.
[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.
