روشی نوین برای خوشه‌بندی داده‌ها با استفاده از الگوریتم بهینه‌سازی چهارگرگ خاکستری

محورهای موضوعی : مهندسی برق و کامپیوتر

لاله عجمی بختیاروند ¹ (دانشگاه آزاد اسلامی واحد نجف آباد،دانشكده مهندسي كامپيوتر)
زهرا بهشتی ² (دانشگاه آزاد اسلامی واحد نجف آباد،دانشكده مهندسي كامپيوتر)

تاریخ دریافت : 1399/09/18 تاریخ پذیرش : 1400/09/22 تاریخ انتشار : 1400/12/14

کلید واژه: الگوریتم‌های فراابتکاری, الگوریتم بهینه‌سازی گرگ خاکستری, الگوریتم بهینه‌سازی چهارگرگ, خوشه‌بندی,

چکیده مقاله :

امروزه، خوشه‌بندی داده‌ها به دلیل حجم و تنوع داده‎ها بسیار مورد توجه قرار گرفته است. مشکل اصلی روش‌های خوشه‌بندهای معمول این است که در دام بهینه محلی گرفتار می‌آیند. الگوریتم‌های فراابتکاری به دلیل داشتن توانایی فرار از بهینه‌های محلی، نتایج موفقی را در خوشه‌بندی داده‌ها نشان داده‌اند. الگوریتم بهینه‌سازی گرگ خاکستری از جمله این دسته الگوریتم‌ها است که قابلیت بهره‌برداری خوبی دارد و در برخی از مسایل راه حل مناسبی ارائه داده است، اما اکتشاف آن ضعیف است و در بعضی از مسایل به بهینه محلی همگرا می‌شود. در این تحقیق برای بهبود خوشه‌بندی داده‌ها، نسخه بهبودیافته‌ای از الگوریتم بهینه‌سازی گرگ خاکستری به نام الگوریتم بهینه‌سازی چهارگرگ خاکستری ارائه شده که با استفاده از بهترین موقعیت دسته چهارم گرگ‌ها به نام گرگ‌های امگای پیشرو در تغییر موقعیت هر گرگ، قابلیت اکتشاف بهبود می‌یابد. با محاسبه امتیاز هر گرگ نسبت به بهترین راه حل، نحوه حرکت آن مشخص می‌شود. نتایج الگوریتم پیشنهادی چهارگرگ خاکستری با الگوریتم‌های بهینه‌سازی گرگ خاکستری، بهینه‌سازی ازدحام ذرات، کلونی زنبور عسل مصنوعی، ارگانیسم‌های هم‌زیست و بهینه‌سازی ازدحام سالپ در مسأله خوشه‌بندی روی چهارده مجموعه دادگان ارزیابی شده است. همچنین عملکرد الگوریتم پیشنهادی با چند نسخه بهبودیافته از الگوریتم گرگ خاکستری مقایسه شده است. نتایج به دست آمده عملکرد قابل توجه الگوریتم پیشنهادی را نسبت به سایر الگوریتم‌های فراابتکاری مورد مقایسه در مسأله خوشه‌بندی نشان می‌دهد. بر اساس میانگین معیار F روی تمام مجموعه دادگان، روش پیشنهادی 82/172% و الگوریتم بهینه ذرات 78/284% را نشان می‌دهد و در مقایسه با نسخه‌های بهبودیافته الگوریتم گرگ، الگوریتم EGWO که در رتبه بعدی است دارای میانگین معیار F برابر 80/656% می‌باشد.

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

Nowadays, clustering methods have received much attention because the volume and variety of data are increasing considerably.The main problem of classical clustering methods is that they easily fall into local optima. Meta-heuristic algorithms have shown good results in data clustering. They can search the problem space to find appropriate cluster centers. One of these algorithms is gray optimization wolf (GWO) algorithm. The GWO algorithm shows a good exploitation and obtains good solutions in some problems, but its disadvantage is poor exploration. As a result, the algorithm converges to local optima in some problems. In this study, an improved version of gray optimization wolf (GWO) algorithm called 4-gray wolf optimization (4GWO) algorithm is proposed for data clustering. In 4GWO, the exploration capability of GWO is improved, using the best position of the fourth group of wolves called scout omega wolves. The movement of each wolf is calculated based on its score. The better score is closer to the best solution and vice versa. The performance of 4GWO algorithm for the data clustering (4GWO-C) is compared with GWO, particle swarm optimization (PSO), artificial bee colony (ABC), symbiotic organisms search (SOS) and salp swarm algorithm (SSA) on fourteen datasets. Also, the efficiency of 4GWO-C is compared with several various GWO algorithms on these datasets. The results show a significant improvement of the proposed algorithm compared with other algorithms. Also, EGWO as an Improved GWO has the second rank among the different versions of GWO algorithms. The average of F-measure obtained by 4GWO-C is 82.172%; while, PSO-C as the second best algorithm provides 78.284% on all datasets.

