COMBINATORIAL OPTIMIZATION WITH USE OF GUIDED EVOLUTIONARY SIMULATED ANNEALING

Feasible approaches to the task of solving NP-complete problems usuall y entails the incorporation of heuristic procedures so as to increase the efficiency of the methods used. In this paper, we propose a new te chnique, which incorporates the idea of simulated annealing into the p ractice of simulated evolution, in place of arbitrary heuristics. The proposed technique is called guided evolutionary simulated annealing ( GESA). We report on the use of GESA approach primarily for combinatori al optimization. fn addition, we report the case of function optimizat ion, treating the task as a search problem. The Traveling Salesman Pro blem is taken as a benchmark problem in the first case. Simulation res ults are reported. The results show that the GESA approach can discove r a very good near-optimum solution after examining an extremely small fraction of possible solutions. A very complicated function with many local minima is used in the second case. The results in both cases in dicate that the GESA technique is a practicable method which yields co nsistent and good near-optimal solutions, superior to simulated evolut ion.