单亲遗传模拟退火及在组合优化问题中的应用  

Parthenon-Genetic Simulated Annealing Algorithm and Its Application in Combinatorial Optimization Problems

作　　者：曹恒智[1] 余先川[1] 

机构地区：[1]北京师范大学信息科学与技术学院,北京100875

出　　处：《北京邮电大学学报》2008年第3期38-41,共4页Journal of Beijing University of Posts and Telecommunications

基　　金：国家自然科学基金项目(4037212960602035);北京市自然科学基金项目(4062020);教育部新世纪优秀人才支持计划项目

摘　　要：基于模拟退火算法(SA)、遗传算法(GA)、单亲遗传算法(PGA)、遗传模拟退火算法(SAGA)理论的优缺点,比照SAGA,并根据SA和PGA的优势互补性,提出了一种融合SA和PGA的新算法,即单亲遗传模拟退火算法(SAPGA).结合SA、PGA的优点,对PGA中每一代操作内部的基因重组操作进行了改进,同时改变了传统的降温方式及在两代操作之间加入的染色体按适应度函数大小排列的过程.用3组城市数据的旅行商问题(TSP)对上述5种算法进行了仿真实验,结果表明,SAPGA的平均最优解始终最小,收敛所用时间始终最短.Based on theories of simulated annealing（SA） .genetic algorithm（GA）.parthenon-genetic algorithm（PGA） and simulated annealing genetic algorithm（SAGA）, the major merits and shortcomings of SA.GA and PGA are analyzed. According to the merits complementary nature of SA and PGA, a new algorithm parthenon-genetic simulated annealing algorithm is proposed. The synthesizing of the merits of the two algorithms, reconstruction operation of gene in every generation in PGA has been improved. The traditional cooling method has been improved too. Between the operations of two generations, the algorithm adds a process which sorts the chromosomes in according to fitness function. In experiments three groups city data＇s traveling salesman problem （TSP） problems with the five algorithms mentioned above are used. It shows that the SAPGA＇ s average optimal solution is the least, and the convergence time is the shortest.

关 键 词：旅行商问题 遗传算法 单亲遗传算法 模拟退火算法 组合优化 

分 类 号：O242.23[理学—计算数学] TP391.72[理学—数学]