TY - JOUR

T1 - Binarization Technique Comparisons of Swarm Intelligence Algorithm

T2 - An Application to the Multi-Demand Multidimensional Knapsack Problem

AU - García, José

AU - Moraga, Paola

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - Pinto, Hernan

N1 - Publisher Copyright:
© 2022 by the authors.

PY - 2022/9

Y1 - 2022/9

N2 - In order to minimize execution times, improve the quality of solutions, and address more extensive target situations, optimization techniques, particularly metaheuristics, are continually improved. Hybridizing procedures are one of these noteworthy strategies due to their wide range of applications. This article describes a hybrid algorithm that combines the k-means method to produce a binary version of the cuckoo search and sine cosine algorithms. The binary algorithms are applied on the (Formula presented.) -hard multi-demand multidimensional knapsack problem. This problem is of particular interest because it has two types of constraints. The first group of constraints is related to the capacity of the knapsacks, and a second type is associated with the demand that must be met. Experiments were undertaken to acquire insight into the contribution of the k-means technique and the local search operator to the final results. Additionally, a comparison is made with two other types of binarization, the first based on a random method and the second based on the percentile concept. The results reveal that the k-means hybrid algorithm consistently provides superior results in most cases studied. In particular, incorporating the local search operator improved the results by an average of 0.23%. On the other hand, when comparing the results with 100 items and 30-30 restrictions, k-means was 1.06% better on average than the random operator.

AB - In order to minimize execution times, improve the quality of solutions, and address more extensive target situations, optimization techniques, particularly metaheuristics, are continually improved. Hybridizing procedures are one of these noteworthy strategies due to their wide range of applications. This article describes a hybrid algorithm that combines the k-means method to produce a binary version of the cuckoo search and sine cosine algorithms. The binary algorithms are applied on the (Formula presented.) -hard multi-demand multidimensional knapsack problem. This problem is of particular interest because it has two types of constraints. The first group of constraints is related to the capacity of the knapsacks, and a second type is associated with the demand that must be met. Experiments were undertaken to acquire insight into the contribution of the k-means technique and the local search operator to the final results. Additionally, a comparison is made with two other types of binarization, the first based on a random method and the second based on the percentile concept. The results reveal that the k-means hybrid algorithm consistently provides superior results in most cases studied. In particular, incorporating the local search operator improved the results by an average of 0.23%. On the other hand, when comparing the results with 100 items and 30-30 restrictions, k-means was 1.06% better on average than the random operator.

KW - combinatorial optimization

KW - machine learning

KW - metaheuristics

KW - multi-demand multidimensional knapsack problem

UR - http://www.scopus.com/inward/record.url?scp=85137822660&partnerID=8YFLogxK

U2 - 10.3390/math10173183

DO - 10.3390/math10173183

M3 - Article

AN - SCOPUS:85137822660

SN - 2227-7390

VL - 10

JO - Mathematics

JF - Mathematics

IS - 17

M1 - 3183

ER -