Attributed Grammatical Evolution with Lookahead for the Multiple Knapsack Problem

Created by W.Langdon from gp-bibliography.bib Revision:1.7615

@Article{Karim:2012:MC,

• author = "Muhammad Rezaul Karim and Conor Ryan",
• title = "Attributed Grammatical Evolution with Lookahead for the Multiple Knapsack Problem",
• journal = "Memetic Computing",
• year = "2012",
• volume = "4",
• number = "4",
• pages = "279--302",
• keywords = "genetic algorithms, genetic programming, Grammatical Evolution, Attribute Grammar, Multiple Knapsack Problem",
• ISSN = "1865-9284",
• publisher = "Springer-Verlag",
• language = "English",
• DOI = "doi:10.1007/s12293-012-0097-8",
• size = "24 pages",
• 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 look ahead 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.",
• notes = "special issue on the NICSO 2011 workshop",

}

Genetic Programming entries for Muhammad Rezaul Karim Conor Ryan

Citations