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

A genetic model: analysis and application to MAXSAT.

A Bertoni1, P Campadelli, M Carpentieri

  • 1Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, Italy. bertoni@ds.unimi.it

Evolutionary Computation
|September 23, 2000
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

Vaginal temperature of lactating cows during heat waves or normal summer day and effect of additional daily cooling treatments as heat load mitigation strategy.

International journal of biometeorology·2023
Same author

Clinical impact of high platelet reactivity in patients with atrial fibrillation and concomitant percutaneous coronary intervention on dual or triple antithrombotic therapy.

Journal of thrombosis and thrombolysis·2023
Same author

Polychromatic emission in a wide energy range from InP-InAs-InP multi-shell nanowires.

Nanotechnology·2019
Same author

Clinical features and outcomes of hepatocellular carcinoma in Caucasian cirrhotic patients on long-term analogue therapy for hepatitis B.

Alimentary pharmacology & therapeutics·2018
Same author

Rate of entropy model for irreversible processes in living systems.

Scientific reports·2017
Same author

Spin-Hall nano-oscillator with oblique magnetization and Dzyaloshinskii-Moriya interaction as generator of skyrmions and nonreciprocal spin-waves.

Scientific reports·2016
Same journal

Computing Optimal Populations for Binary Problems using Logic Minimization.

Evolutionary computation·2026
Same journal

Enhancing Generalization and Scalability for Multi-Objective Optimization with Population Pre-Training.

Evolutionary computation·2026
Same journal

XCS for Sequential Perceptual Aliasing in Multi-Step Decision Making.

Evolutionary computation·2026
Same journal

A dynamic multi-objective evolutionary algorithm using dual-space prediction and surrogate-based sampling.

Evolutionary computation·2026
Same journal

Adapting MOEA/D to CMA-ES for Dealing with Ill-conditioned Multiobjective Problems.

Evolutionary computation·2026
Same journal

Editorial of the Special Issue: Parallel Problem Solving from Nature PPSN 2024 Extended Versions of Best Paper Candidates.

Evolutionary computation·2026
See all related articles

This study introduces a genetic model for combinatorial optimization, deriving deterministic dynamics and developing an approximation algorithm. The algorithm proves optimal for Max Ek-Sat problems (k>=3) in worst-case analysis.

Area of Science:

  • Computational intelligence
  • Theoretical computer science
  • Mathematical optimization

Background:

  • Combinatorial optimization problems are computationally challenging.
  • Genetic models offer a framework for tackling complex optimization tasks.
  • Understanding the dynamics of such models is crucial for algorithm design.

Purpose of the Study:

  • To investigate a genetic model incorporating recombination and mutation for combinatorial optimization.
  • To derive and analyze the deterministic dynamics of the model in the thermodynamic limit.
  • To design and evaluate a novel approximation algorithm for combinatorial optimization problems, specifically Max Ek-Sat.

Main Methods:

  • Derivation of deterministic dynamics equations in the thermodynamic limit.

Related Experiment Videos

  • Characterization of attractors for small mutation rates.
  • Design of a general approximation algorithm for combinatorial optimization.
  • Application and analysis of the algorithm on the Max Ek-Sat problem.

    • Main Results:

    • The deterministic dynamics equations were derived.
    • Attractors were characterized under specific mutation rate conditions.
    • A general approximation algorithm was developed and applied to Max Ek-Sat.
    • The algorithm demonstrated worst-case optimality for k >= 3 and competitive average-case performance for Max E3-Sat.

    Conclusions:

    • The genetic model provides a robust framework for combinatorial optimization.
    • The developed approximation algorithm is effective, particularly for Max Ek-Sat.
    • Further experimental comparisons validate the algorithm's practical performance against existing techniques.