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

《应用GA和PSO算法求解10城市TSP问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Word格式应用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）横坐标纵坐标城市A4044.39城市B24.3914.63城市C17.0722.93城市D22.9376.1城市E51.7194.14城市F8

2、7.3265.36城市G68.7852.19城市H84.8836.09城市I66.8325.36城市J61.9526.342使用GA算法求解2.1算法描述(1)编码和适应度函数分别用1-10表示城市A-J，然后采用自然数编码方式为TSP问题编码，例如，旅程（16289105734）表示从城市A出发分别经过了F-B-H-I-J-E-G-C-D的一次旅行。每一个问题的解及算法中的个体都可以计算相应的距离。那么种群中的最小距离和最大距离也相应的可以确定。选择种群个数为50。根据种群中个体的距离并考虑使用自适应的标定方法，定义如下的适

3、应度函数，使用此适应度函数的后面的乘方次数可以调整来改变淘汰速度。这里选择2，表示淘汰速度比较适中。(2)定义算子选择算子，根据适应度函数的大小进行选择。计算每个个体被选中的概率完美整理Word格式，以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。交叉算子，采用部分映射交叉(PartiallyMappedCrossover,PMX)方法实现算法交叉。首先选取选需要交叉的区间段，然后确定区间段的映射关系，接下来交换区间段的遗传信息，此时未换部分的遗传信息会出现不合法的情况，因此根据将

4、未换部分按映射关系进行交换。交叉率为0.9。变异算子，把一个染色体中的两个基因的交换作为变异算法。在算法中随机的产生一个染色体中需要交换的两个基因的位置，将这两个基因进行交换来实现变异。变异率为0.2。(3)算法流程根据上述的遗传算子的定义，并设置最大的迭代次数为1000，将GA算法流程叙述如下，(i)随机生成初始种群。(ii)按照本节(1)中的公式计算各个个体适应度的值。(iii)判断是否达到了最大的迭代次数。若是，算法结束，输出计算结果；若否，转到(iv)。(iv)按照本节(2)中的选择算子进行选择操作。(v)选择交叉宽度

5、并随机确定交叉切点，按照本节(2)中的交叉算子进行交叉操作。(vi)按照本节(2)中的变异算子进行变异操作。(vii)将遗传算子产生的种群作为新的种群，转到(ii)。2.2GA算法计算结果使用Matlab编程实现2.1中的算法，计算结果如下。完美整理Word格式图1GA算法过程的距离值变化图2GA算法求解的10城市TSP问题的结果最后的结果编码为（89102314567完美整理Word格式），解为H-I-J-B-C-A-D-E-F-G，距离为269.0671。从计算结果可以看出，算法迭代到300步时已经收敛到了局部的最优值。经

6、过大量的计算发现至多迭代到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等是交换子，之间的顺序是有意义的,意味着所有的交换子依

7、次作用于某解上。 若干个交换序可以合并成一个新的交换序，定义为两个交换序的合并算子。设两个交换序SS1和SS2按先后顺序作用于解S上，得到新解S’。假设另外有一个交换序SS’作用于同一解S上，能够得到形同的解S’，可定义 和属于同一等价集，在交换序等价集中，拥有最少交换子的交换序称为该等价集的基本交换序。(2)TSP问题的速度和位置更新算式根据(1)中的交换子和交换序的定义，可以根据基本的PSO算法速度更新算式和位置更新算式，重新定义如下的速度和位置更新算式，式中，、为[0,1]区间的随机数。为粒子与个体极值的交换序，以概率保

8、留；为粒子与全局极值的交换序，以概率保留。粒子的位置按照交换序进行更新。为惯性权重。(3)算法流程按照本节中的有关定义给出算法流程如下，(i)初始化粒子群，给每一个粒子一个初始解和随机的交换序。(ii)判断是否达到最大迭代次数1000。若是，算法结束，输出结果；若不是，转到(