منابع و مأخذ:

[1] M. Jafarzadegan, F. Safi-Esfahani, and Z. Beheshti, "Combining hierarchical clustering approaches using the PCA method," Expert Syst. Appl., vol. 137, pp. 1-10, Dec 2019.
[2] J. Han, J. Pei, and M. Kamber, Data Mining: Concepts and Techniques, Elsevier, 2011.
[3] D. J. Hand, "Principles of data mining," Drug Saf., vol. 30, no. 7, pp. 621-622, Jul. 2007.
[4] D. T. Dinh and V. N. Huynh, "k-PbC: an improved cluster center initialization for categorical data clustering," Appl. Intell., vol. 50, no. 8, pp. 2610-2632, Aug. 2020.
[5] R. Xu and D. Wunsch, "Survey of clustering algorithms," IEEE Trans. Neural Networks, vol. 16, no. 3, pp. 645-678, May 2005.
[6] Z. Beheshti, "A novel x-shaped binary particle swarm optimization," Soft Comput., vol. 25, no. 4, pp. 3013-3042, Feb. 2021.
[7] Z. Beheshti, "UTF: upgrade transfer function for binary meta-heuristic algorithms," Appl. Soft Comput., vol. 106, Article ID: 107346, 28 pp., Jul. 2021.
[8] R. Salgotra, U. Singh, S. Singh, G. Singh, and N. Mittal, "Self-adaptive salp swarm algorithm for engineering optimization problems," Appl. Math. Model., vol. 89, pp. 188-207, Jul. 2021.
[9] Z. Beheshti, "BMNABC: binary multi-neighborhood artificial bee colony for high-dimensional discrete optimization problems," Cybern. Syst., vol. 49, no. 7-8, pp. 452-474, Nov. 2018.
[10] Z. Beheshti, S. M. Shamsuddin, S. Hasan, and N. E. Wong, "Improved centripetal accelerated particle swarm optimization," Int. J. Adv. Soft Comput. its Appl., vol. 8, no. 2, pp. 1-26, Jul. 2016.
[11] I. Aljarah, M. Mafarja, A. A. Heidari, H. Faris, and S. Mirjalili, "Clustering analysis using a novel locality-informed grey wolf-inspired clustering approach," Knowl. Inf. Syst., vol. 62, no. 2, pp. 507-539, Feb. 2020.
[12] H. D. Menendez, F. E. B. Otero, and D. Camacho, "Medoid-based clustering using ant colony optimization," Swarm Intell., vol. 10, no. 2, pp. 123-145, Jul. 2016.
[13] P. Das, D. K. Das, and S. Dey, "A modified bee colony optimization (MBCO) and its hybridization with k-means for an application to data clustering," Appl. Soft Comput., vol. 70, pp. 590-603, Sept. 2018.
[14] R. J. Kuo and F. E. Zulvia, "An improved differential evolution with cluster decomposition algorithm for automatic clustering," Soft Comput., vol. 23, no. 18, pp. 8957-8973, Sept. 2019.
[15] T. Ashish, S. Kapil, and B. Manju, "Parallel bat algorithm-based clustering using mapreduce," In: G. Perez, K. Mishra, S. Tiwari, and M. Trivedi (eds), Networking Communication and Data Knowledge Engineering, Lecture Notes on Data Engineering and Communications Technologies, vol 4. Springer, pp. 73-82, 2018.
[16] O. Tarkhaneh, A. Isazadeh, and H. J. Khamnei, "A new hybrid strategy for data clustering using cuckoo search based on Mantegna levy distribution, PSO and k-means," Int. J. Comput. Appl. Technol., vol. 58, no. 2, pp. 137-149, Jan. 2018.
[17] H. A. Abdulwahab, A. Noraziah, A. A. Alsewari, and S. Q. Salih, "An enhanced version of black hole algorithm via levy flight for optimization and data clustering problems," IEEE Access, vol. 7, pp. 142085-142096, Aug. 2019.
[18] K. W. Huang, Z. X. Wu, H. W. Peng, M. C. Tsai, Y. C. Hung, and Y. C. Lu, "Memetic particle gravitation optimization algorithm for solving clustering problems," IEEE Access, vol. 7, pp. 80950-80968, Jan. 2019.
[19] H. Yu, Z. Chang, G. Wang, and X. Chen, "An efficient three-way clustering algorithm based on gravitational search," Int. J. Mach. Learn. Cybern., vol. 11, no. 5, pp. 1003-1016, May 2020.
[20] A. Kaur, S. K. Pal, and A. P. Singh, "Hybridization of chaos and flower pollination algorithm over K-means for data clustering," Appl. Soft Comput., vol. 97, Article ID: 105523, 17 pp., Dec. 2019.
[21] Y. Zhou, H. Wu, Q. Luo, and M. Abdel-Baset, "Automatic data clustering using nature-inspired symbiotic organism search algorithm," Knowledge-Based Syst., vol. 163, pp. 546-557, Jan. 2019.
[22] G. Drakopoulos, et al., "A genetic algorithm for spatiosocial tensor clustering," Evol. Syst., vol. 11, no. 3, pp. 1-11, Sept. 2019. [23] M. Alswaitti, M. Albughdadi, and N. A. M. Isa, "Density-based particle swarm optimization algorithm for data clustering," Expert Syst. Appl., vol. 91, pp. 170-186, Jan. 2018.
[24] J. Chen, X. Qi, L. Chen, F. Chen, and G. Cheng, "Quantum-inspired ant lion optimized hybrid k-means for cluster analysis and intrusion detection," Knowledge-Based Syst., vol. 203, Article ID: 106167, 10 pp., Sept. 2020.
[25] L. M. Abualigah, A. T. Khader, E. S. Hanandeh, and A. H. Gandomi, "A novel hybridization strategy for krill herd algorithm applied to clustering techniques," Appl. Soft Comput., vol. 60, pp. 423-435, Nov. 2017.
[26] M. Demri, S. Ferouhat, S. Zakaria, and M. E. Barmati, "A hybrid approach for optimal clustering in wireless sensor networks using cuckoo search and simulated annealing algorithms," in Proc. 2nd Int. Conf. on Mathematics and Information Technology, ICMIT’20, pp. 202-207, Adrar, Algeria, 18-19 Feb. 2020.
[27] S. Gavel, P. Joshi, S. Tiwari, and A. S. Raghuvanshi, "An optimized hybrid clustering method using salp swarm optimization with K-means," In: V. Nath and J. Mandal (eds) Nanoelectronics, Circuits and Communication Systems. Nanoelectronics, Circuits and Communication Systems, Lecture Notes in Electrical Engineering, vol. 692, Springer, pp. 247-254, 2020.
[28] S. K. Majhi, "Fuzzy clustering algorithm based on modified whale optimization algorithm for automobile insurance fraud detection," Evol. Intell., vol. 14, no. 1, pp. 35-46, 2021.
[29] E. Rashedi, H. Nezamabadipour, and S. Saryazdi, "GSA: a gravitational search algorithm," Inf. Sci. (Ny), vol. 179, no. 13, pp. 2232-2248, Jan. 2009.
[30] S. Mirjalili, S. M. Mirjalili, and A. Lewis, "Grey wolf optimizer," Adv. Eng. Softw., vol. 69, pp. 46-61, 2014.
[31] G. P. Gupta and S. Jha, "Integrated clustering and routing protocol for wireless sensor networks using Cuckoo and Harmony Search based metaheuristic techniques," Eng. Appl. Artif. Intell., vol. 68, pp. 101-109, Feb. 2018.
[32] G. P. Gupta and B. Saha, "Load balanced clustering scheme using hybrid metaheuristic technique for mobile sink based wireless sensor networks," J. Ambient Intell. Humaniz. Comput., 12 pp., Apr. 2020. (in Press)
[33] M. Shakil, A. Fuad Yousif Mohammed, R. Arul, A. K. Bashir, and J. K. Choi, "A novel dynamic framework to detect DDoS in SDN using metaheuristic clustering," Trans. Emerg. Telecommun. Technol., 12 pp., Apr. 2019. (in Press)
[34] R. J. Kuo, T. C. Lin, F. E. Zulvia, and C. Y. Tsai, "A hybrid metaheuristic and kernel intuitionistic fuzzy c-means algorithm for cluster analysis," Appl. Soft Comput., vol. 67, pp. 299-308, Jan. 2018.
[35] A. Kaur and Y. Kumar, "A new metaheuristic algorithm based on water wave optimization for data clustering," Evol. Intell., 12 pp., Jan. 2021.
[36] M. Ghobaei-Arani and A. Shahidinejad, "An efficient resource provisioning approach for analyzing cloud workloads: a metaheuristic-based clustering approach," J. Supercomput., vol. 77, no. 1, pp. 711-750, 2021.
[37] ح. املشی و ی. بستانی املشی، "روشی جدید به منظور خوشه‌بندی داده‌های سرعت باد در نیروگاه‌های بادی با استفاده از الگوریتم‌های FCM و PSO،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، سال 8، شماره 3، صص. 214-210، پاییز 1389.
[38] م. ع. نژاد و م. خرد، "استفاده از خوشه‌بندی BIRCH و الگوریتم بهینه‌سازی واکنش شیمیایی جهت کشف تقلب در حوزه سلامت،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 17، شماره 2، صص. 160-153، تابستان 1398.
[39] م. یقینی و ج. لسان، "حل مسأله خوشه‌بندی ظرفیت‌دار با استفاده از روش‌های مبتنی بر الگوریتم‌های شبیه‌سازی تبریدی و ژنتیک،" نشریه بین‌المللی مهندسی صنایع و مدیریت تولید، دوره 21، شماره 3، صص. 54-45، پاییز 1389.
[40] ع. فهمی جعفرقلخانلو و م. شمسی، "بخش‌بندی تصاویر رنگی چهره مبتنی بر خوشه‌بند فازی بهینه‌سازی شده با الگوریتم‌های گرگ خاکستری و نهنگ،" مجله علمی رایانش نرم و فناوری اطلاعات، دوره 10، شماره 2، صص. 13-1، تیر 1400.
[41] Y. Li, X. Lin, and J. Liu, "An improved gray wolf optimization algorithm to solve engineering problems," Sustainability, vol. 13, no. 6, Article ID: 3208, 23 pp., 15 Mar. 2021.
[42] M. Kohli and S. Arora, "Chaotic grey wolf optimization algorithm for constrained optimization problems," J. Comput. Des. Eng., vol. 5, no. 4, pp. 458-472, Oct. 2018.
[43] Z. Yue, S. Zhang, and W. Xiao, "A novel hybrid algorithm based on grey wolf optimizer and fireworks algorithm," Sensors, vol. 20, no. 7, Article ID: 2147, 17 pp., Jan. 2020.
[44] ع. محمدزاده، م. مصدری، ف. سلیمانیان قره¬چپق و ا. جعفریان، " ارائه یک الگوریتم بهبودیافته بهینه سازی گرگ های خاکستری برای زمان‌بندی جریان کار در محیط محاسبات ابری،" مجله علمی رایانش نرم و فناوری اطلاعات، دوره 8، شماره 4، صص. 29-17، بهمن 1398.
[45] W. Long, J. Jiao, X. Liang, and M. Tang, "An exploration-enhanced grey wolf optimizer to solve high-dimensional numerical optimization," Eng. Appl. Artif. Intell., vol. 68, pp. 63-80, Feb. 2018.
[46] M. H. Qais, H. M. Hasanien, and S. Alghuwainem, "Augmented grey wolf optimizer for grid-connected PMSG-based wind energy conversion systems," Appl. Soft Comput., vol. 69, pp. 504-515, Aug. 2018.
[47] K. Luo, "Enhanced grey wolf optimizer with a model for dynamically estimating the location of the prey," Appl. Soft Comput., vol. 77, no. ???, pp. 225-235, Apr. 2019.
[48] E. Akbari, A. Rahimnejad, and S. A. Gadsden, "A greedy non‐hierarchical grey wolf optimizer for real‐world optimization," Electron. Lett., vol. 57, no. 13, pp. 499-501, Jan. 2021.
[49] A. Bahrololoum, H. Nezamabadipour, and S. Saryazdi, "A data clustering approach based on universal gravity rule," Eng. Appl. Artif. Intell., vol. 45, pp. 415-428, Oct. 2015.
[50] D. Dua and C. Graff, {UCI} Machine Learning Repository, 2017.
[51] J. Derrac, S. Garcia, D. Molina, and F. Herrera, "A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms," Swarm Evol. Comput., vol. 1, no. 1, pp. 3-18, Mar. 2011.

