前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >遗传算法解决旅行商问题(TSP)二:选择、交叉和变异

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

作者头像
mwangblog
发布2018-10-18 17:54:03
2.3K0
发布2018-10-18 17:54:03
举报
文章被收录于专栏:mwangblog

请到原文地址查看完好代码

本文目录

  • 1 选择
  • 2 交叉
  • 3 变异
  • 4 其他函数

选择

使用轮盘赌法进行选择。

代码语言:javascript
复制
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

MATLAB

交叉

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

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

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

下面是代码实现:

代码语言:javascript
复制
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

MATLAB

代码语言:javascript
复制
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

MATLAB

代码语言:javascript
复制
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

MATLAB

变异

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

代码语言:javascript
复制
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

MATLAB

其他函数

代码语言:javascript
复制
function bestindex = bestindividual(fitvalue)% 得到最优个体索引% fitvalue          input  适应度值% bestindex         output 最优个体索引[~, bestindex] = max(fitvalue);end

MATLAB

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

MATLAB

代码语言:javascript
复制
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

MATLAB

发表评论

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-10-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 mwangblog 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 请到原文地址查看完好代码
    • 选择
      • 交叉
        • 变异
          • 其他函数
            • 发表评论
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档