کد مقاله : 1402061443902 بازدید : 2282 صفحه: 48 - 77

نوع مقاله: پژوهشی

یک الگوریتم فراابتکاری پیوسته جدید و گسسته سازی آن جهت بیشینه سازی نفوذ در شبکه های پیچیده

محورهای موضوعی : فناوری اطلاعات و ارتباطات

وحیده سحرگاهی ¹ , وحید مجیدنژاد ^{2
*} , Saeed Taghavi Afshord ³ , باقر جعفری ⁴

1 - ّدانشجو
2 - هیات علمی
3 - Computer Engineering
4 - هیات علمی

تاریخ دریافت : 1401/05/27 تاریخ پذیرش : 1402/02/17 تاریخ انتشار : 1402/06/14

کلید واژه: الگوریتم بهینهسازي علفهاي هرز, الگوریتمهاي جستجوي گرانشي, الگوریتم IWOGSA,

چکیده مقاله :

طبق نظریه ناهار مجاني (NFL) هیچ الگوریتم فرا اکتشافي موجود قادر به حل همه نوع مسائل به طور کارآمد نیست، بنابراین هر ساله الگوریتمهاي جدیدي جهت تنوع بخشي پیشنهاد ميشوند. در این مقاله، الگوریتم فراابتکاري جدیدي به نام IWOGSA ، براي مسائل بهینهسازي پیوسته پیشنهاد شده است که ترکیبي از الگوریتمهاي بهینهسازي علفهاي هرز و جستجوي گرانشي است. در IWOGSA والدها به دو صورت تکثیر مي شوند و از هر دسته نمونههایي براي انتقال به نسل جدید انتخاب ميگردد. بخشي از تکثیر با توزیع نرمال صورت ميگیرد و بخشي دیگر بر مبناي روابط سرعت و شتاب حرکت سیارات در الگوریتم جستجوي گرانشي انجام ميشوند. یک مدل گسسته جدید از IWOGSA به نام DIWOGSA براي حل مسألههاي بهینهسازي گسسته پیشنهاد شده است و کارایي آن بر روي یک چالش حیاتي تحت عنوان بیشینهسازي نفوذ ارزیابي شده است. در DIWOGSA از رویکرد هوشمندانهاي براي مقداردهي اولیه جمعیت استفاده شده و براي همگرایي سریعتر الگوریتم، یک عملگر جستجوي محلي پیشنهاد شده است. در حالت پیوسته الگوریتم IWOGSA با توابع بنچمارک استاندارد و کامپوزیت و 3 مساله مهندسي رایج ارزیابي شده است. نتایج پیادهسازي ثابت ميکند که الگوریتم IWOGSA در مقایسه با روشهاي اخیر و متداول بسیار رقابتي بوده و با توجه به نتایج رتبهبندي آزمون فریدمن، توانسته است رتبه اول را کسب نماید. در حالت گسسته نیز الگوریتم DIWOGSA با در نظر گرفتن شبکههاي مختلف ارتباطاتي بین محققان براي مساله بیشینهسازي نفوذ مورد ارزیابي قرار گرفته و در مقایسه با الگوریتمهاي رایج در این زمینه از نظر میزان نفوذ و زمان اجرا نتایج قابل قبولي را کسب کرده است.

چکیده انگلیسی:

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.

متن کامل:

بسمه‌ تعالي‌

دو فصلنامه علمي

فناوري اطلاعات و ارتباطات ایران

سال پانزدهم، شماره‌هاي 55 و 56، بهار و تابستان 1402

صفحات:48 تا 77

$E:\E Drive\logo\iicta Logo0.JPG$

A novel metaheuristic algorithm and its discrete form for influence maximizing in complex networks

Vahideh Sahargahi *, Vahid Majidnezhad**, Saeid Taghavi Afshord**, Yasser Jafari**

*Ph.D., Department of Computer Engineering, Islamic Azad University, Shabestar Branch, Shabestar, Iran

** Assistant Professor, Department of Computer Engineering, Islamic Azad University, Shabestar Branch, Shabestar, Iran

Abstract

Keywords: IWOGSA, Invasive weed optimization algorithm, Gravitational search algorithm

یک الگوریتم فراابتکاری پیوسته جدید و گسسته‌سازی آن جهت بیشینه‌سازی نفوذ در شبکه‌های پیچیده

وحیده سحرگاهی*، وحید مجیدنژاد**×، سعید تقوی افشرد**، یاسر جعفری**

* دکتر، گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی، واحد شبستر، شبستر، ایران

** استادیار،گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی، واحد شبستر، شبستر، ایران

تاریخ دریافت: 27/05/1401 تاریخ پذیرش: 17/02/1402

نوع مقاله: پژوهشی

چکيده

طبق نظریه ناهار مجانی (NFL) هیچ الگوریتم‌ فرا اکتشافی موجود قادر به حل همه نوع مسائل به طور کارآمد نیست، بنابراین هر ساله الگوریتم‌های جدیدی جهت تنوع بخشی پیشنهاد می‌شوند. در این مقاله، الگوریتم فراابتکاری جدیدی به نام IWOGSA، برای مسائل بهینه‌سازی پیوسته پیشنهاد شده است که ترکیبی از الگوریتم‌های بهینه‌سازی علف‌های هرز و جستجوی گرانشی است. در IWOGSA والدها به دو صورت تکثیر می‌شوند و از هر دسته نمونه‌هایی برای انتقال به نسل جدید انتخاب می‌گردد. بخشی از تکثیر با توزیع نرمال صورت می‌گیرد و بخشی دیگر بر مبنای روابط سرعت و شتاب حرکت سیارات در الگوریتم جستجوی گرانشی انجام می‌شوند. یک مدل گسسته جدید از IWOGSA به نام DIWOGSA برای حل مسأله‌های بهینه‌سازی گسسته پیشنهاد شده است و کارایی آن بر روی یک چالش حیاتی تحت عنوان بیشینه‌سازی نفوذ ارزیابی شده است. در DIWOGSA از رویکرد هوشمندانه‌ای برای مقداردهی اولیه جمعیت استفاده شده و برای همگرایی سریعتر الگوریتم، یک عملگر جستجوی محلی پیشنهاد شده است. در حالت پیوسته الگوریتم IWOGSA با توابع بنچمارک استاندارد و کامپوزیت و 3 مساله مهندسی رایج ارزیابی شده است. نتایج پیاده‌سازی ثابت می‌کند که الگوریتم IWOGSA در مقایسه با روش‌های اخیر و متداول بسیار رقابتی بوده و با توجه به نتایج رتبه‌بندی آزمون فریدمن، توانسته است رتبه اول را کسب نماید. در حالت گسسته نیز الگوریتم DIWOGSA با در نظر گرفتن شبکه‌های مختلف ارتباطاتی بین محققان برای مساله بیشینه‌سازی نفوذ مورد ارزیابی قرار گرفته و در مقایسه با الگوریتم‌های رایج در این زمینه از نظر میزان نفوذ و زمان اجرا نتایج قابل قبولی را کسب کرده است.

كلمه‌های کلیدی: الگوریتم بهینه‌سازی علف‌های هرز، الگوریتم‌های جستجوی گرانشی، الگوریتم IWOGSA

×نویسنده مسئول: وحید مجیدنژاد vahidmn@yahoo.com

1- مقدمه

مسائل پیچیده، اعم از مسائل مهندسی و یا مسائلی همانند زمانبندی کارها و بهینه‌سازی صرفا توسط دانش و روش‌های ریاضی و الگوریتم‌های متداول قابلیت حل ندارند و یا زمان بالایی برای حل این مسائل نیاز می‌باشد. در این بین علم هوش‌مصنوعی دارای ابزارهای مناسب جهت حل این مسائل می‌باشد. یکی از ابزارهای کارامد برای حل مسائل بهینه‌سازی در علم هوش مصنوعی الگوریتم‌های فراابتکاری هستند. در سال‌های اخیر الگوریتم‌های فراابتکاری بسیاری از جمله الگوریتم گرده افشانی گل ¹CMFPA [1]، الگوریتم کرم شب تاب ترکیبی با جاذبه گروه بندی HFA-GA² [2]، الگوریتم سه درختی TriTSA³ [3]، الگوریتم جستجوی تعاملی بیزی BISA⁴ [4]، الگوریتم جستجوی همکاری CSA⁵ [5]، الگوریتم بهینه‌سازی آزمایشی دو شکاف یانگ (YDSE) [6]ُ، الگوریتم بهینه‌سازی کواتی (COA) [7]و الگوریتم سینوسی کسینوس تقویت شده با بهره برداری (EBSCA)) [8] توسط محققان مختلف پیشنهاد شده‌اند.

انواع الگوریتم‌های فراابتکاری به دسته‌های الگوریتم‌های تکاملی [9-12]، الگوریتم‌های شبیه‌سازی ساختار‌های فیزیکی [13] 41]، الگوریتم‌های هوش جمعی [14-18] و الگوریتم‌های مبتنی بر رفتار انسان [19-22] تقسیم‌بندی می‌شوند [13]. اکثر این الگوریتم‌ها در کنار عملکرد مناسب خود دارای معیاب نیز می‌باشند. زمان اجرای طولانی، نرسیدن به بهینه سراسری در برخی از اوقات و سرعت همگرایی پایین از معیاب الگوریتم زنتیک از دسته الگوریتم‌های تکاملی است [20]. از معایب الگوریتم وال [21] از دسته الگویتم‌های هوش جمعی می‌توان به افتادن در بهینه محلی، سرعت همگرایی و دقت پایین اشاره کرد [22]. دقت حل کم، توانایی کم در جستجوی محلی و سرعت همگرایی پایین [23] از معایب الگوریتم گرگ خاکستری [12] و نرخ همگرایی آهسته، محاسبات بسیار از معایب الگوریتم تکامل تفاضلی [24] است.

الگوریتم علف‌های هرز (IWO⁶) از الگوریتم‌های اکتشافی مبتنی بر جمعیت می‌باشد که توسط مهرآبیان و لوکاس ارائه شده است [23]. این الگوریتم از روند رشد علف‌های هرز در طبیعت الهام می‌گیرد. به طور طبیعی، علف‌های هرز به شدت رشد می‌کنند و این رشد شدید یک تهدید جدی برای گیاهان مفید است. خصوصيات مهم علف‌هاي هرز، پايداري و سازگاري زياد آن‌ها در طبيعت است كه اساس بهينه‌سازي الگوريتم IWO است.

