Result: Modified Artificial Bee Colony Algorithm for Multiple-Choice Multidimensional Knapsack Problem

Le problème du sac à dos multidimensionnel à choix multiples (MMKP) est un problème NP difficile bien connu qui a de nombreuses applications en temps réel. Cependant, en raison de sa complexité, trouver des solutions efficaces sur le plan informatique pour le MMKP reste une tâche difficile. Dans cette étude, nous proposons un algorithme de colonie d'abeilles artificielles modifiées (MABC) pour résoudre le MMKP. Le MABC utilise la relaxation de substitution, la distance de Hamming et une liste tabu pour améliorer le processus de recherche local et exploiter les informations de voisinage. Nous avons évalué les performances du MABC sur des instances de référence standard et l'avons comparé à plusieurs algorithmes de pointe, notamment RLS, ALMMKP, ACO, PEGF-PERC, TIKS-TIKS 2 et D-QPSO. Les résultats expérimentaux révèlent que MABC produit des solutions hautement compétitives en termes de meilleures solutions trouvées, réalisant environ 2% des solutions optimales avec un temps CPU trivial (millisecondes). Le test de Kruskal-Wallis a révélé qu'il n'y avait pas de différence statistiquement significative dans les valeurs de la fonction objective entre l'algorithme MABC et d'autres algorithmes de pointe (H = 0,31506, p = 0,988882). Cependant, pour l'efficacité du processeur, le test a montré une différence statistiquement significative (H = 84,90850, p = 0), indiquant que l'algorithme MABC présentait une efficacité du processeur significativement meilleure (avec des temps d'exécution plus courts) que les autres algorithmes. En plus de ces résultats, la facilité de mise en œuvre de l'algorithme et le petit nombre de paramètres de contrôle rendent notre approche hautement adaptative pour les systèmes en temps réel à grande échelle.
El problema de la mochila multidimensional de opción múltiple (MMKP) es un problema NP-hard bien conocido que tiene muchas aplicaciones en tiempo real. Sin embargo, debido a su complejidad, encontrar soluciones computacionalmente eficientes para el MMKP sigue siendo una tarea difícil. En este estudio, proponemos un algoritmo de Colonia de Abejas Artificial Modificada (MABC) para resolver el MMKP. El MABC emplea la relajación sustituta, la distancia de Hamming y una lista tabú para mejorar el proceso de búsqueda local y explotar la información del vecindario. Evaluamos el rendimiento del MABC en instancias de referencia estándar y lo comparamos con varios algoritmos de última generación, incluidos RLS, ALMMKP, ACO, PEGF-PERC, TIKS-TIKS 2 y D-QPSO. Los resultados experimentales revelan que MABC produce soluciones altamente competitivas en términos de las mejores soluciones encontradas, logrando aproximadamente el 2% de las soluciones óptimas con un tiempo de CPU trivial (milisegundos). La prueba de Kruskal-Wallis reveló que no hubo diferencias estadísticamente significativas en los valores de la función objetivo entre el algoritmo MABC y otros algoritmos de última generación (H = 0.31506, p = 0.98882). Sin embargo, para la eficiencia de la CPU, la prueba mostró una diferencia estadísticamente significativa (H = 84,90850, p = 0), lo que indica que el algoritmo MABC mostró una eficiencia de la CPU significativamente mejor (con tiempos de ejecución más cortos) que los otros algoritmos. Junto con estos hallazgos, la facilidad de implementación del algoritmo y el pequeño número de parámetros de control hacen que nuestro enfoque sea altamente adaptable para sistemas en tiempo real a gran escala.
The multiple-choice multidimensional knapsack problem (MMKP) is a well-known NP-hard problem that has many real-time applications. However, owing to its complexity, finding computationally efficient solutions for the MMKP remains a challenging task. In this study, we propose a Modified Artificial Bee Colony algorithm (MABC) to solve the MMKP. The MABC employs surrogate relaxation, Hamming distance, and a tabu list to enhance the local search process and exploit neighborhood information. We evaluated the performance of the MABC on standard benchmark instances and compared it with several state-of-the-art algorithms, including RLS, ALMMKP, ACO, PEGF-PERC, TIKS-TIKS 2 and D-QPSO. The experimental results reveal that MABC produces highly competitive solutions in terms of the best solutions found, achieving approximately 2% of the optimal solutions with trivial (milliseconds) CPU time. The Kruskal-Wallis test revealed that there was no statistically significant difference in the objective function values between the MABC algorithm and other state-of-the-art algorithms (H = 0.31506, p = 0.98882). However, for CPU efficiency, the test showed a statistically significant difference (H = 84.90850, p = 0), indicating that the MABC algorithm exhibited significantly better CPU efficiency (with shorter execution times) than the other algorithms did. Along with these findings, the ease of implementation of the algorithm and the small number of control parameters make our approach highly adaptive for large-scale real-time systems.
مشكلة حقيبة الظهر متعددة الاختيارات متعددة الأبعاد (MMKP) هي مشكلة صلبة معروفة تحتوي على العديد من التطبيقات في الوقت الفعلي. ومع ذلك، نظرًا لتعقيدها، لا يزال العثور على حلول فعالة حسابيًا لـ MMKP مهمة صعبة. في هذه الدراسة، نقترح خوارزمية مستعمرة النحل الاصطناعي المعدلة (MABC) لحل MMKP. توظف MABC الاسترخاء البديل، ومسافة الهامينغ، وقائمة تابو لتعزيز عملية البحث المحلية واستغلال معلومات الحي. قمنا بتقييم أداء MABC في الحالات المعيارية القياسية وقارناها بالعديد من الخوارزميات الحديثة، بما في ذلك RLS و ALMMKP و ACO و PEGF - PERC و TIKS - TIKS 2 و D - QPSO. تكشف النتائج التجريبية أن MABC تنتج حلولًا عالية التنافسية من حيث أفضل الحلول التي تم العثور عليها، مما يحقق ما يقرب من 2 ٪ من الحلول المثلى مع وقت وحدة المعالجة المركزية التافهة (بالمللي ثانية). كشف اختبار Kruskal - Wallis أنه لا يوجد فرق ذو دلالة إحصائية في قيم الدالة الموضوعية بين خوارزمية MABC وغيرها من الخوارزميات الحديثة (H = 0.31506، p = 0.98882). ومع ذلك، بالنسبة لكفاءة وحدة المعالجة المركزية، أظهر الاختبار فرقًا ذا دلالة إحصائية (H = 84.90850، p = 0)، مما يشير إلى أن خوارزمية MABC أظهرت كفاءة وحدة معالجة مركزية أفضل بكثير (مع أوقات تنفيذ أقصر) من الخوارزميات الأخرى. إلى جانب هذه النتائج، فإن سهولة تنفيذ الخوارزمية والعدد القليل من معلمات التحكم تجعل نهجنا متكيفًا للغاية مع الأنظمة واسعة النطاق في الوقت الفعلي.