TSP问题中产生新解的方法
（1）交换法：随机选择两个点，交换这两个点的位置
（2）移位法：随机选择三个点，将前两个点之间的点移位到第三个点后
（3）倒置法：随机选择两个点，将这两个点之间的顺序完全颠倒
（4）整块交换法：随机选择四个点，将前两个点之间的元素和后两个点之间的元素交换位置
附四种方法的代码：
function [path1,kind,cc] = gen_new_path(path0,varargin)
% path0: 原来的路径
n = length(path0);
if nargin == 1
p1 = 0.25; % 使用交换法产生新路径的概率
p2 = 0.25; % 使用移位法产生新路径的概率
p3 = 0.25; % 使用倒置法产生新路径的概率
else
p1 = varargin{1}; % 使用交换法产生新路径的概率
p2 = varargin{2}; % 使用移位法产生新路径的概率
p3 = varargin{3}; % 使用倒置法产生新路径的概率
end
% 剩下的概率就是整块交换法的概率
% 根据上述概率随机选择产生新路径的方法
r = rand(1); % 随机生成一个[0 1]间均匀分布的随机数
if r< p1 % 使用交换法产生新路径
c1 = randi(n); % 生成1-n中的一个随机整数
c2 = randi(n); % 生成1-n中的一个随机整数
path1 = path0; % 将path0的值赋给path1
path1(c1) = path0(c2); %改变path1第c1个位置的元素为path0第c2个位置的元素
path1(c2) = path0(c1); %改变path1第c2个位置的元素为path0第c1个位置的元素
kind = 1;
cc{1} = c1;
cc{2} = c2;
elseif r < p1+p2 % 使用移位法产生新路径
c1 = randi(n); % 生成1-n中的一个随机整数
c2 = randi(n); % 生成1-n中的一个随机整数
c3 = randi(n); % 生成1-n中的一个随机整数
sort_c = sort([c1 c2 c3]); % 对c1 c2 c3从小到大排序
c1 = sort_c(1); c2 = sort_c(2); c3 = sort_c(3); % c1 < = c2 <= c3
tem1 = path0(1:c1-1);
tem2 = path0(c1:c2);
tem3 = path0(c2+1:c3);
tem4 = path0(c3+1:end);
path1 = [tem1 tem3 tem2 tem4];
kind = 2;
cc{1} = c1;
cc{2} = c2;
cc{3} = c3;
elseif r < p1+p2+p3 % 使用倒置法产生新路径
c1 = randi(n); % 生成1-n中的一个随机整数
c2 = randi(n); % 生成1-n中的一个随机整数
if c1>c2 % 如果c1比c2大，就交换c1和c2的值
tem = c2;
c2 = c1;
c1 = tem;
end
tem1 = path0(1:c1-1);
tem2 = path0(c1:c2);
tem3 = path0(c2+1:end);
path1 = [tem1 fliplr(tem2) tem3]; %矩阵的左右对称翻转 fliplr，上下对称翻转 flipud
kind = 3;
cc{1} = c1;
cc{2} = c2;
else % 整块交换法
c1 = randi(n); % 生成1-n中的一个随机整数
c2 = randi(n); % 生成1-n中的一个随机整数
c3 = randi(n); % 生成1-n中的一个随机整数
c4 = randi(n); % 生成1-n中的一个随机整数
sort_c = sort([c1 c2 c3 c4]); % 对c1 c2 c3从小到大排序
c1 = sort_c(1); c2 = sort_c(2); c3 = sort_c(3); c4 = sort_c(4);% c1 < = c2 <= c3<= c4
tem1 = path0(1:c1-1);
tem2 = path0(c1:c2);
tem3 = path0(c2+1:c3);
tem4 = path0(c3+1:c4);
tem5 = path0(c4+1:end);
path1 = [tem1 tem4 tem3 tem2 tem5];
kind = 4;
cc{1} = c1;
cc{2} = c2;
cc{3} = c3;
cc{4} = c4;
end
end