الگوریتم علف‌های هرز در مطالعات قبلی بهبود یافته که از آن جمله می‌توان به موارد زیر مانند IWO گسسته [24]، ترکیب الگوریتم علف‌های هرز با الگوریتم تکامل دیفرانسیل [25]، بکارگیری IWO برای الگوریتم‌‌های بهینه‌سازی چند هدفه [26]، بهبود یافته الگوریتم IWO [27, 28]، ترکیب الگوریتم PSO و الگوریتم بهینه‌سازی علف‌های هرز [29]، ترکیب الگوریتم بهینه‌سازی علف‌های هرز و الگوریتم کرم شب‌تاب [30]اشاره کرد.

الگوریتم جستجوی گرانشی از دسته الگوریتم‌های شبیه‌سازی ساختار‌های فیزیکی از سوی خانم راشدی معرفی شد [31]. این الگوریتم با شبیه‌سازی قوانینی شبیه به قانون گرانش و حرکت نیوتن در محیطی با زمان گسسته در فضای جستجو، طراحی شده است. الگوریتم GSA دارای ویژگی‌های مثبت زیادی همچون همگراییِ سریع، عدم توقف در بهینه‌های محلی، کاهش حجم محاسباتی نسبت به الگوریتم‌های تکاملی و عدم نیاز به حافظه در مقایسه با دیگر الگوریتم‌های خانواده هوش جمعی، بستر جدیدی از تحقیقات را فرا روی محققان قرار داده است. از این‌رو، با توجه به زمینه‌های کاربردی مورد استفاده، نسخه‌های متفاوتی از الگوریتم GSA ارائه شده است که می‌توان به الگوریتم جستجوی گرانشی باینری (BGSA) [32] و الگوریتم جستجوی گرانشی نخبه‌گرای پیشرفته(AEGSA) [33] اشاره کرد.

طبق نظریه نهار مجانی (NFL⁷) [34] منطقاً اثبات شده است که هیچ فراابتکاری برای حل تمام مسائل بهینه‌سازی صحیح جواب نمی‌دهد. به عبارت دیگر، یک فراابتکار بخصوص، ممکن است نتایج امیدبخشی را برای حل یک سری از مسائل نشان دهد، اما همین الگوریتم ممکن است کارآیی ضعیفی را برای تعداد دیگری از مسائل نشان دهد. بنابراین، هر ساله محققان در زمینه بهینه‌سازی در تلاش هستند تا تکنیک‌های بهینه‌سازی بهتری را ایجاد کند.

زمان اجرا طولانی تر، مشکل همگرایی درصورت تولید نامناسب جمعیت اولیه از معایب الگورتم GSA است [37]. از سوی دیگر، از معایب IWO می‌توان به دقت حل پایین و گیرکردن در بهینه‌های محلی و همگرایی اولیه اشاره کرد[32] . در سال‌های اخیر، بسیاری از محققان، سعی در ترکیب الگوریتم‌ها برای غلبه بر کاستی‌های فردی آن‌ها دارند. در این مقاله سعی کرده ایم از قابلیت‌های الگوریتم GSA، در بهبود عملکرد الگوریتم علف‌های هرز جهت حل مسائل بهینه‌سازی استفاده نماییم. در روش ترکیبی پیشنهادی IWOGSA برای تکثیر والدها علاوه بر توزیع نرمال از روابط سرعت و شتاب حرکت سیارات در الگوریتم جستجوی گرانشی استفاده شده است و انتخاب والدها در هر نسل از هر دو مجموعه فرزندهای تولید شده و خود والدها صورت می‌گیرد. روش پیشنهادی با در نظر گرفتن 29 تابع بنچمارک استاندارد با روش‌های رایج و جدید موجود در این زمینه مقایسه شده است.

همچنین در این مقاله یک مدل گسسته جدید از الگوریتم پیشنهادی IWOGSA به نام DIWOGSA برای حل مسأله‌های بهینه‌سازی گسسته پیشنهاد شده است و کارایی آن بر روی یک چالش حیاتی تحت عنوان بیشینه‌سازی نفوذ ارزیابی شده است. مساله بیشینه‌سازی نفوذ انتخاب مجموعه‌ای از گره‌های اولیه در شبکه‌های پیچیده برای گسترش نفوذ تا حد ممکن است. این مساله به طور گسترده مورد مطالعه بسیاری از محققان قرار گرفته است. روش‌های حریصانه برای مساله بیشینه‌سازی نفوذ نتایج خوبی را ارایه می‌دهد. اما این الگوریتم‌ها از مسائل مربوط به کارایی زمان و مقیاس‌پذیری رنج می‌برند. در مقابل الگوریتم‌های حریصانه، الگوریتم‌های به حداکثر رساندن تأثیر فرااکتشافی کارایی را بهبود می‌بخشند، اما نمی‌توانند نتایج دقیق را تضمین کنند. در این مقاله مدل گسسته از الگوریتم IWOGSA به نام DIWOGSA برای مساله بیشینه‌سازی نفوذ پیشنهاد شده است. روش پیشنهادی با در نظر گرفتن شبکه‌های مختلف با روش‌های رایج به نام IWO، GSA، EO، WOA، SSA، PSO، GA، FEP، SHADE و LSHADE-SPACMA مورد مقایسه قرار خواهد گرفت.

در ادامه پس از بیان توضیح مختصری از الگوریتم علف‌های هرز و جستجوی گرانشی ترکیبی از این دو الگوریتم برای حل مسائل بهینه‌سازی در قسمت دوم بیان خواهد شد. روش پیشنهادی با جزئیات کامل در قسمت سوم بیان شده است. قسمت چهارم حاوی ارزیابی روش پیشنهادی با درنظر گرفتن توابع بنچمارک استاندارد می‌باشد. در قسمت پنجم نحوه به کارگیری الگوریتم پیشنهادی برای حل سه مساله مهندسی رایج به نام‌ طراحی مجرای فشار، طراحی پرتو جوش و مینیمم‌سازی وزن یک مطرح شده است. در قسمت ششم مدل گسسته الگوریتم IWOGSA برای حل مساله بیشینه سازی نفوذ پیشنهاد شده و مورد ارزیابی قرار گرفته و با روش‌های رایج هوشمند و حریصانه به نام CELF، DPSO، Single Discount، Degree، Betweenness Centrality و PageRank مقایسه شده است. در قسمت هفتم نتیجه‌گیری در ادامه کارهای آتی بیان خواهند شد.

2- علف‌های هرز و جستجوی گرانشی

در این قسمت به بیان مختصری از الگوریتم‌های جستجوی گرانشی و الگوریتم علف‌های هرز می‌پردازیم و در ادامه یک روش ترکیبی از این دو روش برای غلبه بر کاستی‌های فردی آن‌ها در حل مسائل بهینه‌سازی مطرح می‌گردد.

3- الگوریتم علف‌های هرز

الگوریتم علف‌های هرز (IWO) یکی از الگوریتم‌های برجسته در حل مسائل بهینه‌سازی می‌باشد [23]. این الگوریتم را می‌توان با استفاده از تمهیدات خاص در شرایط گسسته، پیوسته و باینری بکار برده و نتایج بهتری از آن در مقایسه با سایر روش‌های بهینه‌سازی بدست آورد. الگوریتم علف‌های هرز در روش بهینه‌سازی از عملکرد رشد علف‌های هرز در طبیعت الهام گرفته است. در طبیعت علف‌های هرز رشد شدیدی دارند و این رشد شدید تهدیدی جدی برای گیاهان مفید می‌باشد. یکی از ویژگی‌های مهم علف‌های هرز پایداری و تطابق‌پذیری بسیار بالای آن‌ها در طبیعت می‌باشد که این ویژگی مبنای بهینه‌سازی در الگوریتم IWO قرار گرفته است.

الگوریتم فراابتکاری علف‌های هرز یکی از الگوریتم‌های بهینه‌سازی جدید و توانمند است که بر اساس تقلید از قابلیت تطابق‌پذیری و تصادفی بودن کولونی علف‌های هرز، بهینه عمومی یک تابع ریاضی را پیدا می‌کند. علف هرز پدیده‌ای است که در جستجوی بهینگی و یافتن بهترین محیط برای زندگی بوده و به سرعت خود را با شرایط محیطی وفق داده و در مقابل تغییرات مقاوم میباشد. در ابتدا علف هرز به دنبال تولید تعداد زیاد فرزندان بوده که موجب افزایش کمیت و همچنین پوشش محیط در دسترس خود می‌شود، سپس به دلیل محدودیت ظرفیت، با افزایش کیفیت به رشد به صورت رقابتی ادامه می‌دهد و رفتار حریصانه خواهد داشت. به طور کلی هدف یافتن بهترین محیط برای زندگی علف‌های هرز می‌باشد.

مراحل الگوریتم علف‌های هرز:

· پخش دانه در فضای مورد نظر

· رشد دانه‌ها با توجه به مطلوبیت (زاد و ولد و پراکندگی محیطی)

