PubMed Health⌕ Search
Home/Archive/PubMed

PubMed · 11928691

Genetic programming over context-free languages with linear constraints for the knapsack problem: first results.

Peter Bruhn·Andreas Geyer-Schulz
View original source ↗Export metadata ↓

Abstract

In this paper, we introduce genetic programming over context-free languages with linear constraints for combinatorial optimization, apply this method to several variants of the multidimensional knapsack problem, and discuss its performance relative to Michalewicz's genetic algorithm with penalty functions. With respect to Michalewicz's approach, we demonstrate that genetic programming over context-free languages with linear constraints improves convergence. A final result is that genetic programming over context-free languages with linear constraints is ideally suited to modeling complementarities between items in a knapsack problem: The more complementarities in the problem, the stronger the performance in comparison to its competitors.

Explore related subjects

Combinatorial Chemistry TechniquesEvolution, MolecularLanguageModels, GeneticModels, TheoreticalJournal ArticleReview

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Peter Bruhn, Andreas Geyer-Schulz. 2002. Genetic programming over context-free languages with linear constraints for the knapsack problem: first results.. https://doi.org/10.1162/106365602317301772

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related citations

PubMed2007

New solid support for the synthesis of 3'-oligonucleotide conjugates through glyoxylic oxime bond formation.

A novel solid support 1 was synthesized to incorporate glyoxylic aldehyde functionality at the oligonucleotide 3'-terminus. 6-mer and 11-mer oligonucleotide sequences containing 3'-glyoxylic aldehyde functionality were prepared by using this support. These modified oligonucleotides were coupled to reporters containing an aminooxy group to prepare oligonucleotide 3'-conjugates through glyoxylic oxime bond formation. The hydrolytic stability of a glyoxylic oxime linkage was also investigated. [reaction: see text].

Combinatorial Chemistry Techniques↗
PubMed2007

Chemical genetics: an evolving toolbox for target identification and lead optimization.

Chemical genetics combines chemistry with biology as a means of exploring the function of unknown proteins or identifying the proteins responsible for a particular phenotype. Chemical genetics is thus a valuable tool in the identification of novel drug targets. This chapter describes the application of chemical genetics in traditional and systems-based approaches to drug target discovery and the tools/approaches that appear most promising for guiding future pharmaceutical development.

Combinatorial Chemistry Techniques↗
PubMed2007

Protein library design and screening: working out the probabilities.

In designing protein libraries for selection, we must coordinate our capacity to create a large diversity of protein variants with the physical limitations of what we can actually screen. This chapter aims to bring the language of probabilities into the protein engineer's laboratory to answer some of our common questions: How can we most efficiently design a library? What fraction of the theoretical library diversity have we actually sampled at the end of the day? What is the probability of missing an individual of the library? Are the mutations present in the variants we have selected statistically meaningful or the product of random variation? The computation of these criteria throughout the process of experimental protein engineering will enable us to better design and evaluate the products of our libraries of protein variants.

Combinatorial Chemistry Techniques↗