<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>The growing need for profit maximization and cost minimization has made the optimization field very attractive to both researchers and practitioners. In fact, many authors were interested in this field and they have developed a large number of optimization algorithms to solve either academic or real-life problems. Among such algorithms, we cite a well-known metaheuristic called the genetic algorithm. This optimizer tool, as any algorithm, suffers from some drawbacks; like the problem of premature convergence. In this paper, we propose a new selection strategy hoping to avoid such a problem. The proposed selection operator is based on the principle of the k-means clustering method for the purpose of guiding the genetic algorithm to explore different regions of the search space. We have elaborated a genetic algorithm based on this new selection mechanism. We have then tested our algorithm on various data instances of the 0/1 multidimensional knapsack problem. The obtained results are encouraging when compared with those reached by other versions of genetic algorithms and those reached by an adapted version of the particle swarm optimization algorithm.</p>
</abstract>

The growing need for profit maximization and cost minimization has made the optimization field very attractive to both researchers and practitioners. In fact, many authors were interested in this field and they have developed a large number of optimization algorithms to solve either academic or real-life problems. Among such algorithms, we cite a well-known metaheuristic called the genetic algorithm. This optimizer tool, as any algorithm, suffers from some drawbacks; like the problem of premature convergence. In this paper, we propose a new selection strategy hoping to avoid such a problem. The proposed selection operator is based on the principle of the k-means clustering method for the purpose of guiding the genetic algorithm to explore different regions of the search space. We have elaborated a genetic algorithm based on this new selection mechanism. We have then tested our algorithm on various data instances of the 0/1 multidimensional knapsack problem. The obtained results are encouraging when compared with those reached by other versions of genetic algorithms and those reached by an adapted version of the particle swarm optimization algorithm.

On Solving 0/1 Multidimensional Knapsack Problem with a Genetic Algorithm Using a Selection Operator Based on K-Means Clustering Principle

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

The growing need for profit maximization and cost minimization has made the optimization field very attractive to both researchers and practitioners. In fact,...

On Solving 0/1 Multidimensional Knapsack Problem with a Genetic Algorithm Using a Selection Operator Based on K-Means Clustering Principle

Publié en ligne: 08 oct. 2022

Pages: 247 - 269

Reçu: 03 sept. 2021

Accepté: 12 juil. 2022

DOI: https://doi.org/10.2478/fcds-2022-0014

Mots clés
Genetic Algorithm, K-Means Clustering Method, Optimization, Selection Operator, 0/1 Multidimensional Knapsack Problem

© 2022 Soukaina Laabadi et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

On Solving 0/1 Multidimensional Knapsack Problem with a Genetic Algorithm Using a Selection Operator Based on K-Means Clustering Principle

Publié en ligne: 08 oct. 2022

Pages: 247 - 269

Reçu: 03 sept. 2021

Accepté: 12 juil. 2022

DOI: https://doi.org/10.2478/fcds-2022-0014

Mots clésGenetic Algorithm, K-Means Clustering Method, Optimization, Selection Operator, 0/1 Multidimensional Knapsack Problem

© 2022 Soukaina Laabadi et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
Genetic Algorithm, K-Means Clustering Method, Optimization, Selection Operator, 0/1 Multidimensional Knapsack Problem