· ادامه حیات علف‌هایی با مطلوبیت بیشتر)حذف رقابتی(

4- الگوریتم جستجوی گرانشی

الگوریتم جستجوی گرانشی درسال 2009 از سوی خانم راشدی معرفی شد [31]. این الگوریتم با شبیه‌سازی قوانینی شبیه به قانون گرانش و حرکت نیوتن در محیطی با زمان گسسته در فضای جستجو، طراحی شده است.

مطابق قانون نیوتن هرجسم به جسم دیگر نیرویی وارد می‌کند که این نیرو با جرم خود جسم و معکوس مجذور فاصله تا جسم دیگر متناسب است. بنابراین، جرم‌های بزرگتر نیروی بیشتری بر جرم‌های کوچکتر وارد می‌کنند و برعکس جرم‌های کوچکتر نیروی کمتری بر جرم‌های بزرگتر وارد می‌کنند.

با توجه به قوانین فیزیکی هر جسم بر اثر نیرویی که به آن وارد می‌شود، دارای شتاب و در نتیجه سرعتی هم جهت با آن نیرو می‌شود. بنابراین، جرم‌های کوچکتر به علت آنکه نیروی اعمالی ‌بر آن‌ها‌ بسیار بیشتر است، به سمت جرم‌های بزرگتر حرکت می‌کنند. بدین ترتیب، اگر نقاط بهینه را محل اجرام بزرگتر در نظر بگیریم، با استفاده از قانون گرانش می‌توانیم این اطلاعات را به بقیه اجرام منتقل کنیم و آن‌ها را به سمت نقاط بهینه سوق دهیم.

مراحل مختلف الگوریتم جستجوی گرانشی عبارتست از:

1. مشخص کردن فضای جستجو

2. رقم‌دهی تصادفی

3. ارزیابی برازش عامل‌ها

4. بروز کردن G(t)، best (t)، worst (t) و Mi(t) برای i=1, 2, …, N.

5. محاسبه نیروی کلی در مسیرهای مختلف

6. محاسبه سرعت و شتاب

7. بروز کردن وضعیت و موقعیت عامل‌ها

8. تکرار مراحل c تا g تا زمان رسیدن به معیار توقف

9. پایان

5- الگوریتم پیشنهادی IWOGSA

روش IWOGSA بهبود الگوریتم علف‌های هرز بر مبنای الگوریتم جستجوی گرانشی می‌باشد. در الگوریتم علف‌های هرز تکثیر دانه‌ها با توزیع نرمال صورت می‌گیرد ما برای بهبود این مرحله از الگوریتم GSA استفاده کرده‌ایم به طوریکه تکثیر والد در روش پیشنهادی با دو روش مختلف توزیع نرمال و توزیع بر مبنای مکان مجموعه‌ای از راه‌حل‌های مطلوب با توجه به شایستگی آن‌ها صورت می‌گیرد. مراحل الگوریتم IWOGSA با بیان جزئیات هر مرحله در ادامه مطرح می‌گردد.

6- جمعیت اولیه

جمعیت اولیه به صورت تصادفی به تعداد اعضای جمعیت (N) تعریف شده به صورت برداری از متغیرهای مساله با توجه به ابعاد آن‌ها ایجاد می‌گردد.

7- تکثیر

برای تکثیر هر راه حل در ابتدا با توجه به برازندگی هر راه‌حل مقدار برای هر راه‌حل با نرمال سازی مقادیر با رابطه 1-2 محاسبه می‌شود.

(1)
(2)

که در fiti(t) مقدار شایستگی راه‌حل i در دور t را نشان می‌دهد، best (t)، worst (t) به ترتیب بهترین و بدترین مقدار شایستگی در میان اعضای جمعیت می‌باشند. سپس مقدار با رابطه 3 محاسبه خواهد شد.

(3)

که در آن و بردار راه‌حل‌های i ام و jام است. و مقادیر محاسبه شده با رابطه 2 می‌باشند. مقدار یک مقدار ثابت کوچک، فاصله اقلیدسی بین دو راه حل i و j، و مقادیر ثابت و عددی تصادفی است. Xbest مجموعه‌ای از راه‌حل‌های مطلوب از اعضای جمعیت است. تعداد اعضای این مجموعه در ابتدا برابر با اعضای جمعیت N بوده و با گذر زمان کاهش می‌یابد و در آخر فقط یک راه‌حل وجود دارد که به عنوان راه حل مطلوب شناخته می‌شود.

در ادامه مقادیر دو متغییر و به صورت مجزا باتوجه به مقادیر اولیه و نهایی هر کدام با رابطه 4-5 به دست می‌آیند.

(4)
(5)

که در ان بیشترین تعداد تکرار، t دور جاری، مقدار اولیه و نهایی انحراف معیار اول و مقدار اولیه و نهایی انحراف معیار دوم است.

مقدار تکثیر هر والد با بر اساس میزان شایستگی آن با رابطه 6 مشخص می‌گردد.

(6)

در این مرحله هر والد با توجه به تعداد تکثیر محاسبه شده برای آن تکثیر خواهد شد. به طوری‌که راه‌حل‌های فرزند در حوالی والد خود به دو صورت توزیع می‌شوند:

a. ایجاد راه‌حل‌های فرزند با توزیع نرمال با احتمال با رابطه زیر صورت می‌گیرد و راه‌حل‌های جدید ایجاد شده در لیست جداگانه‌ای به نام populationI با رابطه 7-8 قرار می‌گیرد.

(7)
(8)

b. ایجاد راه‌حل‌های فرزند بر مبنای حرکت سیارات در الگوریتم جستجوی گرانشی (با توجه به سرعت و شتاب محاسبه شده) با احتمال با رابطه 9-10 صورت گرفته و راه‌حل‌های ایجاد شده به اعضای جمعیت فعلی اضافه می‌گردد.

(9)
(10)

قابل ذکر است که برای تعیین اینکه چه تعداد از راه‌حل‌ها با هر یک از روش‌ها ایجاد گردد، ما از یک توزیع نرمال دیگری به نام استفاده کرده‌ایم. این مرحله برای آن است که در ابتدا تعداد بیشتری از دانه‌های فرزند با توزیع نرمال ایجاد شده و درصد بیشتری از آن‌ها به مراحل بعد انتقال یابند و در ادامه این تعداد کمتر گردد.

8- انتخاب جمعیت

انتخاب تعداد بیشتری از راه‌حل‌های ایجاد شده بر مبنای الگوریتم جستجوی گرانشی و جمعیت فعلی (NP) با رابطه 11 و تعداد کمی از راه‌حل‌های ایجاد شده با توزیع نرمال (NM) با رابطه 12 بر اساس میزان شایستگی‌ آن‌ها انتخاب می‌شوند به طوریکه مجموع این دانه‌ها از اندازه جمعیت مورد نظر بیشتر نشود.

(11)	NM=round (min (* N,size (populationI)))
(12)	NP= N- NM

که در آن N ماکزیمم اعضای جمعیت هر نسل، populationI جمعیت جدید ایجاد شده با توزیع نرمال، NM تعداد اعضای انتخابی از جمعیت جدید تولید شده با توزیع نرمال، NP تعداد اعضای انتخابی از مجموعه جمعیت فعلی و جمعیت جدید ایجاد شده بر مبنای روابط مبتنی بر شتاب و حرکت سیارات است.

9- شرط پایان

برای الگوریتم‌های فراابتکاری شرایط پایان متفاوتی را می‌توان تعریف کرد که از آن جمله می‌توان به تعداد تکرارهای خاص، محدودیت در تعداد دفعات اجرای تابع شایستگی، رسیدن به دقتی خاص، زمان خاص، عدم تغییر در نتیجه راه‌حل بعد از تعداد تکراری مشخص و یا ترکیبی از این‌ها اشاره کرد. شرط پایانی در الگوریتم پیشنهادی تعداد تکرار مشخص است. شبه کد روش پیشنهادی در الگوریتم 1 و فلوچارت روش پیشنهادی در شکل 1 نشان داده‌ شده است.

[1] flower pollination algorithm

[2] Hybrid firefly algorithm with grouping attraction

[3] Triple Tree-Seed Algorithm

[4] Bayesian Interactive Search Algorithm

[5] Cooperation search algorithm

[6] Invasive Weed Optimization

[7] No Free lunch theoream

الگوریتم 1: شبه کد الگوریتم IWOGSA

Input: maximum number of iteration MaxIt, number of population N,minimum and maximum number of offspring for each parents as , for (Eq. 4-5) and are constants with values equal

1. Initialize population of solutions, set parameters;

2. Iter =1;

3. Calculate the fitness of each solutions

4. while (Iter< MaxIt)

5. Compute the best and worst fitness in the population

6. Compute the σ1 and the σ2 using (Eq. 4-5)

7. Compute m, M, a for each solution in the population using (Eq. 1-3)

8. i=1

9. populationI= [31];

10. for i=1 to nPop

11. Compute the number of offsprings for solutioni using (Eq. 6)

12. for i=1:

13. p=rand;

14. if p<σ2

15. Produce offspring using (Eq.8)

16. Adjust the veleocity of the new offspring using (Eq. 7)

17. Add offspring to the populationI

18. else

19. Produce offspring using (Eq. 9)

20. Update veleocity using (Eq. 10)

21. Add offspring to the population

22. end

23. end

24. end

25. Compute NM, NP using (Eq. 11-12);

26. Select the number of NP offspring from the best members of population

And the number of NM offsprings from the best offsprings of

populationI as new_population

27. population=new_population

28. Iter=Iter+1;

29.end

30.output best solution from population

شکل 1: فلوچارت الگوریتم IWOGSA

10- ارزیابی روش پیشنهادی

برای بررسی کارایی الگوریتم پیشنهادی IWOGSA، این روش را با 29 تابع بنچمارک مختلف ارزیابی کرده‌ایم. این توابع جزو توابع استاندارد بنچمارک می‌باشند که با استفاده از آن‌ها می‌توان روش‌های بهینه‌سازی را با در نظر گرفتن معیارهای مختلفی از جمله اکتشاف، بهره برداری و قدرت ایجاد تعادل بین اکتشاف و بهره برداری و توانایی روش در فرار از بهینه محلی مورد ارزیابی قرار داد [13, 15, 31, 35].

این توابع به چهار دسته اصلی تقسیم‌بندی می‌شوند، توابع تک هدفه، توابع چندهدفه، توابع چندهدفه با ابعاد ثابت و توابع کامپوزیت. توابع (F1-F7) از دسته توابع تک هدفه هستند. این توابع ریاضی دارای یک راه‌حل واحد می‌باشند که برای ارزیابی بهره‌برداری روش‌های بهینه‌سازی طراحی شده‌اند. توابع تک هدفه به همراه ابعاد به کارگرفته شده‌ آن‌ها در جدول 1 نشان داده‌ شده‌اند. توابع (F8-F13) از دسته توابع چندهدفه برای ارزیابی کاوش روش‌های بهینه‌سازی به کارگرفته می‌شوند. این توابع داری بیش از یک راه‌حل بهینه هستند. جدول 2 شامل جزيیات این دسته از توابع می‌باشد. توابع (F14-F23) جزو توابع چندهدفه با ابعاد ثابت می‌باشند. که همانند دسته قبلی ولی با ابعاد کم و ثابت می‌باشند. توابع کامپوزیت (F24-F29) با داشتن تعداد زیادی از بهینه‌های محلی و پیچیدگی یک دامنه جستجوی واقعی را تقلید می‌کند. فلذا این توابع جزو توابع چالش برانگیر هستند. جزئیات بیشتر در مورد عملکرد ترکیب را می‌توان در گزارش فنی CEC2005 یافت [36]. جزییات این دو دسته از توابع نیز به ترتیب در جدول 3 و جدول 4 آورده شده است. نمودار دو بعدی مربوط به نمونه‌هایی از این نوع توابع در شکل 2 آورده شده است. این نمودارهای دو بعدی بر اساس مقادیر مختلف متغیرهای مربوط به هر تابع در بازه هر یک از آن‌ها که در جداول 1-4 بیان گردیده، رسم شده است.

جدول 1. توابع آزمون نک هدفه

Function

Range

F min

[-100,100]

[-10,10]

[-100,100]

[-30,30]

[-100,100]

[-1.28,1.28]

جدول 2 . توابع آزمون چندهدفه

Function	D	Range	fmin
	30	[-500,500]
	30	[-5.12,5.12]	0
	30	[-32,32]	0
	30	[-600,600]	0
	30	[-50,50]	0

	30	[-50,50]	0

جدول 3 . توابع آزمون چندهدفه با ابعاد ثابت

Function	D	Range	fmin
	2	[-65,65]	0.998
	4	[-5,5]	0.00030
	2	[-5,5]	-1.0316
	2	[-5,5]	0.398
	2	[-2,2]	3
	3	[1,3]	-3.86
	6	[0,1]	-3.32
	4	[0,10]	-10.1532
	4	[0,10]	-10.4028
	4	[0,10]	-10.5363

جدول 4. توابع آزمون composite

Function

Range

fmin

[-5,5]

f1, f2= Ackley’s Function, f3, f4= Rastrigin’s Function, f5, f6= Weierstrass Function,

f7, f8= Griewank’s Function, f9, f10= Sphere Function

[-5,5]

f1, f2= Rastrigin’s Function, f3, f4= Weierstrass Function, f5, f6= Griewank’s Function,

f7, f8= Ackley’s Function, f9, f10= Sphere Function

[-5,5]

f1, f2= Rastrigin’s Function, f3, f4= Weierstrass Function,

f5, f6= Griewank’s Function,f7, f8= Ackley’s Function, f9, f10= Sphere Function

[-5,5]

شکل 2: نمونه‌هایی از شکل‌های دو بعدی توابع بنچمارک (a) توابع تک هدفه، (b) توابع چندهدفه، (c) توابع چندهدفه با ابعاد ثابت

مقادیر در نظر گرفته شده برای هر یک از پارامترهای مساله در جدول 5 آورده شده است. پارامتر سیگما اولیه و نهایی برای روش IWOGSA برای هریک از توابع مورد استفاده متفاوت بوده و به صورت دستی بهترین مقادیر برای آن‌ها به دست آمده است. پارامترهای مربوط به سایر الگوریتم‌ها مطابق با مقاله اصلی آن‌ها [13, 23, 31, 35, 37-41] در نظر گرفته شده است. برای بررسی روش پیشنهادی برنامه همانند الگوریتم‌های ارایه شده در مقاله‌های [13, 31, 35] 30 بار اجرا شده و مقادیر میانگین و انحراف معیار محاسبه و برای مقایسه با روش‌های موجود مطرح می‌گردد. برای بررسی نتایج روش پیشنهادی، این روش با روش‌های بهینه‌سازی ازدحام ذرات (PSO) [37]، الگوریتم علف‌های هرز (IWO) [23]، بهینه‌سازی تعادل (EO) [13]، الگوریتم ازدحام سالپ (SSA) [42] و الگوریتم وال (WOA) [35]به عنوان روش‌های مبتنی بر SI، الگوریتم جستجوی گرانشی (GSA) [31] به عنوان روش‌های مبتنی بر فیزیک، روش‌ برنامه‌نویسی تکاملی سریع (FEP) [38]و الگوریتم ژنتیک (GA) [39]به عنوان الگوریتم‌های تکاملی و دو روش SHADE [40]و LSHADE-SPACMA [41]به عنوان بهینه‌سازهایی با عملکرد بالا و برندگان رقابت‌های CEC انتخاب شده‌اند. برای مقایسه منصفانه تعداد جمعیت اولیه و تعداد تکرارها در همه روش‌ها با هم برابر بوده و همانند مقاله [13]به ترتیب برابر با 30 و 500 در نظر گرفته شده‌اند.

جدول 5 :پارامترهای مربوط به الگوریتم پیشنهادی و الگوریتم‌های مورد مقایسه با توجه به مقاله اصلی آن‌ها

Algorithm	Parameters
IWOGSA	are constants with values equal ,
IWO [23]	,, Exponent = 2, initial = 1, final = 0.001
EO [13]
WOA [35]
PSO [13]
GA [39]
GSA [31]
SSA [42]
LSHADE [40]
LSHADE-SPACMA [41]

11- نتایج ارزیابی

توابع (F1-F7) از دسته توابع تک هدفه، توابع ریاضی دارای یک راه‌حل واحد برای ارزیابی توانایی اکتشاف روش‌های بهینه‌سازی طراحی شده‌اند. نتایج ارزیابی روش پیشنهادی با این توابع نیز در جدول 6 آورده شده است. مطابق نتایج به دست آمده روش IWOGSA در تمامی این توابع نسبت به الگوریتم IWO عملکرد بهتری را داشته است و در مقایسه با GSA جز در توابع F1، F4 و F6 در بقیه توابع نتایج بهتری را کسب کرده است.

بر خلاف توابع تک هدفه، توابع چندهدفه (F8-F23) شامل بهینه‌های محلی بسیاری است که تعداد آن‌ها بطور نمایی با اندازه مسئله افزایش می‌یابد (تعداد متغیرهای طراحی). بنابراین، برای ارزیابی توانایی اکتشافی یک الگوریتم بهینه‌سازی، این نوع توابع می‌تواند بسیار مفید باشد. مطابق نتایج به دست آمده و مطرح شده در قسمت دوم و سوم جدول 6 روش IWOGSA توانسته است در توابع F18، F19، F22 و F23 نسبت به بقیه روش‌ها به نتیجه برابر یا بهتر دست یابد و در توابع F10، F15 و F20 با اختلافی کم به عنوان دومین بهترین روش در مقایسه با سایر روش‌ها می‌باشد. در تابع F13 و F21 نیز روش IWOGSA به عنوان سومین بهترین در میان 11 روش مطرح شده می‌باشد. در این دسته از توابع نیز الگوریتم IWOGSA نسبت به الگوریتم IWO در تمامی توابع و نسبت به الگوریتم GSA در تمامی توابع به جز F20 بهبود قابل توجهی را داشته است.

بهینه سازی توابع ریاضی کامپوزیت (F24-F29) یک کار بسیار چالش برانگیز است زیرا تنها با ایجاد تعادل مناسب بین اکتشاف و بهره برداری می‌توان از دام بهینه محلی رها شد. نتایج ارزیابی روش پیشنهادی با این دسته از توابع در مقایسه با روش‌های موجود در قسمت چهارم در جدول 6 آورده شده است. الگوریتم IWOGSA در تابع F24 در مقایسه با سایر روش‌ها به رتبه اول، در تابع F26 و F28 به رتبه دوم و در تابع F25 و F29 به رتبه سوم دست یافته است. در حالت کلی می‌توان گفت که روش پیشنهادی توانسته است در این دسته از توابع با پیچیدگی زیاد در میان ۱۱ روش مطرح عملکرد مناسبی را از خود نشان دهد.

12- مقایسه روش‌ها

برای مقایسه روش پیشنهادی با روش‌های موجود مطرح از روش رتبه‌بندی فریدمن استفاده شده است. آزمون فریدمن یک آزمون ناپارامتری، معادل آنالیز واریانس با اندازه‌های تکراری (درون گروهی است) که از آن برای مقایسه میانگین رتبه‌ها در بین k متغیر (گروه) استفاده می‌شود. مطابق رتبه‌بندی انجام شده با روش فریدمن روش پیشنهادی در مقایسه با روش‌های موجود مطرح شده دارای بالاترین رتبه با درنظر گرفتن 29 تابع آزمون مختلف بوده است. رتبه محاسبه شده برای هر روش در سطر آخر جدول 6 آورده شده است. مطابق رتبه محاسبه شده می‌توان میزان برتری روش IWOGSA را نسبت به سایر روش‌ها با رابطه 13 به دست آورد.

(13)

که در آن رتبه IWOGSA و رتبه مربوط به هر کدام از روش‌های دیگری برای محاسبه میزان برتری روش IWOGSA نسبت به آن روش خواهد بود.

مطابق محاسبات انجام شده برای 29 تابع ریاضی استاندارد IWOGSA قادر به پیشی گرفتن از IWO، GSA، EO، WOA، SSA، PSO، GA، FEP، SHADE و LSHADE-SPACMA به ترتیب برابر با 54٪، 40٪، 12٪، 30٪، 43٪، 42٪، 51٪، 44٪، 17٪،و 25٪ بوده است.







			جدول 6 . نتایج ارزیابی روش پیشنهادی در مقایسه با روش‌های موجود

	Function		IWOGSA	IWO	GSA	EO	WOA	SSA	PSO	GA	FEP	SHADE	LSHADESPACMA
unimodal	1F	Avg	1.07E-15	4.59802	2.53E-16	3.32E-40	1.41E-30	1.58E-07	0.000136	0.55492	0.00057	1.42E-09	0.2237
		Std	1.52E-15	15.78157	9.67E-17	6.78E-40	4.91E-30	1.71E-07	0.000202	1.2301	0.00013	3.09E-09	0.148
	2 F	Avg	1.78E-06	0.048897	0.055655	7.12E-23	1.06E-21	2.66293	0.042144	0.00566	0.0081	0.0087	21.1133
		Std	8.89E-06	0.012188	0.194074	6.36E-23	2.39E-21	1.66802	0.045421	0.01443	0.00077	0.0213	9.5781
	3 F	Avg	20.74358	3898.38	896.5347	8.06E-09	5.39E-07	1709.94	70.12562	846.344	0.016	15.4352	88.7746
		Std	6.172816	1932.498	318.9559	1.6E-08	2.93E-06	11242.3	22.11924	161.499	0.014	9.9489	47.23
	4 F	Avg	17.31664	29.08303	7.35487	5.39E-10	0.072581	11.6741	1.086481	4.55538	0.3	0.9796	2.117
		Std	5.399777	4.011357	1.741452	1.38E-09	0.39747	4.1792	0.317039	0.59153	0.5	0.7995	0.4928
	5 F	Avg	45.71647	129.5344	67.54309	25.32331	27.86558	296.125	96.71832	268.248	5.06	24.4743	28.8255
		Std	29.98074	272.4342	62.22534	0.169578	0.763626	508.863	60.11559	337.693	5.87	11.208	0.8242
	6 F	Avg	1.163636	86.56667	2.5E-16	8.29E-06	3.116266	1.8E-07	0.000102	0.5625	0	5.31E-10	0.2489
		Std	2.016264	209.8963	1.74E-16	5.02E-06	0.532429	3E-07	8.28E-05	1.71977	0	6.35E-10	0.1131
	7 F	Avg	0.011438	0.031599	0.089441	0.001171	0.001425	0.1757	0.122854	0.04293	0.1415	0.0235	0.0047
		Std	0.005894	0.008107	0.04339	0.000654	0.001149	0.0629	0.044957	0.00594	0.3522	0.0088	0.0019
multimodal	8 F	Avg	-7325.3	-6809.7	-2821.07	-9016.34	-508.76	-7455.8	-4841.29	-10546.1	-12554.5	-11713.1	-3154.4
		Std	656.5178	676.7989	493.0375	595.1113	695.7968	772.811	1152.814	353.158	52.6	230.49	317.921
	9 F	Avg	18.80472	56.19846	25.96841	0	0	58.3708	46.70423	30.8229	0.046	8.5332	67.542
		Std	4.24021	13.58114	7.470068	0	0	20.016	11.62938	7.57295	0.012	2.1959	10.016
	10 F	Avg	2.15E-08	6.318483	0.062087	8.34E-14	7.4043	2.6796	0.276015	1.63551	0.018	0.3957	0.0393
		Std	2.01E-08	9.081544	0.23628	2.53E-14	9.897572	0.8275	0.50901	0.46224	0.0021	0.5868	0.0151
	11 F	Avg	0.042914	463.7306	27.70154	0	0.000289	0.016	0.009215	0.56112	0.016	0.0048	0.8948
		Std	0.017549	61.30627	5.040343	0	0.001586	0.0112	0.007724	0.26942	0.022	0.0077	0.1078
	12 F	Avg	0.010367	6.392168	1.799617	7.97E-07	0.339676	6.9915	0.006917	0.03088	9.2E-06	0.0346	0.000818
		Std	0.031632	1.998418	0.95114	7.69E-07	0.214864	4.4175	0.026301	0.04092	3.6E-06	0.0875	0.001
	13 F	Avg	0.000732	0.000757	8.899084	0.029295	1.889015	15.8757	0.006675	0.36222	0.00016	0.000732	0.0102
		Std	0.002788	0.002789	7.126241	0.035271	0.266088	16.1462	0.008907	0.30975	0.000073	0.0028	0.0103
Multimodal (fixed-dimension)	14 F	Avg	1.097275	10.37789	5.859838	0.998004	2.111973	1.1965	3.627168	0.998004	1.22	0.998004	1.9416
		Std	0.39953	7.023539	3.831299	1.54E-16	2.498594	0.5467	2.560828	4.23E-12	0.56	5.83E-17	2.9633
	15 F	Avg	0.000307	0.002805	0.003673	0.002398	0.000572	0.000886	0.000577	0.005206	0.0005	0.002374	0.0003
		Std	1.83E-19	0.005959	0.001647	0.006097	0.000324	0.000257	0.000222	0.007028	0.00032	0.0061	1.93E-19
	16 F	Avg	-1.03163	-1.03163	-1.03163	-1.03162	-1.03163	-1.03163	-1.03163	-1.03162	-1.03	-1.03162	-1.03162
		Std	5.98E-16	7.68E-09	4.88E-16	6.04E-16	4.2E-07	6.13E-14	6.25E-16	1.34E-06	4.9E-07	6.51E-16	1E-15
	17 F	Avg	0.397887	0.397887	0.397887	0.397887	0.397914	0.397887	0.397887	0.39789	0.398	0.397887	0.397887
		Std	0	3.31E-09	0	0	0.000027	3.41E-14	0	1.08E-05	1.5E-07	3.24E-16	0
	18 F	Avg	3	3	3	3	3	3	3	3.000002	3.02	3	3
		Std	1.67E-15	4.83E-07	4.17E-15	1.56E-15	4.22E-15	2.2E-13	1.33E-15	4.06E-06	0.11	1.87E-15	1.25E-15
	19 F	Avg	-3.86278	-3.86278	-3.86278	-3.86278	-3.85616	-3.86278	-3.86278	-3.86278	-3.86	-3.86278	-3.86278
		Std	2.64E-15	1.54E-07	2.29E-15	2.59E-15	0.002706	1.47E-10	2.58E-15	1.63E-07	0.000014	2.69E-15	2.7E-15
	F20	Avg	-3.29821	-3.20309	-3.31778	-3.2687	-2.98105	-3.2304	-3.26634	-3.27443	-3.27	-3.27047	-3.28234
		Std	0.048376	1.31E-05	0.023081	0.05701	0.376653	0.0616	0.060516	0.05924	0.059	0.0599	0.057
	F21	Avg	-9.4722	-7.14234	-5.95512	-8.55481	-7.04918	-9.6334	-6.8651	-5.72536	-5.52	-9.2343	-9.4735
		Std	1.744148	3.378092	3.737079	2.76377	3.629551	1.8104	3.019644	3.32622	1.59	2.4153	1.7626
	F22	Avg	-10.4029	-9.36501	-9.68447	-9.3353	-8.18178	-9.0295	-8.45653	-6.94349	-5.53	-10.1479	-10.2258
		Std	4.66E-16	2.408425	2.014088	2.43834	3.829202	2.3911	3.087094	3.56118	2.12	1.3969	0.9704
	F23	Avg	-10.5364	-7.38001	-10.5364	-9.63655	-9.34238	-9.0333	-9.95291	-7.0208	-6.57	-10.2809	-10.5364
		Std	1.75E-15	3.739253	2.6E-15	2.38811	2.414737	2.9645	1.782786	3.85233	3.14	1.3995	1.77E-15
Composite Function	F24 (CF1)	Avg	2.21E-17	80.00144	6.63E-17	66.666	0.568846	43.333	100	86.671	100	63.333	3.3333
		Std	3.73E-18	130.3835	2.78E-17	95.893	0.505946	67.891	81.65	97.324	188.56	80.872	18.254
	F25 (CF2)	Avg	32.24289	180.4794	200.6202	89.837	75.30874	31.133	155.91	142.72	161.99	40.508	0
		Std	48.22798	44.36343	67.72087	56.366	43.07855	52.149	13.176	119.58	151	61.462	0
	F26 (CF3)	Avg	65.75479	153.6925	180	161.73	55.65147	235.11	172.03	214.67	214.06	139.48	104.29
		Std	63.81726	81.23294	91.89366	33.227	21.87944	80.839	32.769	73.47	74.181	33.366	14.266
	F27 (CF4)	Avg	239.6882	615.4329	170	356.44	53.83778	232.44	314.3	447.01	616.4	316.62	278.63
		Std	32.31643	190.3411	82.32726	115.66	21.621	43.643	20.066	112.34	671.92	96.752	7.067
	F28 (CF5)	Avg	5.457155	28.50666	200	52.309	77.8064	27.538	83.45	91.831	358.3	39.515	2.02E-17
		Std	6.530605	47.16447	47.14045	95.565	52.02346	41.598	101.11	73.898	168.26	51.233	7.69E-17
	F29 (CF6)	Avg	490.5263	900.0019	142.0906	768.48	57.88445	628.69	861.42	811.21	900.26	684.51	540.23
		Std	31.48133	0.000344	88.87141	192.94	34.44601	184.48	125.81	173.11	0.0832	201.22	122.75
Friedman mean rank			3.827586	8.275862	6.362069	4.327586	5.482759	6.706897	6.603448	7.810345	6.862069	4.62069	5.12069
Rank			1	11	6	2	5	8	7	10	9	3	4

13- تجزیه و تحلیل همگرایی

نمودار همگرایی روش پیشنهادی در مقایسه با روش‌های علف‌های هرز (IWO) و الگوریتم جستجوی گرانشی در برخی از توابع بنچمارک در شکل 3 آورده شده است. با توجه به نمودارهای نمونه‌ی نشان داده شده روش ترکیبی IWOGSA نسبت به دو روش IWO و GSA در توابع تک هدفه و چندهدفه، F3، F7، F9، F11، F12، F13، F14، F21 و توابع کامپوزیت FC2، FC3 و FC5 به همگرایی سریع‌تر و بهتری رسیده است و این نشان می‌دهد که با ترکیب الگوریتم GSA با IWO، قابلیت همگرایی IWO و GSA اصلی بهبود یافته است.

$E:\1N.Farzi\Code Samples\Thesis\3 vahideh sahrghahi\PHD\thesis\optimization\IWO\compare\Results\R3_30-500\result\All.tif$

شکل 3. مقایسه همگرایی الگوریتم‌های بهینه‌سازی IWOGSA، IWO و GSAدر توابع مختلف

14- الگوریتم IWOGSA برای حل مسائل مهندسی

روش پیشنهادی برای حل سه مساله مهندسی شناخته شده‌ی طراحی مجرای فشار، طراحی پرتو جوش و مینیمم‌سازی وزن یک مورد استفاده قرار گرفته و میزان کارایی آن در حل چنین مسائلی مورد ارزیابی قرار گرفته شده است. یک روش ساده برای کنترل محدودیت به نام جریمه ایستا، در حل این مسائل اعمال می‌شود تا اگر هرگونه محدودیت در هر سطح از مرزهای تعریف شده خود نقض شود، عملکرد هدف را با مقدار زیادی جریمه می‌کنیم. ضریب جریمه باید به اندازه کافی بزرگ باشد تا بتواند عملکرد هدف را در محدودیتهای برابری / نابرابری مجازات کند.

روابط مربوط به هر یک از این مسائل و نتایج حاصل از روش IWOGSA در حل آن‌ها در ادامه آورده شده است. قابل ذکر است که تمام ارزیابی‌ها به تعداد دفعات 30 بار با درنظر گرفتن ۲۰ جمعیت اولیه و ۵۰۰ تکرار انجام شده و مقدار میانگین نتایج و بهترین نتیجه، بدترین نتیجه و مقدار انحراف معیار به دست‌ آمده در مقایسه با روش‌های موجود در جداول مربوطه آورده شده است.

15- طراحی یک مجرای فشار (Pressure Vessle)

هدف از این مسئله مینیمم سازی هزینه کلی مواد، شکل دهی و جوشکاری یک مجرای استوانه‌ای نشان داده شده در شکل 4 می‌باشد. در اینجا چهار متعیر طراحی وجود دارد: (، ضخامت پوسته )، (، ضخامت دماغه)، (، شعاع داخلی) و (، طول بخش استوانه ای مجرا). و و مضرب‌های صحیحی از 0.0625 اینچ که ضخامت‌های در دسترس صفحات استیل پیچیده شده می‌باشند، خواهند بود. و پیوسته هستند. مسئله می‌تواند با رابطه 14 تعریف شود:

مینیمم سازی

به منظور

(14)

از محدوده‌های زیر برای متغیر‌ها استفاده می‌شود:

$img0$

شکل 4. مجرای فشار: (a) شماتیک، (b) نقشه حرارتی تنش (c) نقشه حرارتی جابجایی [15]

الگوریتم‌های تکاملی زیادی از جمله GSA، MSCA، PRO، SMO، WOA، GWO، PSO، GA، برای حل این مساله به کار رفته‌اند. الگوریتم GSA با مینیمم هزینه 8538.836، الگوریتم MSCA با مینیمم هزینه 5935.716، الگوریتم PRO با مینیمم هزینه 6050.713، الگوریتم WOA با مینیمم هزینه 6059.741 این مساله را حل کرده‌اند. در مقابل الگوریتم IWOGSA با مینیمم هزینه 5887.88750525968 توانسته است این مساله را حل کرده و نه تنها نسبت به آن روش‌ها بلکه توانسته است نسبت به همه روش‌هایی دیگری که در جدول 7 آورده شده است پیشی بگیرد. مقادیر میانگین، بیشترین، کمترین و انحراف معیار نتایج ارزیابی به همراه سایر روش‌هایی که این مقادیر برای آن‌ها قابل دسترس بود در جدول 8 آورده شده است. مطابق این جدول نیز روش IWOGSA نسبت به همه روش‌های مورد مقایسه به نتایج بهتری رسیده است.

جدول 7 . مقایسه نتایج بهینه‌سازی IWOGSA با روش‌های بهینه‌سازی دیگر در طراحی مخزن تحت فشار

Algorithm	Optimal Value				Optimal Cost
Algorithm	Ts	Th	R	L	Optimal Cost
IWOGSA	0.778515	0.384821	40.337598	1.997498	5885.926
IWO	0.778940	0.385082	40.356598	1.995174	5887.887
GSA [35]	1.125	0.625	55.98866	84.4542	8538.836
MSCA [43]	0.779256	0.3996	40.32545	199.9213	5935.716
EO [13]	0.8125	0.4375	42.09844	176.63659	6059.7143
PRO [44]	0.7445	0.4424	38.48998	200	6050.713
SMO [45]	0.8242	0.4072	42.36585	173.7973	6021.629
WOA [35]	0.8125	0.4375	42.09827	176.6389	6059.741
GWO [15]	0.8125	0.4345	42.08918	176.7587	6051.564
PSO [46]	0.8125	0.4375	42.09127	176.7465	6061.078
GA [39]	0.8125	0.4345	40.3239	200	6288.745

جدول 8 . مقایسه نتایج آماری ICO با روش‌های بهینه‌سازی دیگر در طراحی مخزن تحت فشار

Algorithm	Min	mean	Max	Std
IWOGSA	5885.926	7918.9905	52628.27	8451.458
IWO	5887.888	22294.318	90989.54	25337.115
GSA [35]	8538.836	8932.95	65535	683.5475
EO [13]	6059.714	6668.114	7544.493	566.24
WOA [35]	6059.741	6068.05	65535	65.6519
PSO [46]	6061.078	6531.1	65535	154.3716
CPSO [46]	6061.078	6147.133	6363.804	86.4545
HGA(1) ) [47]	6065.821	6632.376	8248.003	515
HGA(2) [47]	6832.584	7187.314	8012.615	276
T-Cell [48]	6390.554	6737.065	7694.066	357
DTS-GA [49]	6059.946	6177.253	6469.322	130.92
HAIS-GA [50]	6061.123	6743.085	7368.06	457.99
BFOA [51]	6060.46	6074.625	65535	156
ES [52]	6059.746	6850	7332.87	426