متن کامل:

معرفي يک روش جديد خوشه‌يابي خودکار

مقاله پژوهشی

روشی نوین برای خوشه‌بندی داده‌ها با استفاده
از الگوریتم بهینه‌سازی چهارگرگ خاکستری

لاله عجمی بختیاروند و زهرا بهشتی

چكیده: امروزه، خوشه‌بندی داده‌ها به دلیل حجم و تنوع داده‎ها بسیار مورد توجه قرار گرفته است. مشکل اصلی روش‌های خوشه‌بندهای معمول این است که در دام بهینه محلی گرفتار می‌آیند. الگوریتم‌های فراابتکاری به دلیل داشتن توانایی فرار از بهینه‌های محلی، نتایج موفقی را در خوشه‌بندی داده‌ها نشان داده‌اند. الگوریتم بهینه‌سازی گرگ خاکستری از جمله این دسته الگوریتم‌ها است که قابلیت بهره‌برداری خوبی دارد و در برخی از مسایل راه حل مناسبی ارائه داده است، اما اکتشاف آن ضعیف است و در بعضی از مسایل به بهینه محلی همگرا می‌شود. در این تحقیق برای بهبود خوشه‌بندی داده‌ها، نسخه بهبودیافته‌ای از الگوریتم بهینه‌سازی گرگ خاکستری به نام الگوریتم بهینه‌سازی چهارگرگ خاکستری ارائه شده که با استفاده از بهترین موقعیت دسته چهارم گرگ‌ها به
نام گرگ‌های امگای پیشرو در تغییر موقعیت هر گرگ، قابلیت اکتشاف بهبود می‌یابد. با محاسبه امتیاز هر گرگ نسبت به بهترین راه حل، نحوه حرکت آن مشخص می‌شود. نتایج الگوریتم پیشنهادی چهارگرگ خاکستری با الگوریتم‌های بهینه‌سازی گرگ خاکستری، بهینه‌سازی ازدحام ذرات، کلونی زنبور عسل مصنوعی، ارگانیسم‌های هم‌زیست و بهینه‌سازی ازدحام سالپ در مسأله خوشه‌بندی روی چهارده مجموعه دادگان ارزیابی شده است. همچنین عملکرد الگوریتم پیشنهادی با چند نسخه بهبودیافته از الگوریتم گرگ خاکستری مقایسه شده است. نتایج به دست آمده عملکرد قابل توجه الگوریتم پیشنهادی را نسبت به سایر الگوریتم‌های فراابتکاری مورد مقایسه در مسأله خوشه‌بندی نشان می‌دهد. بر اساس میانگین معیار F روی تمام مجموعه دادگان، روش پیشنهادی 172/82% و الگوریتم بهینه ذرات 284/78% را نشان می‌دهد و در مقایسه با نسخه‌های بهبودیافته الگوریتم گرگ، الگوریتم EGWO که در رتبه بعدی است دارای میانگین معیار F برابر 656/80% می‌باشد.

