Applying the genetic approach to simulated annealing in solving some NP-hard problems

Abstract

A stochastic approach called the annealing-genetic algorithm is presented for solving some well-known combinatorial optimization problems. This approach incorporates genetic algorithms into simulated annealing to improve the performance of simulated annealing. The authors' approach can be viewed as a simulated annealing algorithm with population-based state transition and with genetic-operator-based quasi-equilibrium control and as a genetic algorithm with the Boltzmann-type selection operator. The goals of efficiency in the algorithm are (1) the gap between final solution and the optimal solution should be around 3% or less, and (2) the computation time should be bounded by a polynomial function of the problem size. Empirically, the error rate of the proposed annealing-genetic algorithm for solving the multiconstraint zero-one knapsack problem is less than 1%, for solving the set partitioning problem is less than 0.1%, and for solving the traveling salesman problem is around 3%.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Keywords

Affiliated Institutions

• National Taiwan University TW
• Chinese Culture University TW

Related Publications