16- طراحی پرتوجوش (Welded Beam)

هدف مینیمم سازی هزینه یک پرتو جوش به منظور قیدهایی بر روی تنش کششی، تنش خمشی در پرتو، بار مقابله بر روی میله، خمش نهایی پرتو و قیدهای جانبی می‌باشد که در شکل 5 نشان داده شده است. مسئله با رابطه 15 نمایش داده می‌شود:

مینیمم سازی

با هدف

(15)

که

محدوده‌های زیر برای متغیرها استفاده می‌شود.

شکل 5. ساختار طرح تیر جوش (a) شماتیک (b) نقشه حرارتی تنش (c) نقشه حرارتی جابجایی[15]

الگوریتم‌های تکاملی مختلفی برای حل این مساله به کار گرفته شده‌اند. مینیمم مقدار به دست آمده به همراه مقادیر محاسبه شده برای متغیرها در مقایسه با روش‌های موجود در جدول 9 آورده شده است. همچنین مقادیر میانگین، بیشترین، کمترین و انحراف معیار نتایج 30 بار اجرا انجام شده در مقایسه با روش‌های موجود در جدول 10آورده شده است.همانگونه که در جداول مشخص است روش IWOGSA عملکرد مناسبی را برای حل این مساله نداشته است و در مقابل الگوریتم MSCA با مقدار بهینه 1.6979 از بقیه روش‌ها در حل این مساله پیشی گرفته است.

