Guided genetic algorithm for the multidimensional knapsack problem

Abdellah Rezoug, Mohamed Bader-El-Den, Dalila Boughaci

Research output: Contribution to journalArticlepeer-review

287 Downloads (Pure)

Abstract

Genetic Algorithm (GA) has emerged as a powerful method for solving a wide range of combinatorial optimisation problems in many fields. This paper presents a hybrid heuristic approach named Guided Genetic Algorithm (GGA) for solving the Multidimensional Knapsack Problem (MKP). GGA is a two-step memetic algorithm composed of a data pre-analysis and a modified GA. The pre-analysis of the problem data is performed using an efficiency-based method to extract useful information. This prior knowledge is integrated as a guide in a GA at two stages: to generate the initial population and to evaluate the produced offspring by the fitness function. Extensive experimentation was carried out to examine GGA on the MKP. The main GGA parameters were tuned and a comparative study with other methods was conducted on well-known MKP data. The real impact of GGA was checked by a statistical analysis using ANOVA, t-Test and Welch's t-Test. The obtained results showed that the proposed approach largely improved standard GA and was highly competitive with other optimisation methods.
Original languageEnglish
Pages (from-to)29-42
Number of pages14
JournalMemetic Computing
Volume10
Issue number1
Early online date10 May 2017
DOIs
Publication statusPublished - 1 Mar 2018

Keywords

  • genetic algorithm
  • hybrid heuristic
  • memetic algorithm
  • multidimensional knapsack problem
  • core concept
  • guided genetic algorithm

Fingerprint

Dive into the research topics of 'Guided genetic algorithm for the multidimensional knapsack problem'. Together they form a unique fingerprint.

Cite this