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

Memetic algorithms for the unconstrained binary quadratic programming problem.

Peter Merz1, Kengo Katayama

  • 1Department of Computer Science, University of Kaiserslautern, P.O. Box 3049, D-67653 Kaiserslautern, Germany. peter.merz@ieee.org

Bio Systems
|November 24, 2004
PubMed
Summary
This summary is machine-generated.

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

Advanced fitness landscape analysis and the performance of memetic algorithms.

Evolutionary computation·2004
Same author

Analysis of gene expression profiles: an application of memetic algorithms to the minimum sum-of-squares clustering problem.

Bio Systems·2003
Same journal

Ruliological Resilience: Pattern Restoration and Robustness in Wolfram Patterns. A Basis for Regeneration, Not Just in Cone Shells?

Bio Systems·2026
Same journal

The quantum-to-classical transducer: A thermodynamic and quantum mechanical framework for the emergence of bioenergetics.

Bio Systems·2026
Same journal

Forward-backward gene expression binarization for boolean state inference over a known regulatory network.

Bio Systems·2026
Same journal

Partial-label metric ceilings for evaluating gene regulatory networks inferred from single-cell foundation models.

Bio Systems·2026
Same journal

The impedance mismatch theory: A non-equilibrium thermodynamic framework for a shared energetic stress pathway in neurodegeneration.

Bio Systems·2026
Same journal

Immune signal-status misclassification: A theoretical framework for biological status assignment and failed status resolution.

Bio Systems·2026
See all related articles

A new memetic algorithm, combining local search with a novel "innovative variation" operator, efficiently solves large unconstrained binary quadratic programming problems (BQP). This evolutionary approach finds top solutions quickly and frequently.

Area of Science:

  • Optimization
  • Computer Science
  • Computational Intelligence

Background:

  • The unconstrained binary quadratic programming problem (BQP) is a computationally challenging optimization task.
  • Evolutionary algorithms (EAs) are often used for complex optimization problems, but their effectiveness can be enhanced with local search components.

Purpose of the Study:

  • To introduce and evaluate a novel memetic algorithm for solving the BQP.
  • To investigate the suitability of recombination-based variation operators within EAs that incorporate local search for BQP instances.

Main Methods:

  • Fitness landscape analysis was performed to understand BQP characteristics.
  • A memetic algorithm was developed, integrating a randomized k-opt local search with a new "innovative variation" operator.

Related Experiment Videos

  • The innovative variation operator introduces novel genetic material not present in parents, differing from traditional crossover.

    • Main Results:

    • Experimental analysis confirmed that recombination-based operators are effective for EAs with local search on BQP.
    • The proposed memetic algorithm demonstrated high performance on 35 public BQP instances.
    • The algorithm achieved best-known solutions for large BQP instances rapidly and with high success rates.

    Conclusions:

    • The developed memetic algorithm is highly effective for solving the unconstrained binary quadratic programming problem.
    • The innovative variation operator is a key component contributing to the algorithm's superior performance, especially on large-scale BQPs.
    • This approach offers a more effective solution for BQP compared to existing methods, particularly for instances with 1000 or 2500 binary variables.