جدول 9 . مقایسه نتایج بهینه‌سازی ICO با روش‌های بهینه‌سازی دیگر در مساله طراحی تیر جوش

Algorithm	Optimal Value				Optimal Cost
Algorithm	H	L	t	B	Optimal Cost
IWOGSA	0.20573296	7.092414	9.0366239	0.2057296	2.218151
IWO	0.206507	7.078934	9.018934	0.20663	2.223365
GSA [35]	0.182129	3.856979	10	0.202376	1.879952
MSCA [43]	0.20545	3.2524	9.0576	0.20568	1.6979
WOA [35]	0.205396	3.484293	9.037426	0.206276	1.730499
EO [13]	0.2057	3.4705	9.03664	0.2057	1.7249
GWO [15]	0.205676	3.478377	9.03681	0.205778	1.72624
GA [39]	65535	65535	65535	65535	1.8245
HS [53]	0.2442	6.2231	8.2915	0.2433	2.3807
Random [54]	0.4575	4.7313	5.0853	0.66	4.1185
Simple [54]	0.2792	5.6256	7.7512	0.2796	2.5307
David [54]	0.2434	6.2552	8.2915	0.2444	2.3841
Approx [54]	0.2444	6.2189	8.2915	0.2444	2.3815

جدول 10 . مقایسه نتایج آماری IWOGSA با روش‌های بهینه‌سازی دیگر در مساله طراحی تیر جوش

