A New Variance-Based Method for Solving Stochastic Graph Optimization Problem Using Learning Automata
Subject Areas : electrical and computer engineeringM. R. Mollakhalili Meybodi 1 , M. R. Meybodi 2 *
1 -
2 -
Keywords: Learning Automata stochastic graph, optimization variance,
Abstract :
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.