Yip P C, Pao Y H
Dept. of Electr. Eng. and Appl. Phys., Case Western Reserve Univ., Cleveland, OH.
IEEE Trans Neural Netw. 1995;6(2):290-5. doi: 10.1109/72.363466.
Feasible approaches to the task of solving NP-complete problems usually entails the incorporation of heuristic procedures so as to increase the efficiency of the methods used. We propose a new technique, which incorporates the idea of simulated annealing into the practice 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 combinatorial optimization. In addition, we report the case of function optimization, treating the task as a search problem. The traveling salesman problem is taken as a benchmark problem in the first case. Simulation results are reported. The results show that the GESA approach can discover 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 indicate that the GESA technique is a practicable method which yields consistent and good near optimal solutions, superior to simulated evolution.
解决NP完全问题任务的可行方法通常需要纳入启发式程序，以提高所使用方法的效率。我们提出了一种新技术，该技术将模拟退火的思想融入模拟进化实践中，以取代任意启发式方法。所提出的技术称为引导进化模拟退火（GESA）。我们报告了GESA方法主要用于组合优化的情况。此外，我们报告了函数优化的案例，将该任务视为一个搜索问题。在第一个案例中，旅行商问题被用作基准问题。报告了模拟结果。结果表明，GESA方法在检查了极小部分可能的解决方案后，能够发现非常好的近似最优解。在第二个案例中，使用了一个具有许多局部最小值的非常复杂的函数。两个案例的结果都表明，GESA技术是一种可行的方法，能够产生一致且良好的近似最优解，优于模拟进化。