کلیدواژه: الگوریتم‌های فراابتکاری، الگوریتم بهینه‌سازی گرگ خاکستری، الگوریتم بهینه‌سازی چهارگرگ، خوشه‌بندی.

1- مقدمه

با توجه به تولید حجم بالای اطلاعات در زمینه‌های مختلف و این حقیقت که ترکیبی از داده‌های مفید و غیر مفید در اختیار افراد قرار می‌گیرد، لزوم استفاده از روش‌های داده‌کاوی² جهت استخراج اطلاعات مفید از حجم انبوهی از داده‌ها به خوبی احساس می‌گردد [1]. داده‌کاوی استخراج دانش از ‌‌مجموعه‌های داده‌ای و تبدیل آن به یک ساختار قابل فهم برای استفاده‌هایی در آینده می‌باشد [2]. شکاف موجود بین داده‌ها و اطلاعات، سبب ایجاد نیاز به ابزارهای داده‌کاوی شده است تا داده‌های بی‌ارزش را به دانشی ارزشمند تبدیل کند [3]. برای این کار الگوریتم‌های متعددی وجود دارد که هر یک برای هدف خاصی کاربرد دارند. خوشه‌بندی از مهم‌ترین الگوریتم‌های داده‌کاوی است و کاربرد بسیاری دارد. الگوریتم‌های خوشه‌بندی، اطلاعاتی را که ویژگی‌های نزدیک به هم و مشابه دارند، در دسته‌هایی که به آنها خوشه گفته می‌شود قرار می‌دهند. اکثر الگوریتم‌ها مراکز خوشه را به صورت تصادفی انتخاب می‌کنند و راه حل نهایی وابستگی به انتخاب اولیه این مراکز دارد [4]. از این رو امکان دارد به جای همگراشدن به بهینه سراسری به بهینه محلی همگرا شود. مسأله خوشه‌بندی یک مسأله ان‌پی- سخت³ [5] محسوب می‌شود و الگوریتم‌های دقیق⁴ قادر به حل نمونه‌هایی از آن با ابعاد کوچک هستند. از این رو می‌توان از الگوریتم‌های فراابتکاری⁵ که از دسته الگوریتم‌های تقریبی هستند و برای حل مسایل پیچیده با ابعاد بالا کاربرد دارند استفاده کرد [6] تا [11].

