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

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