A new approach to solving 0-1 multiconstraint knapsack problems using attribute grammar with lookahead

Muhammad Rezaul Karim; Conor Ryan

doi:10.1007/978-3-642-20407-4_22

A new approach to solving 0-1 multiconstraint knapsack problems using attribute grammar with lookahead

Muhammad Rezaul Karim, Conor Ryan

Department of Computer Science & Information Systems

University of Limerick

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In this paper, we introduce a new approach to genotype-phenotype mapping for Grammatical Evolution (GE) using an attribute grammar (AG) to solve 0-1 multiconstraint knapsack problems. Previous work on AGs dealt with constraint violations through repeated remapping of non-terminals, which generated many introns, thus decreasing the power of the evolutionary search. Our approach incorporates a form of lookahead into the mapping process using AG to focus only on feasible solutions and so avoid repeated remapping and introns. The results presented in this paper show that the proposed approach is capable of obtaining high quality solutions for the tested problem instances using fewer evaluations than existing methods.

Original language	English
Title of host publication	Genetic Programming - 14th European Conference, EuroGP 2011, Proceedings
Pages	250-261
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-20407-4_22
Publication status	Published - 2011
Event	14th European Conference on Genetic Programming, EuroGP 2011 - Torino, Italy Duration: 27 Apr 2011 → 29 Apr 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6621 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th European Conference on Genetic Programming, EuroGP 2011
Country/Territory	Italy
City	Torino
Period	27/04/11 → 29/04/11

Access to Document

10.1007/978-3-642-20407-4_22

Cite this

Karim, M. R., & Ryan, C. (2011). A new approach to solving 0-1 multiconstraint knapsack problems using attribute grammar with lookahead. In Genetic Programming - 14th European Conference, EuroGP 2011, Proceedings (pp. 250-261). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6621 LNCS). https://doi.org/10.1007/978-3-642-20407-4_22

Karim, Muhammad Rezaul ; Ryan, Conor. / A new approach to solving 0-1 multiconstraint knapsack problems using attribute grammar with lookahead. Genetic Programming - 14th European Conference, EuroGP 2011, Proceedings. 2011. pp. 250-261 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{bba9926574184d02904765a08903e15a,

title = "A new approach to solving 0-1 multiconstraint knapsack problems using attribute grammar with lookahead",

abstract = "In this paper, we introduce a new approach to genotype-phenotype mapping for Grammatical Evolution (GE) using an attribute grammar (AG) to solve 0-1 multiconstraint knapsack problems. Previous work on AGs dealt with constraint violations through repeated remapping of non-terminals, which generated many introns, thus decreasing the power of the evolutionary search. Our approach incorporates a form of lookahead into the mapping process using AG to focus only on feasible solutions and so avoid repeated remapping and introns. The results presented in this paper show that the proposed approach is capable of obtaining high quality solutions for the tested problem instances using fewer evaluations than existing methods.",

author = "Karim, {Muhammad Rezaul} and Conor Ryan",

year = "2011",

doi = "10.1007/978-3-642-20407-4_22",

language = "English",

isbn = "9783642204067",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "250--261",

booktitle = "Genetic Programming - 14th European Conference, EuroGP 2011, Proceedings",

note = "14th European Conference on Genetic Programming, EuroGP 2011 ; Conference date: 27-04-2011 Through 29-04-2011",

}

Karim, MR & Ryan, C 2011, A new approach to solving 0-1 multiconstraint knapsack problems using attribute grammar with lookahead. in Genetic Programming - 14th European Conference, EuroGP 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6621 LNCS, pp. 250-261, 14th European Conference on Genetic Programming, EuroGP 2011, Torino, Italy, 27/04/11. https://doi.org/10.1007/978-3-642-20407-4_22

A new approach to solving 0-1 multiconstraint knapsack problems using attribute grammar with lookahead. / Karim, Muhammad Rezaul; Ryan, Conor.
Genetic Programming - 14th European Conference, EuroGP 2011, Proceedings. 2011. p. 250-261 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6621 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A new approach to solving 0-1 multiconstraint knapsack problems using attribute grammar with lookahead

AU - Karim, Muhammad Rezaul

AU - Ryan, Conor

PY - 2011

Y1 - 2011

N2 - In this paper, we introduce a new approach to genotype-phenotype mapping for Grammatical Evolution (GE) using an attribute grammar (AG) to solve 0-1 multiconstraint knapsack problems. Previous work on AGs dealt with constraint violations through repeated remapping of non-terminals, which generated many introns, thus decreasing the power of the evolutionary search. Our approach incorporates a form of lookahead into the mapping process using AG to focus only on feasible solutions and so avoid repeated remapping and introns. The results presented in this paper show that the proposed approach is capable of obtaining high quality solutions for the tested problem instances using fewer evaluations than existing methods.

AB - In this paper, we introduce a new approach to genotype-phenotype mapping for Grammatical Evolution (GE) using an attribute grammar (AG) to solve 0-1 multiconstraint knapsack problems. Previous work on AGs dealt with constraint violations through repeated remapping of non-terminals, which generated many introns, thus decreasing the power of the evolutionary search. Our approach incorporates a form of lookahead into the mapping process using AG to focus only on feasible solutions and so avoid repeated remapping and introns. The results presented in this paper show that the proposed approach is capable of obtaining high quality solutions for the tested problem instances using fewer evaluations than existing methods.

UR - http://www.scopus.com/inward/record.url?scp=79955763523&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-20407-4_22

DO - 10.1007/978-3-642-20407-4_22

M3 - Conference contribution

AN - SCOPUS:79955763523

SN - 9783642204067

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 250

EP - 261

BT - Genetic Programming - 14th European Conference, EuroGP 2011, Proceedings

T2 - 14th European Conference on Genetic Programming, EuroGP 2011

Y2 - 27 April 2011 through 29 April 2011

ER -

Karim MR, Ryan C. A new approach to solving 0-1 multiconstraint knapsack problems using attribute grammar with lookahead. In Genetic Programming - 14th European Conference, EuroGP 2011, Proceedings. 2011. p. 250-261. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-20407-4_22

A new approach to solving 0-1 multiconstraint knapsack problems using attribute grammar with lookahead

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this