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

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.

Keywords

• genetic algorithm
• k-means clustering method
• optimization
• selection operator
• 0/1 multidimensional knapsack problem