具有能量奖励策略的微正则退火算法  

Microcanonical Annealing Algorithm with Energy Award Strategy

作　　者：徐俊杰[1] 忻展红[2] 

机构地区：[1]安庆师范学院经济与管理学院,安徽安庆246133 [2]北京邮电大学经济管理学院,北京100876

出　　处：《小型微型计算机系统》2008年第10期1842-1844,共3页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(70473006)资助;安徽省高校自然科学研究项目(KJ2008B151)资助

摘　　要：为提高微正则退火算法求解旅行推销员问题的最终解质量,提出一种对妖的能量进行奖励的策略,在拒绝状态时增大妖所携带的能量,用以提高脱离局部极值的能力.按照能量奖励后是否做限界检查,给出了无上界约束和有上界约束两种实施方式.仿真显示无上界约束的能量奖励策略能够提高最终解的质量,而有上界约束不能提高算法性能.为加快应用该策略后的收敛速度,设计了一种容忍机制,降低了搜索到最优解时的平均目标评价次数.In order to improve the solution quality of traveling salesman problem tackling with microcanonical annealing algorithm, an energy award strategy applied on demon was proposed. It enhanced the chances of escaping from local optimum by augmenting the energy taken by demon when rejecting a possible state. Two kinds of implementations were presented, one is energy award without upper bound and the other is that with upper bound. The simulations showed that the former improved the solution qualities successfully while the latter failed on the benchmark. To quicken the convergence of the new strategy without upper bound, a tolerance mechanism was designed to attain a compromise between solution quality and convergence speed and its effect was demonstrated by the simulations.

关 键 词：旅行推销员问题 微正则退火算法 配送路径 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]