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

Publisher Website
Google Scholar
Abstract
This paper presents a new stochastic approach called the annealing-genetic algorithm for solving some well-known combinatorial optimization problems. This approach incorporates genetic algorithms into simulated annealing to improve the performance of simulated annealing. Our approach has the following features: 1) it can be viewed as a simulated annealing algorithm with the population-based state transition and with the genetic-operator-based quasi-equilibrium control and 2) it can be viewed as a genetic algorithm with the Boltzmann-type selection operator. The goals of efficiency in our 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 percent, for solving the set partitioning problem it is less than 0.1 percent, and for solving the traveling salesman problem it is around 3 percent. In all the test cases, the annealing-genetic approach obtained much better performance than simulated annealing did. The time complexity of the proposed algorithm is empirically O(n(2)) for all the three problems.