<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

Published Online: Oct 08, 2022

Page range: 247 - 269

Received: Sep 03, 2021

Accepted: Jul 12, 2022

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

Keywords
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

Published Online: Oct 08, 2022

Page range: 247 - 269

Received: Sep 03, 2021

Accepted: Jul 12, 2022

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

KeywordsGenetic 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.

Keywords
Genetic Algorithm, K-Means Clustering Method, Optimization, Selection Operator, 0/1 Multidimensional Knapsack Problem