A novel metaheuristic algorithm and its discrete form for influence maximizing in complex networks
Subject Areas : ICT
Vahideh Sahargahi
1
,
Vahid Majidnezhad
2
,
Saeed Taghavi Afshord
3
,
Bagher Jafari
4
1 - Student
2 - Assistant professor
3 -
4 - Academic staff
Keywords: IWOGSA, Invasive weed optimization algorithm, Gravitational search algorithm,
Abstract :
In light of the No Free Lunch (NFL) theorem, which establishes the inherent limitations of meta-heuristic algorithms in universally efficient problem solving, the ongoing quest for enhanced diversity and efficiency prompts the introduction of novel algorithms each year. This research presents the IWOGSA meta-heuristic algorithm, a pioneering solution tailored for addressing continuous optimization challenges. IWOGSA ingeniously amalgamates principles from both the invasive weed optimization algorithm and the gravitational search algorithm, capitalizing on their synergies. The algorithm's key innovation lies in its dual-pronged sample generation strategy: a subset of samples follows a normal distribution, while others emulate the planetary motion-inspired velocities and accelerations from the gravitational search algorithm. Furthermore, a selective transfer of certain samples from distinct classes contributes to the evolution of succeeding generations. Expanding upon this foundation, a discrete variant of IWOGSA, termed DIWOGSA, emerges to tackle discrete optimization problems. The efficacy of DIWOGSA is demonstrated through its application to the intricate influence maximization problem. DIWOGSA distinguishes itself with an astute population initialization strategy and the integration of a local search operator to expedite convergence. Empirical validation encompasses a rigorous assessment of IWOGSA against established benchmark functions, composite functions, and real-world engineering structural design problems. Remarkably, the IWOGSA algorithm asserts its superiority, eclipsing both contemporary and traditional methods. This ascendancy is statistically affirmed through the utilization of the Friedman test rank, positioning IWOGSA as the premier choice. Also, DIWOGSA algorithm is evaluated by considering different networks for influence maximization problem, and it shows acceptable results in terms of influence and computational time in comparison to conventional algorithms.
] Y. Chen and D. Pi, "An innovative flower pollination algorithm for continuous optimization problem," Applied Mathematical Modelling, vol. 83, pp. 237-265, 2020/07/01/ 2020, doi: https://doi.org/10.1016/j.apm.2020.02.023.
[2] Z. Cheng, H. Song, J. Wang, H. Zhang, T. Chang, and M. Zhang, "Hybrid firefly algorithm with grouping attraction for constrained optimization problem," Knowledge-Based Systems, vol. 220, p. 106937, 2021/05/23/ 2021, doi: https://doi.org/10.1016/j.knosys.2021.106937.
[3] J. Jiang, Y. Liu, and Z. Zhao, "TriTSA: Triple Tree-Seed Algorithm for dimensional continuous optimization and constrained engineering problems," Engineering Applications of Artificial Intelligence, vol. 104, p. 104303, 2021/09/01/ 2021, doi: https://doi.org/10.1016/j.engappai.2021.104303.
[4] A. Mortazavi, "Bayesian Interactive Search Algorithm: A New Probabilistic Swarm Intelligence Tested on Mathematical and Structural Optimization Problems," Advances in Engineering Software, vol. 155, p. 102994, 2021/05/01/ 2021, doi: https://doi.org/10.1016/j.advengsoft.2021.102994.
[5] Z.-k. Feng, W.-j. Niu, and S. Liu, "Cooperation search algorithm: A novel metaheuristic evolutionary intelligence algorithm for numerical optimization and engineering optimization problems," Applied Soft Computing, vol. 98, p. 106734, 2021/01/01/ 2021, doi: https://doi.org/10.1016/j.asoc.2020.106734.
[6] J. R. Koza, Genetic programming. MIT Press, 55 Hayward St., Cambridge, MA, United States, 1992.
[7] K. Price, R. Storn, and J. A. Lampinen, Differential Evolution, A Practical Approach to Global Optimization (Natural Computing Series). Springer-Verlag Berlin Heidelberg, 2005.
[8] I. Rechenberg, "Evolution Strategy: Nature’s Way of Optimization," in Optimization: Methods and Applications, Possibilities and Limitations, Berlin, Heidelberg, H. W. Bergmann, Ed., 1989// 1989: Springer Berlin Heidelberg, pp. 106-126.
[9] I. M. Ali, D. Essam, and K. Kasmarik, "A novel differential evolution mapping technique for generic combinatorial optimization problems," Applied Soft Computing, vol. 80, pp. 297-309, 2019/07/01/ 2019, doi: https://doi.org/10.1016/j.asoc.2019.04.017.
[10] A. Faramarzi, M. Heidarinejad, B. Stephens, and S. Mirjalili, "Equilibrium optimizer: A novel optimization algorithm," Knowledge-Based Systems, vol. 191, p. 105190, 2020/03/05/ 2020, doi: https://doi.org/10.1016/j.knosys.2019.105190.
[11] W. Al-Sorori and A. M. Mohsen, "New Caledonian crow learning algorithm: A new metaheuristic algorithm for solving continuous optimization problems," Applied Soft Computing, vol. 92, p. 106325, 2020/07/01/ 2020, doi: https://doi.org/10.1016/j.asoc.2020.106325.
[12] S. Mirjalili, S. M. Mirjalili, and A. Lewis, "Grey Wolf Optimizer," Advances in Engineering Software, vol. 69, pp. 46-61, 2014/03/01/ 2014, doi: https://doi.org/10.1016/j.advengsoft.2013.12.007.
[13] M. Dorigo, M. Birattari, and T. Stutzle, "Ant colony optimization," IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, 2006, doi: 10.1109/MCI.2006.329691.
[14] X. Chu et al., "An artificial bee colony algorithm with adaptive heterogeneous competition for global optimization problems," Applied Soft Computing, vol. 93, p. 106391, 2020/08/01/ 2020, doi: https://doi.org/10.1016/j.asoc.2020.106391.
[15] Q. Liu, L. Wu, W. Xiao, F. Wang, and L. Zhang, "A novel hybrid bat algorithm for solving continuous optimization problems," Applied Soft Computing, vol. 73, pp. 67-82, 2018/12/01/ 2018, doi: https://doi.org/10.1016/j.asoc.2018.08.012.
[16] E. Atashpaz-Gargari and C. Lucas, "Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition," in 2007 IEEE Congress on Evolutionary Computation, 25-28 Sept. 2007 2007, pp. 4661-4667, doi: 10.1109/CEC.2007.4425083.
[17] E. Bogar and S. Beyhan, "Adolescent Identity Search Algorithm (AISA): A novel metaheuristic approach for solving optimization problems," Applied Soft Computing, vol. 95, p. 106503, 2020/10/01/ 2020, doi: https://doi.org/10.1016/j.asoc.2020.106503.
[18] M. A. Eita and M. M. Fahmy, "Group counseling optimization," Applied Soft Computing, vol. 22, pp. 585-604, 2014/09/01/ 2014, doi: https://doi.org/10.1016/j.asoc.2014.03.043.
[19] A. Kaveh and V. R. Mahdavi, "Colliding bodies optimization: A novel meta-heuristic method," Computers & Structures, vol. 139, pp. 18-27, 2014/07/15/ 2014, doi: https://doi.org/10.1016/j.compstruc.2014.04.005.
[20] A. R. Mehrabian and C. Lucas, "A novel numerical optimization algorithm inspired from weed colonization," Ecological Informatics, vol. 1, no. 4, pp. 355-366, 2006/12/01/ 2006, doi: https://doi.org/10.1016/j.ecoinf.2006.07.003.
[21] A. Ouyang, X. Peng, Q. Wang, and Y. Wang, "Discrete invasive weed optimization algorithm for traveling salesman problems," in 2017 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), 29-31 July 2017 2017, pp. 523-528, doi: 10.1109/FSKD.2017.8393324.
[22] S. Roy, M. I. Sk, S. Das, S. Ghosh, and A. Vasilakos, "A simulated weed colony system with subregional differential evolution for multimodal optimization," Engineering Optimization - ENG OPTIMIZ, vol. 45, pp. 1-23, 11/30 2012, doi: 10.1080/0305215X.2012.678494.
[23] D. Kundu, K. Suresh, S. Ghosh, S. Das, B. K. Panigrahi, and S. Das, "Multi-objective optimization with artificial weed colonies," Information Sciences, vol. 181, no. 12, pp. 2441-2454, 2011/06/15/ 2011, doi: https://doi.org/10.1016/j.ins.2010.09.026.
[24] P. Pahlavani, M. R. Delavar, and A. U. Frank, "Using a modified invasive weed optimization algorithm for a personalized urban multi-criteria path optimization problem," International Journal of Applied Earth Observation and Geoinformation, vol. 18, pp. 313-328, 2012/08/01/ 2012, doi: https://doi.org/10.1016/j.jag.2012.03.004.
[25] GhoshArnob, DasSwagatam, ChowdhuryAritra, and GiriRitwik, "An ecologically inspired direct search method for solving optimal control problems with Bézier parameterization," Engineering Applications of Artificial Intelligence, 2011.
[26] A. Ojha and R. Yenugula, "Hybridizing Particle Swarm Optimization with Invasive Weed Optimization for Solving Nonlinear Constrained Optimization Problems," Advances in Intelligent Systems and Computing, vol. 336, pp. 595-606, 12/01 2015, doi: 10.1007/978-81-322-2220-0_49.
[27] M. R. Panda, S. Dutta, and S. Pradhan, "Hybridizing Invasive Weed Optimization with Firefly Algorithm for Multi-Robot Motion Planning," Arabian Journal for Science and Engineering, vol. 43, no. 8, pp. 4029-4039, 2018/08/01 2018, doi: 10.1007/s13369-017-2794-6.
[28] E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi, "GSA: A Gravitational Search Algorithm," Information Sciences, vol. 179, no. 13, pp. 2232-2248, 2009/06/13/ 2009, doi: https://doi.org/10.1016/j.ins.2009.03.004.
[29] E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi, "BGSA: binary gravitational search algorithm," Natural Computing, vol. 9, no. 3, pp. 727-745, 2010/09/01 2010, doi: 10.1007/s11047-009-9175-3.
[30] M. Dehbashian, Advanced Elitism gravitational Search Algorithm (AEGSA). 2010.
[31] D. H. Wolpert and W. G. Macready, "No free lunch theorems for optimization," Trans. Evol. Comp, vol. 1, no. 1, pp. 67–82, 1997, doi: 10.1109/4235.585893.
[32] J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proceedings of ICNN'95 - International Conference on Neural Networks, 27 Nov.-1 Dec. 1995 1995, vol. 4, pp. 1942-1948 vol.4, doi: 10.1109/ICNN.1995.488968.
[33] S. Mirjalili and A. Lewis, "The Whale Optimization Algorithm," Advances in Engineering Software, vol. 95, pp. 51-67, 2016/05/01/ 2016, doi: https://doi.org/10.1016/j.advengsoft.2016.01.008.
[34] Y. Xin, L. Yong, and L. Guangming, "Evolutionary programming made faster," IEEE Transactions on Evolutionary Computation, vol. 3, no. 2, pp. 82-102, 1999, doi: 10.1109/4235.771163.
[35] C. A. Coello Coello, "Use of a self-adaptive penalty approach for engineering optimization problems," Computers in Industry, vol. 41, no. 2, pp. 113-127, 2000/03/01/ 2000, doi: https://doi.org/10.1016/S0166-3615(99)00046-9.
[36] R. Tanabe and A. Fukunaga, "Success-history based parameter adaptation for Differential Evolution," in 2013 IEEE Congress on Evolutionary Computation, 20-23 June 2013 2013, pp. 71-78, doi: 10.1109/CEC.2013.6557555.
[37] A. W. Mohamed, A. A. Hadi, A. M. Fattouh, and K. M. Jambi, "LSHADE with semi-parameter adaptation hybrid with CMA-ES for solving CEC 2017 benchmark problems," in 2017 IEEE Congress on Evolutionary Computation (CEC), 5-8 June 2017 2017, pp. 145-152, doi: 10.1109/CEC.2017.7969307.
[38] H. Chen, M. Wang, and X. Zhao, "A multi-strategy enhanced sine cosine algorithm for global optimization and constrained practical engineering problems," Applied Mathematics and Computation, vol. 369, p. 124872, 2020/03/15/ 2020, doi: https://doi.org/10.1016/j.amc.2019.124872.
[39] S. H. Samareh Moosavi and V. K. Bardsiri, "Poor and rich optimization algorithm: A new human-based and multi populations algorithm," Engineering Applications of Artificial Intelligence, vol. 86, pp. 165-181, 2019/11/01/ 2019, doi: https://doi.org/10.1016/j.engappai.2019.08.025.
[40] S. Balochian and H. Baloochian, "Social mimic optimization algorithm and engineering applications," Expert Systems with Applications, vol. 134, pp. 178-191, 2019/11/15/ 2019, doi: https://doi.org/10.1016/j.eswa.2019.05.035.
[41] Q. He and L. Wang, "An effective co-evolutionary particle swarm optimization for constrained engineering design problems," Engineering Applications of Artificial Intelligence, vol. 20, no. 1, pp. 89-99, 2007/02/01/ 2007, doi: https://doi.org/10.1016/j.engappai.2006.03.003.
[42] H. S. Bernardino, H. J. C. Barbosa, A. C. C. Lemonge, and L. G. Fonseca, "A new hybrid AIS-GA for constrained optimization problems in mechanical engineering," in 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), 1-6 June 2008 2008, pp. 1455-1462, doi: 10.1109/CEC.2008.4630985.
[43] V. S. Aragón, S. C. Esquivel, and C. A. C. Coello, "A modified version of a T-Cell Algorithm for constrained optimization problems," International Journal for Numerical Methods in Engineering, vol. 84, no. 3, pp. 351-378, 2010/10/15 2010, doi: 10.1002/nme.2904.
[44] C. Coello, "Use of dominance-based tournament selection to handle constraints in genetic algorithms," Intelligent Engineering Systems Through Artificial Neural Networks, vol. 11, 01/01 2001.
[45] C. A. C. Coello and N. C. Cortés, "Hybridizing a genetic algorithm with an artificial immune system for global optimization," Engineering Optimization, vol. 36, no. 5, pp. 607-634, 2004/10/01 2004, doi: 10.1080/03052150410001704845.
[46] E. M. Montes and B. H. Oca "Bacterial foraging for engineering design problems: preliminary results," 4th Mex. Congr. Evol. Comput. COMCEV’2008, Mexico,, pp. 33-38, 2008.
[47] E. Mezura-Montes and C. A. C. Coello, "An empirical study about the usefulness of evolution strategies to solve constrained optimization problems," International Journal of General Systems, vol. 37, no. 4, pp. 443-473, 2008/08/01 2008, doi: 10.1080/03081070701303470.
[48] K. S. Lee and Z. W. Geem, "A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice," Computer Methods in Applied Mechanics and Engineering, vol. 194, no. 36, pp. 3902-3933, 2005/09/23/ 2005, doi: https://doi.org/10.1016/j.cma.2004.09.007.
[49] K. M. Ragsdell and D. T. Phillips, "Optimal Design of a Class of Welded Structures Using Geometric Programming," Journal of Engineering for Industry, vol. 98, no. 3, pp. 1021-1025, 1976, doi: 10.1115/1.3438995.
[50] S. Akhtar, K. Tai, and T. Ray, "A socio-behavioural simulation model for engineering design optimization," Engineering Optimization, vol. 34, no. 4, pp. 341-354, 2002/01/01 2002, doi: 10.1080/03052150212723.
[51] T. Ray and K. M. Liew, "Society and civilization: An optimization algorithm based on the simulation of social behavior," IEEE Transactions on Evolutionary Computation, vol. 7, no. 4, pp. 386-396, 2003, doi: 10.1109/TEVC.2003.814902.
[52] J. Zhang, C. Liang, Y. Huang, J. Wu, and S. Yang, "An effective multiagent evolutionary algorithm integrating a novel roulette inversion operator for engineering optimization," Applied Mathematics and Computation, vol. 211, no. 2, pp. 392-416, 2009/05/15/ 2009, doi: https://doi.org/10.1016/j.amc.2009.01.048.
[53] A.-R. Hedar and M. Fukushima, "Derivative-Free Filter Simulated Annealing Method for Constrained Continuous Global Optimization," Journal of Global Optimization, vol. 35, no. 4, pp. 521-549, 2006/08/01 2006, doi: 10.1007/s10898-005-3693-z.
[54] S. He, E. Prempain, and Q. H. Wu, "An improved particle swarm optimizer for mechanical design optimization problems," Engineering Optimization, vol. 36, no. 5, pp. 585-605, 2004/10/01 2004, doi: 10.1080/03052150410001704854.
[55] S.-F. Hwang and R.-S. He, "A hybrid real-parameter genetic algorithm for function optimization," Advanced Engineering Informatics, vol. 20, no. 1, pp. 7-21, 2006/01/01/ 2006, doi: https://doi.org/10.1016/j.aei.2005.09.001.
[56] F.-z. Huang, L. Wang, and Q. He, "An effective co-evolutionary differential evolution for constrained optimization," Applied Mathematics and Computation, vol. 186, no. 1, pp. 340-356, 2007/03/01/ 2007, doi: https://doi.org/10.1016/j.amc.2006.07.105.
[57] A. D. Belegundu and J. S. Arora, "A study of mathematical programming methods for structural optimization. Part I: Theory," International Journal for Numerical Methods in Engineering, vol. 21, no. 9, pp. 1583-1599, 1985/09/01 1985, doi: 10.1002/nme.1620210904.
[58] T. Ray and P. Saini, "ENGINEERING DESIGN OPTIMIZATION USING A SWARM WITH AN INTELLIGENT INFORMATION SHARING AMONG INDIVIDUALS," Engineering Optimization, vol. 33, no. 6, pp. 735-748, 2001/08/01 2001, doi: 10.1080/03052150108940941.
[59] C. A. Coello Coello and E. Mezura Montes, "Constraint-handling in genetic algorithms through the use of dominance-based tournament selection," Advanced Engineering Informatics, vol. 16, no. 3, pp. 193-203, 2002/07/01/ 2002, doi: https://doi.org/10.1016/S1474-0346(02)00011-3.
[60] K. Zhang, H. Du, and M. W. Feldman, "Maximizing influence in a social network: Improved results using a genetic algorithm," Physica A: Statistical Mechanics and its Applications, vol. 478, pp. 20-30, 2017/07/15/ 2017, doi: https://doi.org/10.1016/j.physa.2017.02.067.
[61] M. T. Nguyen and K. Kim, "Genetic convolutional neural network for intrusion detection systems," Future Generation Computer Systems, vol. 113, pp. 418-427, 2020/12/01/ 2020, doi: https://doi.org/10.1016/j.future.2020.07.042.
[62] J. Jabari Lotf, M. Abdollahi Azgomi, and M. R. Ebrahimi Dishabi, "An improved influence maximization method for social networks based on genetic algorithm," Physica A: Statistical Mechanics and its Applications, vol. 586, p. 126480, 2022/01/15/ 2022, doi: https://doi.org/10.1016/j.physa.2021.126480.
[63] G. Iacca, K. Konotopska, D. Bucur, and A. Tonda, "An evolutionary framework for maximizing influence propagation in social networks," Software Impacts, vol. 9, p. 100107, 2021/08/01/ 2021, doi: https://doi.org/10.1016/j.simpa.2021.100107.
[64] Q. Jiang, G. Song, G. Cong, Y. Wang, W. Si, and K. Xie, "Simulated annealing based influence maximization in social networks," presented at the Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, San Francisco, California, 2011.
[65] M. E. J. Newman, "Finding community structure in networks using the eigenvectors of matrices," Physical Review E, vol. 74, no. 3, p. 036104, 09/11/ 2006, doi: 10.1103/PhysRevE.74.036104.
[66] R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas, "Self-similar community structure in a network of human interactions," Physical Review E, vol. 68, no. 6, p. 065103, 12/17/ 2003, doi: 10.1103/PhysRevE.68.065103.
[67] J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graph evolution: Densification and shrinking diameters," ACM Trans. Knowl. Discov. Data, vol. 1, no. 1, pp. 2–es, 2007, doi: 10.1145/1217299.1217301.
[68] F. Lu, W. Zhang, L. Shao, X. Jiang, P. Xu, and H. Jin, "Scalable influence maximization under independent cascade model," Journal of Network and Computer Applications, vol. 86, pp. 15-23, 2017/05/15/ 2017, doi: https://doi.org/10.1016/j.jnca.2016.10.020.
[69] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, "Cost-effective outbreak detection in networks," presented at the Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, San Jose, California, USA, 2007. [Online]. Available: https://doi.org/10.1145/1281192.1281239.
[70] M. Gong, J. Yan, B. Shen, L. Ma, and Q. Cai, "Influence maximization in social networks based on discrete particle swarm optimization," Information Sciences, vol. 367-368, pp. 600-614, 2016/11/01/ 2016, doi: https://doi.org/10.1016/j.ins.2016.07.012.
[71] W. Chen, Y. Wang, and S. Yang, "Efficient influence maximization in social networks," presented at the Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, Paris, France, 2009. [Online]. Available: https://doi.org/10.1145/1557019.1557047.
[72] S. Brin and L. Page, "The anatomy of a large-scale hypertextual Web search engine," Computer Networks and ISDN Systems, vol. 30, no. 1, pp. 107-117, 1998/04/01/ 1998, doi: https://doi.org/10.1016/S0169-7552(98)00110-X.
[73] D. Kempe, J. Kleinberg, and É. Tardos, "Maximizing the spread of influence through a social network," presented at the Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, Washington, D.C., 2003. [Online]. Available: https://doi.org/10.1145/956750.956769.
