Attributed Grammatical Evolution with Lookahead for the Multiple Knapsack Problem

Muhammad Rezaul Karim, Conor Ryan

Research output: Contribution to journalArticlepeer-review

Abstract

This paper presents an Attribute Grammar with Lookahead (AG+LA) approach, a technique to solve heavily constrained Multiple Knapsack Problem. This approach incorporates a form of lookahead into the mapping process of Grammatical Evolution (GE) using Attribute Grammar (AG) to focus only on feasible solutions, thereby avoiding issues such as repeated remapping and introns, both of which are limitations of previous approaches based on AG. We also present AG+LAE (AG+LA with an efficiency measure to bias the search towards the most efficient, i. e., best value, objects), the successor of AG+LA where a biasing process is incorporated using problem specific knowledge to significantly improve the performance of its predecessor, both in terms of the number of evaluations required and the quality of solutions obtained. Degenerate code, as used in DNA, is code that uses redundancy, so that different codons can represent the same thing. Many developmental systems, such as GE, use a degenerate encoding to help promote neutral mutations, that is, minor genetic changes that do not result in a phenotypic change. While early work in GE suggested that some level of degeneracy was important, it does come at the cost of increasing the size of the search space. Duplicate Elimination techniques, as opposed to degenerate encoding, are employed in decoder-based Evolutionary Algorithms to ensure that the newly generated solutions are not already contained in the current population. The results and analysis show that it is crucial to incorporate duplicate elimination to improve the performance of both approaches, while the reduced level of degeneracy is crucial only for AG+LA.

Original languageEnglish
Pages (from-to)279-302
Number of pages24
JournalMemetic Computing
Volume4
Issue number4
DOIs
Publication statusPublished - Nov 2012

Keywords

  • Attribute Grammar
  • Grammatical Evolution
  • Multiple Knapsack Problem

Fingerprint

Dive into the research topics of 'Attributed Grammatical Evolution with Lookahead for the Multiple Knapsack Problem'. Together they form a unique fingerprint.

Cite this