Attributed Grammatical Evolution with Lookahead for the Multiple Knapsack Problem

doi:10.1007/s12293-012-0097-8

2012-11-06

PRE

Muhammad Rezaul Karim *

Conor Ryan

DOI：10.1007/s12293-012-0097-8

原文链接

原文求助

摘要

En 中文

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

Keyword:

Attribute Grammar

Grammatical Evolution

Multiple Knapsack Problem