针对广义最小生成树问题,设计了2种改进的元启发式算法来求解:单亲遗传模拟退火算法和改进的禁忌搜索算法.通过综合遗传算法和模拟退火算法的优点,提出了单亲遗传和模拟退火的混合算法,并设计了自适应选择法和自适应基因重组操作；在改进的禁忌搜索算法中,通过在2种邻域进行搜索来避免陷入局部最优.数值实验验证了算法的有效性.%Two improved meta-heuristic algorithms: partheno genetic simulated annealing algorithm and a revised tabu search algorithm, are proposed to solve the generalized minimum spanning tree (GMST). First, a hybrid algorithm of partheno genetic and simulated annealing (GASA), which takes the advantages of both genetic algorithm (GA) and the simulated annealing algorithm (SAA), is proposed for solving GMST. A self-adaptive selection and self-adaptive gene combination operator are devised for GASA. Second, an improved tabu search algorithm is also proposed for solving GMST within which the local optimum is avoided by forcing the algorithm to search the two neighborhoods of the current feasible solution area. Finally, the effectiveness of the two algorithms is proved by a numerical experiment.
展开▼
