بهبود کارایی الگوریتم تکامل شوراهای شهر با کاهش خطی اندازه جمعیت و فضای جستجو

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

نویسندگان

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

چکیده

الگوریتم تکامل شوراهای شهر (CCE)، یک نوع الگوریتم فراابتکاری است که با توجه به ماهیت تشکیل شوراها از کوچکترین محله‌ها تا بزرگترین مناطق شهری، از فرآیند تشکیل شورای عالی یک شهر الهام گرفته شده است. در این مقاله می‌خواهیم کارایی الگوریتم CCE را با دو تغییر مهم در آن بهبود بدهیم. اولین تغییر مربوط به کاهش پیوسته‌ی اندازه‌ی جمیعت با استفاده از تکنیک کاهش خطی جمعیت (LPSR) است. در این تکنیک، اندازه‌ی جمعیت در تکرارهای اولیه‌ی الگوریتم به اندازه‌ی کافی بزرگ در نظر گرفته می‌شود تا الگوریتم بتواند مناطق وسیعی از فضای جستجو را پیمایش کند. با پیشروی الگوریتم، اندازه‌ی جمعیت به‌تدریج کاهش داده می‌شود تا سرعت همگرایی افزایش یابد. دومین تغییر به دامنه‌ی متغیرها مربوط می‌شود که به‌طور پیوسته کاهش می‌یابد تا فضای جستجو محدودتر شده و در نتیجه، امکان یافتن راه‌حل‌های بهینه افزایش پیدا کند. برای ارزیابی و مقایسه‌ی کارایی الگوریتم تکامل شوراهای شهر بهبودیافته (تحت عنوان ICCE که در این مقاله مطرح شده است) با الگوریتم‌های تکامل شوراهای شهر (CCE)، بهینه‌سازی شامپانزه، بهینه‌سازی بیوه سیاه، بهینه‌ساز سیاسی، بهینه‌ساز جفت‌گیری بارناکل‌ها، بهینه‌سازی مار و بهینه‌ساز آکیلا، آن‌ها را روی 29 تابع تست از مسابقات سال 2017 مربوط به کنگره IEEE در زمینه محاسبات تکاملی (CEC 2017) اجرا می‌کنیم. نتایج آزمون‌های میانگین رتبه‌ی فریدمن و رتبه علامت‌دار ویلکاکسون، کارایی بالای الگوریتم ICCE را نسبت به الگوریتم‌های مذکور تأیید می‌کنند.

کلیدواژه‌ها


