Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (29): 46-48.

• 研究、探讨 • Previous Articles     Next Articles

Study of hybrid genetic algorithm based on multi-step reinforcement mutation operator

LIU Fei,LV Shihui,ZHAO Zhonghua   

  1. Unit 72671 of the PLA
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-10-11 Published:2011-10-11

基于多步强化变异算子的混合遗传算法

刘 菲,吕世辉,赵中华   

  1. 中国人民解放军 72671部队

Abstract: A number of algorithms and strategies and their variations are currently being used for solving complex optimization problems.Genetic Algorithms(GAs) are one of the best strategies for solving such problems basically due to their inherent parallel search capability.An attempt is made to intermix the search properties of GA and reinforcement learning,in order to develop a hybrid algorithm which has a better searching ability and power to reach a near optimal solution.A multi-step reinforcement mutation has been incorporated as mutation criteria in a GA framework.This multi-step mutation operation is improved by the single-step mutation policy.It affects the individuals by considering multi-step evolution affection and transfers this affection back up.A number of TSP instances are used to compare the performances of the new hybrid algorithm and the classical genetic algorithm.The influence on this algorithm by discount rate is also proposed.

Key words: hybrid genetic algorithm, multi-step reinforcement mutation, reinforcement learning, Traveling Salesman Problem(TSP) instances

摘要: TSP是一类经典的NP-hard组合优化问题。通过引进多步强化变异算子MrM,提出了一种求解TSP实例的混合遗传算法MrMGA。多步强化变异是在单步强化变异策略的基础上进行了改进,通过向前考察几步个体进化效果,将该信息向回传递,影响个体变异策略。TSPLIB实例测试表明,MrMGA在求解小规模TSP实例时,其质量和求解速度都较EAX-GA有明显改进,从实验中得到折扣因子的值的变化对算法的影响。

关键词: 混合遗传算法, 多步强化变异, 强化学习, 旅行商问题(TSP)实例