الگوریتم‌های فراابتکاری با انتخاب مراکز خوب در میان حجم وسیعی از داده‌ها، خوشه‌بندی را انجام می‌دهند و از نظر پیچیدگی زمانی و مصرف حافظه، شرایط بهتری را نسبت به الگوریتم‌های دقیق فراهم می‌کنند. از قابلیت جستجوی این الگوریتم‌ها برای جستجوی مراکز خوشه‌های مناسب در فضای ویژگی داده‌شده استفاده می‌گردد. در این راستا، تحقیقات زیادی روی بهبود کیفیت خوشه‌بندی با الگوریتم‌های فراابتکاری انجام شده است و هر روز نیز کارهای جدیدی به آن اضافه می‌گردد. الگوریتم‌هایی مانند بهینه‌سازی کلونی مورچه‌ها (ACO) [12]، کلونی زنبور عسل (ABC) [13]، تکامل تفاضلی (DE) [14]، خفاش (BA) [15]، فاخته (CA) [16]، سیاه‌چاله (BH) [17]، ممتیک بهینه‌سازی گرانش ذرات (MPGO) [18]، جستجوی گرانشی (GSA) [19]، گرگ خاکستری (GWO) [11]، گرده‌افشانی گل (FPA) [20]، جستجوی ارگانیسم هم‌زیست (SOS) [21]، ژنتیک (GA) [22]، بهینه‌سازی ازدحام ذرات (PSO) [23]، شیر مورچه (ALO) [24]، گروه میگوها (KHA) [25]، شبیه‌سازی تبرید (SA) [26]، ازدحام سالپ (SSA) [27] و الگوریتم بهینه‌سازی نهنگ (WOA) [28] از جمله الگوریتم‌های فراابتکاری هستند که در خوشه‌بندی استفاده شده‌اند.

