Knowledge-based Genetic Algorithm for the 0-1 Multidimensional Knapsack Problem

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

253 Downloads (Pure)

Abstract

This paper presents an improved version of Genetic Algorithm (GA) to solve the 0-1 Multidimensional Knapsack Problem (MKP01), which is a well-known NP-hard combinatorial optimisation problem. In combinatorial optimisation problems, the best solutions have usually a common partial structure. For MKP01, this structure contains the items with a high values and low weights. The proposed algorithm called Genetic Algorithm Guided by Pretreatment information (GAGP) calculates these items and uses this information to guide the search process. Therefore, GAGP is divided into two steps, in the first, a greedy algorithm based on the efficiency of each item determines the subset of items that are likely to appear in the best solutions. In the second, this knowledge is utilised to guide the GA process. Strategies to generate the initial population and calculate the fitness function of the GA are proposed based on the pretreatment information. Also, an operator to update the efficiency of each item is suggested. The pretreatment information has been investigated using the CPLEX deterministic optimiser. In addition, GAGP has been examined on the most used MKP01 data-sets, and compared to several other approaches. The obtained results showed that the pretreatment succeeded to extract the most part of the important information. It has been shown, that GAGP is a simple but very competitive solution.
Original languageEnglish
Title of host publicationProceedings of the 2017 IEEE Congress on Evolutionary Computation (CEC)
PublisherIEEE
ISBN (Electronic)978-1509046010
ISBN (Print)978-1509046027
DOIs
Publication statusPublished - 7 Jul 2017
EventIEEE Congress on Evolutionary Computation 2017 - Donostia - San Sebastián, Spain
Duration: 5 Jun 20178 Jun 2017
http://www.cec2017.org/

Conference

ConferenceIEEE Congress on Evolutionary Computation 2017
Country/TerritorySpain
CityDonostia - San Sebastián
Period5/06/178/06/17
Internet address

Keywords

  • computational complexity
  • genetic algorithms
  • greedy algorithms
  • knapsack problems
  • search problems

Fingerprint

Dive into the research topics of 'Knowledge-based Genetic Algorithm for the 0-1 Multidimensional Knapsack Problem'. Together they form a unique fingerprint.

Cite this