6533b7d0fe1ef96bd125b6a5

RESEARCH PRODUCT

Influence of rounding errors on the quality of heuristic optimization algorithms

Martin RansbergerIngo MorgensternJohannes J. Schneider

subject

Statistics and ProbabilityMathematical optimizationHeuristic (computer science)Simulated annealingRound-off errorCondensed Matter PhysicsGreedy algorithmTravelling salesman problemMetaheuristicGlobal optimizationSmoothingMathematics

description

Abstract Search space smoothing and related heuristic optimization algorithms provide an alternative approach to simulated annealing and its variants: while simulated annealing traverses barriers in the energy landscape at finite temperatures, search space smoothing intends to remove these barriers, so that a greedy algorithm is sufficient to find the global minimum. Several formulas for smoothing the energy landscape have already been applied, one of them making use of the finite numerical precision on a computer. In this paper, we thoroughly investigate the effect of finite numerical accuracy on the quality of results achieved with heuristic optimization algorithms. We present computational results for the traveling salesman problem.

yearjournalcountryeditionlanguage
2011-07-01Physica A: Statistical Mechanics and its Applications
https://doi.org/10.1016/j.physa.2011.02.037