A rapid learning automata-based approach for generalized minimum spanning tree problem. (English) Zbl 1466.90094
Summary: Generalized minimum spanning tree problem, which has several real-world applications like telecommunication network designing, is related to combinatorial optimization problems. This problem belongs to the NP-hard class and is a minimum tree on a clustered graph spanning one node from each cluster. Although exact and metaheuristic algorithms have been applied to solve the problems successfully, obtaining an optimal solution using these approaches and other optimization tools has been a challenge. In this paper, an attempt is made to achieve a sub-optimal solution using a network of learning automata (LA). This algorithm assigns an LA to every cluster so that the number of actions is the same as that of nodes in the corresponding cluster. At each iteration, LAs select one node from their clusters. Then, the weight of the constructed generalized spanning tree is considered as a criterion for rewarding or penalizing the selected actions. The experimental results on a set of 20 benchmarks of TSPLIB demonstrate that the proposed approach is significantly faster than the other mentioned algorithms. The results indicate that the new algorithm is competitive in terms of solution quality.
MSC:
| 90C27 | Combinatorial optimization |
Keywords:
generalized minimum spanning tree; induced subgraph; learning automata; combinatorial optimization problems; random searchSoftware:
TSPLIBReferences:
| [1] | Akbari Torkestani, J.; Meybodi, MR, An intelligent backbone formation algorithm for wireless ad hoc networks based on distributed learning automata, Comput Netw, 54, 5, 826-843 (2010) · Zbl 1213.68102 · doi:10.1016/j.comnet.2009.10.007 |
| [2] | Akbari Torkestani, J.; Meybodi, MR, Mobility-based multicast routing algorithm for wireless mobile Ad-hoc networks: a learning automata approach, Comput Commun, 33, 6, 721-735 (2010) · doi:10.1016/j.comcom.2009.11.019 |
| [3] | Akbari Torkestani, J.; Meybodi, MR, Learning automata-based algorithms for solving stochastic minimum spanning tree problem, Appl Soft Comput J, 11, 6, 4064-4077 (2011) · doi:10.1016/j.asoc.2011.02.017 |
| [4] | BoussaïD, I.; Lepagnot, J.; Siarry, P., A survey on optimization metaheuristics, Inf Sci, 237, 82-117 (2013) · Zbl 1321.90156 · doi:10.1016/j.ins.2013.02.041 |
| [5] | Contreras-Bolton, C.; Gatica, G.; Rey, C.; Parada, V., A multi-operator genetic algorithm for the generalized minimum spanning tree problem, Expert Syst Appl, 50, 1-8 (2016) · doi:10.1016/j.eswa.2015.12.014 |
| [6] | Daliri Khomami, MM; Rezvanian, A.; Bagherpour, N.; Meybodi, MR, Minimum positive influence dominating set and its application in influence maximization: a learning automata approach, Appl Intell, 48, 3, 570-593 (2018) · doi:10.1007/s10489-017-0987-z |
| [7] | Di, C.; Li, S.; Li, F.; Qi, K., A novel framework for learning automata: a statistical hypothesis testing approach, IEEE Access, 7, 27911-27922 (2019) · doi:10.1109/ACCESS.2019.2901941 |
| [8] | Dror, M.; Haouari, M., Generalized steiner problems and other variants, J Comb Optim, 4, 4, 415-436 (2000) · Zbl 0980.90074 · doi:10.1023/A:1009881326671 |
| [9] | Dua A, Sharma P, Ganju S, Jindal A, Aujla GS, Kumar N, Rodrigues JJ (2018) Rovan: a rough set-based scheme for cluster head selection in vehicular ad-hoc networks. In: 2018 IEEE global communications conference (GLOBECOM), IEEE, pp 206-212 |
| [10] | Fahimi, M.; Ghasemi, A., A distributed learning automata scheme for spectrum management in self-organized cognitive radio network, IEEE Trans Mob Comput, 16, 6, 1490-1501 (2017) · doi:10.1109/TMC.2016.2601926 |
| [11] | Farman, H.; Jan, B.; Javed, H.; Ahmad, N.; Iqbal, J.; Arshad, M.; Ali, S., Multi-criteria based zone head selection in internet of things based wireless sensor networks, Future Gener Comput Syst, 87, 364-371 (2018) · doi:10.1016/j.future.2018.04.091 |
| [12] | Ferreira, CS; Ochi, LS; Parada, V.; Uchoa, E., A GRASP-based approach to the generalized minimum spanning tree problem, Expert Syst Appl, 39, 3, 3526-3536 (2012) · doi:10.1016/j.eswa.2011.09.043 |
| [13] | García, S.; Molina, D.; Lozano, M.; Herrera, F., A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization, J Heurist, 15, 6, 617-644 (2009) · Zbl 1191.68828 · doi:10.1007/s10732-008-9080-4 |
| [14] | Ghavipour, M.; Meybodi, MR, An adaptive fuzzy recommender system based on learning automata, Electron Commer Res Appl, 20, 105-115 (2016) · doi:10.1016/j.elerap.2016.10.002 |
| [15] | Ghavipour, M.; Meybodi, MR, Trust propagation algorithm based on learning automata for inferring local trust in online social networks, Knowl Based Syst, 143, 317-326 (2018) · doi:10.1016/j.knosys.2017.06.034 |
| [16] | Golden, B.; Raghavan, S.; Stanojević, D., Heuristic search for the generalized minimum spanning tree problem, INFORMS J Comput, 17, 3, 290-304 (2005) · Zbl 1239.90099 · doi:10.1287/ijoc.1040.0077 |
| [17] | Haouari, M.; Chaouachi, JS, Upper and lower bounding strategies for the generalized minimum spanning tree problem, Eur J Oper Res, 171, 2, 632-647 (2006) · Zbl 1090.90163 · doi:10.1016/j.ejor.2004.07.072 |
| [18] | Hasanzadeh-Mofrad, M.; Rezvanian, A., Learning automata clustering, J Comput Sci, 24, 379-388 (2018) · doi:10.1016/j.jocs.2017.09.008 |
| [19] | Hu, B.; Leitner, M.; Raidl, GR, Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem, J Heurist, 14, 5, 473-499 (2008) · Zbl 1211.90309 · doi:10.1007/s10732-007-9047-x |
| [20] | Jiang, W.; Li, B.; Li, S.; Tang, Y.; Chen, CLP, A new prospective for learning automata: a machine learning approach, Neurocomputing, 188, 319-325 (2016) · doi:10.1016/j.neucom.2015.04.125 |
| [21] | Krishna PV, Misra S, Nagaraju D, Saritha V, Obaidat MS (2016) Learning automata based decision making algorithm for task offloading in mobile cloud. In: IEEE CITS 2016—2016 international conference on computer, information and telecommunication systems |
| [22] | Kumar, N.; Misra, S.; Obaidat, MS, Collaborative learning automata-based routing for rescue operations in dense urban regions using vehicular sensor networks, IEEE Syst J, 9, 3, 1081-1090 (2015) · doi:10.1109/JSYST.2014.2335451 |
| [23] | Misra, S.; Krishna, PV; Kalaiselvan, K.; Saritha, V.; Obaidat, MS, Learning automata-based QoS framework for cloud IaaS, IEEE Trans Netw Serv Manag, 11, 1, 15-24 (2014) · doi:10.1109/TNSM.2014.011614.130429 |
| [24] | Misra, S.; Venkata Krishna, P.; Saritha, V.; Agarwal, H.; Vasilakos, AV; Obaidat, MS, Learning automata-based fault-tolerant system for dynamic autonomous unmanned vehicular networks, IEEE Syst J, 11, 4, 1-10 (2017) · doi:10.1109/JSYST.2015.2418353 |
| [25] | Mollakhalili Meybodi, MR; Meybodi, MR, Extended distributed learning automata: an automata-based framework for solving stochastic graph optimization problems, Appl Intell, 41, 3, 923-940 (2014) · doi:10.1007/s10489-014-0577-2 |
| [26] | Moradabadi, B.; Meybodi, MR, A novel time series link prediction method: learning automata approach, Physica A Stat Mech Its Appl, 482, 422-432 (2017) · doi:10.1016/j.physa.2017.04.019 |
| [27] | Moradabadi, B.; Meybodi, MR, Link prediction in weighted social networks using learning automata, Eng Appl Artif Intell, 70, February, 16-24 (2018) · doi:10.1016/j.engappai.2017.12.006 |
| [28] | Mostafaei, H., Stochastic barrier coverage in wireless sensor networks based on distributed learning automata, Comput Commun, 55, 51-61 (2015) · doi:10.1016/j.comcom.2014.10.003 |
| [29] | Mostafaei, H.; Meybodi, MR, Maximizing lifetime of target coverage in wireless sensor networks using learning automata, Wirel Pers Commun, 71, 2, 1461-1477 (2013) · doi:10.1007/s11277-012-0885-y |
| [30] | Mostafaei, H.; Montieri, A.; Persico, V.; Pescapé, A., A sleep scheduling approach based on learning automata for WSN partial coverage, J Netw Comput Appl, 80, December 2016, 67-78 (2017) · doi:10.1016/j.jnca.2016.12.022 |
| [31] | Mukherjee A, Keshary V, Pandya K, Dey N, Satapathy SC (2018) Flying ad hoc networks: a comprehensive survey. In: Information and decision sciences. Springer, pp 569-580 |
| [32] | Myung, Y-S; Lee, C-H, On the generalized minimum spanning tree problem, Networks, 11, 4, 231-241 (1995) · Zbl 0856.90117 · doi:10.1002/net.3230260407 |
| [33] | Nettleton, DF, Data mining of social networks represented as graphs, Comput Sci Rev, 7, 1-34 (2013) · Zbl 1298.68046 · doi:10.1016/j.cosrev.2012.12.001 |
| [34] | Öncan, T.; Cordeau, J-F; Laporte, G., A tabu search heuristic for the generalized minimum spanning tree problem, Eur J Oper Res, 191, 2, 306-319 (2008) · Zbl 1149.90068 · doi:10.1016/j.ejor.2007.08.021 |
| [35] | Park J-H, Choi S-C, Hussen HR, Kim J (2017) Analysis of dynamic cluster head selection for mission-oriented flying ad hoc network. In: 2017 ninth international conference on ubiquitous and future networks (ICUFN). IEEE, pp 21-23 |
| [36] | Pop, PC; Kern, W.; Still, G., A new relaxation method for the generalized minimum spanning tree problem, Eur J Oper Res, 170, 3, 900-908 (2006) · Zbl 1091.90068 · doi:10.1016/j.ejor.2004.07.058 |
| [37] | Prabaharan, G.; Jayashri, S., Mobile cluster head selection using soft computing technique in wireless sensor network, Soft Comput, 23, 18, 8525-8538 (2019) · doi:10.1007/s00500-019-04133-w |
| [38] | Ranjbari, M.; Akbari Torkestani, J., A learning automata-based algorithm for energy and SLA efficient consolidation of virtual machines in cloud data centers, J Parallel Distrib Comput, 113, 55-62 (2018) · doi:10.1016/j.jpdc.2017.10.009 |
| [39] | Rao, PS; Jana, PK; Banka, H., A particle swarm optimization based energy efficient cluster head selection algorithm for wireless sensor networks, Wirel Netw, 23, 7, 2005-2020 (2017) · doi:10.1007/s11276-016-1270-7 |
| [40] | Reddy, MPK; Babu, MR, A hybrid cluster head selection model for internet of things, Clust Comput, 22, 6, 13095-13107 (2019) |
| [41] | Ren, J.; Wu, G.; Su, X.; Cui, G.; Xia, F.; Obaidat, MS, Learning automata-based data aggregation tree construction framework for cyber-physical systems, IEEE Syst J, 12, 2, 1467-1479 (2018) · doi:10.1109/JSYST.2015.2507577 |
| [42] | Rezvanian, A.; Meybodi, MR, Finding minimum vertex covering in stochastic graphs: a learning automata approach, Cybern Syst, 46, 8, 698-727 (2015) · doi:10.1080/01969722.2015.1082407 |
| [43] | Rezvanian, A.; Meybodi, MR, A new learning automata-based sampling algorithm for social networks, Int J Commun Syst, 30, 5, 1-21 (2017) · doi:10.1002/dac.3091 |
| [44] | Sang, Q.; Lin, Z.; Acton, ST, Learning automata for image segmentation, Pattern Recognit Lett, 74, 46-52 (2016) · doi:10.1016/j.patrec.2015.12.004 |
| [45] | Sengottuvelan, P.; Prasath, N., Bafsa: breeding artificial fish swarm algorithm for optimal cluster head selection in wireless sensor networks, Wirel Pers Commun, 94, 4, 1979-1991 (2017) · doi:10.1007/s11277-016-3340-7 |
| [46] | Shojafar, M.; Abolfazli, S.; Mostafaei, H.; Singhal, M., Improving channel assignment in multi-radio wireless mesh networks with learning automata, Wirel Pers Commun, 82, 1, 61-80 (2015) · doi:10.1007/s11277-014-2194-0 |
| [47] | Tang D, Liu X, Jiao Y, Yue Q (2011) A load balanced multiple cluster-heads routing protocol for wireless sensor networks. In: 2011 IEEE 13th international conference on communication technology. IEEE, pp 656-660 |
| [48] | Tarabalka, Y.; Benediktsson, JA; Chanussot, J., Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques, IEEE Trans Geosci Remote Sens, 47, 8, 2973-2987 (2009) · doi:10.1109/TGRS.2009.2016214 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
