A Metaheuristic to Solve the Capacitated Clustering Problem | ||
| Journal of Al-Azhar University Engineering Sector | ||
| Volume 18, Issue 69, October 2023, Pages 884-899 PDF (957.76 K) | ||
| Document Type: Original Article | ||
| DOI: 10.21608/auej.2023.235083.1420 | ||
| Author | ||
| Banan N. AlTuwaim* | ||
| Department of Computer Science, College of Computer & Information Sciences, Al Imam Mohammad Ibn Saud Islamic University, Riyadh, Saudi Arabia | ||
| Abstract | ||
| One of the most important combinatorial optimisation problems (COPs) is the capacitated clustering problem (CCP). This sort of problem involves dividing a set of nodes into a predefined number of clusters within specific limits (upper and lower); for each node in the cluster, a pair of nodes is defined that has a benefit value, and the total values of these benefits in the cluster must be maximised. The CCP is of a non-deterministic polynomial-time hard (NP-hard) nature. Such problems cannot be practically solved by exact optimisation algorithms, so we must choose one of the metaheuristic algorithms to solve them. The CCP has many applications in a variety of domains. This paper aims to design a metaheuristic method that solves the CCP, with an artificial bee colony (ABC) as the metaheuristic algorithm. The effectiveness of the proposed ABC based algorithm was confirmed through several computational experiments. The results demonstrate that the proposed algorithm produced competitive outcomes compared to the state-of-the-art metaheuristics developed for the CCP. مشكلة التجميع مقيد السعه واحد من اهم مسائل الاستمثال التوافقى ، هذا النوع من المشكلات ترتكز على تقسيم مجموعة من الكائنات الى مجموعات منفصلة بحيث تكون الاوزان الاجمالية لهذه الكائنات ضمن حدود معينة (حد علوى وسفلى) ، وفى نفس الوقت يتم تحقيق اقصى قدر من اجمالى اوزان الاضلاع بين ازواج الكائنات فى نفس المجموعة. هذه المسشكلة تعد مسالة كثيرة الحدود وغير قطعية ومعقدة وبالتالى فان خوارزميات التحسن الدقيقة غير عملية لحل مثل هذه المشكلات لذلك توجب علينا اختيار احدى خوارزميات الاسترشاد. وتوجد العديد من التطبيقات لحل مشكلة التجميع مقيد السعة والتى يمكن تطبيقها فى مجالات ومشكلات مختلفة. إن الهدف الرئيسى من هذا البحث هو تصميم خوارزمية استرشادية فعالة لحل مشكلة التجميع مقيد السعة باستخدام خوارزمية مجتمع النحل الاصطناعى كخوارزمية استرشادية. خوازمية البحث المحلى لها اثر ملموس على قيمة دالة الهدف، وهذا يحدث عند مقارنة النتائج الحسابية مع بعض نتائج الدراسات السابقة، وهذة المقارنة تبين ان خوارزمية النحل الاصطناعى هى خوارزمية منافسىة لخوارزميات الاسترشاد الاخرى بخصوص حل مشكلة التجميع مقيد السعه. | ||
| Keywords | ||
| Capacitated clustering problem (CCP); Local search; Neighbouring operators; Constraints handling; Artificial bee colony (ABC). مشكلة التجمع مقيد السعه، البحث المحلي، العوامل المجاورة، التعامل مع القيود، مستعمرة النحل الاصطناعية | ||
|
Statistics Article View: 104 PDF Download: 135 |
||
