应用GA和PSO算法求解10城市TSP问题.doc

- -

应用 GA 和 PSO 算法求解 10 城市 TSP

问题

1 问题描述

旅行团方案近期在城市 A、B、C、D、E、F、G、H、I 和 J 共 10 个城市间

进展一次周游旅行，为了尽量节省旅行开支，希望能找到一条里程数最少或相

对较少的旅行路线。

问题 1，给定 10 个城市之间的公路里程如表 1 所示，并要求使用 GA 算法

城市 B

24.39 14.63

城市 C

17.07 22.93

城市 D

22.93 76.1

城市 E

51.71 94.14

城市 F

87.32 65.36

61.95 26.34

2 使用 GA 算法求解

2.1 算法描述

如，旅程〔1 6 2 89105734〕表示从城市 A 出发分别经过了 F-B-H-I-J-E-G-

C-D 的一次旅行。每一个问题的解及算法中的个体都可以计算相应的距离。那

么种群中的最小距离和最大距离也相应的可以确定。选择种群个数为 50。

- -

基于这些概率用赌盘选择法来产生下一代群体。

实现算法穿插。首先选取选需要穿插的区间段，然后确定区间段的映射关系，

接下来交换区间段的遗传信息，此时未换局部的遗传信息会出现不合法的情况，

因此根据将未换局部按映射关系进展交换。穿插率为 0.9。

机的产生一个染色体中需要交换的两个基因的位置，将这两个基因进展交换来

实现变异。变异率为 0.2。

插操作。

2.2GA 算法计算结果

- -