|
编码目的和解析
旅行商问题： 地图上有n个点，旅行商要求从一个点出发，经过每个城市一次且仅一次并最终回到出发城市，求最短路径 使用matlab作为编程工具，采用遗传算法对tsp（旅行商）问题进行基本编码实现和优化解答，最终控制误差在一定范围内，或者找到旅行商问题的最优解。
注：旅行商问题的已知最优解是通过遍历得到的，不可能通过智能算法得到更短的距离，除非计算公式出错或者数据出现问题。
数据获取
所需工具/软件/数据
软件：matlab
日志：csdn博客
资料来源：百度搜索的结果页面链接
搜索到的资料及其网址
《TSP的已知最优解》：百度文库网址 该文档的上传日期为2014年，该文档最后一行显示的时间点为2007年。 oschina中的数据集下载网址：MP-TESTDATA - The TSPLIB Symmetric Traveling Salesman Problem Instances
数据集和代码已经上传到csdn中，欢迎学习和交流
遇到的第一个问题是距离的计算问题，具体可以通过下载这个文件去查看具体数据集的距离计算公式：http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf 文件第九页有每种问题的对应距离计算方法，再通过该方法找到具体的措施即可
举个例子：
a280数据集（图片中的第一个），可以找到Type为EUC_2D，在pdf文件中搜索该类型，即可找到对应的计算公式如下：
原理解析
种群确定与基本操作
首先要确定每个个体的元素和一个规模合适的种群 tsp问题每个个体其实可以看做n个城市的链条比如n = 5，的排列顺序可以看成一个个体1 2 3 4 5就是一个一个基因片段，后续重组变异也是基于此实现 确定种群的规模 和个体的基因数有关，一般规模不大时设置为100-1000即可注意：规模越大，可能导致运算时间过长 到这里，对应实现种群的初始化即可 比如一千个个体，每个个体48个基因（n=48）随机排列
选择
是挑选父代的个体作为随后重组、变异的来源主要有两种方法：轮盘赌和锦标赛（试验效果更好）生成一个个体所需的父代一般是两个 所以使用两次算法得出两个个体参与重组、变异即可
轮盘赌：
结合tsp算法进行解释：适应度：粗略理解为该个体生存下去的可能性的大小 在tsp问题中，可以理解为距离越小，适应度越高所以可以取距离的倒数 求出父代每个个体的适应度，并进行累加得到max 这里需要生成一个数组，存放自第一个到第m个个体的累积适应度 例如有三个个体，适应度为0.2,0.5,0.7生成的数组就是[0.2,0.7,1.4] 随后获得一个随机数 ran 在0-max之间 看看这个ran小于哪个累计数（0.2,0.7,1.4）就选择哪个个体例如ran=0.6，则选择第二个个体，因为0.6>0.2且0.6 对大数据集优化明显 任选一个城市作为初始节点选择距离这个城市最短距离的城市作为下一个节点随后跳转到【下一个节点】,并重复执行上一步操作，知道找到一条"贪婪算法最短链"注意：找的时候已经找过的点不要再用了，可以使用一个zeros(n)数组保存是否已经被使用，使用过了就置为1，没有就还是0，读取对应位置的元素进行替换即可，非常快速 变异的时候变异多个基因 效果不大 重组的时候重组多个部分 效果好一点 设置超过200次，变异概率提高 效果好点 设置超过1000次，跳出循环 为了避免长时间无效运转
实验成果举例
迭代收敛图
路线图
运行结果 
tsp主程序代码
clear;
clc;
tStart = tic; % 算法计时器
%%%%%%%%%%%%自定义参数%%%%%%%%%%%%%
[ctype,cityNum,cities] = Read('att48.tsp');
cities = cities';
%cityNum = 100;
maxGEN = 50000;
popSize = 1000; % 遗传算法种群大小
inputCrossoverProbabilty = 0.75;%0.75最优
crossoverProbabilty = inputCrossoverProbabilty; %交叉概率
inputProbabilty = 0.2;%0.1最好
maxProbabilty = 0.9;
mutationProbabilty = inputProbabilty; %变异概率
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%存储最好的生成结果为最大值
gbest = Inf;
% 计算上述生成的城市距离
distances = calculateDistance(cities, ctype);
% 生成种群，每个个体代表一个路径 popSize*cityNum的矩阵
pop = zeros(popSize, cityNum);
%for i=1:popSize
% pop(i,:) = randperm(cityNum);
%end
pop = initParent(distances, cityNum,popSize);offspring = zeros(popSize,cityNum);
%保存每代的最小路径便于画图
minPathes = zeros(maxGEN,1);
% GA算法
% 计算有多少次没更新最好权值了
count = 0;
lastgbest = 0;
countGen = 1;
flag = 0;
for gen=1:maxGEN% sumDistance(n*1):总长度[sumDistance] = newFitness(distances, pop); [sortDistance, sortIndex] = sort(sumDistance);% 保留上一代的最好结果offspring(1,:) = pop(sortIndex(1),:);minPath = sortDistance(1);minPathes(gen,1) = minPath; fprintf('代数:%d 最短路径:%.2fKM \n', gen,minPath);for k=2:popSize% 选择父代进行交叉 4*1parent1Path = selectParent(sortIndex, pop, popSize);parent2Path = selectParent(sortIndex, pop, popSize);subPath = crossover(parent1Path, parent2Path, crossoverProbabilty);%交叉subPath1 = mutate(subPath, mutationProbabilty);%变异offspring(k,:) = subPath1(:);end% 更新pop = offspring;% 画出当前状态下的最短路径if minPath < gbestgbest = minPath;countGen = gen;flag = 1;end% 超过一定次数没有更新，就跳出if gen - countGen > 1000break;end%超过500次没更新就画图if gen - countGen > 500 && flag == 1paint(cities, pop, gbest, sumDistance, gen);flag = 0;end%超过200次没更新就调整变异概率if gen - countGen > 200mutationProbabilty = maxProbabilty;end
% if mutationProbabilty < 1
% mutationProbabilty = mutationProbabilty + 0.05;
% end
% if crossoverProbabilty < 0.8
% crossoverProbabilty = crossoverProbabilty + 0.05;
% end
% else
% %更新了就复原
% mutationProbabilty = inputProbabilty;
% crossoverProbabilty = inputCrossoverProbabilty;
% end
endfigure
plot(minPathes, 'MarkerFaceColor', 'red','LineWidth',1);
title('收敛曲线图（每一代的最短路径）');
set(gca,'ytick',500:100:5000);
ylabel('路径长度');
xlabel('迭代次数');
grid on
tEnd = toc(tStart);
fprintf('时间:%d 分 %f 秒.\n', floor(tEnd/60), rem(tEnd,60));
initparent——初始化
function pop = initParent(distances, cityNum,popSize)pop = zeros(popSize, cityNum);[row, col] = size(distances);% 1/4*popSize 和 cityNum之间选最小的作为最优初始化的个数% 为了保证选择前面50%的时候多样性还在if(popSize / 4 > cityNum)minLength = cityNum;else minLength = popSize / 4;end% 随机生成一个随机数数组作为开头randomList = randperm(cityNum);for k = 1:minLengthcityBest = zeros(1, cityNum);flagList = zeros(1, cityNum);%轮到第几行被遍历了rowIndex = k;%第k行的数字已经被使用了，不可以再使用flagList(randomList(k)) = 1;%第一个数字是randomList(k)cityBest(1) = randomList(k);%一共循环cityNum - 1for i = 2:rowthisRow = distances(rowIndex, :);best = Inf;bestIndex = 1;for j = 1:colif thisRow(j) ~= 0 && thisRow(j) < best && flagList(j) == 0best = thisRow(j);bestIndex = j;endendflagList(bestIndex) = 1;rowIndex = bestIndex;cityBest(i) = bestIndex;endpop(k, :) = cityBest;end%如果更大，证明还有一些种群要随机生成for i=minLength + 1:popSizepop(i,:) = randperm(cityNum); end
end
crossver——重组
function [returnPath] = crossover(parent1Path, parent2Path, prob)
% 交叉random = rand();if prob >= random[l, length] = size(parent1Path);% 交叉后会生成两个子代childPath = zeros(1,length);flagPath = zeros(1, length);% 交换的幅度是不超过一半startIndex = randi(length);%middleIndex = randi(length);%middleIndex1 = randi(length);endIndex = randi(length);%list = [startIndex, endIndex, middleIndex, middleIndex1];%list = sort(list);%two = sort([startIndex, endIndex]);count = 1;for i = startIndex:endIndexchildPath(count) = parent1Path(i);%flag上面为1，证明被使用了flagPath(parent1Path(i)) = 1;count = count + 1;end%for i = list(3):list(4)% childPath(count) = parent1Path(i);% %flag上面为1，证明被使用了% flagPath(parent1Path(i)) = 1;% count = count + 1;%end%赋值第二个父代的不同部分for i = 1:lengthif(flagPath(parent2Path(i)) == 1)continue;elsechildPath(count) = parent2Path(i);count = count + 1;endendreturnPath = childPath;elsereturnPath = parent1Path;endend
mutate——变异
function [ mutatedPath ] = mutate( path, prob)
%对指定的路径利用指定的概率进行更新random = rand();length1 = length(path);%thisDistance = getDistance(path, distances);% 概率->允许变异if random |