Pengaruh rasio banyaknya Employed Bee dan Onlooker Bee terhadap performa algoritma Artificial Bee Colony pada Penyelesaian Traveling Salesman Problem

INDONESIA:

Algoritma Artificial Bee Colony (ABC) merupakan metode optimasi metaheuristik yang terinspirasi dari perilaku pencarian makanan oleh koloni lebah madu, yang dapat diadaptasi untuk menyelesaikan Traveling Salesman Problem (TSP). Dalam algoritma ABC, dinamika eksplorasi dan eksploitasi mempengaruhi performa algoritma dalam menemukan solusi optimal. Secara standar, algoritma ABC menetapkan rasio banyaknya employed bee dan onlooker bee sebesar 1:1, namun konfigurasi ini dinilai kurang memiliki mekanisme efektif untuk mengontrol tingkat eksplorasi dan eksploitasi. Oleh karena itu, penelitian ini bertujuan untuk mengevaluasi pengaruh variasi rasio banyaknya employed bee dan onlooker bee terhadap performa algoritma ABC dalam menemukan jarak rute terpendek pada TSP, serta mengidentifikasi rasio yang paling optimal. Metode penelitian ini menggunakan pendekatan kuantitatif eksperimental. Pengujian dilakukan dengan menerapkan lima variasi rasio (1:9, 3:7, 1:1, 7:3, dan 9:1) pada tiga model graf komplit berbobot acak yang masing-masing berukuran 50, 100, dan 200 simpul yang mempresentasikan masalah TSP. Untuk memastikan validitas dan kestabilan data, algoritma dijalankan sebanyak 20 kali pengulangan pada setiap variasi rasio. Analisis data statistik dilakukan menggunakan uji ANOVA. Hasil pengujian memberikan nilai signifikansi 0,000, yang membuktikan bahwa variasi rasio tersebut memberikan pengaruh yang signifikan secara statistik terhadap panjang rute terpendek yang dihasilkan. Analisis lebih lanjut melalui uji Post-Hoc menunjukkan bahwa rasio 1:9 menghasilkan performa paling optimal pada skenario eksperimen penelitian ini. Temuan ini menunjukkan bahwa peningkatan proporsi onlooker bee secara efektif memperkuat intensitas mekanisme eksploitasi, sehingga algoritma menjadi lebih terarah dalam menyempurnakan kualitas solusi terbaik.

ENGLISH:

The Artificial Bee Colony (ABC) algorithm is a metaheuristic optimization method inspired by the foraging behavior of honeybee colonies, which can be adapted to solve the Traveling Salesman Problem (TSP). In the ABC algorithm, the dynamics of exploration and exploitation influence the algorithm’s performance in finding optimal solutions. By default, the ABC algorithm sets the ratio of employed bees to onlooker bees at 1:1; however, this configuration is considered to lack an effective mechanism for controlling the levels of exploration and exploitation. Therefore, this study aims to evaluate the effect of varying the ratio of employed bees and onlooker bees on the ABC algorithm’s performance in finding the shortest route distance in the TSP, as well as to identify the optimal ratio. This study employs a quantitative experimental approach. Testing was conducted by applying five ratio variations (1:9, 3:7, 1:1, 7:3, and 9:1) to three randomly weighted complete graph models, each with 50, 100, and 200 nodes, representing the TSP. To ensure the validity and stability of the data, the algorithm was run 20 times for each ratio variation. Statistical data analysis was performed using an ANOVA test. The results provide a significance value of 0,000, demonstrating that variations in the ratio had a statistically significant effect on the length of the shortest route generated. Further analysis via a Post-Hoc test showed that the 1:9 ratio produced the optimal performance in the experimental scenarios of this study. This finding shows that increasing the proportion of onlooker bees effectively strengthens the intensity of the exploitation mechanism, thereby making the algorithm more focused on refining the quality of the best solution.

ARABIC:

تُعد خوارزمية مستعمرة النحل الاصطناعية (ABC) طريقة تحسين ميتاهيوريستيكية مستوحاة من سلوك البحث عن الغذاء لدى طوائف نحل العسل، والتي يمكن تكييفها لحل مشكلة البائع المتجول (TSP). في خوارزمية ABC ، تؤثر ديناميكيات الاستكشاف (exploration) والاستغلال (exploitation) على أداء الخوارزمية في إيجاد الحلول المثلى. افتراضياً، تحدد خوارزمية ABC نسبة النحل العامل (employed bees) إلى النحل المراقب (onlooker bees) بمقدار ١:١؛ ومع ذلك، يُعد هذا التكوين مفتقراً إلى آلية فعالة للتحكم في مستويات الاستكشاف والاستغلال. لذلك، هدفت هذه الدراسة إلى تقييم تأثير تباين نسبة النحل العامل إلى النحل المراقب على أداء خوارزمية ABC في إيجاد أقصر مسافة للمسار في مشكلة TSP ، بالإضافة إلى تحديد النسبة المثلى. يستخدم هذا البحث المنهج الكمي التجريبي، حيث أُجريت الاختبارات بتطبيق خمسة تباينات في النسب (١:٩، ٣:٧، ١:١، ٧:٣، ٩:١) على ثلاثة نماذج لمخططات كاملة (complete graphs) عشوائية الأوزان، تتكون من ٥٠ و ١٠٠ و ٢٠٠ عقدة، والتي تمثل مشكلة TSP. ولضمان صحة البيانات واستقرارها، تم تشغيل الخوارزمية ٢٠ مرة لكل تباين في النسبة. أُجري تحليل البيانات الإحصائية باستخدام اختبار تحليل التباين (ANOVA)، وذلك بعد التأكد من استيفاء البيانات لافتراضات التوزيع الطبيعي عبر اختبار شابيرو-ويلك (Shapiro-Wilk) وتجانس التباين عبر اختبار ليفين (Levene). وقد أسفرت النتائج عن قيمة دلالة إحصائية تبلغ ٠٫٠٠٠، مما يثبت أن تباين النسب له تأثير ذو دلالة إحصائية على طول أقصر مسار ناتج. كما أظهر تحليل إضافي من خلال اختبار البعدي (Post-Hoc) أن النسبة ١:٩ حققت الأداء الأمثل في السيناريوهات التجريبية لهذه الدراسة. ويشير هذا الاكتشاف إلى أن زيادة نسبة النحل المراقب تعزز بشكل فعال من كثافة آلية الاستغلال، مما يجعل الخوارزمية أكثر تركيزاً على تحسين جودة الحل الأفضل.