یک معیار مبتنی بر واریانس برای ارزیابی یادگیری آتاماتای یادگیر در حل مسایل بهینه‌سازی گراف تصادفی
محورهای موضوعی : مهندسی برق و کامپیوترمحمدرضا ملاخلیلی میبدی 1 , محمدرضا میبدی 2 *
1 - دانشگاه آزاد اسلامی، واحد میبد
2 - دانشگاه صنعتی امیرکبیر
کلید واژه: شبکه آتاماتاهای یادگیر واریانس همگرایی درخت پوشای کمینه تصادفی کوتاه‌ترین مسیر تصادفی,
چکیده مقاله :
در این مقاله به بررسی یک معیار جدید مقایسه‌ای برای تولید پاسخ محیط در حل مسایل بهینه‌سازی روی گراف‌های تصادفی به عنوان مدلی از شبکه‌های کامپیوتری توسط شبکه‌ای از آتاماتاهای یادگیر می‌پردازیم. این روش جدید به دلیل لحاظ‌کردن تقریبی از واریانس پاسخ‌های تولیدشده توسط شبکه آتاماتاهای یادگیر، قادر به انطباق بیشتری با محیط بوده و در نتیجه پاسخ‌های مناسب‌تری به اقدام‌های انجام‌شده توسط آتاماتاها در شبکه‌ای از آتاماتاهای یادگیر می‌دهد. روش جدید از طریق واردکردن یک مقدار نویز محاسبه‌شده، از ایستایی فرایند یادگیری و گیرافتادن آن در نقاط کمینه محلی جلوگیری کرده و باعث تسریع در فرایند یادگیری می‌شود. به کمک شبیه‌سازی‌ها نشان می‌دهیم این روش جدید در مقایسه با روش‌های فعلی که تا کنون مورد استفاده بوده است، هم به لحاظ سرعت همگرایی به جواب بهینه و هم به لحاظ قابلیت گریز از اثر واریانس وزن یال‌های گراف تصادفی- که باعث میل جواب نهایی به سمت کوچک‌ترین مقدار و نه مقدار میانگین می‌شود- عملکرد بهتری دارد.
In this paper, a new criterion is introduced for solving optimization problems on stochastic graphs- as a model of computer networks-by stochastic learning Automata. This proposed method, because of considering estimated variance of response of environment, can better adaptation to changes of environment. As a result, the proposed method can produce better response to learning Automata actions. The proposed method, by entering a noise, can avoid learning Automata being stuck at a local optimum point. Our simulation shows that this proposed method can be improve the convergence rate of Automata-based algorithm.
[1] K. S. Narendra and M. A. L. Thathachar, "Learning automata: a survey," IEEE Trans. Syst. Man, Cyberentics, vol. 14, no. 4, pp. 323-334, Jul. 1974.
[2] S. Lakshmivarahan, Learning Algorithms Theory and Applications, vol. 30, Springer-Verlag, New York, 1981.
[3] G. Santharam and P. S. Sastry, "A reinforcement learning neural network for adaptive control of Markov chains," IEEE Trans.Syst. Man Cybern. Part A, Syst. Humans, vol. 27, no. 5, pp. 588-600, Sept. 1997.
[4] B. J. Oommen and D. C. Y. Ma, "Deterministic learning automata solutions to the equipartitioning problem," IEEE Trans. Comput., vol. 37, no. 1, pp. 2-13, Jan. 1988.
[5] B. J. Oommen and E. V De St Croix, "String taxonomy using learning automata," IEEE Trans. Syst. Man, Cybern. Part B, Cybern. a Publ. IEEE Syst. Man, Cybern. Soc., vol. 27, no. 2, pp. 354-65, Jan. 1997.
[6] B. J. Oommen and E. V de St Croix, "Graph partitioning using learning automata," IEEE Trans. Comput., vol. 45, no. 2, pp. 195-208, Feb. 1996.
[7] A. Tsoularis, C. Kambhampati, and K. Warwick, "Path planning of robots in noisy workspaces using learning automata," in Proc. of the 1993 IEEE Int. Symp. on Intelligent Control, pp. 560-564, Aug. 1993.
[8] T. J. Gordon, C. Marsh, and Q. H. Wu, "Stochastic optimal control of active vehicle suspensions using learning automata," Proc. Inst. Mech. Eng. Part I J. Syst. Control Eng., vol. 207, no. 3, pp. 143-152, Aug. 1993.
[9] C. Marsh, T. J. Gordon, and Q. H. Wu, "Application of learning automata to controller design in slow-active automobile suspensions," Veh. Syst. Dyn., vol. 24, no. 8, pp. 597-616, Sept. 1995.
[10] E. Ikonen and K. Najim, "Use of learning automata in distributed fuzzy logic processor training," IEE Proc.Control Theory Appl., vol. 144, no. 3, pp. 255-262, May 1997.
[11] T. Aoki, T. Oka, T. Suzuki, and S. Okuma, "Acquisition of optimal action selection to avoid moving obstacles in autonomous mobile robot," in Proc., IEEE Int. Conf. on Robotics and Automation, vol. 3, pp. 2055-2060, Apr. 1996.
[12] M. A. Thathachar and B. Harita, "Learning automata with changing number of actions," IEEE Trans. Syst. Man, Cybern.-Part A Syst. Humans, vol. 17, no. 6, pp. 1095-1100, Nov. 1987.
[13] H. Beigy and M. Meybodi, Intelligent Channel Assignment in Cellular Networks: A Learning Automata Approach, Amirkabir University of Technology, Technical Report, 2004.
[14] H. Beigy and M. R. Meybodi, "Utilizing distributed learning automata to solve stochastic shortest path problems," Int. J. Uncertainty, Fuzziness Knowledge-Based Syst., vol. 14, no. 5, pp. 591-615, Oct. 2006.
[15] م. ر. ملاخلیلی میبدی و م. ر. میبدی، "یک الگوریتم جدید مبتنی بر آتاماتای یادگیر توزیع‌شده برای حل مسأله کوتاه‌ترین مسیر تصادفی،" مجموعه مقالات ششمین کنفرانس سیستم‌های هوشمند، کرمان، 10 ص.، 5-4 آذر 1384.
[16] J. Akbari Torkestani and M. R. Meybodi, "Learning automata-based algorithms for solving stochastic minimum spanning tree problem," Appl. Soft Comput., vol. 11, no. 6, pp. 4064-4077, Sep. 2011.
[17] A. Rezvanian and M. R. Meybodi, "A new learning automata-based sampling algorithm for social networks," Int. J. Commun. Syst., vol. 30, no. 5, 21 pp., 25 Mar. 2015.
[18] م. ر. ملاخلیلی میبدی و م. ر. میبدی، "روشی مبتنی بر آتاماتای یادگیر توزیع‌شده برای مدل‌سازی کاربران در محیط‌های فراپیوندی،" مجموعه مقالات کنگره ملی مهندسی برق، کامپیوتر و فناوری اطلاعات، 5 ص.، 19-17 آبان 1391.
[19] م. ر. ملاخلیلی‌میبدی و م. ر. میبدی، "استفاده از آتاماتای یادگیر توزیع‌شده در پیش‌بینی حرکت کاربران در وب،" مجموعه مقالات سیزدهمین کنفرانس سالانه انجمن کامپیوتر ایران، 6 ص.، تهران، 21-19 اسفند 1386.
[20] ع. براداران هاشمی و م. ر. میبدی، "داده‌کاوی استفاده از وب با استفاده از آتاماتای یادگیر توزیع‌شده،" مجموعه مقالات دوازدهمین کنفرانس سالانه انجمن کامپیوتر ایران، 7 ص.، تهران، 3-1 اسفند 1385.
[21] ب. اناری، م. ر. میبدی و ز. اناری، "ارائه روشی جدید برای رتبه‌بندی صفحات وب با استفاده از آتاماتای یادگیر توزیع‌شده،" مجموعه مقالات سیزدهمین کنفرانس سالانه انجمن کامپیوتر ایران، 7 ص.، تهران، 21-19 اسفند 1386.
[22] M. R. Mollakhalili Meybodi and M. R. Meybodi, "Extended distributed learning automata: an automata-based framework for solving stochastic graph optimization problems," Appl. Intell., vol. 41, no. 2, pp. 923-940, Oct. 2014.
[23] م. ر. ملاخلیلی میبدی و م. ر. میبدی، "یک الگوریتم جدید مبتنی بر آتاماتای یادگیر توزیع‌شده توسعه‌یافته برای یادگیری پارامتری شبکه بیزی،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، سال 12، شماره ۲- ب، صص. 126-119، زمستان 1393.
[24] م. ر. ملاخلیلی میبدی و م. ر. میبدی، "یادگیری ساختاری شبکه‌های بیزی: یک رهیافت مبتنی بر آتاماتای یادگیر،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، سال 14، شماره ۱- ب، صص. 40-27، بهار 1395.
[25] J. B. Kruskal, "On the shortest spanning sub tree of a graph and the traveling salesman problem," American Mathematical Society, vol. 7, no. 1, pp. 48-50, Feb. 1956.
[26] M. Elkin, "An unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem," SIAM Journal on Computing, vol. 36, no.2, pp.433-456, 2006.
[27] J. Garay, S. Kutten, and D. Peleg, "A sublinear time distributed algorithm for minimum-wight-spanning tree," SIAM J. Comput., vol. 27, no. 1, pp. 302-326, 1998.
[28] M. Khan and G. Pandurangan, "A fast distributed approximation algorithm for minimum spanning trees," in Proc. of the 20th Int. Symp. on Distributed Computing, DISC'06, pp. 355-369, 2006.
[29] H. Beigy and M. R. Meybodi, "Solving stochastic shortest path problem using distributed learning automata," in Proc. 6th Annual CSI Computer Conf., CSICC'01, pp. 70-86, 2001.
[30] K. Liu, Stochastic Online Learning for Network Optimization under Random Unknown Weights, 18 pp.
[31] م. ر. ملاخلیلی میبدی و م. ر. میبدی، "یک روش جدید مبتنی بر معیارهای آماری توزیع برای تنظیم خودکار نرخ یادگیری آتاماتای یادگیر در محیط‌های پویا،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، سال ۱۱، شماره ۱- ب، صص. 51-43، تابستان 1392.
[32] م. قربعلی‌پوردرو و م. ر. میبدی، "یافتن درخت پوشای مینیمم در گراف‌های تصادفی با استفاده از آتاماتاهای یادگیر،" مجموعه مقالات چهاردهمين کنفرانس سالانه انجمن کامپیوتر ایران، 7 ص.، تهران، 21-20 اسفند 1387.
[33] K. R. Hutson and D. R. Shier, "Bounding distributions for the weight of a minimum spanning tree in stochastic networks," Oper. Res., vol. 53, no. 5, pp. 879-886, Oct. 2005.