[1] E. Pira, "City councils evolution: a socio-inspired metaheuristic optimization algorithm," Journal of Ambient Intelligence and Humanized Computing, pp. 1-50, 2022.
[2] S. Kundu and D. R. Parhi, "Navigation of underwater robot based on dynamically adaptive harmony search algorithm," Memetic Computing, vol. 8, no. 2, pp. 125-146, 2016.
[3] S. Richter and M. Westphal, "The LAMA planner: Guiding cost-based anytime planning with landmarks," Journal of Artificial Intelligence Research, vol. 39, pp. 127-177, 2010.
[4] E. Pira, "A novel approach to solve AI planning problems in graph transformations," Engineering Applications of Artificial Intelligence, vol. 92, p. 103684, 2020.
[5] E. Pira, "Using deep learning techniques for solving AI planning problems specified through graph transformations," Soft Computing, pp. 1-18, 2022.
[6] O. Ozkan, M. Ermis, and I. Bekmezci, "Reliable communication network design: The hybridisation of metaheuristics with the branch and bound method," Journal of the Operational Research Society, vol. 71, no. 5, pp. 784-799, 2020.
[7] J. W. Zhang and G. G. Wang, "Image matching using a bat algorithm with mutation," in Applied mechanics and materials, 2012, vol. 203: Trans Tech Publ, pp. 88-93.
[8] E. Pira, "Using Markov Chain Based Estimation of Distribution Algorithm for Model-Based Safety Analysis of Graph Transformation," Journal of Computer Science and Technology, vol. 36, no. 4, pp. 839-855, 2021.
[9] S. Mirjalili, S. M. Mirjalili, and A. Lewis, "Grey wolf optimizer," Advances in engineering software, vol. 69, pp. 46-61, 2014.
[10] E. Alba and B. Dorronsoro, "The exploration/exploitation tradeoff in dynamic cellular genetic algorithms," IEEE transactions on evolutionary computation, vol. 9, no. 2, pp. 126-142, 2005.
[11] S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi, "Optimization by simulated annealing," science, vol. 220, no. 4598, pp. 671-680, 1983.
[12] D. H. Wolpert and W. G. Macready, "No free lunch theorems for optimization," IEEE transactions on evolutionary computation, vol. 1, no. 1, pp. 67-82, 1997.
[13] J. L. J. Laredo, C. Fernandes, J. J. Merelo, and C. Gagné, "Improving genetic algorithms performance via deterministic population shrinkage," in Proceedings of the 11th Annual conference on Genetic and evolutionary computation, 2009, pp. 819-826.
[14] J. H. Holland, "Genetic algorithms," Scientific american, vol. 267, no. 1, pp. 66-73, 1992.
[15] X. Yao, Y. Liu, and G. Lin, "Evolutionary programming made faster," IEEE Transactions on Evolutionary computation, vol. 3, no. 2, pp. 82-102, 1999.
[16] R. Storn and K. Price, "Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces," Journal of global optimization, vol. 11, no. 4, pp. 341-359, 1997.
[17] B. Webster and P. J. Bernhard, "A local search optimization algorithm based on natural principles of gravitation," 2003.
[18] R. Poli, J. Kennedy, and T. Blackwell, "Particle swarm optimization," Swarm intelligence, vol. 1, no. 1, pp. 33-57, 2007.
[19] M. Dorigo, M. Birattari, and T. Stutzle, "Ant colony optimization," IEEE computational intelligence magazine, vol. 1, no. 4, pp. 28-39, 2006.
[20] D. Karaboga and B. Basturk, "A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm," Journal of global optimization, vol. 39, no. 3, pp. 459-471, 2007.
[21] X.-S. Yang, "Flower pollination algorithm for global optimization," in International conference on unconventional computing and natural computation, 2012: Springer, pp. 240-249.
[22] A. Askarzadeh, "A novel metaheuristic method for solving constrained engineering optimization problems: crow search algorithm," Computers & Structures, vol. 169, pp. 1-12, 2016.
[23] M. Khishe and M. R. Mosavi, "Chimp optimization algorithm," Expert systems with applications, vol. 149, p. 113338, 2020.
[24] V. Hayyolalam and A. A. P. Kazem, "Black widow optimization algorithm: a novel meta-heuristic approach for solving engineering optimization problems," Engineering Applications of Artificial Intelligence, vol. 87, p. 103249, 2020.
[25] M. H. Sulaiman, Z. Mustaffa, M. M. Saari, and H. Daniyal, "Barnacles mating optimizer: a new bio-inspired algorithm for solving engineering optimization problems," Engineering Applications of Artificial Intelligence, vol. 87, p. 103330, 2020.
[26] F. A. Hashim and A. G. Hussien, "Snake Optimizer: A novel meta-heuristic optimization algorithm," Knowledge-Based Systems, vol. 242, p. 108320, 2022.
[27] L. Abualigah, D. Yousri, M. Abd Elaziz, A. A. Ewees, M. A. Al-Qaness, and A. H. Gandomi, "Aquila optimizer: a novel meta-heuristic optimization algorithm," Computers & Industrial Engineering, vol. 157, p. 107250, 2021.
[28] S. Saremi, S. Mirjalili, and A. Lewis, "Grasshopper optimisation algorithm: theory and application," Advances in Engineering Software, vol. 105, pp. 30-47, 2017.
[29] J. J. Flores, R. López, and J. Barrera, "Gravitational interactions optimization," in International Conference on Learning and Intelligent Optimization, 2011: Springer, pp. 226-237.
[30] A. H. Kashan, "A new metaheuristic for optimization: optics inspired optimization (OIO)," Computers & Operations Research, vol. 55, pp. 99-125, 2015.
[31] S. Kumar, D. Datta, and S. K. Singh, "Black hole algorithm and its applications," in Computational intelligence applications in modeling and control: Springer, 2015, pp. 147-170.
[32] H. Eskandar, A. Sadollah, A. Bahreininejad, and M. Hamdi, "Water cycle algorithm–A novel metaheuristic optimization method for solving constrained engineering optimization problems," Computers & Structures, vol. 110, pp. 151-166, 2012.
[33] I. Ahmadianfar, O. Bozorg-Haddad, and X. Chu, "Gradient-based optimizer: A new metaheuristic optimization algorithm," Information Sciences, vol. 540, pp. 131-159, 2020.
[34] R. V. Rao, V. J. Savsani, and D. Vakharia, "Teaching–learning-based optimization: a novel method for constrained mechanical design optimization problems," Computer-aided design, vol. 43, no. 3, pp. 303-315, 2011.
[35] S. Satapathy and A. Naik, "Social group optimization (SGO): a new population evolutionary optimization technique," Complex & Intelligent Systems, vol. 2, no. 3, pp. 173-203, 2016.
[36] A. Faramarzi, M. Heidarinejad, B. Stephens, and S. Mirjalili, "Equilibrium optimizer: A novel optimization algorithm," Knowledge-Based Systems, vol. 191, p. 105190, 2020.
[37] Q. Askari, I. Younas, and M. Saeed, "Political Optimizer: A novel socio-inspired meta-heuristic for global optimization," Knowledge-based systems, vol. 195, p. 105709, 2020.
[38] I. Naruei and F. Keynia, "Wild horse optimizer: A new meta-heuristic algorithm for solving engineering optimization problems," Engineering with Computers, pp. 1-32, 2021.
[39] J. L. Melvix, "Greedy politics optimization: Metaheuristic inspired by political strategies adopted during state assembly elections," in 2014 IEEE international advance computing conference (IACC), 2014: IEEE, pp. 1157-1162.
[40] W. Lv, C. He, D. Li, S. Cheng, S. Luo, and X. Zhang, "Election campaign optimization algorithm," Procedia Computer Science, vol. 1, no. 1, pp. 1377-1386, 2010.
[41] A. Borji, "A new global optimization algorithm inspired by parliamentary political competitions," in Mexican international conference on artificial intelligence, 2007: Springer, pp. 61-71.
[42] S. H. S. 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.
[43] M. Friedman, "A comparison of alternative tests of significance for the problem of m rankings," The Annals of Mathematical Statistics, vol. 11, no. 1, pp. 86-92, 1940.
[44] R. F. Woolson, "Wilcoxon signed‐rank test," Wiley encyclopedia of clinical trials, pp. 1-3, 2007.
[45] X. He and Y. Zhou, "Enhancing the performance of differential evolution with covariance matrix self-adaptation," Applied Soft Computing, vol. 64, pp. 227-243, 2018.
[46] A. Osyczka and A. Osyczka, Evolutionary algorithms for single and multicriteria design optimization. Springer, 2002.