A New Genetic Algorithm for Multiple-Choice Multidimensional Knapsack Problem

Heikal, A. F.; Rasmy, M. H.; Tharwat, A. A.; El-Beltagy, M. A.

doi:10.21608/iceeng.2010.33055

A New Genetic Algorithm for Multiple-Choice Multidimensional Knapsack Problem

Document Type : Original Article

Authors

¹ Egyptian Armed Forces.

² Faculty of Computers and Information, Cairo University, Cairo, Egypt.

10.21608/iceeng.2010.33055

Abstract

Abstract:
A New Genetic Algorithm (NGA) for solving the Multiple Choice Multidimensional
Knapsack Problem (MMKP) is presented in this paper. The MMKP can be applied to
solve a wide variety of real life problems i.e., in any area where tasks must be scheduled
or budgeted. This paper introduces NGA algorithm that hybridize the solution
construction mechanism of GA operators (hybrid selection operator, hybrid cross-over
operator and new hybrid mutation operator) for permutation encoding genetic algorithm.
In addition we present a strong initial population is created by the Maximizing Value
per Resources Consumption (MVRC) heuristic algorithm. The experimental results
show that the method is very efficient and competitive to solve the MMKP compared
with the better existing methods

Keywords