یک الگوریتم فراابتکاری پیوسته جدید و گسسته سازی آن جهت بیشینه سازی نفوذ در شبکه های پیچیده
الموضوعات :
وحیده سحرگاهی
1
,
وحید مجیدنژاد
2
,
Saeed Taghavi Afshord
3
,
باقر جعفری
4
1 - ّدانشجو
2 - هیات علمی
3 - Computer Engineering
4 - هیات علمی
الکلمات المفتاحية: الگوریتم بهینهسازي علفهاي هرز, الگوریتمهاي جستجوي گرانشي, الگوریتم IWOGSA,
ملخص المقالة :
طبق نظریه ناهار مجاني (NFL) هیچ الگوریتم فرا اکتشافي موجود قادر به حل همه نوع مسائل به طور کارآمد نیست، بنابراین هر ساله الگوریتمهاي جدیدي جهت تنوع بخشي پیشنهاد ميشوند. در این مقاله، الگوریتم فراابتکاري جدیدي به نام IWOGSA ، براي مسائل بهینهسازي پیوسته پیشنهاد شده است که ترکیبي از الگوریتمهاي بهینهسازي علفهاي هرز و جستجوي گرانشي است. در IWOGSA والدها به دو صورت تکثیر مي شوند و از هر دسته نمونههایي براي انتقال به نسل جدید انتخاب ميگردد. بخشي از تکثیر با توزیع نرمال صورت ميگیرد و بخشي دیگر بر مبناي روابط سرعت و شتاب حرکت سیارات در الگوریتم جستجوي گرانشي انجام ميشوند. یک مدل گسسته جدید از IWOGSA به نام DIWOGSA براي حل مسألههاي بهینهسازي گسسته پیشنهاد شده است و کارایي آن بر روي یک چالش حیاتي تحت عنوان بیشینهسازي نفوذ ارزیابي شده است. در DIWOGSA از رویکرد هوشمندانهاي براي مقداردهي اولیه جمعیت استفاده شده و براي همگرایي سریعتر الگوریتم، یک عملگر جستجوي محلي پیشنهاد شده است. در حالت پیوسته الگوریتم IWOGSA با توابع بنچمارک استاندارد و کامپوزیت و 3 مساله مهندسي رایج ارزیابي شده است. نتایج پیادهسازي ثابت ميکند که الگوریتم IWOGSA در مقایسه با روشهاي اخیر و متداول بسیار رقابتي بوده و با توجه به نتایج رتبهبندي آزمون فریدمن، توانسته است رتبه اول را کسب نماید. در حالت گسسته نیز الگوریتم DIWOGSA با در نظر گرفتن شبکههاي مختلف ارتباطاتي بین محققان براي مساله بیشینهسازي نفوذ مورد ارزیابي قرار گرفته و در مقایسه با الگوریتمهاي رایج در این زمینه از نظر میزان نفوذ و زمان اجرا نتایج قابل قبولي را کسب کرده است.
] 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.