Algorithm	Min	mean	Max	Std
IWOGSA	2.218151	2.258579	2.544425	0.072630
GSA [35]	1.879952	3.5761	65535	0.2874
EO [13]	1.724853	1.726482	1.736725	0.003257
WOA [35]	1.730499	1.732	65535	0.0226
PSO [46]	65535	1.7422	65535	1.01275
SBM [55]	2.4426	2.5215	2.6315	65535
BFOA [51]	2.3868	2.404	65535	0.016
SCA [56]	2.3854	3.2551	6.3996	0.959
EA [57]	2.3816	65535	2.38297	0.00034
T-Cell [48]	2.3811	2.4398	2.7104	0.09314
FSA [58]	2.3811	2.4041	2.4889	65535
IPSO [59]	2.381	2.3819	65535	0.00523
HSA-GA [60]	2.25	2.26	2.28	0.0078
CDE [61]	1.7335	1.768158	1.824105	0.022194
CPSO [46]	1.728	1.748831	1.782143	0.012926

17- مینیمم سازی وزن یک

این مسئله شامل مینیمم سازی وزن یک¹ به منظور قیدهایی بر روی مینیمم انحراف، تنش کشش، فرکانس غلیان و محدودیت بر روی ضخامت خارجی و بر روی متغیرهای طراحی می‌باشد که در شکل 6 نشان داده شده است. متغیرهای طراحی، متوسط قطر هسته D، قطر سیم d و تعداد هسته‌های فعال N می‌باشد. مسئله می‌تواند با رابطه 16 تشریح گردد:

مینیمم سازی

به منظور

(16)

و از محدوده‌های زیر برای متغیر‌ها استفاده می‌شود:

شکل 6. مینیمم سازی وزن یک: (a) شماتیک، (b) نقشه حرارتی تنش (c) نقشه حرارتی جابجایی [15]

این مسئله مدل سازی ریاضی را می‌توان با تکنیک‌های ریاضی مانند تصحیح محدودیت در یک تابع هزینه و و توابع جریمه [62] و یا با الگوریتم‌های فرا اکتشافی حل کرد. Chen و همکاران در مقاله [43] از روش MSCA که بهبود یافته روش SCA‌ می‌باشد برای حل این مساله استفاده کرده و به وزن بهینه 0.0126670 رسیدند. Coello و همکاران [39] از GA برای رفع این مشکل استفاده کرده و وزن بهینه 0.0127048 بدست آورده‌اند.

الگوریتم‌های WOA، EO، GWO، PSO، GA، RO، HIS و DE برای حل این کار استفاده شدند. همانطور که در جدول 11 دیده می‌شود، IWOGSA با داشتن وزن مطلوب ، در کنار الگوریتم EO و GWO بهترین الگوریتم در بین الگوریتم‌های متااکتشافی استاندارد و تکنیک‌های ریاضی مورد استفاده در این مقاله است و این امر نشان می‌دهد که IWOGSA می‌تواند به عنوان ابزاری مفید برای این مساله باشد. مقدار مینیمم، ماکزیمم، میانگین و انحراف معیار محاسبه شده برای این الگوریتم در مقایسه با روش‌هایی که مقادیر مذکور برای آن‌ها قابل دسترس بود برای مقایسه در جدول 12 آورده شده است. قابل ذکر است که میانگین و انحراف معیار به دست آمده با روش IWOGSA از میانگین و انحراف معیار به دست آمده با روش EO بهتر است.

