应用GA和PSO算法求解10城市TSP问题.pdf-资料库

应用 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）城市 A 城市 B 城市 C 城市 D 城市 E 城市 F 城市 G 城市 H 城市 I 城市 J 40 24.39 17.07 22.93 51.71 87.32 68.78 84.88 66.83 61.95 2 使用 GA 算法求解横坐标纵坐标 44.39 14.63 22.93 76.1 94.14 65.36 52.19 36.09 25.36 26.34 (1) 编码和适应度函数 2.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。根据种群中个体的距离并考虑使用自适应的标定方法，定义如下的适应度函数，使用此适应度函数的后面的乘方次数可以调整来改变淘汰速度。这里选择2，表示淘汰速度比较适中。选择算子，根据适应度函数的大小进行选择。计算每个个体被选中的概率 (2) 定义算子 2i)-x1()(种群最小距离种群最大距离种群最小距离距离ixf

，以各个个体所分配到的概率值作为其遗传到下一代的概率，基 (3) 算法流程于这些概率用赌盘选择法来产生下一代群体。交叉算子，采用部分映射交叉(Partially Mapped Crossover, PMX)方法实现算法交叉。首先选取选需要交叉的区间段，然后确定区间段的映射关系，接下来交换区间段的遗传信息，此时未换部分的遗传信息会出现不合法的情况，因此根据将未换部分按映射关系进行交换。交叉率为 0.9。变异算子，把一个染色体中的两个基因的交换作为变异算法。在算法中随机的产生一个染色体中需要交换的两个基因的位置，将这两个基因进行交换来实现变异。变异率为 0.2。根据上述的遗传算子的定义，并设置最大的迭代次数为 1000，将 GA 算法流程叙述如下，否，转到(iv)。操作。 2.2 GA 算法计算结果使用 Matlab 编程实现 2.1 中的算法，计算结果如下。 (i) 随机生成初始种群。 (ii) 按照本节(1)中的公式计算各个个体适应度的值。 (iii) 判断是否达到了最大的迭代次数。若是，算法结束，输出计算结果；若 (iv) 按照本节(2)中的选择算子进行选择操作。 (v) 选择交叉宽度并随机确定交叉切点，按照本节(2)中的交叉算子进行交叉 (vi) 按照本节(2)中的变异算子进行变异操作。 (vii) 将遗传算子产生的种群作为新的种群，转到(ii)。 Niiiixfxfxp1)()()(

图 1 GA 算法过程的距离值变化图 2 GA 算法求解的 10 城市 TSP 问题的结果最后的结果编码为（8 9 10 2 3 1 4 5 6 7），解为 H-I-J-B-C-A-D-E-F-G，距离 01002003004005006007008009001000260280300320340360380GA算法过程迭代次数距离值102030405060708090102030405060708090100kmkmGA算法求解10个城市TSP问题规划路径规划路径

为 269.0671。从计算结果可以看出，算法迭代到 300 步时已经收敛到了局部的最优值。经过大量的计算发现至多迭代到 300 步，算法收敛到局部最优值。经过进一步的验证发现，这个局部最优解也是全局最优解。 3 使用 PSO 算法求解 (1)TSP 问题的交换子和交换序 3.1 算法描述设 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’，可定义和属于同一等价集，在交换序等价集中，拥有最少交换子的交换序称为该等价集的基本交换序。 (2) TSP 问题的速度和位置更新算式根据(1)中的交换子和交换序的定义，可以根据基本的 PSO 算法速度更新算式和位置更新算式，重新定义如下的速度和位置更新算式，式中，、为[0,1]区间的随机数。为粒子与个体极值的交换序，以概率保留；为粒子与全局极值的交换序，以概率保留。粒子的位置按照交换序进行更新。为惯性权重。按照本节中的有关定义给出算法流程如下， (3) 算法流程 (i) 初始化粒子群，给每一个粒子一个初始解和随机的交换序。 (ii) 判断是否达到最大迭代次数 1000。若是，算法结束，输出结果；若不是，转到(iii)。 (iii) 根据粒子当前位置计算下一个新解： (a) 计算 A= ，A 是一个基本交换序，表示 A 作用于得到； (b) 计算 B= ，B 是一个基本交换序； 21'SSSSSS'SS21SSSSididididgdididididvxxxpxpvv)()(ididxpidgdxpidvidxidvididxpidxidpidgdxp

(c) 按照(2)中的公式更新速度和位置。 (d) 如果得到了更好的个体位置，更新。 (iv) 如果得到了更好的群体位置，更新。 3.2 PSO 算法的计算结果编程实现 3.1 中的算法，计算结果如下。计算程序见附录。图 3 PSO 算法过程的距离值变化 idpgdp01002003004005006007008009001000260280300320340360380PSO算法过程迭代次数距离值

图 4 PSO 算法求解的 10 城市 TSP 问题的结果最后的结果编码为（1 4 5 6 7 8 9 10 2 3），解为 A-D-E-F-G-H-I-J-B-C，距离为 269.0671。从计算结果可以看出，算法迭代到 200 步时已经收敛到了局部的最优值。这个局部最优解也是全局最优解。从收敛的速度的平均意义上而言，PSO 算法与 GA 算法比收敛的更快。附录 % GA 算法的代码 % GA算法程序. data = load('pos10.txt'); a=[data(:,2) data(:,3)]; n=50; % 种群数目 C=1000; % 迭代次数 Pc=0.9; % 交叉概率 Pm=0.2; % 变异概率 % GA算法初始化. [N,NN]=size(D); farm=zeros(n,N); for i=1:n farm(i,:)=randperm(N); 102030405060708090102030405060708090100kmkm规划路径规划路径

end R=farm(1,:); len=zeros(n,1); fitness=zeros(n,1); counter=0; % GA算法迭代 while counter=rand nn=nn+1; FARM(nn,:)=farm(i,:); end end FARM=FARM(1:nn,:); % FARM (nn*N) [aa,bb]=size(FARM);%(aa=nn) % 交叉 FARM2=FARM; for i=1:2:aa if Pc>rand&&i=rand&&L>10 W=ceil(L/10)+8; else

W=floor(L/10)+8; end p=unidrnd(L-W+1);%随机选择交叉范围 for i=1:W x=find(a==b(1,p+i-1)); y=find(b==a(1,p+i-1)); [a(1,p+i-1),b(1,p+i-1)]=exchange(a(1,p+i-1),b(1,p+i-1)); [a(1,x),b(1,y)]=exchange(a(1,x),b(1,y)); end FARM(i,:)=A; FARM(i+1,:)=B; end end % 变异 FARM2=FARM; for i=1:aa if Pm>=rand FARM(i,:)=mutate(FARM(i,:)); end end % 群体更新 FARM2=zeros(n-aa+1,N); if n-aa>=1 for i=1:n-aa FARM2(i,:)=randperm(N); end end FARM=[R;FARM;FARM2]; [aa,bb]=size(FARM); if aa>n FARM=FARM(1:n,:); end farm=FARM; clear FARM RR(counter+1)=myLength(D,R) % 统计迭代次数。 counter=counter+1 ; end % 结果图形显示

资料库

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

相关推荐

课程资源

热门标签

最新资料