-
题名一种求解TSP问题的动态杂交算子
被引量：3
- 1
-
-
作者
崔志华
曾建潮
徐玉斌
-
机构
太原重型机械学院系统仿真与计算机应用研究所
-
出处
《计算机工程与应用》
CSCD
北大核心
2004年第23期74-75,101,共3页
-
基金
山西省青年科学基金(编号:20041017)
太原重型机械学院青年基金资助
-
文摘
TSP(TravelingSalesmanProblem)问题是最经典的NP-hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的时间内解决大规模问题。论文在文犤5犦提出的两交换启发交叉算子的基础上,通过分析,发现该算子的杂交结果与所选择的首城市有关,因而不同的首城市的选择会大大影响该算子的效率,此外,在杂交母体范围内执行贪婪策略也导致了算法的效率较低。为此,提出了一种新的有效利用局部信息的杂交算子,该算子能够有效地保存母体信息,进一步摆脱首城市的选择问题。实例仿真证明了该算子的有效性。
-
关键词
遗传算法
TSP问题
动态杂交算子
NP-hard组合优化问题
两交换启发交叉算子
-
Keywords
genetic algorithm,TSP problem,dynamic crossover operator
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
O242.23
[自动化与计算机技术—控制科学与工程]
-
