matlab|【原】总（tu）结（cao）粒子群算法(PSO)解决旅行商问题(TSP) pso算法|pso解决tsp|pso算法|tsp问

% main.m % 调用 clc clear close allnumber = 14; % 14个城市 global cities cities = rand(number,2) * 200 - 100; % 假设城市分布在 [-100,-100] ,[100,100]的平面内[best,par,ItorMean,ItorBest] = PSO4TSP_v1(cities); netplot(cities,best.loc); figure itor = length(ItorMean); plot(1:itor,ItorMean,'r',1:itor,ItorBest,'g');

% PSO 算法，globalBest为全局最优，par是最终的粒子信息，ItorMean是每次迭代平均适应度，ItorBest是每次迭代最佳适应度 function [globalBest,par,ItorMean,ItorBest] = PSO4TSP_v1(cities) %% 参数设置 number_cities = size(cities,1); % 城市数 number_pars = 50; % 粒子个数 maxItor = 2000; % 最大迭代次数 initSSnumber = number_cities; ss = zeros(initSSnumber,2); globalBest.fitness = -inf; ItorMean = zeros(1,maxItor); ItorBest = zeros(1,maxItor); %% 粒子初始化 for i = 1 : number_pars % 初始化粒子位置 par(i).loc = randperm(number_cities); % 初始化交换 for j = 1 : initSSnumber ss(j,:) = randperm(number_cities,2); end par(i).v = ss; par(i).best = par(i); par(i).fitness = fitness(par(i).loc); if globalBest.fitness < par(i).fitness globalBest = par(i); end end %% 迭代求优 eachItor = zeros(1,number_pars); for i = 1 : maxItor for j = 1 : number_pars t = rand; u = rand; ssLoc = getSS(par(j).best.loc,par(j).loc); ssLocLen = size(ssLoc,1); ssGlo = getSS(globalBest.loc,par(j).loc); ssGloLen = size(ssGlo,1); temp1 = rand(1,ssLocLen); Item2 = ssLoc(temp1 par(j).fitness par(j).fitness = myfitness; par(j).best = par(j); if myfitness > globalBest.fitness globalBest = par(j); end else par(j).fitness = myfitness; end end ItorMean(i) = mean(eachItor); ItorBest(i) = max(eachItor); end end

% netplot.m function netplot(city,n)%连线各城市，将路线画出来 figure hold on plot(city(:,1),city(:,2),'*'); line([city(:,1); city(1,1)],[city(:,2); city(1,2)]); end

% fitness.m % 计算城市间的距离 function z = fitness(n) global cities tstart = n; tend = [n(2:end),n(1)]; z = sum(distance(cities(tstart,1),cities(tstart,2),cities(tend,1),cities(tend,2))); z=1/z; end

% getSS.m function ss = getSS(v1,v2) % 求SS算子 % v1，v2是一组向量，v1，v2所包含的元素应该相同。 % 若v1,v2顺序相同，则返回ss = []; % 若顺序不同，则返回一个ss算子，即v2通过ss变换可以得到v1 ss = []; while 1 idx = find(v1 ~= v2); if isempty(idx) break; end idx2 = find(v2 == v1(idx(1))); so = [idx(1),idx2]; ss = [ss; so]; v2 = doSO(v2,so); end

% doSS.m function v = doSS(v,ss) % SS操作函数 % v:之前的方案 % ss:SS算子，用作交换(n*2)的矩阵 % v:SS操作之后的结果 if ~isempty(ss) [m,n] = size(ss); if m == 2 && n ~= 2 ss = ss'; m = n; n = 2; end if n ~= 2 help doSS error('ss must be n*2 matrix'); endfor i = 1 : m v = doSO(v,ss(i,:)); end end end

% doSO.m function v = doSO(v,so) % SO操作函数 % v:之前的方案 % so:SO算子，用作交换 % v:SO操作之后的结果 if ~isempty(so) if length(so) ~= 2 help doSO error('length of "so" iso must equals 2'); else len = length(v); if so(1) > len || so(2) > len || so(1) < 1 || so(2) < 1 help doSO error('"so" iso is not the index of v'); else v(so(1)) = v(so(1)) + v(so(2)); v(so(2)) = v(so(1)) - v(so(2)); v(so(1)) = v(so(1)) - v(so(2)); end end end end

% getSS.m % 论文中的减法操作 function ss = getSS(v1,v2) % 求SS算子 % v1，v2是一组向量，v1，v2所包含的元素应该相同。 % 若v1,v2顺序相同，则返回ss = []; % 若顺序不同，则返回一个ss算子，即v2通过ss变换可以得到v1 ss = []; while 1 idx = find(v1 ~= v2); if isempty(idx) break; end idx2 = find(v2 == v1(idx(1))); so = [idx(1),idx2]; ss = [ss; so]; v2 = doSO(v2,so); end

% unionSS.m % 论文中的⊕操作 function ss = unionSS(ss1,ss2) % ss1,ss2算子合并操作vm1 = max(max(ss1)); vm2 = max(max(ss2)); if isempty(ss1) if isempty(ss2) ss = []; else ss = ss2; end elseif isempty(ss2) ss = ss1; else vm = max(vm1,vm2); v = 1 : vm; v2 = doSS(doSS(v,ss1),ss2); ss = getSS(v,v2); end end

当我信心满满的运行的时候，效果却令人大跌眼镜。

matlab|【原】总（tu）结（cao）粒子群算法(PSO)解决旅行商问题(TSP)

文章图片

文章图片

虽然从迭代的图中能看出来，算法确实是取寻优了而且也收敛，但是得到的最终效果却不能令人满意。
后来，我又查阅了相关资料，发现这两篇帖子java版本的PSO求解TSP问题，C++版本的PSO求解TSP问题参考的同一篇文献，而且结果同样有不能令人接受，所以只能暂时认为这篇古老的文献的公式出错。
展望下未来的情况，也许可以找到更好的文献取代这篇文献，亦或者把之前的迭代公式改正确。
如果是后者，我们可以通过经典PSO问题类比推理出求解TSP的V’id可能需要在原先的公式加上一个随机速度Vir。推测Vir为一个SO或者是随着迭代次数增加而算子长度向0收敛的SS。笔者正向这个方向进行尝试。