应用GA和PSO算法求解10城市TSP
问题
1 问题描述
旅行团计划近期在城市A、B、C、D、E、F、G、H、I和J共10个城市间进行一次周游旅行，为了尽量节省旅行开支，希望能找到一条里程数最少或相对较少的旅行路线。
问题1，给定10个城市之间的公路里程如表1所示，并要求使用GA算法求解优化问题。
问题2，与问题1数据相同，要求使用PSO算法求解优化问题。 表1 城市位置坐标（单位：km） 横坐标 40 24.39 17.07 22.93 51.71 87.32 68.78 84.88 66.83 61.95 44.39 14.63 22.93 76.1 94.14 65.36 52.19 36.09 25.36 26.34 纵坐标 城市A 城市B 城市C 城市D 城市E 城市F 城市G 城市H 城市I 城市J 2 使用GA算法求解
2.1 算法描述
(1) 编码和适应度函数
分别用1-10表示城市A-J，然后采用自然数编码方式为TSP问题编码，例如，旅程（1 6 2 8 9 10 5 7 3 4）表示从城市A出发分别经过了F-B-H-I-J-E-G-C-D的一次旅行。每一个问题的解及算法中的个体都可以计算相应的距离。那么种群中的最小距离和最大距离也相应的可以确定。选择种群个数为50。
根据种群中个体的距离并考虑使用自适应的标定方法，定义如下的适应度函数，
f(xi)?(1?xi距离?种群最小距离)2
种群最大距离-种群最小距离使用此适应度函数的后面的乘方次数可以调整来改变淘汰速度。这里选择2，
表示淘汰速度比较适中。 (2) 定义算子
选择算子，根据适应度函数的大小进行选择。计算每个个体被选中的概率
p(xi)?f(xi)?f(x)ii?1N，以各个个体所分配到的概率值作为其遗传到下一代的概率，基
于这些概率用赌盘选择法来产生下一代群体。
交叉算子，采用部分映射交叉(Partially Mapped Crossover, PMX)方法实现算法交叉。首先选取选需要交叉的区间段，然后确定区间段的映射关系，接下来交换区间段的遗传信息，此时未换部分的遗传信息会出现不合法的情况，因此根据将未换部分按映射关系进行交换。交叉率为0.9。
变异算子，把一个染色体中的两个基因的交换作为变异算法。在算法中随机的产生一个染色体中需要交换的两个基因的位置，将这两个基因进行交换来实现变异。变异率为0.2。 (3) 算法流程
根据上述的遗传算子的定义，并设置最大的迭代次数为1000，将GA算法流程叙述如下，
(i) 随机生成初始种群。
(ii) 按照本节(1)中的公式计算各个个体适应度的值。
(iii) 判断是否达到了最大的迭代次数。若是，算法结束，输出计算结果；若否，转到(iv)。
(iv) 按照本节(2)中的选择算子进行选择操作。
(v) 选择交叉宽度并随机确定交叉切点，按照本节(2)中的交叉算子进行交叉操作。
(vi) 按照本节(2)中的变异算子进行变异操作。
(vii) 将遗传算子产生的种群作为新的种群，转到(ii)。 2.2 GA算法计算结果
使用Matlab编程实现2.1中的算法，计算结果如下。
GA算法过程380360340距离值3203002802600100200300400500600迭代次数7008009001000
图1 GA算法过程的距离值变化
GA算法求解10个城市TSP问题规划路径100规划路径90807060
km5040302010 1020304050km60708090 图2 GA算法求解的10城市TSP问题的结果 最后的结果编码为（8 9 10 2 3 1 4 5 6 7），解为H-I-J-B-C-A-D-E-F-G，距离
为269.0671。
从计算结果可以看出，算法迭代到300步时已经收敛到了局部的最优值。经过大量的计算发现至多迭代到300步，算法收敛到局部最优值。经过进一步的验证发现，这个局部最优解也是全局最优解。
3 使用PSO算法求解
3.1 算法描述
(1)TSP问题的交换子和交换序
设n个节点的TSP问题的解序列为s=(ai)，i=1…n。定义交换子SO(i1,i2)为交换解S中的点ai1和ai2，则S’=S+SO(i1,i2)为解S经算子SO(i1,i2)操作后的新解。
一个或多个交换子的有序队列就是交换序，记作SS，SS=(SO1,SO2,…SON)。其中，SO1,…,SON等是交换子，之间的顺序是有意义的, 意味着所有的交换子依次作用于某解上。
若干个交换序可以合并成一个新的交换序，定义?为两个交换序的合并算子。设两个交换序SS1和SS2按先后顺序作用于解S上，得到新解S’。假设另外有一个交换序SS’作用于同一解S上，能够得到形同的解S’，可定义
SS'?SS1?SS2
SS'和SS1?SS2属于同一等价集，在交换序等价集中，拥有最少交换子的交
换序称为该等价集的基本交换序。
(2) TSP问题的速度和位置更新算式
根据(1)中的交换子和交换序的定义，可以根据基本的PSO算法速度更新算式和位置更新算式，重新定义如下的速度和位置更新算式，
???vid??(pid?xid)??(pgd?xid)?vid ????xid?xid?vid式中，?、?为[0,1]区间的随机数。pid?xid为粒子与个体极值的交换序，以概率??进保留；pgd?xid为粒子与全局极值的交换序，以概率?保留。粒子的位置按照交换序vid行更新。?为惯性权重。
(3) 算法流程
按照本节中的有关定义给出算法流程如下，
(i) 初始化粒子群，给每一个粒子一个初始解xid和随机的交换序vid。
(ii) 判断是否达到最大迭代次数1000。若是，算法结束，输出结果；若不是，转到(iii)。
(iii) 根据粒子当前位置计算下一个新解：
(a) 计算A=pid?xid，A是一个基本交换序，表示A作用于xid得到pid； (b) 计算B=pgd?xid，B是一个基本交换序；
(c) 按照(2)中的公式更新速度和位置。 (d) 如果得到了更好的个体位置，更新pid。
(iv) 如果得到了更好的群体位置，更新pgd。
3.2 PSO算法的计算结果
编程实现3.1中的算法，计算结果如下。计算程序见附录。
PSO算法过程380360340距离值3203002802600100200300400500600迭代次数7008009001000
图3 PSO算法过程的距离值变化