يک الگوريتم جديد مبتني بر آتاماتاي یادگير توزيع‌شده براي حل مسئله بهینه‌سازی خطی تصادفی روی گروه جایگشت‌ها
محورهای موضوعی : مهندسی برق و کامپیوتر
محمدرضا ملاخليلي ميبدي
1
(دانشگاه آزاد اسلامي واحد ميبد،گروه کامپیوتر)
معصومه زجاجی
2
(دانشگاه آزاد اسلامی واحد میبد،گروه کامپیوتر)
کلید واژه: آتاماتاي يادگير, آتاماتاي يادگير توزيع‌شده, گراف تصادفي, درخت پوشاي کمينه تصادفي,
چکیده مقاله :
در این مقاله ابتدا نوعی از بهینه‌سازی جایگشت معرفی شده است. در این نوع بهینه‌سازی فرض گردیده که تابع هزینه، دارای یک تابع توزیع احتمال ناشناخته است. این فرض باعث می‌شود که پیچیدگی حل مسئله یافتن جایگشت بهینه که به دلیل بزرگی ذاتی فضای جواب‌ها پیچیده است، تشدید شود. یک الگوریتم مبتنی بر آتاماتای یادگیر توزیع‌شده برای حل مسئله از طریق انجام توأمان جستجو در فضای جواب‌های جایگشت و نمونه‌گیری از مقادیر تصادفی ارائه می‌دهیم. ضمن بررسی ریاضی رفتار الگوریتم جدید پیشنهادی، نشان می‌دهیم که با انتخاب مقادیر مناسب پارامترهای الگوریتم یادگیر، این روش جدید می‌تواند جواب بهینه را با احتمالی به اندازه دلخواه نزدیک به ۱۰۰% و از طریق هدفمندکردن جستجو به کمک آتاماتای یادگیر توزیع‌شده پیدا کند. نتیجه اتخاذ این سیاست، کاهش تعداد نمونه‌گیری‌ها در روش جدید در مقایسه با روش‌های مبتنی بر نمونه‌گیری استاندارد است. در ادامه، مسئله یافتن درخت پوشای کمینه در گراف تصادفی به عنوان یک مسئله بهینه‌سازی جایگشت تصادفی بررسی گردیده و راه حل ارائه‌شده مبتنی بر آتاماتای یادگیر برای حل آن به کار گرفته شده است.
In the present research, a type of permutation optimization was introduced. It is assumed that the cost function has an unknown probability distribution function. Since the solution space is inherently large, solving the problem of finding the optimal permutation is complex and this assumption increases the complexity. In the present study, an algorithm based on distributed learning automata was presented to solve the problem by searching in the permutation answer space and sampling random values. In the present research, in addition to the mathematical analysis of the behavior of the proposed new algorithm, it was shown that by choosing the appropriate values of the parameters of the learning algorithm, this new method can find the optimal solution with a probability close to 100% and by targeting the search using the distributed learning algorithms. The result of adopting this policy is to decrease the number of samplings in the new method compared to methods based on standard sampling. In the following, the problem of finding the minimum spanning tree in the stochastic graph was evaluated as a random permutation optimization problem and the proposed solution based on learning automata was used to solve it.
[1] D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
[2] V. V Vazirani, Approximation Algorithms, Berlin: springer, 2001.
[3] E. G. Talbi, Metaheuristics: from Design to Implementation, vol. 74, John Wiley & Sons, 2009.
[4] C. C. Sims, "Graphs and finite permutation groups," Math. Zeitschrift, vol. 95, no. 1, pp. 76-86, Feb. 1967.
[5] G. Cooperman and E. Robinson, "Memory-based and disk-based algorithms for very high degree permutation groups," in Proc. of the Int. Symp. on Symbolic and Algebraic Computation, pp. 66-73, Philadelphia, PA, USA, 3-6 Aug. 2003.
[6] J. Grabowski and J. Pempera, "The permutation flow shop problem with blocking. A tabu search approach," Omega, vol. 35, no. 3, pp. 302-311, Jun. 2007.
[7] J. Kaabi and Y. Harrath, "Permutation rules and genetic algorithm to solve the traveling salesman problem," Arab J. Basic Appl. Sci., vol. 26, no. 1, pp. 283-291, Jan. 2019.
[8] H. Ishii, S. Shiode, T. Nishida, and Y. Namasuya, "Stochastic spanning tree problem," Discret. Appl. Math., vol. 3, no. 1, pp. 263-273, Nov. 1981.
[9] S. A. Dehkordi, et al., "A survey on data aggregation techniques in IoT sensor networks," Wirel. Networks, vol. 26, no. 2, pp. 1243-1263, Feb. 2020.
[10] C. Buchheim and M. Jünger, "Linear optimization over permutation groups," Discret. Optim., vol. 2, no. 4, pp. 308-319, Dec. 2005.
[11] M. A. L. Thathachar and P. S. Sastry, Networks of Learning Automata: Techniques for Online Stochastic Optimization, Springer Science & Business Media, 2003.
[12] M. A. L. Thathachar and P. S. Sastry, "Varieties of learning automata: an overview," IEEE Trans. Syst. Man, Cybern. Part B, vol. 32, no. 6, pp. 711-722, Dec. 2002.
[13] M. L. Tsetlin, Automaton Ttheory and Modeling of Biological Systems, vol. 102, pp.160-196, Academic Press New York, 1973.
[14] Q. Sang, Z. Lin, and S. T. Acton, "Learning automata for image segmentation," Pattern Recognit. Lett., vol. 74, pp. 46-52, Apr. 2016. [15] J. A. Torkestani and M. R. Meybodi, "Mobility-based multicast routing algorithm for wireless mobile ad-hoc networks: a learning automata approach," Comput. Commun., vol. 33, no. 6, pp. 721-735, Apr. 2010.
[16] M. Shojafar, S. Abolfazli, H. Mostafaei, and M. Singhal, "Improving channel assignment in multi-radio wireless mesh networks with learning automata," Wirel. Pers. Commun., vol. 82, no. 1, pp. 61-80, May 2015.
[17] M. Fahimi and A. Ghasemi, "A distributed learning automata scheme for spectrum management in self-organized cognitive radio network," IEEE Trans. Mob. Comput., vol. 16, no. 6, pp. 1490-1501, Aug. 2016.
[18] H. Mostafaei, "Stochastic barrier coverage in wireless sensor networks based on distributed learning automata," Comput. Commun., vol. 55, pp. 51-61, Jan. 2015.
[19] H. Mostafaei and M. R. Meybodi, "Maximizing lifetime of target coverage in wireless sensor networks using learning automata," Wirel. Pers. Commun., vol. 71, no. 2, pp. 1461-1477, Jul. 2013.
[20] H. Mostafaei, A. Montieri, V. Persico, and A. Pescapé, "A sleep scheduling approach based on learning automata for WSN partialcoverage," J. Netw. Comput. Appl., vol. 80, pp. 67-78, Feb. 2017.
[21] S. Misra, P. V. Krishna, K. Kalaiselvan, V. Saritha, and M. S. Obaidat, "Learning automata-based QoS framework for cloud IaaS," IEEE Trans. Netw. Serv. Manag., vol. 11, no. 1, pp. 15-24, Feb. 2014.
[22] P. V. Krishna, S. Misra, D. Nagaraju, V. Saritha, and M. S. Obaidat, "Learning automata based decision making algorithm for task offloading in mobile cloud," in Proc. IEEE Int. Conf. Comput. Inf. Telecommun. Syst., 6 pp., Kunming, China, 6-8 Jul. 2016.
[23] A. A. Rahmanian, M. Ghobaei-Arani, and S. Tofighy, "A learning automata-based ensemble resource usage prediction algorithm for cloud computing environment," Futur. Gener. Comput. Syst., vol. 79, pp. 54-71, Feb. 2018.
[24] A. Rezvanian and M. R. Meybodi, "A new learning automata-based sampling algorithm for social networks," Int. J. Commun. Syst., vol. 30, no. 5, pp. 1-21, Mar. 2017.
[25] J. A. Torkestani and M. R. Meybodi, "Solving the minimum spanning tree problem in stochastic graphs using learning automata," in Proc. Int. Conf. on Information Management and Engineering, pp. 643-647, Kuala Lumpur, Malaysia, 3-5 Apr. 2009.
[26] M. R. Meybodi and H. Beigy, "Solving stochastic shortest path problem using Monte Carlo sampling method: a distributed learning automata approach," Neural Networks and Soft Computing, Springer, pp. 626-631, 2003.
[27] A. Rezvanian and M. R. Meybodi, "Finding minimum vertex covering in stochastic graphs: a learning automata approach," Cybern. Syst., vol. 46, no. 8, pp. 698-727, Nov. 2015.
[28] M. R. Mollakhalili Meybodi and M. R. Meybodi, "Extended distributed learning automata," Appl. Intell., vol. 41, no. 3, pp. 923-940, Oct. 2014.
[29] J. A. Torkestani and M. R. Meybodi, "A new vertex coloring algorithm based on variable action-set learning automata," Comput. Informatics, vol. 29, no. 3, pp. 447-466, 2010.
[30] M. R. Mirsaleh and M. R. Meybodi, "A new memetic algorithm based on cellular learning automata for solving the vertex coloring problem," Memetic Comput., vol. 8, no. 3, pp. 211-222, Sept. 2016.
[31] J. A. 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, Feb. 2012.
[32] M. Alipour, "A learning automata based algorithm for solving traveling salesman problem improved by frequency-based pruning," Environment, vol. 46, no. 17, pp. 7-13, Jan. 2012.
[33] M. Hasanzadeh-Mofrad and A. Rezvanian, "Learning automata clustering," J. Comput. Sci., vol. 24, pp. 379-388, Jan. 2018.
[34] A. Rezvanian, A. M. Saghiri, S. M. Vahidipour, M. Esnaashari, and M. R. Meybodi, Recent Advances in Learning Automata, vol. 754, Springer Nature, 2018.
[35] M. A. L. Harita and B. Thathachar, "Learning automata with changing number of actions," IEEE Trans. Syst. Man, Cybern.-Part A Syst. Humans, vol. 17, no. 6, pp. 1095-1100, Nov./Dec. 1987.
[36] H. Beigy and M. Meybodi, Intelligent Channel Assignment in Cellular Networks: A Learning Automata Approach, Amirkabir University of Technology, 2004.
[37] M. Thathachar and K. Ramakrishnan, "A hierarchical system of learning automata," IEEE Trans. Syst. Man. Cybern., vol. 11, no. 3, pp. 236-241, Mar. 1981.
[38] 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.
[39] F. Norman, "On the linear model with two absorbing," J. Math. Psychol., vol. 5, no. 2, pp. 225-241, Jun. 1968.
[40] S. Lakshmivarahan and M. Thathachar, "Bounds on the convergence probabilities of learning automata," IEEE Trans. Syst. Man, Cybern.-Part A Syst. Humans, vol. 6, no. 11, pp. 756-763, Jun. 1976.
[41] J. Nešetřil, E. Milková, and H. Nešetřilová, "Otakar Borůvka on minimum spanning tree problem translation of both the 1926 papers, comments, history," Discrete Math., vol. 233, no. 1-3, pp. 3-36, Apr. 2001.
[42] R. C. Prim, "Shortest connection networks and some generalizations," Bell Syst. Tech. J., vol. 36, no. 6, pp. 1389-1401, Nov. 1957.
[43] J. B. Kruskal, "On the shortest spanning sub tree of a graph and the traveling salesman problem," American Mathematical Society, vol. 17, no. 1, pp. 48-50, Feb. 1956.
[44] R. L. Graham and P. Hell, "On the history of the minimum spanning tree problem," IEEE Ann. Hist. Comput., vol. 7, no. 1, pp. 43-57, Jan. 1985.
[45] M. Mares, "Two linear time algorithms for MST on minor closed graph classes," Arch. Math., vol. 40, pp. 315-320, 2004.
[46] M. Khan, V. S. A. Kumar, G. Pandurangan, and G. Pei, "A fast distributed approximation algorithm for minimum spanning trees in the SINR model," in Proc. of the 26th Int. Conf. on Distributed Computing, DISC'12, pp. 409-410, Salvador, Brazil, 16-18 Oct. 2012.
[47] D. R. Karger, P. N. Klein, and R. E. Tarjan, "A randomized linear-time algorithm to find minimum spanning trees," J. ACM, vol. 42, no. 2, pp. 321-328, Mar. 1995.
[48] K. W. Chong, Y. Han, and T. W. Lam, "Concurrent threads and optimal parallel minimum spanning trees algorithm," J. ACM, vol. 48, no. 2, pp. 297-323, Mar. 2001.
[49] J. Garay, S. Kutten, and D. Peleg, "A sublinear time distributed algorithm for minimum-weight-spanning tree," SIAM J. Comput., vol. 27, no. 1, pp. 302-326, Feb. 1998.
[50] M. Khan and G. Pandurangan, "A fast distributed approximation algorithm for minimum spanning trees," Distributed Computing, vol. 20, no.6, pp. 391-402, Apr. 2008.
[51] H. Ohlsson, O. Gustafsson, and L. Wanhammar, "Implementation of low complexity FIR filters using a minimum spanning tree," in Proc. of the 12th IEEE Mediterranean Electrotechnical Conf., pp. 261-264, Dubrovnik, Croatia, 12- 15 May 2004.
[52] Y. Xu, V. Olman, and D. Xu, "Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees," Bioinformatics, vol. 18, no. 4, pp. 536-545, Apr. 2002.
[53] N. Päivinen, "Clustering with a minimum spanning tree of scale-free-like structure," Pattern Recognit. Lett., vol. 26, no. 7, pp. 921-930, May 2005.
[54] T. Asano, B. Bhattacharya, M. Keil, and F. Yao, "Clustering algorithms based on minimum and maximum spanning trees," in Proc. of the 4th Annual Symp. on Computational Geometry, SCG'88, pp. 252-257, Urbana-Champaign, IL, USA, 6-8 Jun. 1988.
[55] B. Ma, A. Hero, J. Gorman, and O. Michel, "Image registration with minimum spanning tree algorithm," in Proc. Int. Conf. on Image, vol. 1, pp. 481-484, Vancouver, Canada, 10-13 Sept. 2000.
[56] N. Christofides, "Worst-case analysis of a new heuristic for the travelling salesman problem," Operations Research Forum, vol. 3, no. 1, 4 pp., Mar. 2022.
[57] P. H. A. Sneath, "The application of computers to taxonomy," J. Gen. Microbiol., vol. 17, no. 1, pp. 201-226, Aug. 1957.
[58] K. J. Supowit, D. A. Plaisted, and E. M. Reingold, "Heuristics for weighted perfect matching," in Proc. of the 12th Annual ACM Symp. on Theory of Computing, STOC'80, pp. 398-419, Los Angeles, CA, USA, 28- 30 Apr. 1980.
[59] H. Lshii and T. Nishida, "Stochastic bottleneck spanning tree problem," Networks, vol. 13, no. 3, pp. 443-449, Sept. 1983.
[60] I. B. Mohd, "Interval elimination method for stochastic spanning tree problem," Appl. Math. Comput., vol. 66, no. 2-3, pp. 325-341, Dec. 1994.
[61] م. قربعلی¬پور درو و م. ر. میبدی، "یافتن درخت پوشای مینیمم در گرافهای تصادفی با استفاده از اتوماتاهای یادگیر،" مجموعه مقالات چهاردهمین کنفرانس سالانه انجمن کامپیوتر ایران، 7 صص.، تهران، 21-20 اسفند 1387.
[62] J. Akbari Torkestani and M. R. Meybodi, "Learning automata-based algorithms for solving stochastic minimum spanning tree problem," Appl. Soft Comput. J., vol. 11, no. 6, pp. 4064-4077, Sept. 2011.
[63] K. Liu and Q. Qing Zhao, Stochastic Online Learning for Network Optimization under Random Unknown Weights, pp. 1-18, 2012.
[64] M. R. M. Meybodi and M. R. Meybodi, Extended Distributed Learning Automata: A New Method for Solving Stochastic Graph Optimization Problems, arXiv:1308.2772, p. 37, Aug. 2013.
[65] K. R. Hutson and D. R. Shier, Online Supplement to 'Minimum Spanning Trees in Networks with Varying Edge Weights', pp. 1-8, retived on 29 Oct. 2020 from http://www.math.clemson.edu/~shierd/Shier/appendix2.pdf.