Cet article présente un nouvel algorithme de chauve-souris binaire (NBBA) pour résoudre les problèmes de sac à dos 0–1. L'algorithme proposé combine deux phases importantes : l'algorithme bat binaire (BBA) et le schéma de recherche locale (LSS). L'algorithme bat permet aux chauves-souris d'améliorer la capacité d'exploration tandis que le LSS vise à stimuler les tendances d'exploitation et, par conséquent, il peut empêcher le BBA-LSS de se coincer dans l'optima local. De plus, le LSS commence sa recherche à partir de BBA trouvé jusqu'à présent. Par cette méthodologie, le BBA–LSS améliore la diversité des chauves-souris et améliore les performances de convergence. L'algorithme proposé est testé sur différentes instances de taille de la littérature. Des expériences informatiques montrent que le BBA-LSS peut être une alternative prometteuse pour résoudre des problèmes de sac à dos 0–1 à grande échelle.

Este documento presenta un novedoso algoritmo binario Bat (NBBA) para resolver problemas de mochila 0–1. El algoritmo propuesto combina dos fases importantes: el algoritmo binario Bat (BBA) y el esquema de búsqueda local (LSS). El algoritmo Bat permite a los murciélagos mejorar la capacidad de exploración, mientras que LSS tiene como objetivo impulsar las tendencias de explotación y, por lo tanto, puede evitar que el BBA-LSS quede atrapado en los óptimos locales. Además, el LSS inicia su búsqueda a partir del BBA encontrado hasta el momento. Mediante esta metodología, el BBA–LSS mejora la diversidad de murciélagos y mejora el rendimiento de convergencia. El algoritmo propuesto se prueba en instancias de diferentes tamaños de la literatura. Los experimentos computacionales muestran que el BBA-LSS puede ser una alternativa prometedora para resolver problemas de mochila 0–1 a gran escala.

This paper presents a novel binary bat algorithm (NBBA) to solve 0–1 knapsack problems. The proposed algorithm combines two important phases: binary bat algorithm (BBA) and local search scheme (LSS). The bat algorithm enables the bats to enhance the exploration capability while LSS aims to boost the exploitation tendencies and, therefore, it can prevent the BBA–LSS from the entrapment in the local optima. Moreover, the LSS starts its search from BBA found so far. By this methodology, the BBA–LSS enhances the diversity of bats and improves the convergence performance. The proposed algorithm is tested on different size instances from the literature. Computational experiments show that the BBA–LSS can be promise alternative for solving large-scale 0–1 knapsack problems.

تقدم هذه الورقة خوارزمية الخفافيش الثنائية الجديدة (NBBA) لحل مشاكل حقيبة الظهر 0–1. تجمع الخوارزمية المقترحة بين مرحلتين مهمتين: خوارزمية الخفافيش الثنائية (BBA) ومخطط البحث المحلي (LSS). تمكن خوارزمية الخفافيش الخفافيش من تعزيز قدرة الاستكشاف بينما تهدف LSS إلى تعزيز ميول الاستغلال، وبالتالي، يمكنها منع BBA - LSS من الوقوع في الفخ في الأمثلية المحلية. علاوة على ذلك، تبدأ LSS بحثها من BBA الذي تم العثور عليه حتى الآن. من خلال هذه المنهجية، تعزز BBA - LSS تنوع الخفافيش وتحسن أداء التقارب. يتم اختبار الخوارزمية المقترحة على حالات مختلفة الحجم من الأدبيات. تُظهر التجارب الحسابية أن BBA - LSS يمكن أن يكون بديلاً واعداً لحل مشكلات حقيبة الظهر 0–1 واسعة النطاق.