دلیل کاربرد زیاد این الگوریتم‌ها در خوشه‌بندی آن است که این الگوریتم‌ها راهکارهایی را پیشنهاد می‌کنند که در فرار از دام بهینه‌های محلی مؤثر هستند. عامل مهم در یافتن راه حل‌های خوب در این الگوریتم‌ها، توازن بین قابلیت‌های اکتشاف⁶ و بهره‌برداری⁷ است. قابلیت اکتشاف به جستجوی گسترده در فضای جواب اشاره دارد و قابلیت بهره‌برداری، استفاده از تجربیات به دست آمده در فرایند جستجو و تمرکز بر نواحی امیدبخش فضای جواب می‌باشد [29]. بنابراین با ایجاد توازن پویا بین این دو قابلیت، جستجو به سمت محدوده‌هایی از فضای جواب سوق داده می‌شود که جواب‌های بهتری در آنها یافت شده و از طرف دیگر، موجب عدم اتلاف زمان بیشتر در بخشی از فضای جواب می‌شود که قبل از این بررسی شده و یا شامل جواب‌های نامرغوبی می‌باشد. اما این الگوریتم‌ها از آنجایی که در دسته الگوریتم‌های تقریبی هستند و تمام فضای جواب را جستجو نمی‌کنند، ممکن است به دام بهینه محلی گرفتار آیند و نتوانند از آن رهایی یابند که در این حالت جواب خوبی را برنمی‌گردانند. یکی از الگوریتم‌هایی که در بسیاری از مسایل بهینه‌سازی استفاده شده است، الگوریتم بهینه‌سازی گرگ‌های خاکستری [30] است که قابلیت بهره‌برداری خوبی دارد ولی در اکتشاف و برقراری توازن با بهره‌برداری ضعیف عمل می‌کند. در این الگوریتم، حرکت گرگ‌ها بر اساس سه گرگ برتر جمعیت صورت می‌گیرد و اگر این سه گرگ
در نقطه بهینه محلی باشند کل جمعیت به سمت آن نقطه حرکت خواهند کرد.

