یک چارچوب مبتنی بر آتاماتای یادگیر توزیع شده توسعه یافته برای حل مسأله یافتن زیرگراف بهینه تصادفی
محورهای موضوعی : مهندسی برق و کامپیوترمحمدرضا ملاخلیلی میبدی 1 * , محمدرضا میبدی 2
1 - دانشگاه آزاد اسلامی، واحد میبد
2 - دانشگاه صنعتی امیرکبیر
کلید واژه: آتاماتای یادگیر آتاماتای یادگیر توزیع‌شده توسعه‌یافته شبکه آتاماتاهای یادگیر زیرگراف گراف تصادفی نمونه‌گیری,
چکیده مقاله :
در این مقاله، یک ساختار جدید شبکه‌ای از آتاماتاهای یادگیر موسوم به آتاماتای یادگیر توزیع‌شده توسعه‌یافته معرفی شده و سپس الگوریتمی مبتنی بر این ساختار شبکه‌ای برای حل مسأله زیرگراف بهینه در گراف‌های تصادفی با یال‌های وزن‌دار از طریق نمونه‌گیری ارائه می‌شود. نشان داده شده که ساختار شبکه‌ای جدید پیشنهادی قادر به حل مسایل بهینه‌سازی روی گراف‌های تصادفی از طریق نمونه‌گیری با تعداد نمونه کمتر نسبت به روش نمونه‌گیری استاندارد است. علاوه بر این، اثباتی برای همگرایی آن به جواب بهینه ارائه شده و نشان داده می‌شود که ساختار شبکه‌ای پیشنهادی همواره با احتمال 1 به جواب بهینه همگرا می‌گردد.
In this paper a new structure of learning automata which is called as extended distributed learning automata (eDLA) is introduced. A new eDLA-based iterative sampling method for finding optimal sub-graph in stochastic graphs is proposed. Some mathematical analysis of the proposed algorithm is presented and the convergence property of the algorithm is studied. Our study shows that the proposed algorithm can be converge to the optimal sub-graph.
[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, 1974.
[2] M. L. Thathachar and P. S. Sastry, "Varieties of learning automata: an overview," IEEE Trans. Syst. Man. Cybern. B. Cybern., vol. 32, no. 6, pp. 711-722, Jan. 2002.
[3] H. Beigy and M. Meybodi, Intelligent Channel Assignment in Cellular Networks: A Learning Automata Approach, Amirkabir University of Technology, 2004.
[4] 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.
[5] M. R. Meybodi and H. Beigy, "A sampling method based on distributed learning automata," in Proc. the 10th Iranian Conf. on Electrical Engineering, vol. 1, pp. 618-626, May 2002.
[6] M. R. MollakhaliliMeybodi and M. R. Meybodi, "A new distributed learning automata based algorithm for solving stochastic shortest path," presented at 6th Conf. on Intelligent Systems, 2004.
[7] M. R. Meybodi and H. Beigy, "Solving stochastic shoretst path problem using Monte Carlo sampling method: a distributed learning automata approach," Neural Networks and Soft Computing, Physica-Verlag HD, pp. 626-632, 2003.
[8] A. Motevalian and M. R. Meybodi, "Solving maximal independent set problem using distributed learning automata," in Proc. 14th Iranian Electrical Engineering Conf., ICEE2006, Tehran, Iran, 16-18 May, 2006.
[9] A. Alipour and M. R. Meybodi, "Solving traveling salesman problem using distributed learning automata," in Proc. 10th Annual CSI Computer Conf., pp. 759-761, Tehran, Iran, Feb. 2005.
[10] S. Saati and M. Meybodi, "A self organizing model for document structure using distributed learning automata," in Proc. 2nd Int. Conf. on Information and Knowledge Technology, IKT2005, Tehran, Iran, 24-26 May, 2005.
[11] Z. Anari, M. R. Meybodi, and B. Anari, "Web page ranking based on fuzzy and learning automata," in Proc. Int. Conf. Manag. Emergent Digit. Ecosyst., MEDES'09, pp. 162-166, Lion, France, 27-31 Oct. 2009.
[12] M. R. Mollakhalili Meybodi and M. R. Meybodi, "Link prediction in adaptive web sites using distributed learning automata," in Proc. 13th Annual CSI Computer Conf. of Iran, Kish Island, Iran, 9-11, Mar. 2008.
[13] M. R. MollakhaliliMeybodi and M. R. Meybodi, "A distributed learning automata based approach for user modeling in adaptive hypermedia," in Proc. Congress on Electrical, Computer, and Information Technology, 2012.
[14] A. BaradaranHashemi and M. R. Meybodi, "Web usage mining using distributed learning automata," in Proc. 12th Annual CSI Computer Conf. of Iran, pp. 553-560, 2007.
[15] S. Misra and B. J. Oommen, "Dynamic algorithms for the shortest path routing problem: learning automata - based solutions," IEEE Trans. Syst. Man. Cybern. B. Cybern., vol. 35, no. 6, pp. 1179-1192, Dec. 2005.
[16] K. Liu, Stochastic Online Learning for Network Optimization under Random Unknown Weights, 18 pp. 1-18.
[17] K. S. Narendra and M. A. L. Thathachar, Learning Automata: An Introduction, Prentice Hall, p. 476, 1989.
[18] S. Lakshmivarahan and M. A. L. Thathachar, "Absolutely expedient learning algorithms for stochastic automata," IEEE Trans. Syst. Man Cybern., vol. 6, pp. 281-286, 1973.
[19] M. A. L.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, Dec. 1987.
[20] J. Akbari Torkestani and M. R. Meybodi, "A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs," J. Supercomput., vol. 59, no. 2, pp. 1035-1054, Oct. 2012.
[21] F. Norman, "On the linear model with two absorbing," J. Math. Psychol., vol. 5, pp. 225-241, Jun. 1968.
[22] A. Papoulis, Probability, Random Variables, and Stochastic Processes, 3rd ed. New York, USA: McGrawHill, 1991.
[23] S. M. Ross, Introduction to Probability and Statistics for Engineers and Scientists, 3rd. Ed., Elsevier Academic Press, 2004.
[24] K. R. Hutson and D. R. Shier, Online Supplement to ‘Bounding Distributions for the Weight of a Minimum Spanning Tree in Stochastic Networks,’ 12 pp.
[25] 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.