جدول 11 . مقایسه نتایج بهینه‌سازی IWOGSA با روش‌های بهینه‌سازی دیگر در مساله مینیمم سازی وزن یک

Algorithm	Optimal Value			Optimal Cost
Algorithm	D	N	D	Optimal Cost
IWOGSA	0. 0515	0. 3529	11. 5149	0.012666
IWO	0.0523	0. 3708	10. 5403	0.012711
MSCA [43]	0.050276	0.32368	13.52541	0.012702
WOA [35]	0.051207	0.345215	12.00403	0.012676
EO [13]	0.05162	0.355054	11.38797	0.012666
GWO [15]	0.05169	0.356737	11.28885	0.012666
GSA [35]	0.051668	0.356199	11.3207	0.012667
PSO [46]	0.051728	0.357644	11.24454	0.012674
GA [39]	0.05148	0.351661	11.6322	0.012704
RO [22]	0.05137	0.349096	11.76279	0.012679
DE [61]	0.051609	0.354714	11.41083	0.012670

جدول 12 . مقایسه نتایج آماری IWOGSA با روش‌های بهینه‌سازی دیگر در مساله مینیمم سازی وزن یک

Algorithm	Min	Mean	Max	Std
IWOGSA	0.012666	0.012752	0.013031	0.000084
IWO	0.012711	0.012861	0.013807	0.000263
GSA [35]	0.012702	0.0136	65535	0.002630
WOA [35]	0.012676	0.0127	65535	0.0003
PSO [46]	0.012675	139	65535	0.0033
SI [63]	0.01306	0.015526	0.018992	65535
GA(1) [39]	0.012704	0.012769	0.012822	3.93E-05
T-Cell [48]	0.012665	0.013309	0.012732	0.000094
GA(2) [64]	0.012681	0.012742	0.012973	0.000095
SCA [56]	0.012669	0.012922	0.016717	0.000592
EO [13]	0.012666	0. 01302	0.013997	0.000391
CDE [61]	0.01267	0.012703	0.01279	2.07E-05

18- الگوریتم IWOGSA برای مساله گسسته افزایش نفوذ

بیشینه سازی نفوذ یک مساله بهینه‌سازی است که هدف از آن انتخاب گره‌های اولیه با بیشترین میزان نفوذ است. این مساله توسط الگوریتم‌های تکاملی مختلفی [65-68] توسط محققان مورد بررسی قرار گرفته شده است. الگوریتم تکاملی IWOGSA برای حل مسائل بهینه‌سازی پیوسته در قسمت‌های قبل مطرح گردید در این بخش مدل گسسته IWOGSA برای به کارگیری این الگوریتم برای مسأله‌‌ی افزایش نفوذ به نام DIWOGSA بیان می‌گردد.

19- الگوریتم پیشنهادی DIWOGSA

روش پیشنهادی از یک استراتژی مبتنی بر توپولوژی شبکه برای بیشینه‌سازی نفوذ در شبکه‌های پیچیده استفاده می‌کند. در روش پیشنهادی یک عملگر هوشمند جدید مبتنی بر درجه گره‌ها برای مقداردهی راه حل‌های اولیه به کار گرفته شده است. همچنین از یک عملگر جستجوی محلی برای افزایش سرعت همگرایی این مساله استفاده شده است. در ادامه مراحل روش پیشنهادی برای مساله افزایش نفوذ با جزئیات کامل بیان می‌گردد.

20- نمایش مساله

هر یک از راه حل‌ها از جمعیت از یک بردار k عضوی تشکیل می‌یابد که هر المان از این ارایه بیانگر گرهی از گراف G است. برای مثال اگر k=5 و بردار باشد. این به این معنی است که 5 گره و C به عنوان گره‌های اولیه ² از گراف G انتخاب شده و نفوذ در شبکه با این گره‌ها صورت می‌گیرد.

21- تابع هدف

محاسبه میزان نفوذ و کشف مجموعه‌ای از دانه‌ها با بهترین نفوذ در یک شبکه دو مساله در زمینه بیشینه‌سازی نفوذ است که به ترتیب به عنوان مسائل P-hard و NP-hard شناخته شده‌اند. به منظور محاسبه میزان گسترش نفوذ، شبیه‌سازی سنتی مونت کارلو نیاز به حداقل ده‌ها هزار بار اجرا دارد تا یک برآورد دقیق بدست آورد، که بسیار وقت‌گیر است. برای مقابله با این مشکل، جیانگ و همکاران یک تابع EDV سریع بیان شده در رابطه 17 را برای جایگزینی شبیه‌سازی‌های انتشار در مدل IC ارائه داده است [69].

(17)

که در آن نشان دهنده همسایگان مجموعه‌ی Sاست. پارامتر احتمال فعال ثابت گره i است که برابر با p در مدل IC است. در روش پیشنهادی از این مدل به عنوان تابع هدف برای تخمین میزان شایستگی هر راه‌حل استفاده شده است.

22- مقداردهی اولیه

در روش پیشنهادی جمعیت اولیه از N راه‌حل تشکیل می‌شود. برای ایجاد هر راه حل k گره با بیشترین درجه (به صورت مرتب شده بر مبنای درجه شان ) به عنوان گره‌های اولیه پایه IN در نظر گرفته می‌شود. سپس برای ایجاد تنوع در میان اعضا گره‌هایی انتخاب و به صورت تصادفی با گره‌های دیگری از شبکه جایگزین می‌گردند.

23- تکثیر

در DIWOGSA نیز همانند حالت پیوسته تمامی راه‌حل‌ها در جمعیت فعلی به عنوان والد در نظر گرفته شده و تکثیر می‌شوند. در روش گسسته تعداد تکثیر هر والد همانند روش پیوسته برمبنای شایستگی هر والد محاسبه می‌شود ولی نحوه تکثیر متفاوت است به طوریکه در روش گسسته مقادیر، ، و همانند روش پیوسته محاسبه می‌شود سپس مقدار فرزندان با رابطه 18 ایجاد خواهند شد.

(18)

که در آن r یک عدد تصادفی در بازه 0 تا 1، و با تابع یک گره به صورت تصادفی از میان گره‌های شبکه که در راه حل نباشد انتخاب شده و با جایگزین می‌شود.

24- جستجوی محلی

بعد از انتخاب بهترین گره‌ها و به کارگیری جستجوی محلی برای افزایش شایستگی بهترین گره صورت می‌گیرد. در این مرحله تک تک گره‌های موجود در راه‌حل مورد بررسی قرار گرفته و با اولین همسایه‌ای که منجر به افزایش نفوذ در راه‌حل گردد جایگزین خواهد شد. شبه‌کد جستجوی محلی در الگوریتم 2 آورده شده است.

Algorithm 2 local search

1: Input: Particle Xa.

2: ;

3: for each element do

4: ;

6: while (1)

8: if EDV(Xb)>EDV(Xa) then

9: Xa Xb;

10: else

11: Flag TRUE;

12: end if

13: if Flag is TRUE

14: Break;

15: end if

16: end while

14: ;

15: end for

16: Output: Xb.

25- ارزیابی الگوریتم DIWOGSA در حل مساله بیشینه‌سازی نفوذ

مساله بیشینه‌سازی نفوذ با در نظر گرفتن گراف G(V,E) می‌توان به صورت ریاضی با رابطه 19 تعریف کرد [70]. اگر n و u به ترتیب تعداد المآن‌های V و E باشد. K عدد صحیح مثبت K<n است. هدف از مساله بیشینه‌سازی نفوذ، پیدا کردن مجموعه‌ای از K گره با عنوان S، به عنوان گره‌های اولیه به صورتی‌که باشد.

(19)

در این بخش، ما الگوریتم پیشنهادی خود را بر روی شبکه‌های دنیای واقعی (بیان شده در جدول 13) پیاده‌سازی کرده و نتایج به دست آمده با روش‌های موجود مقایسه خواهد شد. ارزیابی‌ها بر روی پلتفرم نرم افزاری MATLAB R2019b تحت سیستم‌‌ عامل ویندوز 10 با یک پردازنده Intel (R) Core (TM) i7 CPU @ 3.15 انجام شده است.

ما برای ارزیابی روش پیشنهادی خود و مقایسه آن با روش‌های موجود و اخیر شش شبکه مختلف واقعی با سایزهای متفاوتی را در نظر گرفته‌ایم. مشخصات مربوط به شبکه‌های مورد ارزیابی در جدول 13 آورده شده است. که در آن |V| تعداد گره‌ها، |E| تعداد لینک‌ها، <k> میانگین درجه نودها، C میانگین ضریب خوشه‌بندی و AC³ ضریب تجزیه است. شبکه Netscience [71]،Email [72]، شبکه Ca-GrQc [73] و شبکه Ca-HepTh [74] شبکه‌های ارتباطاتی بین محققان در زمینه‌های مختلف است.

جدول 13 . مشخصات مربوط به شبکه‌های واقعی

Datasets	\|V\|	\|E\|	〈k〉	C	AC
Netsience⁴	379	914	4.823	0.798	-0.082
Email⁵	1133	5451	9.622	0.254	0.078
Ca-GRQC⁶	5242	14496	5.53	0.5296	0.659
Ca-HepTH⁷	9877	25998	5.264	0.600	0.268

روش‌هایی که برای مقایسه با روش پیشنهادی در نظر گرفته شده‌اند شامل الگوریتم CELF، DPSO، Single Discount، Degree، Betweenness Centrality و PageRank است. در ادامه توضیح مختصری از هر کدام بیان شده است.

· CELF: الگوریتم “Cost-Efficient Lazy Forward” یک الگوریتم حریصانه بهبود یافته با استراتژی بهینه‌سازی “Lazy forward” است [75]. این الگوریتم 700 برابر سریعتر از الگوریتم greedy است.

· DPSO: الگوریتم DPSO یک الگوریتم بیشینه‌سازی نفوذ مبتنی بر بهینه‌سازی ازدحام ذرات گسسته است [76]. در این روش از جستجوی محلی برای افزایش نفوذ استفاده شده است.

