DocumentCode :
1013868
Title :
Applying the genetic approach to simulated annealing in solving some NP-hard problems
Author :
Lin, Feng-Tse ; Kao, Cheng-Yan ; Hsu, Ching-Chi
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Volume :
23
Issue :
6
fYear :
1993
Firstpage :
1752
Lastpage :
1767
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%
Keywords :
combinatorial mathematics; computational complexity; genetic algorithms; simulated annealing; Boltzmann-type selection operator; NP-hard problems; annealing-genetic algorithm; combinatorial optimization problems; genetic-operator-based quasi-equilibrium control; multiconstraint zero-one knapsack problem; polynomial function; population-based state transition; set partitioning problem; simulated annealing; stochastic approach; traveling salesman problem; Computational modeling; Computer science; Error analysis; Genetic algorithms; NP-hard problem; Polynomials; Simulated annealing; Stochastic processes; Temperature control; Temperature distribution;
fLanguage :
English
Journal_Title :
Systems, Man and Cybernetics, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9472
Type :
jour
DOI :
10.1109/21.257766
Filename :
257766
Link To Document :
بازگشت