Sami Khuri
A genetic algorithm, GENEsYs, is applied to an NPcomplete problem, the 0/1 multiple knapsack problem. The partitioning of the search space resulting from this highly constrained problem may include substantially large infeasible regions. Our implementation allows for the breeding and participation o...
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Text |
Language: | English |
Published: |
ACM Press
1994
|
Subjects: | |
Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.2713 http://ls11-www.informatik.uni-dortmund.de/people/baeck/papers/sac94.ps.gz |
id |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.51.2713 |
---|---|
record_format |
openpolar |
spelling |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.51.2713 2023-05-15T18:12:01+02:00 Sami Khuri San Jos'e Sami Khuri Thomas Back Jorg Heitkotter The Pennsylvania State University CiteSeerX Archives 1994 application/postscript http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.2713 http://ls11-www.informatik.uni-dortmund.de/people/baeck/papers/sac94.ps.gz en eng ACM Press http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.2713 http://ls11-www.informatik.uni-dortmund.de/people/baeck/papers/sac94.ps.gz Metadata may be used without restrictions as long as the oai identifier remains attached to it. http://ls11-www.informatik.uni-dortmund.de/people/baeck/papers/sac94.ps.gz text 1994 ftciteseerx 2016-01-08T09:34:23Z A genetic algorithm, GENEsYs, is applied to an NPcomplete problem, the 0/1 multiple knapsack problem. The partitioning of the search space resulting from this highly constrained problem may include substantially large infeasible regions. Our implementation allows for the breeding and participation of infeasible strings in the population. Unlike many other GA-based algorithms that are augmented with domain-specific knowledge, GENEsYs uses a simple fitness function that uses a graded penalty term to penalize infeasibly bred strings. We apply our genetic algorithm to problem instances from the literature of well known test problems and report our experimental results. These encouraging results, especially for relatively large test problems, indicate that genetic algorithms can be successfully used as heuristics for finding good solutions for highly constrained NP-complete problems. Genetic Algorithms Direct random search algorithms based on the model of organic evolution received remarka. Text sami Unknown |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
ftciteseerx |
language |
English |
description |
A genetic algorithm, GENEsYs, is applied to an NPcomplete problem, the 0/1 multiple knapsack problem. The partitioning of the search space resulting from this highly constrained problem may include substantially large infeasible regions. Our implementation allows for the breeding and participation of infeasible strings in the population. Unlike many other GA-based algorithms that are augmented with domain-specific knowledge, GENEsYs uses a simple fitness function that uses a graded penalty term to penalize infeasibly bred strings. We apply our genetic algorithm to problem instances from the literature of well known test problems and report our experimental results. These encouraging results, especially for relatively large test problems, indicate that genetic algorithms can be successfully used as heuristics for finding good solutions for highly constrained NP-complete problems. Genetic Algorithms Direct random search algorithms based on the model of organic evolution received remarka. |
author2 |
The Pennsylvania State University CiteSeerX Archives |
format |
Text |
author |
San Jos'e Sami Khuri Thomas Back Jorg Heitkotter |
spellingShingle |
San Jos'e Sami Khuri Thomas Back Jorg Heitkotter Sami Khuri |
author_facet |
San Jos'e Sami Khuri Thomas Back Jorg Heitkotter |
author_sort |
San Jos'e |
title |
Sami Khuri |
title_short |
Sami Khuri |
title_full |
Sami Khuri |
title_fullStr |
Sami Khuri |
title_full_unstemmed |
Sami Khuri |
title_sort |
sami khuri |
publisher |
ACM Press |
publishDate |
1994 |
url |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.2713 http://ls11-www.informatik.uni-dortmund.de/people/baeck/papers/sac94.ps.gz |
genre |
sami |
genre_facet |
sami |
op_source |
http://ls11-www.informatik.uni-dortmund.de/people/baeck/papers/sac94.ps.gz |
op_relation |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.2713 http://ls11-www.informatik.uni-dortmund.de/people/baeck/papers/sac94.ps.gz |
op_rights |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
_version_ |
1766184598609330176 |