用有指导的进化模拟退火法解组合优化问题

Combinatorial Optimization with Use of Guided Evolutionary Simulated Annealing

基于模拟退火和模拟进化思想，提出了一种解决组合优化问题的新方法：有指导的进化模拟退火法（ＧＥＳＡ）．该方法允许问题的多个解同时存在，这些解之间进行局部或全部的比较和竞争，然后指导越来越多的搜索进入可行解的范围内．用ＧＥＳＡ方法求解两个典型的组合优化问题：旅行商（ＴＳＰ）和作业调度（ＳＣＰ）问题．结果表明，此方法优于单纯的模拟退火方法．

Incorperating the idea of simulated annealling into the practice of simulated evolution,a new technique called guided evolutionary simulated annealing (GESA) is proposed.The approach allows many candidate solutions to be ′alive′ at the same time.There is local competition and global competition and more and more search resources are guided into promising regions.Simulated annealing avoids entrapment in local minima.Two examples of travelling salesman problem and job scheduling problem are investigated.The results obtained with GESA are superior to those obtained with a simulated annealing.