در این تحقیق برای بهبود خوشه‌بندی داده‌ها نسخه‌ای از الگویتم بهینه‌سازی گرگ خاکستری به نام الگوریتم بهینه‌سازی چهارگرگ ⁸GWO)4( ارائه می‌گردد. در الگوریتم بهینه‌سازی گرگ خاکستری، به منظور شبیه‌سازی رفتار اجتماعی گرگ‌ها، یک جمعیت تصادفی از راه حل‌ها تولید شده و اولین راه حل بهینه به نام آلفا و دومین و سومین راه حل‌های بهینه به ترتیب به نام بتا و دلتا معرفی می‌شود. سایر گرگ‌ها با استفاده از موقعیت این سه گرگ تغییر موقعیت می‌دهند، بنابراین اگر این سه گرگ در بهینه محلی گرفتار شوند سایر اعضای جمعیت را نیز به سمت این موقعیت خواهند کشاند. در الگوریتم پیشنهادی، از عملکرد دسته چهارم که گرگ‌های امگای پیشرو⁹ نامیده می‌شوند برای فرار از بهینه‌های محلی و بهبود قابلیت اکتشاف استفاده می‌گردد. به این منظور برای هر گرگ جمعیت، امتیازی محاسبه می‌گردد و بر اساس آن، نوع حرکت مشخص می‌شود. هرچه گرگ موقعیت بهتری داشته باشد (یعنی به جواب خوب نزدیک باشد) امتیاز آن بیشتر است. در ابتدای اجرای الگوریتم که گرگ‌ها از نقطه بهینه فاصله دارند، امتیاز کمی دارند و بنابراین بر اساس موقعیت بهترین گرگ‌‌های امگای پیشرو که موقعیتی تصادفی در فضای جستجو است، تغییر موقعیت می‌دهند و به اکتشاف می‌پردازند. گرگ‌ها به تدریج که از حالات اکتشاف به سمت بهره‌برداری حرکت می‌کنند، دارای امتیاز بهتری می‌گردند و بر اساس حرکت سه گرگ برتر جمعیت حرکت می‌کنند. این نحوه حرکت، باعث پیمایش بهتر فضای مسأله می‌گردد و مراکز خوشه دقیق‌تر انتخاب می‌شوند.

در ادامه و در بخش 2 پژوهش‌های اخیر در زمینه خوشه‌بندی با الگوریتم‌های فراابتکاری شرح داده می‌شوند و پس از آن، الگوریتم بهینه‌سازی گرگ خاکستری توضیح داده می‌شود. روش پیشنهادی شامل الگوریتم بهینه‌سازی چهارگرگ خاکستری و استفاده از آن در خوشه‌بندی داده‌ها در بخش 3 بیان می‌گردد. در ادامه این بخش با استفاده از مثالی، عملکرد روش پیشنهادی برای خوشه‌بندی داده‌ها نشان داده می‌شود. نتایج و بحث در بخش 4 ارائه می‌گردد و در بخش 5، نتیجه‌گیری و تحقیقات آینده شرح داده خواهند شد.

2- پژوهش‌ها و کارهای موجود

2-1پژوهش‌های اخیر در زمینه خوشه‌بندی با استفاده از الگوریتم‌های فراابتکاری

در یکی

اشتراک گذاری

آدرس مقاله

روشی نوین برای خوشه‌بندی داده‌ها با استفاده از الگوریتم بهینه‌سازی چهارگرگ خاکستری