· Single Discount: در این روش در هر تکرار از الگوریتم گره‌ای با بیشترین درجه انتخاب می‌شود سپس درجه همسایگان آن گره یک واحد کاهش پیدا می‌کند [77].

· Degree: در این روش K گره با بیشترین درجه به عنوان گره‌های اولیه انتخاب می‌شوند.

· Betweenness Centrality: معیار Betweenness به جای توجه به خود گره‌ها در شبکه‌ها، ساختار شبکه را برای تشخیص گره‌های با نفوذ در نظر می‌گیرد. در این روش K گره با بیشترین Betweenness Centrality به عنوان گره‌های اولیه انتخاب می‌شوند.

· PageRank: برای بیشینه‌سازی نفوذ با روش PageRank [78]، K گره با بالاترین PageRank به عنوان گره‌های اولیه در نظر گرفته خواهد شد.

در تمامی ارزیابی‌های انجام گرفته برای محاسبه میزان نفوذ روش انتشار مدل آبشاری مستقل (IC⁸) با 10000 مونت کارلو در نظر گرفته شده است. مدل آبشاری مستقل یکی از مدلهای انتشار اطلاعات احتمالاتی است که توسط کمپ و همکاران در مقاله [79] برای مساله بیشینه‌سازی نفوذ استفاده شده است. در این مدل، یک گره می‌تواند در حالت فعال یا در حالت غیر فعال باشد. در ابتدا (به عنوان مثال در t = 0 ) همه گره‌ها به جز دانه‌ها غیرفعال هستند. هر گره فعال (مثلاً Ui) در هر دور t فرصتی برای فعال کردن همسایه فعلاً غیرفعال خود ( و ) با احتمال وزن لبه خود دارد. اگر موفق شود، به یک گره فعال در دور t + 1 تبدیل می‌شود. یک گره می‌تواند حالت خود را از غیر فعال به فعال تغییر دهد اما از حالت فعال به غیر فعال تبدیل نمی‌شود. این روند آبشاری تا زمانی که گره فعال دیگری در دور وجود نداشته باشد ادامه خواهد یافت.

26- مقایسه میزان نفوذ

برای محاسبه میزان نفوذ روش انتشار مدل آبشاری با 10000 مونت کارلو در نظر گرفته شده است. در الگوریتم DPSO مطابق مقاله [76] مقادیر پارامترهای C1 و C2 برابر با 2، ω برابر با 0.8، n و gmax برابر با 100 در نظر گرفته شده است. الگوریتم CELF با 10000 مونت کارلو مورد ارزیابی قرار گرفته است. در ارزیابی الگوریتم DIWOGSA مقدار پارامتر جمعیت اولیه و Imax به ترتیب برابر 20 و 250 است. Smax برای شبکه‌های Netsience، Email و NetGrQc برابر 5 و برای سایر شبکه‌ها با سایز بیشتر برابر با 20 در نظر گرفته شده است. پارامتر به ترتیب برابر با تعداد گره‌های موجود در راه‌حل و 1 است. پارامترهای به ترتیب برابر با 0.5 و 0.1 بوده و سایر پارامترها همانند روش پیوسته از جدول 5 در نظر گرفته شده است. روش‌های فرا اکتشافی DPSO و DIWOGSA به تعداد 30 بار به صورت مستقل اجرا شده و میانگین نتایج در نمودارها آورده شده است. ارزیابی‌ها با در نظر گرفتن تعداد گره‌های اولیه مختلف k={1, 5, 10,15, …, 30} صورت گرفته و نتایج ارزیابی‌ها در مقایسه با سایر روش‌ها با مقدار احتمال انتشار 0.01 و 0.05 در شکل 7 نشان داده شده است.

مطابق نتایج به دست آمده در شکل 7 الگوریتم greedy-based CELF در بیشتر شبکه‌ها از همه‌ی روش‌های مورد مقایسه نتایج بهتری را داشته است. الگوریتم DIWOGSA در بیشتر شبکه‌ها به عنوان دومین بهترین بوده است. در مقایسه الگوریتم DIWOGSA با الگوریتم DPSO، الگوریتم DIWOGSA در تمامی شبکه‌ها نسبت به الگوریتم DPSO میزان نفوذ بالاتری را دارد.

[1]

[2] Seed set

[3] Assortativity Coefficient

[4] http://networkrepository.com/ca-netscience.php

[5] https://www.cc.gatech.edu/dimacs10/archive/clustering.shtml

[6] https://snap.stanford.edu/data/ca-GrQc.html

[7] https://snap.stanford.edu/data/ca-HepTh.html

[8] Independent Cascade Model

$C:\1 personal\vahideh sahargahi\Paper 4 book\Influence Maximization\Results\SpreadSize1.tiff$ $C:\1 personal\vahideh sahargahi\Paper 4 book\Influence Maximization\Results\SpreadSize2.tiff$

شکل 7. میزان نفوذ روش پیشنهادی در مقایسه با سایر روش‌ها با در نظر گرفتن روش مدل آبشاری با احتمال انتشار 0.05

مقایسه زمان اجرا

مدت زمان اجرا روش پیشنهادی در مقایسه با سایر روش‌ها با در نظر گرفتن روش مدل آبشاری با مقدار احتمال0.01 و 0.05 به ترتیب در شکل 8 و شکل 9 نشان داده شده است. مطابق نمودار رسم شده به طور میانگین، روش PageRank کمترین زمان اجرا و الگوریتم CELF بیشترین زمان اجرا را دارد. همچنین روش پیشنهادی نسبت به الگوریتم CELF در تمامی شبکه‌ها و نسبت به DPSO در تمامی شبکه‌ها به غیر از NetScience زمان اجرای کمتری را داشته است.

$C:\1 personal\vahideh sahargahi\Paper 4 book\Influence Maximization\Results\0.01Time2.tiff$

شکل 8. مدت زمان اجرا روش پیشنهادی در مقایسه با سایر روش‌ها با در نظر گرفتن روش مدل آبشاری با مقدار احتمال 0.01

$C:\1 personal\vahideh sahargahi\Paper 4 book\Influence Maximization\Results\0.05Time2.tiff$

شکل 9. مدت زمان اجرا روش پیشنهادی در مقایسه با سایر روش‌ها با در نظر گرفتن روش مدل آبشاری با مقدار احتمال 0.05

27- تحلیل آماری

رتبه‌بندی فریدمن روش‌های مختلف تشخیص نفوذ، با در نظر گرفتن میزان نفوذ روش‌های مختلف با در نظر گرفتن k=30 با مقدار احتمال انتشار اطلاعات 0.01 و 0.05 در پایگاه داده‌های مختلف صورت گرفته است. میانگین رتبه‌های هر روش به همراه رتبه نهایی آن روش در جدول 14 نشان داده شده است. مقدار ‌P-value محاسبه شده در رتبه‌بندی فریدمن برابر با 3.26e-06 است. چون این مقدار کمتر از 0.05 می‌باشد می‌توان نتیجه گرفت که بین نتایج الگوریتم‌های مختلف تفاوت معنی داری وجود دارد. مطابق نتایج به دست آمده الگوریتم پیشنهادی DIWOGSA در کنار greedy-based CELF رتبه اول را در مقایسه با سایر روش‌های به دست آورده‌اند.

جدول 14. رتبه‌بندی الگوریتم‌های مختلف با آزمون رتبه‌بندی فریدمن

Algorithm	Average Ranking	Final Rank
CELF	6	1
DIWOGSA	6	1
DPSO	2.625	3
Page Rank	3.5	4
Single Discount	5.75	2
Degree Centrality	2.25	5
Betweenness Centrality	1.875	6

28- نتیجه‌گیری

الگوریتم IWOGSA یک روش بهینه‌سازی ترکیبی از الگوریتم علف‌های هرز و الگوریتم جستجوی گرانشی برای حل مسائل بهینه‌سازی می‌باشد. برای بررسی کارایی روش پیشنهادی این روش را برای حل 29 تابع مختلف بنچمارک در چهار دسته توابع تک هدفه، توابع چندهدفه، توابع چندهدفه با ابعاد ثابت و توابع کامپوزیت به کار گرفته‌ایم. همچنین برای بررسی کارایی روش پیشنهادی ما این روش را با الگوریتم‌های جدید و رایج در این زمینه به نام‌های الگوریتم بهینه‌سازی ازدحام ذرات (PSO)، الگوریتم علف‌های هرز (IWO)، بهینه‌سازی تعادل (EO)، الگوریتم ازدحام سالپ (SSA) و الگوریتم وال (WOA)، الگوریتم جستجوی گرانشی (GSA)، روش‌ برنامه‌نویسی تکاملی سریع (FEP) و الگوریتم ژنتیک (GA) و دو روش SHADE و LSHADE-SPACMA مقایسه کرده‌ایم. مطابق نتایج به دست آمده روش پیشنهادی در مقایسه با روش‌های موجود مطرح شده در این مقاله با روش رتبه‌بندی فریدمن به عنوان بهترین روش معرفی شده است. همچنین این روش برای حل سه مساله مهندسی شناخته شده‌ی طراحی مجرای فشار، طراحی پرتو جوش و مینیمم‌سازی وزن یک مورد استفاده قرار گرفته و میزان کارایی آن در حل چنین مسائلی مورد ارزیابی قرار گرفته شده است. در مقایسه با روش‌های موجود از میان سه مساله مطرح در زمینه مهندسی روش پیشنهادی در دو مورد از آن‌ها به بهترین نتیجه دست یافته است.

همچنین در این مقاله مدل گسسته از الگوریتم IWOGSA به نام DIWOGSA برای حل مساله بیشینه سازی نفوذ پیشنهاد شده است. روش پیشنهادی با روش‌های موجود و رایج در این زمینه مقایسه شده است. مطابق رتبه‌بندی فریدمن الگوریتم پیشنهادی DIWOGSA بعد از الگوریتم حریصانه CELF رتبه دوم را کسب کرده است. از نظر زمان اجرا الگوریتم پیشنهادی بسیار سریعتر از الگوریتم CELF است. همچنین روش پیشنهادی نسبت به DPSO نیز در بیشتر دیتاست‌ها زمان اجرای کمتری را دارد. به عنوان کارهای آتی، می‌توان روش پیشنهادی IWOGSA را برای حل مسائل باینری و چندهدفه طراحی کرد.