Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

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

Peter Bruhn1, Andreas Geyer-Schulz

  • 1Department of Information Business, Vienna University of Economics and Business Administration, Austria. Peter.Bruhn@wu-wien.ac.at

Evolutionary Computation
|April 4, 2002
PubMed
Summary

Genetic programming over context-free languages with linear constraints enhances convergence for combinatorial optimization problems like the multidimensional knapsack problem. This method excels when modeling item complementarities, outperforming existing algorithms.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Assessment of Dementia in Individuals with Dual Sensory Loss: Application of a Tactile Test Battery.

Dementia and geriatric cognitive disorders extra·2018
Same author

Early resuscitation with lyophilized plasma provides equal neuroprotection compared with fresh frozen plasma in a large animal survival model of traumatic brain injury and hemorrhagic shock.

The journal of trauma and acute care surgery·2016
Same author

Behavioral variant of frontotemporal dementia mimicking Huntington's disease.

International psychogeriatrics·2010
Same author

Heart rate variability and intima media thickness.

International journal of behavioral medicine·2006

Area of Science:

  • Computer Science
  • Artificial Intelligence
  • Operations Research

Background:

  • Combinatorial optimization problems, such as the multidimensional knapsack problem, are computationally challenging.
  • Existing genetic algorithms, like Michalewicz's approach with penalty functions, have limitations in convergence and modeling complex relationships.

Purpose of the Study:

  • To introduce and evaluate a novel approach: genetic programming over context-free languages with linear constraints (GP-CFL-LC).
  • To assess the performance of GP-CFL-LC for combinatorial optimization, specifically for multidimensional knapsack problem variants.
  • To compare GP-CFL-LC against established methods, particularly Michalewicz's genetic algorithm.

Main Methods:

  • Genetic programming over context-free languages with linear constraints (GP-CFL-LC) was developed and applied.

Related Experiment Videos

  • The method was tested on several variations of the multidimensional knapsack problem.
  • Performance was benchmarked against Michalewicz's genetic algorithm using penalty functions.

    • Main Results:

    • GP-CFL-LC demonstrated improved convergence compared to Michalewicz's genetic algorithm.
    • The effectiveness of GP-CFL-LC was particularly pronounced in problems with significant complementarities between items.
    • Stronger complementarities in knapsack problems led to superior performance of GP-CFL-LC relative to competitors.

    Conclusions:

    • Genetic programming over context-free languages with linear constraints offers a powerful new tool for combinatorial optimization.
    • GP-CFL-LC is especially well-suited for problems involving item complementarities, providing a competitive advantage.
    • This approach advances the field by offering enhanced convergence and superior modeling capabilities for specific problem structures.