精华内容
下载资源
问答
  • Matlab遗传算法TSP求解
    千次阅读
    2020-07-10 19:53:22

    遗传算法简介

    遗传算法包括初始种群生成,适应度的计算,种群选择,交叉和变异这几项内容

    TSP问题

    TSP问题是旅行商经过一系列城市使得旅行商经过的总路程最短的问题

    遗传算法内容

    生成初始种群

    // An highlighted block
    for i=1:NP
        f(i,:)=randperm(N);   %初始种群
    end
    

    计算个体适应度

    // An highlighted block
        for i=1:NP
            len(i,1)=D(f(i,N),f(i,1));
            for j=1:N-1
                len(i,1)=len(i,1)+D(f(i,j),f(i,j+1));
            end
        end
        maxlen=max(len);
        minlen=min(len
        %计算归一化适应值
        for i=1:NP
            fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.001));
        end
    

    轮盘赌选择

    // An highlighted block
        sumFit=sum(fitness);
        fitvalue=fitness./sumFit;
        fitvalue=cumsum(fitvalue);
        ms=sort(rand(NP,1));
        fiti=1;
        newi=1;
        while newi <= NP
           if (ms(newi)) < fitvalue(fiti)
               nf(newi,:)=f(fiti,:);  %种群重新生成
               newi=newi+1;
           else
               fiti=fiti+1;
           end 
        end
    

    交叉操作

    交叉操作是单点交叉的方式,例如12345678和87654321,假如第一个点交叉则变成8234571和17654328

    // An highlighted block
        for i=1:2:NP
            for j=1:N
                if rand<pc
                    %同一种群变化
                    A=find(nf(i,:)==nf(i+1,j));
                    nf(i,A)=nf(i,j);
                    B=find(nf(i+1,:)==nf(i,j));
                    nf(i+1,B)=nf(i+1,j);
                    %交换位置
                    temp1=nf(i+1,j);
                    nf(i+1,j)=nf(i,j);
                    nf(i,j)=temp1;
                end
            end
        end
    

    变异操作

    变异是采用单点变异的方式,比如12345678第5个位置变异,则在随机生成一个值比如1赋给第5个位置,则生成的个体是52341678

    // An highlighted block
        for i=1:NP
            for j=1:N
                if rand<pm
                    temp2=nf(i,j);
                    temp3=randi([1,N],1,1);
                    A=find(nf(i,:)==temp3);
                    nf(i,j)=temp3;
                    nf(i,A)=temp2; 
                end
            end
        end
    

    图像输出

    figure
    for i=1:N-1
        plot([C(R(i),1),C(R(i+1),1)],[C(R(i),2),C(R(i+1),2)],'bo-')
        hold on;
    end
    plot([C(R(N),1),C(R(1),1)],[C(R(N),2),C(R(1),2)],'ro-')
    title(['优化最短距离:',num2str(minlen)])
    

    完整代码

    close all 
    clear all
    clc
    
    %读入初始数据
    FP1=fopen('shuju.txt','rt');
    N=fscanf(FP1,'%d',1);  %初始个体数
    C=fscanf(FP1,'%f',[2,N]);   %个体坐标
    C=C';
    D=zeros(N);   %两两距离
    for i=1:N
        for j=1:N
            D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;%求任意两个城市的间距
        end
    end
    NP=200;   %种群规模
    G=500;   %迭代次数
    f=zeros(NP,N);   %种群
    nf=zeros(NP,N);   %子种群
    pc=0.4; %交叉概率
    pm=0.2; %变异概率
    F=[];
    for i=1:NP
        f(i,:)=randperm(N);   %初始种群
    end
    R=f(1,:);   %最优种群
    len=zeros(NP,1);   %存储路径长度
    fitness=zeros(NP,1);   %存储归一化值
    gen=0;
    
    %计算各种群的适应度值,即种群的长度
    while gen<G
        for i=1:NP
            len(i,1)=D(f(i,N),f(i,1));
            for j=1:N-1
                len(i,1)=len(i,1)+D(f(i,j),f(i,j+1));
            end
        end
        maxlen=max(len);
        minlen=min(len);
        rr=find(len==minlen);   %找到最小值种群所在的位置
        R=f(rr(1,1),:);   %最小值种群的基因
        
        %计算归一化适应值
        for i=1:NP
            fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.001));
        end
        
        %基于轮盘赌的复制操作
        sumFit=sum(fitness);
        fitvalue=fitness./sumFit;
        fitvalue=cumsum(fitvalue);
        ms=sort(rand(NP,1));
        fiti=1;
        newi=1;
        while newi <= NP
           if (ms(newi)) < fitvalue(fiti)
               nf(newi,:)=f(fiti,:);  %种群重新生成
               newi=newi+1;
           else
               fiti=fiti+1;
           end 
        end
        
        %交叉操作
        for i=1:2:NP
            for j=1:N
                if rand<pc
                    %同一种群变化
                    A=find(nf(i,:)==nf(i+1,j));
                    nf(i,A)=nf(i,j);
                    B=find(nf(i+1,:)==nf(i,j));
                    nf(i+1,B)=nf(i+1,j);
                    %交换位置
                    temp1=nf(i+1,j);
                    nf(i+1,j)=nf(i,j);
                    nf(i,j)=temp1;
                end
            end
        end
        %变异操作
        for i=1:NP
            for j=1:N
                if rand<pm
                    temp2=nf(i,j);
                    temp3=randi([1,N],1,1);
                    A=find(nf(i,:)==temp3);
                    nf(i,j)=temp3;
                    nf(i,A)=temp2; 
                end
            end
        end
       f=nf;
       f(1,:)=R;
       clear F
       gen=gen+1;
       Rlength(gen)=minlen;
    end
    figure
    for i=1:N-1
        plot([C(R(i),1),C(R(i+1),1)],[C(R(i),2),C(R(i+1),2)],'bo-')
        hold on;
    end
    plot([C(R(N),1),C(R(1),1)],[C(R(N),2),C(R(1),2)],'ro-')
    title(['优化最短距离:',num2str(minlen)])
    figure
    plot(Rlength)
    xlabel('迭代次数')
    ylabel('目标函数')
    title('适应度进化曲线')
    disp('最短路径路程是:')
    disp(R)
    
    

    运行结果

    在这里插入图片描述
    在这里插入图片描述

    总结

    利用遗传算法可以解决TSP问题,结果较准确,但是迭代收敛的慢,易陷入局部最优

    更多相关内容
  • 遗传算法 TSP 实现

    2018-10-31 12:00:46
    遗传算法(GeneticAlgorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,通过模拟自然进化过程搜索最优解。遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,初代...
  • 遗传算法tsp案例

    2019-04-26 18:26:07
    遗传算法解决tsp(旅行商问题)的python实现代码,有图形和控制台输出
  • 基于遗传算法TSP算法的MATLAB实现
  • 这是基于遗传算法TSP算法的MATLAB仿真源码,下载后直接运行主程序即可,请大家参考!!!
  • Matlab TSP(遗传算法)

    2019-12-09 22:44:53
    关于TSP问题的遗传算法求解总代码 包含每个过程单独函数 可以自己修改选择变异函数 备有注释 易于理解
  • 遗传算法解决TSP问题··························································································...
  • 遗传算法 TSP

    2018-10-16 14:45:21
    解压直接运行即可 有画图功能 主程序. 主程序中有一rand('seed',n) n 为某一整 数, 这是设置随机数发生器的种子,这样实际上规定 了随机数发生的方式,因此后面的随机数其实都是定 下来的,这样所有人就可以看到...
  • 遗传算法解决 TSP 问题(附matlab源程序).docx
  • 遗传算法tsp

    2018-12-29 11:53:36
    10个城市的路径优化单纯的使用了遗传算法,其中使用了交叉和变异,没有进行更深的优化。
  • 用于TSP旅商问题的遗传算法,txt文件内涵源代码,复制粘贴即可
  • 旅行商问题(TSP问题)。假设有一个旅行商人要拜访全国31 个省会城市,他需要选择所要走的路径,路径的限制是每个城市只能拜访 一次,而且最后要回到原来出发的城市。对路径选择的要求是:所选路径 的路程为所有路径...
  • tsp_遗传算法TSP_

    2021-09-28 21:05:40
    遗传算法解决tsp问题,可自行生成城市坐标,也可选择导入,交叉方法也有两种
  • 遗传算法TSP变异matlab代码,代码简洁明了,超级适合新手小白上手练习,没有复杂运算,
  • 遗传算法解决TSP问题的Python代码,三个py文件,一个小DEMO
  • 经典的TSP旅行商问题,遗传算法优化问题,可用于解决各种复杂的问题,欢迎大家交流指正。
  • NULL 博文链接:https://tristan-s.iteye.com/blog/1122493
  • GA-TSP_遗传算法TSP_

    2021-09-30 01:03:51
    TSP(旅行商问题)是典型的NP完全问题,即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长,到目前为止还没有一个多项式时间的有效算法
  • 遗传算法TSP.txt

    2021-08-11 18:54:57
    matlab遗传TSP算法.txt
  • 遗传算法TSP

    2014-01-07 21:26:03
    遗传算法解决TSP求解问题设计,包括大中小地图文件
  • 遗传算法解决TSP旅行商问题 python,带图像输出,可自行修改经纬度。
  • 用于学习和介绍旅行商问题的遗传算法基础教学
  • 使用了较为简单的遗传算法,来解决一般的tsp问题
  • 遗传算法解决TSP问题(C++版),内容详细,可以很好地帮助初学者学习遗传算法
  • 遗传算法解决TSP问题

    2017-01-17 21:48:49
    资源包含“遗传算法解决TSP问题”的相关代码(.cpp和.h)以及TSP相关的城市数据。
  • MATLAB遗传算法求解TSP问题
  • 遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法算法流程:1. 开始2.建立种群(或者更新种群)3.记录上次迭代...
  • 使用遗传算法优化旅行规划问题,目标是使总的路程最短或路费最少
  • C++程序—遗传算法TSP.docx

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,278
精华内容 1,711
关键字:

遗传算法tsp

友情链接: 扫雷.zip