Abstract:

The Multidimensional Knapsack Problem which is an integer programming problem serves as a mathematical basis for the analysis and solution of various types of problems facing businesses. When the number of variables and constraints that compose the mathematical model of the problem increases, the problem is often solved with heuristic approaches that can find values that converge to the optimum. Genetic Algorithm, which is a population-based heuristic algorithm, is one of the leading approaches in solving the problem. Within the scope of the study, a new hybrid Genetic Algorithm was proposed to solve the problem. The hybrid approach based on local search improvement in the initial population and on repairing unsuitable solutions with a new problem-specific repair operator was compared with the standard Genetic Algorithm through the solution of sample problems. When the results were examined, it was seen that the proposed hybrid Genetic Algorithm achieved higher performance in Multidimensional Knapsack Problem.

Keywords: