Title :
Finding improved simulated annealing schedules with genetic programming
Author :
Thonemann, Ulrich Wilhelm
Author_Institution :
Dept. of Ind. Eng. & Eng. Manage., Stanford Univ., CA, USA
Abstract :
Many combinatorial problems are too difficult to be solved optimally, and hence heuristics are used to obtain “good” solutions in “reasonable” time. A heuristic that has been successfully applied to a variety of problems is simulated annealing. However, the performance of simulated annealing strongly depends on the appropriate choice of a key parameter, the annealing schedule. Usually, researchers experiment with a number of manually created annealing schedules and then choose the one that performs best for their algorithms. This work applies genetic programming to replace this manual search. For a given problem, we search for an optimal annealing schedule. We demonstrate the potential of this new approach by optimizing the annealing schedule for one of the hardest combinatorial optimization problem, the quadratic assignment problem. We introduce a new algorithm for solving the quadratic assignment problem that performs extremely well, and we outline properties of good annealing schedules
Keywords :
combinatorial mathematics; genetic algorithms; optimisation; scheduling; simulated annealing; combinatorial optimization problem; genetic programming; heuristics; optimal annealing schedule; performance; quadratic assignment problem; simulated annealing schedules; Algorithm design and analysis; Computational modeling; Engineering management; Genetic programming; Industrial engineering; Job shop scheduling; Monte Carlo methods; Scheduling algorithm; Simulated annealing; Temperature;
Conference_Titel :
Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-1899-4
DOI :
10.1109/ICEC.1994.349919