遗传算法解决旅行商问题(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;
    endendend

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
    endendend

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;
    returnend% 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);endconflictindex = 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);endrv1 = 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,:));
    endendchildpop = 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;
    endendchildpop = 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;endplot([pos(1,v(end)), pos(1,v(1))], [pos(2,v(end)), pos(2,v(1))], 'b');end