遗传算法解决旅行商问题(TSP)二:选择、交叉和变异

选择

使用轮盘赌法进行选择。

function childpop = selection(pop, fitvalue, leaving)
% 选择
% pop           input  种群
% fitvalue      input  种群适应度值
% leaving       input  选出size(pop,1)-leaving个个体
% childpop      outupt 选择出的种群
totalfit = sum(fitvalue);
fitvalue = fitvalue ./ totalfit;
fitvalue = cumsum(fitvalue);
n = size(pop, 1) - leaving;
rnum = sort(rand(n, 1));
childpop = zeros(n, size(pop, 2));
fitin = 1;
newin = 1;
while newin <= n
    if rnum(newin) < fitvalue(fitin)
        childpop(newin,:) = pop(fitin,:);
        newin = newin + 1;
    else
        fitin = fitin + 1;
    end
end
end

交叉

随机选择两个个体，再随机选择一段基因进行交换，以完成交叉操作。交叉后可能会产生冲突（访问同一个城市两次），保持交换的基因段（之后简称为交换段）不变，取得冲突基因在交换段内的位置，将交换段外的冲突基因替换为另一染色体对应位置的基因。

比如下面两个个体之间交叉

A: 9 5 1 3 7 4 2 10 8 6
B: 10 5 4 6 3 8 7 2 1 9

得到

A: 9 5 1 6 3 8 7 10 8 6
B: 10 5 4 3 7 4 2 2 1 9

可见，二者交换的基因段为 6 3 8 7 和 3 7 4 2 ，保持此段不变，对于A，第一个冲突基因为8，取得8在交换段中的位置（6），将交换段外冲突基因替换为B中相应位置的基因，即4. 多次执行直到没有冲突，得到基因：

A: 9 5 1 6 3 8 7 10 4 2
B: 10 5 8 3 7 4 2 6 1 9

下面是代码实现：

function index = isconflict(v, left, right)
% 判断向量内是否有冲突：是否有重复的城市
% v             input  城市序列
% left          input  忽略序列左索引
% right         input  忽略序列右索引
% index         output 0表示不冲突，其他表示冲突位置
index = 0;
for i = 1:length(v)
    if i >= left && i <= right
        continue
    end
    n = size(find(v == v(i)), 2);
    if n ~= 1
        index = i;
        break
    end
end
end

function [rv1, rv2] = crossvector(v1, v2)
% 交叉两个向量，并确保每个向量经过每个点一次
% (v1, v2)      input  需要交叉的两个向量
% [rv1, rv2]    ouptut 交叉完成后的两个向量

% 随机生成交叉点
len = length(v1);
r1 = ceil(len * rand);
r2 = ceil(len * rand);
left = min([r1 r2]);
right = max([r1 r2]);
if left == right
    rv1 = v1;
    rv2 = v2;
    return
end
% fprintf('left=%d, right=%d\n', left, right);
% 交叉
tempv1 = [v1(1:left-1) v2(left:right) v1(right+1:len)];
tempv2 = [v2(1:left-1) v1(left:right) v2(right+1:len)];


% 解决冲突，确保一条路线覆盖每个点一次
conflictindex = isconflict(tempv1, left, right);
while conflictindex ~= 0
    tempindex = find(tempv1(left:right) == tempv1(conflictindex));
    tempv1(conflictindex) = tempv2(tempindex+left-1);
    conflictindex = isconflict(tempv1, left, right);
end
conflictindex = isconflict(tempv2, left, right);
while conflictindex ~= 0
    tempindex = find(tempv2(left:right) == tempv2(conflictindex));
    tempv2(conflictindex) = tempv1(tempindex+left-1);
    conflictindex = isconflict(tempv2, left, right);
end

rv1 = tempv1;
rv2 = tempv2;
end

function childpop = crossover(pop, pc)
% 交叉
% pop       input  种群
% pc        input  交叉概率
% childpop  output 交叉后的种群
n = size(pop, 1);
for i = 1:n
    if rand < pc
        r1 = unidrnd(n);
        r2 = unidrnd(n);
%         fprintf('r1=%d, r2=%d\n', r1, r2);
        if (r1 == r2)
            continue
        end
        [pop(r2,:), pop(r1,:)] = crossvector(pop(r1,:), pop(r2,:));
    end
end
childpop = pop;
end

变异

随机交换染色体中的两个基因的位置即可：

function childpop = mutation(pop, pm)
% 变异
% pop           input  种群
% pm            input  变异概率
% childpop      output 变异后的种群
[n, l] = size(pop);
for i = 1:n
    if rand < pm
        r1 = ceil(rand * l);
        r2 = ceil(rand * l);
        temp = pop(i, r1);
        pop(i, r1) = pop(i, r2);
        pop(i, r2) = temp;
    end
end
childpop = pop;
end

其他函数

function bestindex = bestindividual(fitvalue)
% 得到最优个体索引
% fitvalue          input  适应度值
% bestindex         output 最优个体索引
[~, bestindex] = max(fitvalue);
end

function plot_pos(pos)
% 绘制种群图（城市坐标图）
% pos               input  城市坐标
% lx                input  绘图横轴左边界
% ux                input  绘图横轴右边界
% ly                input  绘图纵轴下边界
% uy                input  绘图纵轴上边界
plot(pos(1,:), pos(2,:), 'bo');
title('种群图(城市坐标图)');
end

function plot_route(pos, v)
% 绘制路线图
% pos           input  城市坐标
% v             input  城市序列
plot_pos(pos);
hold on;
for i = 1:(size(v,2)-1)
    x1 = pos(1,v(i)); y1 = pos(2,v(i));
    x2 = pos(1,v(i+1)); y2 = pos(2,v(i+1));
    plot([x1, x2], [y1, y2], 'b');
    hold on;
end
plot([pos(1,v(end)), pos(1,v(1))], [pos(2,v(end)), pos(2,v(1))], 'b');
end