The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems

DOI10.1007/s10898-011-9790-2zbMath1257.90050OpenAlexW1980158661MaRDI QIDQ1928267

Yuren Zhou, Xinsheng Lai

Publication date: 3 January 2013

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-011-9790-2

zbMATH Keywords

Markov chainsatisfiabilityexpected fitnesssuccess ratio

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Boolean programming (90C09)

Uses Software

• UnitWalk

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Towards an analytic framework for analysing the computation time of evolutionary algorithms
• A comparative runtime analysis of heuristic algorithms for satisfiability problems
• On the analysis of the \((1+1)\) evolutionary algorithm
• UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
• Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP
• A new approach to estimating the expected first hitting time of evolutionary algorithms
• When is Eaton's Markov chain irreducible?
• GRASP with path relinking for the weighted MAXSAT problem
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• The time complexity of maximum matching by simulated annealing
• Theory and Applications of Satisfiability Testing
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• The complexity of theorem-proving procedures
• Drift analysis and average time complexity of evolutionary algorithms