精华内容
下载资源
问答
  • 该代码包括遗传算法 (GA) 的主要功能:精英主义、锦标赛选择、交叉(两点和启发式)和变异。 有一些使用 GA 的 benchmank 测试函数。 * 它是在遗传工具箱的帮助下开发的。
  • 启发式算法解TSP问题

    千次阅读 2018-05-30 10:24:03
    从结果可以看出启发式算法的特点,由于是经验算法,结果并不是严格意义上的最优解,因此具有一定的随机性,但只要迭代次数足够多,总可以收敛到最优解附近。 三、遗传算法  遗传算法(GA)是模拟达尔文生物进化论的...

    一、前言

           旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。由于该问题的可行解是所有顶点的全排列,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题。早期的研究者使用精确算法求解该问题,常用的方法包括:分枝定界法、线性规划法、动态规划法等。但是,随着问题规模的增大,精确算法将变得无能为力,因此,在后来的研究中,国内外学者重点使用近似算法或启发式算法,主要有遗传算法模拟退火法蚁群算法禁忌搜索算法、贪婪算法神经网络等。

    二、模拟退火法

           模拟退火算法的思想借鉴于固体的退火原理,当固体的温度很高的时候,内能比较大,固体的内部粒子处于快速无序运动,当温度慢慢降低的过程中,固体的内能减小,粒子的慢慢趋于有序,最终,当固体处于常温时,内能达到最小,此时,粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。其流程可以概括如下

    • 随机产生一个初始访问序列,并计算响应的行程和,保存为当前最佳路径。
    • 设置初始温度T(0),终止温度T(min),降温系数a。
    • while(T>T(min)),在当前的最优值,按照某一邻域函数,产生新的路径,并计算新路径的路径和。如果优于最优值,则更迭最优决策,如果不是,按照Metropolis法则选择是否更新。
    • 降温,达到循环终止条件则跳出。
    • Metropolis法则
    可以避免局部陷阱
    • matlab代码
    %C表示初始城市坐标
    C=[1,2;70,90;80,60;10,100;800,200;800,100;90,80;200,600;230,4;500,90];
    n=length(C);
    D=zeros(n,n);%D表示完全图的赋权邻接矩阵
    %计算距离矩阵
    for i=1:n
        for j=i:n
            if i~=j
                D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
            else
                D(i,j)=eps;      %i=j时不计算,应该为0,用eps(浮点相对精度)表示
            end
            D(j,i)=D(i,j);   %对称矩阵
        end
    end
    %初始化
    path_best=[];
    T=3000;
    delta_T=0.98; %降温系数
    p=randperm(n);
    dist=0.0;
    path_best=p;
    for i=1:n-1
        dist=dist+D(p(i),p(i+1));
    end
    dist=dist+D(p(1),p(n));
    dist_best=dist;
    %降温循环过程
    while(T>1e-8)
        %采用最简单的邻域取法,直接对换其中两个节点的城市
        x=ceil(n*rand());
        y=ceil(n*rand());
        while(x==y)
            x=ceil(n*rand());
            y=ceil(n*rand());
        end
        z=p(x);
        p(x)=p(y);
        p(y)=z;
        for i=1:n-1
            dist=dist+D(p(i),p(i+1));
        end
        dist=dist+D(p(1),p(n));    
        if(dist<dist_best)
            dist_best=dist;
            path_best=p;
        else
            a=exp(-(dist-dist_best)/T);
            b=rand(); 
            if(a>b)  %概率大于产生随机数时则采用
                dist_best=dist;
                path_best=p;  
            end
        end
        T=T*delta_T;
    end
    %画图输出结果
    subplot(1,1,1) 
    scatter(C(:,1),C(:,2));
    hold on
    plot([C(path_best(1),1),C(path_best(n),1)],[C(path_best(1),2),C(path_best(n),2)],'g')
    hold on
    for ii=2:n
    plot([C(path_best(ii-1),1),C(path_best(ii),1)],[C(path_best(ii-1),2),C(path_best(ii),2)],'g')
    hold on
    end
    title(['旅行商问题优化结果 :',num2str(dist_best)])
    
    • 输出结果

                                  

    从结果可以看出启发式算法的特点,由于是经验算法,结果并不是严格意义上的最优解,因此具有一定的随机性,但只要迭代次数足够多,总可以收敛到最优解附近。

    三、遗传算法

           遗传算法(GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群开始的,而一个种群则由经过基因编码的一定数目的个体(individual)组成。每个个体实际上是染色体带有特征的实体。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。

    其主要流程如下:

    • 初始化参数,包括种群数量,繁衍代数,变异概率,城市坐标,染色体长度等。
    • 计算距离矩阵,生成初始种群。
    • 当迭代次数不满足时,执行杂交循环。
    • 杂交包括选择,交叉,变异三个过程。选择的方法有很多种,此处采用最简单的最优者生存的方法,即目标函数前60%的个体可以顺利繁衍后代。也可以采用轮盘赌的方法,所有个体均可以繁衍后代,但是目标值越优的个体被挑选的概率越大。交叉的过程是随机生成染色体长度内的两个整数值,并将选择出的两个个体的该段染色体交叉互换。变异按照一定概率进行,当生成的随机数大于变异概率时则进行变异。
    • 更新种群,采用“精英保留”的策略。即在种群数量一定的情况下,每次总是留下目标最优的群体。继续循环直到满足跳出条件。

    matlab代码如下:

    %主程序部分
    NUM=20;%种群大小
    GEN=100;%代数
    P=0.7;%变异概率
    C=[1,2;70,90;80,60;10,100;800,200;800,100;90,80;200,600;230,4;500,90];%城市坐标
    n=length(C);
    D=zeros(n,n);%D表示完全图的赋权邻接矩阵
    %计算初始距离矩阵
    for i=1:n
        for j=i:n
            if i~=j
                D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
            else
                D(i,j)=eps;      %i=j时不计算,应该为0,用eps(浮点相对精度)表示
            end
            D(j,i)=D(i,j);   %对称矩阵
        end
    end
    group=zeros(NUM,n);%种群
    dist=zeros(NUM,1);%路径和
    
    %生成初始种群
    for i=1:NUM
        group(i,:)=randperm(n);
        for j=1:n-1
            dist(i)=dist(i)+D(group(i,j),group(i,j+1));
        end
        dist(i)=dist(i)+D(group(i,1),group(i,n));
    end
    res=[group,dist];
    res=sortrows(res,n+1);%按路径和排序
    path_best=res(1,1:n);%保存最优路径和最小路径和
    dist_min=res(1,n+1);
    M=floor(NUM*0.6);%0.6为适应度系数,即假设60%为适应并繁衍的种群
    
    %执行杂交操作
    for i=1:GEN         
        res=yichuan(res,M,n,D,P,NUM);
        path_best=res(1,1:n);
        dist_min=res(1,n+1);
    end
    %输出结果
    subplot(1,1,1) 
    scatter(C(:,1),C(:,2));
    hold on
    plot([C(path_best(1),1),C(path_best(n),1)],[C(path_best(1),2),C(path_best(n),2)],'g')
    hold on
    for ii=2:n
    plot([C(path_best(ii-1),1),C(path_best(ii),1)],[C(path_best(ii-1),2),C(path_best(ii),2)],'g')
    hold on
    end
    title(['旅行商问题优化结果 :',num2str(dist_min)])

    遗传函数部分

    function [res]=yichuan(res,M,n,D,P,NUM)
    %res为储存路径和总距离的矩阵,M为适应生存的种群数,n为染色体长度,D为距离矩阵,P是变异概率,NUM为种群数
    group=res(1:M,1:n);
    dist=res(1:M,n+1);
    list=randperm(M);%随机生成父本和母本序列
    for j=1:2:M-1
        [group(list(j),:),group(list(j+1),:)]=jiaocha(group(list(j),:),group(list(j+1),:),n,P);
        dist(j)=cal_dist(group(j,:),D,n);
        dist(j+1)=cal_dist(group(j+1,:),D,n); 
    end
    R=zeros(2*M,n+1);
    R=[res;group,dist];
    R=sortrows(R,n+1);
    res=R(1:NUM,:);%精英保留
    end
    
    %交叉,变异
    function [r1,r2]=jiaocha(r1,r2,n,P)
        a=randperm(n,2);
        l=min(a);
        m=max(a);
        while(l==m)
            a=randperm(10,2);
            l=min(a);
            m=max(a);
        end    
        a1=r1;
        a2=r2;
        %交换中间部分,并替换重复出现的染色体
        for k=l:m
            r1(k)=a2(k);
            r2(k)=a1(k);
            x=find(a1==r1(k));
            y=find(a2==r2(k));
            r1(x)=a1(k);
            r2(y)=a2(k);
            a1=r1;
            a2=r2;
        end
        %随机数大于变异概率则变异
        if(rand()>P)
            q=randperm(n,2);
            s=r1(q(1));
            r1(q(1))=r1(q(2));
            r1(q(2))=s;
        end
        if(rand()>P)
            q=randperm(n,2);
            s=r2(q(1));
            r2(q(1))=r2(q(2));
            r2(q(2))=s;
        end
    end
    
    %计算路径和
    function [dist]=cal_dist(path,Dist,n)
        dist=0;
        for k=1:n-1
            dist=dist+Dist(path(k),path(k+1));
        end
        dist=dist+Dist(path(1),path(n));
            
    end

    输出结果


    四、蚁群算法

           最早是由Marco Dorigo等人在1991年提出,基于信息正反馈原理。蚂蚁视觉十分不发达,却能够在没有任何提示的情况下找到食物源到巢穴的最短路径,并在周围环境发生变化后,自适应地搜索新的最佳路径。原因是蚂蚁在寻找食物源的时候,能在其走过的路径上释放信息素,当一些路径上通过的蚂蚁越来越多,信息素也越来越多,蚂蚁选择该路径的概率也就越大。对单个蚂蚁来说,它没有找到最短路径,但对整个蚁群来说,却达到了寻找最优路径的客观效果。

    其算法流程如下:

    • 对相关参数进行初始化,包括蚁群规模、信息素因子、启发函数因子、信息素挥发因子、信息素常数、最大迭代次数等,以及将数据读入程序,并进行预处理:比如将城市的坐标信息转换为城市间的距离矩阵。 
    • 随机将蚂蚁放于不同出发点,对每个蚂蚁计算其下个访问城市,直到有蚂蚁访问完所有城市。 
    • 计算各蚂蚁经过的路径长度LkLk,记录当前迭代次数最优解,同时对路径上的信息素浓度进行更新。
    • 判断是否达到最大迭代次数,若否,继续循环。
    • 输出结果,并根据需要输出寻优过程中的相关指标,如运行时间、收敛迭代次数等。

    代码如下:

    %%第一步:变量初始化
    C=[1,2;70,90;80,60;10,100;800,200;800,100;90,80;200,600;230,4;500,90];
    
    NC_max=200;
    m=18;
    Alpha=1;
    Beta=5;
    Rho=0.5;
    Q=1;
    n=size(C,1);%n表示问题的规模(城市个数)
    D=zeros(n,n);%D表示完全图的赋权邻接矩阵
    for i=1:n
        for j=i:n
            if i~=j
                D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
            else
                D(i,j)=eps;      %i=j时不计算,应该为0,但后面的启发因子要取倒数,用eps(浮点相对精度)表示
            end
            D(j,i)=D(i,j);   %对称矩阵
        end
    end
    Eta=1./D;          %Eta为启发因子,这里设为距离的倒数
    Tau=ones(n,n);     %Tau为信息素矩阵
    Tabu=zeros(m,n);   %存储并记录路径的生成
    NC=1;               %迭代计数器,记录迭代次数
    R_best=zeros(NC_max,n);       %各代最佳路线
    L_best=inf.*ones(NC_max,1);   %各代最佳路线的长度
    L_ave=zeros(NC_max,1);        %各代路线的平均长度
     
    while NC<=NC_max        %停止条件之一:达到最大迭代次数,停止
    %%第二步:将m只蚂蚁放到n个城市上
    Randpos=[];   %随即存取
    for i=1:(ceil(m/n))  %向上取整
        Randpos=[Randpos,randperm(n)];  %并成一列
    end
    Tabu(:,1)=(Randpos(1,1:m))';    %第一行的1到m列元素
     
    %%第三步:m只蚂蚁按概率函数选择下一座城市,完成各自的周游
    for j=2:n     %所在城市不计算
        for i=1:m    
            visited=Tabu(i,1:(j-1)); %记录已访问的城市,避免重复访问
            J=zeros(1,(n-j+1));       %待访问的城市
            P=J;                      %待访问城市的选择概率分布
            Jc=1;
            for k=1:n
                if length(find(visited==k))==0   %开始时置0,找出未访问的城市,find返回的是位置
                    J(Jc)=k;
                    Jc=Jc+1;                         
                end
            end
    %下面计算待选城市的概率分布
            for k=1:length(J)
                P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
            end
            P=P/(sum(P));
            %按概率原则选取下一个城市
    %         Pcum=cumsum(P);     %cumsum返回行和和列和,sum返回列和
    %         Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线
            Select=max(P);
            Select=find(P==Select);
            to_visit=J(Select(1));
            Tabu(i,j)=to_visit;
        end
    end
    if NC>=2
        Tabu(1,:)=R_best(NC-1,:);
    end
     
    %%第四步:记录本次迭代最佳路线
    L=zeros(m,1);     %开始距离为0,m*1的列向量
    for i=1:m
        R=Tabu(i,:);
        for j=1:(n-1)
            L(i)=L(i)+D(R(j),R(j+1));    %原距离加上第j个城市到第j+1个城市的距离
        end
        L(i)=L(i)+D(R(1),R(n));      %一圈,回到起点
    end
    L_best(NC)=min(L);           %最佳距离取最小
    pos=find(L==L_best(NC));
    R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线
    L_ave(NC)=mean(L);           %此轮迭代后的平均距离
    NC=NC+1                      %迭代继续
     
     
    %%第五步:更新信息素
    Delta_Tau=zeros(n,n);        %开始时信息素为n*n的0矩阵
    for i=1:m
        for j=1:(n-1)
            Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);          
            %此次循环在路径(i,j)上的信息素增量
        end
        Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
        %此次循环在整个路径上的信息素增量
    end
    Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发,更新后的信息素
    Tabu=zeros(m,n);             %%直到最大迭代次数
    end
    %%第六步:输出结果
    Pos=find(L_best==min(L_best)); %找到最佳路径(非0为真)
    Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径
    Shortest_Length=L_best(Pos(1)) %最大迭代次数后最短距离
    subplot(1,2,1)                  %绘制第一个子图形
    DrawRoute(C,Shortest_Route)     %画路线图的子函数
    subplot(1,2,2)                  %绘制第二个子图形
    plot(L_best)
    hold on                         %保持图形
    plot(L_ave,'r')
    title('平均距离和最短距离')     %标题
    end
    
    
    function DrawRoute(C,R)
    N=length(R);
    scatter(C(:,1),C(:,2));
    hold on
    plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)],'g')
    hold on
    for ii=2:N
    plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'g')
    hold on
    end
    title('旅行商问题优化结果 ')
    end

    输出结果


    展开全文
  • 作者注:本文写于三年前,今天才转到这里来。  在生物的自然进化过程中,两个同源染色体通过交配而重组,生成新的染色体,从而产生新的个体或物种。...交叉操作的作用是组合出新的个体,在串空间进行有效搜索,同时

        作者注:本文写于三年前,今天才转到这里来。

        在生物的自然进化过程中,两个同源染色体通过交配而重组,生成新的染色体,从而产生新的个体或物种。交配重组是生物遗传和进化过程中的一个主要环节。遗传算法中的交叉算子就是通过模仿这个交配重组的环节而产生的。

        交叉又称重组,是指把两个父代个体的部分结构加以替换、重组而生成新个体的操作。交叉操作的作用是组合出新的个体,在串空间进行有效搜索,同时降低对有效模式的破坏概率。交叉操作是遗传算法区别于其它进化算法的重要特征,在遗传算法的运算中起核心作用。

        那么,设计交叉算子需考虑如下两点:

        1)需保证前一代中优秀个体的性状能够在后一代的新个体中尽可能地得到遗传和继承;

        2)交叉算子设计要和编码设计协调操作。

        交叉算子的设计主要包括以下两个方面的内容:

        1)如何确定交叉点的位置;

        2)如何进行部分基因交换。

        二进制编码的主要交叉操作有:一点交叉、两点交叉、多点交叉、均匀交叉等。

        一点交叉又称简单交叉,它是指在个体基因串中只随机设置一个交叉点,然后随机选择两个个体做为父代个体,相互交换它们交叉点后面的那部分基因块,然后产生两个新的子代个体。

        两点交叉是指在个体基因串中随机设置了两个交叉点,然后再进行部分基因块交换。
        多点交叉,是指在个体基因串中随机设置多个交叉点,然后进行基因块交换。其操作过程与一点交叉和两点交叉相类似。

        均匀交叉,也称一致交叉,其具体运算是通过随机生成一个屏蔽字来决定子代个体如何从父代个体获得基因。这个屏蔽字的长度要与个体基因串长度相同,且均由01生成。比如说屏蔽字的第一位数是0,那么第一个子代个体基因串的第一位基因便继承父代个体A,第二个子代个体基因串的第一位基因便继承父代个体B;如果屏蔽字的第一位数是1,那么第一个子代个体基因串的第一位基因便继承父代个体B,第二个子代个体基因串的第一位基因便继承父代个体A。以此类推。

        均匀交叉在开始迭代时可以加快新的较优模式的发现,在趋于收敛时可防止收敛于局部极值点,而且具有比经典交叉更好的重组能力,但比较容易破坏好的基因模式。在集合覆盖问题中,每个个体的一些优秀的基因模式都有一定的阶,都是以基因块的形式存在的,而均匀交叉只是针对每一位基因进行交换重组,容易破坏好的模式。针对这一点,本文提出基于适应度的广义多点交叉,在保留好的基因模式、减少生成重复个体方面都有很好的表现,并且加快了遗传算法的收敛速度。

        基于适应度的启发式多点交叉:设A和B分别是选择出来进行交叉父代个体,它们的适应度分别为fA和fB,对它们进行交叉操作产生的子代个体记为C,每个个体的基因串长度为L。那么如何确定交叉点的位置呢?以及交叉点的个数有多少?本文记交叉点个数为Nu,交叉点的位置是随机产生的。

      具体操作如下:

       
       
    展开全文
  • 遗传算法是一种启发式算法,那什么是启发式算法呢?简单来讲,启发式算法就是例如遗传算法、模拟退火以及各种种群算法如蚁群算法、鱼群算法、粒子群算法、人工神经网络等等模仿自然界或生命体行为模式的算法,一般...

    你好,我是goldsun

    让我们一起进步吧!

    算法简介

    遗传算法(Genetic Algorithm,GA):是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。

    遗传算法是一种启发式算法,那什么是启发式算法呢?简单来讲,启发式算法就是例如遗传算法、模拟退火以及各种种群算法如蚁群算法、鱼群算法、粒子群算法、人工神经网络等等模仿自然界或生命体行为模式的算法,一般也称为人工智能算法或全局优化算法。

    启发式稍官方的定义是一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。

    相关术语

    因为遗传算法是由进化论和遗传学机理而产生的搜索算法,所以在这个算法中会用到很多生物学知识,下面简单介绍一些相关术语:

    • 转录:是指以DNA为模板,以ATP、UTP、GTP、CTP为原料,按照碱基互补原则,在RNA聚合酶的作用下合成信使RNA的过程,是基因表达的第一步。
    • 翻译:是根据遗传密码的中心法则,将成熟的信使RNA分子中”碱基的排列顺序(核苷酸序列)“解码,并生成对应的特定氨基酸序列的过程。
    • 基因型:性状染色体的内部表现。
    • 表现型:染色体决定的性状的外部表现。
    • 适应度:度量某个物种对于生存环境的适应程度。
    • 选择:以一定的概率从种群中选择若干个个体。一般来说,选择过程是一种基于适应度的优胜劣汰的过程。
    • 交叉:两个染色体的某一相同位置DNA被切断,前后两串分别交叉组合形成两个新的染色体,也称基因重组或杂交。
    • 变异:基因在复制时有一定概率产生复制差错,变异产生新的染色体,表现为新的性状。

    生物遗传与算法间相关术语的关系

    转录 ->编码
    翻译 ->解码
    个体交配->交叉
    染色体变异->变异
    自然选择->适应度函数选择

    编码

    编码是应用遗传算法时要解决的首要问题,也是设计遗传算法时的一个关键步骤。编码方法影响到交叉算子、变异算子等遗传算子的运算方法,很大程度上决定了遗传进化的效率。

    迄今为止人们已经提出了许多种不同的编码方法。总的来说这邪恶编码方法可以分为三大类:二进制编码、浮点是编码、符号编码。

    编码一直是遗传算法的首要难题,目前没有统一的方法可以解决。

    二进制编码

    就像人类的基因含有四种碱基一样。不过在这里我们只用了0和1两种碱基,然后将他们串成一条链形成染色体。一个位能表示出两种状态的信息量,因此足够长的二进制染色体便能表示出所有的特征。

    二进制编码其实就是变为二进制代码的过程。
    首先,要计算出编码长度k
    设某一参数的取值范围为(L,U),使用长度为k的二进制数编码表示该参数,则它共有 2 k 2^k 2k种不同的编码。该参数编码时的对应关系为:

    00000000 = 0 ->L
    00000001 = 1 ->L + δ \delta δ
    00000010 = 2 ->L + 2 δ \delta δ
    00000011 = 3 ->L + 3 δ \delta δ
    ......
    111111111 = 2 k 2^k 2k - 1 -> U = L + ( 2 k 2^k 2k - 1) δ \delta δ
    U = L + ( 2 k − 1 ) δ U = L + (2^k - 1)\delta U=L+(2k1)δ
    则易知:
    δ = U − L 2 k − 1 \bm{\delta} = \bm{\frac{U - L}{2^k - 1}} δ=2k1UL
    δ \delta δ表示求解精度,k是计算链长度,即编码的长。

    实数编码

    本文的示例代码为解决TSP问题,采用实数编码方式。
    实数编码指直接使用实数表示基因,容易理解且不需要解码过程,但容易过早收敛,从而陷入局部最优。

    解码

    解码的目的就是为了将不直观的二进制码还原成十进制。假设一个个体的二进制编码为:
    b k b k − 1 b k − 2 . . . b 3 b 2 b 1 b_kb_{k-1}b_{k-2}...b_3b_2b_1 bkbk1bk2...b3b2b1,则对应的解码公式为:
    x = L + ( ∑ i = 1 k b i 2 i − 1 ) U − L 2 k − 1 x = L + (\sum_{i=1}^kb_i2^{i-1})\frac{U - L}{2^k - 1} x=L+(i=1kbi2i1)2k1UL

    例如:设有参数X,取值为[2,4],现在用3位二进制数对X进行编码,可得 2 3 = 8 2^3 = 8 23=8条染色体:
    000 , 002 , 010 , 011 , 100 , 101 , 110 , 111 000,002,010,011,100,101,110,111 000,002,010,011,100,101,110,111,对于任意的二进制数据串只要代入解码公式,就可以得到对应的解码,如 x 4 = 011 x_4 = 011 x4=011,则它对应的十进制数为:
    ∑ i = 1 3 b i 2 i − 1 = 1 ∗ 2 0 + 1 ∗ 2 1 + 0 ∗ 2 2 = 3 \sum_{i=1}^3b_i2^{i-1} = 1*2^0 + 1*2^1 + 0*2^2 = 3 i=13bi2i1=120+121+022=3,则对应的参数X的值为:
    x = 2 + 3 ∗ 4 − 2 2 3 − 1 = 2.8571 x = 2 + 3 *\frac{4 - 2}{2^3 - 1} = 2.8571 x=2+323142=2.8571

    适应度函数

    适应度函数用来评价一个个体(解)的好坏程度,它是遗传算法进化过程的驱动力,也是进行自然选择的唯一标准,它的设计应结合求解问题本身的要求而定。
    例如求解一个函数的最值,那么函数的法则就用来做适应度函数。

    遗传算子

    选择算子

    选择算子:适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体,被遗传到下一代群体中的概率小。
    选择操作的任务就是从父代群体中选取一些个体,遗传到下一代群体。
    基本的遗传算法采用轮赌法进行,思想是各个个体被选中的概率与其适应度函数值大小成正比。

    如设群体大小为N, x i x_i xi的适应度为 f ( x i ) f(x_i) f(xi),则个体的 x i x_i xi的选择概率为:
    p ( x i ) = f ( x i ) ∑ j = 1 n f ( x j ) p(x_i) = \frac{f(x_i)}{\sum_{j=1}^nf(x_j)} p(xi)=j=1nf(xj)f(xi),这为其基本思想,在计算机程序中可以以如下的方法进行实现:

    1. 在[0,1]内产生一个均匀分布的随机数r
    2. r ⩽ q 1 r \leqslant q_1 rq1,则染色体 x 1 x_1 x1被选中
    3. q k − 1 < r ⩽ q k ( 2 ⩽ k ⩽ N ) , q_{k-1} < r \leqslant q_k (2\leqslant k \leqslant N), qk1<rqk(2kN),则染色体 x k x_k xk被选中
    4. 其中的 q i q_i qi称为染色体 x i ( i = 1 , 2 , . . . , N ) x_i(i = 1,2,...,N) xi(i=1,2,...,N)的累计概率,其计算公式为: q i = ∑ j = 1 i p ( x j ) q_i = \sum_{j=1}^ip(x_j) qi=j=1ip(xj)

    假若有染色体:
    s i = 13 ( 01101 ) s 2 = 24 ( 11000 ) s 3 = 8 ( 01000 ) s 4 = 19 ( 10011 ) s_i=13(01101)\quad s_2=24(11000)\quad s_3 = 8(01000)\quad s_4=19(10011) si=13(01101)s2=24(11000)s3=8(01000)s4=19(10011)
    若要求解 f ( x ) = x 2 f(x)=x^2 f(x)=x2的适应度,那么轮盘赌算法如下:
    f ( s 1 ) = x 1 2 = 169 f(s_1)=x_{1}^{2}=169 f(s1)=x12=169 f ( s 2 ) = 576 f(s_2) = 576 f(s2)=576 f ( s 3 ) = 64 f(s_3)=64 f(s3)=64 f ( s 4 ) = 361 f(s_4)=361 f(s4)=361则染色体的概率为:
    p ( s 1 ) = 0.14 p(s_1)=0.14 p(s1)=0.14 p ( s 2 ) = 0.49 p(s_2)=0.49 p(s2)=0.49 p ( s 3 ) = 0.06 p(s_3)=0.06 p(s3)=0.06 p ( s 4 ) = 0.31 p(s_4)=0.31 p(s4)=0.31

    交叉算子

    在遗传算法中,交叉有很多种实现方法,如:

    1.单点交叉法
    2.两点交叉法
    3.PMX(洗牌)交叉法
    4.均匀交叉法
    5.离散交叉法
    ······

    交叉运算,是指对两个相互配对的染色体依据交叉概率 P c P_c Pc按某种方式相互交换其部分基因,从而形成两个新的个体。基本的遗传算法采用单点交叉。如下所示:
    11010111110010 -> 11010101001010
    10010101001010 -> 10010111110010

    而当采用其它编码方式时,如实数编码会产生一些问题,如下所示:
    4287/1653
    6138/5274
    交叉后:
    6138/1653
    4287/5274
    从交叉结果来看,字串中出现了重复的码,但在一些问题中,串中的码不允许出现重复现象,如TSP问题,那么可以采用如下方法:

    • 单点交叉映射法
    • 单点顺序交叉法

    单点映射交叉法:对于交叉点前的码,检查其出现的遍历重复,依据交叉点后的位置映射关系,逐一进行交换。
    使用前:
    9 1 4 5 6 / 9 5 4 7
    6 8 1 2 3 / 7 8 3 2
    使用后:
    8 1 2 3 6 9 5 4 7
    6 9 1 4 5 7 8 3 2
    单点顺序交叉法:设两父串为A,B.随机选取交叉点,定义交叉点后面为匹配区域,首先将A和B的匹配区域分别加到B和A的前面, 然后分别在匹配区域后依次删除与匹配区域相同的码得到最终的子串。
    如:
    9 1 4 5 6 / 7 8 3 2
    6 8 1 2 3 / 9 5 4 7
    变化得:
    9 5 4 7 / 9 1 4 5 6 7 8 3 2
    7 8 3 2 / 6 8 1 2 3 9 5 4 7
    消除重复得:
    9 5 4 7 1 6 8 3 2
    7 8 3 2 6 1 9 5 4

    变异算子

    变异运算,是指改变个体编码串中的某些基因值,从而形成新的个体。
    决定遗传算法的局部搜索能力,保持种群多样性。
    交叉运算和变异运算的相互配合,共同完成对搜索空间的全局搜索和局部搜索。
    基本遗传算法(SGA)中变异算子采用基本位变异算子。
    基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于二进制编码符号串所表示的个体,若需要进行变异操作的某一基因座上的原有基因值为0,则将其变为1;
    反之,若原有基因值为1,则将其变为0 。
    如:
    10010101001010
    变化得:
    10011101001010

    算法步骤

    • 初始化种群
    • 计算种群上每个个体的适应度
    • 按由个体适应度所决定的某个规则选择将进入下一代的个体
    • 按概率Pc进行交叉操作
    • 按概率Pm进行变异操作
    • 若没有满足某种停止条件,则转入第2步
    • 输出种群中适应度最优的染色体作为问题的满意解或最优解。

    实例代码

    代码以函数及主代码的方式存在,其中,读取的文件是一个写了城市数据的.txt文件,代码末尾给出数据,代码如下:
    主代码

    clear all;
    close all;
    
    CityNum=48; 
    inn=30; %初始种群大小  
    gnmax=10000;  %最大代数  
    pc=0.8; %交叉概率  
    pm=0.5; %变异概率  
    [dislist,Clist]=tsp(CityNum); %dislist为距离方阵,Clist就是48行两列的原数据
    
    %产生初始种群  
    s=zeros(inn,CityNum);  %30行,48列
    for i=1:inn  
        s(i,:)=randperm(CityNum);  %randperm(N) 返回一个长度为N,数值是1:N的随机打乱的数组
    end  
    [~,p]=objf(s,dislist);  
      
    gn=1;  %当前代数
    ymean=zeros(gn,1);  
    ymax=zeros(gn,1);  
    xmax=zeros(inn,CityNum);  
    scnew=zeros(inn,CityNum);  
    smnew=zeros(inn,CityNum);
    tic
    %10000代迭代开始
    while gn<gnmax+1  
       for j=1:2:inn  
          seln=sel(p);  %选择操作  
          scro=cro(s,seln,pc);  %交叉操作  
          scnew(j,:)=scro(1,:);  
          scnew(j+1,:)=scro(2,:);  
          smnew(j,:)=mut(scnew(j,:),pm);  %变异操作  
          smnew(j+1,:)=mut(scnew(j+1,:),pm);  
       end  
       s=smnew;  %产生了新的种群  
       [f,p]=objf(s,dislist);  %计算新种群的适应度  
       %记录当前代最好和平均的适应度  
       [fmax,nmax]=max(f);  
       ymean(gn)=1000/mean(f);  
       ymax(gn)=1000/fmax;  
       %记录当前代的最佳个体  
       x=s(nmax,:);  
       xmax(gn,:)=x;  
       %drawTSP(Clist,x,ymax(gn),gn,0);  
       gn=gn+1;  
    end
    toc
    [min_ymax,index]=min(ymax);  
    drawTSP(Clist,xmax(index,:),min_ymax,index,1);
    
    % figure(2);  
    % plot(ymax,'r'); hold on;  
    % plot(ymean,'b');grid;  
    % title('搜索过程');  
    % legend('最优解','平均解');  
    fprintf('遗传算法得到的最短距离:%.2f\n',min_ymax);  
    fprintf('遗传算法得到的最短路线');  
    disp(xmax(index,:));  
    

    求距离矩阵代码

    %城市位置坐标  
    function [DLn,cityn]=tsp(n)  
    DLn=zeros(n,n);  
    city=importdata('att48.txt');
    %利用整数编码对城市编码
    for i=1:48  
        for j=1:48
            %伪欧式距离,最优解为10628
            dst1=(((city(i,1)-city(j,1))^2+(city(i,2)-city(j,2))^2)/10)^0.5;  
            dst2=round(dst1);    %round函数对每个元素进行四舍五入取整
            if (dst2 < dst1)
                DLn(i,j) = dst2 + 1;  
                DLn(j,i) = DLn(i,j);
            else 
                DLn(i,j) = dst2;  
                DLn(j,i)=DLn(i,j);
            end
        end  
    end  
    cityn=city;  
    end
    

    选择代码

    function seln=sel(p)  %轮盘赌选择
    seln=zeros(2,1);  
    %从种群中选择两个种群,最好不要两次选择同一个种群 
    for i=1:2  
       r=mod(randi([1,65535]),1000)/1000.0;  %产生一个随机数  
       prand=p-r;  
       j=1;  
       while prand(j)<0  %当随机概率小于个体累计概率时则选中
           j=j+1;  
       end  
       seln(i)=j; %选中个体的序号  
       if i==2&&j==seln(i-1)    %%若相同就再选一次  
           r=rand;  %产生一个随机数  
           prand=p-r;
           j=1;
           while prand(j)<0  
               j=j+1;  
           end  
       end  
    end  
    end  
    

    交叉代码

    %根据变异(交叉)概率判断是否变异(交叉)
    %((rand()%100 + 0.0) / 100)
    %产生的随机数小于变异(交叉)概率 则该个体进行变异(交叉)
    function pcc=pro(pc)  
        test(1:100)=0;  
        l=round(100*pc);  
        test(1:l)=1;  
        n=round(rand*99)+1;  
        pcc=test(n);     
    end  
    

    求累计概率代码

    function [f,p]=objf(s,dislist)%传入初始化种群、距离方阵
      
    inn=size(s,1);  %读取种群大小,30  
    f=zeros(inn,1);  %f为存放30个种群适应度的矩阵
    for i=1:inn  
       f(i)=CalDist(dislist,s(i,:));  %计算函数值,即适应度,就是此种群总城市距离  
    end  
    f=1000./f'; %取距离倒数  ,f可以理解为某种概率,代表选择程度,越大越选择
      
    %根据个体的适应度计算其被选择的概率  
    fsum=0;  
    for i=1:inn  
       fsum=fsum+f(i)^15;% 让适应度越好的个体被选择概率越高  
    end  
    ps=zeros(inn,1);  
    for i=1:inn  
       ps(i)=f(i)^15/fsum;  
    end  
      
    %计算累积概率  
    p=zeros(inn,1);  
    p(1)=ps(1);  
    for i=2:inn  
       p(i)=p(i-1)+ps(i);  
    end  
    p=p';  
    end  
    

    变异代码

    %“变异”操作  
    function snnew=mut(snew,pm)  
      
    bn=size(snew,2);  
    snnew=snew;  
      
    pmm=pro(pm);  %根据变异概率决定是否进行变异操作,1则是,0则否  
    if pmm==1  
       c1=mod(randi([65535]),48);  %在[1,bn-1]范围内随机产生一个变异位  
       c2=mod(randi([65535]),48);  
       chb1=min(c1,c2);  
       chb2=max(c1,c2);  
       x=snew(chb1+1:chb2);  
       snnew(chb1+1:chb2)=fliplr(x);  
    end  
    end  
    

    交叉操作代码

    %“交叉”操作  
    function scro=cro(s,seln,pc)  
      
    bn=size(s,2);  
    pcc=pro(pc);  %根据交叉概率决定是否进行交叉操作,1则是,0则否  
    scro(1,:)=s(seln(1),:);  
    scro(2,:)=s(seln(2),:); 
    if pcc==1  
       c1=mod(randi([65535]),48);  %在[1,bn-1]范围内随机产生一个交叉位  
       c2=mod(randi([65535]),48);  
       chb1=min(c1,c2);  
       chb2=max(c1,c2);  
       middle=scro(1,chb1+1:chb2);  
       scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2);  
       scro(2,chb1+1:chb2)=middle;  
       for i=1:chb1  
           while find(scro(1,chb1+1:chb2)==scro(1,i))  
               zhi=find(scro(1,chb1+1:chb2)==scro(1,i));  
               y=scro(2,chb1+zhi);  
               scro(1,i)=y;  
           end  
           while find(scro(2,chb1+1:chb2)==scro(2,i))  
               zhi=find(scro(2,chb1+1:chb2)==scro(2,i));  
               y=scro(1,chb1+zhi);  
               scro(2,i)=y;  
           end  
       end  
       for i=chb2+1:bn  
           while find(scro(1,1:chb2)==scro(1,i))  
               zhi=logical(scro(1,1:chb2)==scro(1,i));  
               y=scro(2,zhi);  
               scro(1,i)=y;  
           end  
           while find(scro(2,1:chb2)==scro(2,i))  
               zhi=logical(scro(2,1:chb2)==scro(2,i));  
               y=scro(1,zhi);  
               scro(2,i)=y;  
           end  
       end  
    end  
    end  
    

    适应度函数代码

    %适应度函数  
    function F=CalDist(dislist,s)  
      
    DistanV=0;  
    n=size(s,2);  %n为城市数目
    for i=1:(n-1)  
        DistanV=DistanV+dislist(s(i),s(i+1));  %把此种群总城市距离加起来
    end  
    DistanV=DistanV+dislist(s(n),s(1));  
    F=DistanV;  
    end
    

    画图代码

    %画图  
    function drawTSP(Clist,BSF,bsf,p,f)
    CityNum=size(Clist,1);  
    for i=1:CityNum-1  
        plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'ms-','LineWidth',1,'MarkerEdgeColor','k','MarkerFaceColor','g');  
        text(Clist(BSF(i),1),Clist(BSF(i),2),['  ',int2str(BSF(i))]);  
        text(Clist(BSF(i+1),1),Clist(BSF(i+1),2),['  ',int2str(BSF(i+1))]);  
        hold on;  
    end  
    plot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist(BSF(1),2)],'ms-','LineWidth',1,'MarkerEdgeColor','k','MarkerFaceColor','g');  
    title([num2str(CityNum),'城市TSP']);  
    if f==0&&CityNum~=10  
        text(10,5500,['第 ',int2str(p),' 代','  最短距离为 ',num2str(bsf)]);  
    else  
        text(10,5500,['最终搜索结果:最短距离 ',num2str(bsf),', 在第 ',num2str(p),' 代达到']);  
    end  
    hold off;  
    pause(0.05);   
    end 
    

    数据

    6734 1453
    2233 10
    5530 1424
    401 841
    3082 1644
    7608 4458
    7573 3716
    7265 1268
    6898 1885
    1112 2049
    5468 2606
    5989 2873
    4706 2674
    4612 2035
    6347 2683
    6107 669
    7611 5184
    7462 3590
    7732 4723
    5900 3561
    4483 3369
    6101 1110
    5199 2182
    1633 2809
    4307 2322
    675 1006
    7555 4819
    7541 3981
    3177 756
    7352 4506
    7545 2801
    3245 3305
    6426 3173
    4608 1198
    23 2216
    7248 3779
    7762 4595
    7392 2244
    3484 2829
    6271 2135
    4985 140
    1916 1569
    7280 4899
    7509 3239
    10 2676
    6807 2993
    5185 3258
    3023 1942
    

    将此数据复制粘贴入.txt文件即可,如出现问题可私聊我,如果觉得文章有用,请点个赞吧,谢谢!

    展开全文
  • 总结五种常见启发式算法(遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法和粒子群算法)求解TSP问题的效果,并针对存在的问题进行简单讨论。

    1. 前言

    本文将总结先前设计的五个启发式算法的求解效果,算法文章如下表:

    智能优化算法类别启发式算法求解TSP问题系列博文
    进化算法遗传算法求解TSP问题
    仿人智能优化算法禁忌搜索算法求解TSP问题
    仿自然优化算法模拟退火算法求解TSP问题
    群智能优化算法蚁群算法求解TSP问题
    群智能优化算法粒子群算法求解TSP问题

    上述博文中所采用的例子是随机在(0,101)二维坐标平面上生成的20个城市数据,五种常见启发式算法在此例子上均能取得较好的表现,为了进一步对比算法求解的效果,本文将扩大城市规模进行算法测试,即随机在(0,101)二维坐标平面上生成50个城市数据。

    #随机生成城市数据代码,CityNum、MinCoordinate、MaxCoordinate三个参数可调节
    CityNum = 50#城市数量
    MinCoordinate = 0#二维坐标最小值
    MaxCoordinate = 101#二维坐标最大值
    CityCoordinates = [(random.randint(MinCoordinate,MaxCoordinate),random.randint(MinCoordinate,MaxCoordinate)) for i in range(CityNum)]
    
    #20个城市数据
    CityCoordinates = [(88, 16),(42, 76),(5, 76),(69, 13),(73, 56),(100, 100),(22, 92),(48, 74),(73, 46),(39, 1),(51, 75),(92, 2),(101, 44),(55, 26),(71, 27),(42, 81),(51, 91),(89, 54),(33, 18),(40, 78]
    
    #50个城市数据
    CityCoordinates = [(71, 71),(68, 71),(19, 41),(9, 67),(22, 34),(15, 2),(60, 56),(36, 38),(18, 92), (96, 27),(71, 85),(24, 70),(12, 31),(77, 88),(59, 49),(27, 87),(94, 97),(37, 42),(32, 78),(65, 57), (96, 47),(95, 86),(61, 80),(55, 7),(94, 74),(39, 6),(62, 43),(34, 11),(18, 89),(79, 16),(100, 99),(76, 39),(35, 51),(74, 71),(59, 48),(98, 1),(35, 98),(82, 91),(0, 64),(56, 48),(89, 8),(69, 54),(3, 72),(79, 16),(66, 88),(80, 15),(56, 88),(30, 57),(67, 86),(75, 4)]
    

    2. 算法求解效果分析与讨论

    以下采用50个城市数据进行分析,只调节算法参数,不更改算法设计,具体设计可参考原博文。

    #50个城市数据,编号分别为0,1,...,49
    CityCoordinates = [(71, 71),(68, 71),(19, 41),(9, 67),(22, 34),(15, 2),(60, 56),(36, 38),(18, 92), (96, 27),(71, 85),(24, 70),(12, 31),(77, 88),(59, 49),(27, 87),(94, 97),(37, 42),(32, 78),(65, 57), (96, 47),(95, 86),(61, 80),(55, 7),(94, 74),(39, 6),(62, 43),(34, 11),(18, 89),(79, 16),(100, 99),(76, 39),(35, 51),(74, 71),(59, 48),(98, 1),(35, 98),(82, 91),(0, 64),(56, 48),(89, 8),(69, 54),(3, 72),(79, 16),(66, 88),(80, 15),(56, 88),(30, 57),(67, 86),(75, 4)]
    

    2.1 遗传算法

    #GA参数
    generation = 1000  #迭代次数
    popsize = 100   #种群大小
    tournament_size = 5 #锦标赛小组大小
    pc = 0.95   #交叉概率
    pm = 0.1    #变异概率
    

    最优解为[25, 27, 5, 12, 2, 4, 7, 17, 32, 47, 38, 42, 3, 11, 18, 36, 15, 28, 8, 46, 44, 48, 37, 10, 22, 19, 6, 39, 26, 34, 14, 41, 24, 21, 16, 30, 13, 33, 1, 0, 31, 20, 9, 35, 40, 49, 43, 29, 45, 23],其适应度值为681.3,路径图和迭代效果如下:

    在这里插入图片描述
    在这里插入图片描述
    讨论】对比其他几个算法的求解效果,可以发现遗传算法求解表现最差,算法后期迭代收敛性较差,可能是迭代到一定程度种群多样性较低,解决该问题的一个方法是引入“灾变”,丰富种群多样性。在初始解构造上,也可以采用贪婪策略等加速求解过程。

    2.2 禁忌搜索算法

    '''这里采用贪婪算法构造初始解,随机构造初始解方法表现不佳。'''
    #参数
    iterMax = 500#迭代次数
    iterI = 1#当前迭代次数
    #PSO参数
    birdNum = 100#粒子数量
    w = 0.2#惯性因子
    c1 = 0.4#自我认知因子
    c2 = 0.4#社会认知因子
    

    最优解为[38, 42, 28, 8, 15, 36, 46, 22, 44, 48, 10, 13, 37, 16, 30, 21, 24, 33, 0, 1, 41, 19, 6, 34, 14, 39, 26, 31, 20, 9, 35, 40, 45, 43, 29, 49, 23, 25, 27, 5, 12, 2, 4, 7, 17, 32, 47, 18, 11, 3],其适应度值为563.5,路径图如下:

    在这里插入图片描述

    2.3 模拟退火算法

    模拟退火算法有两个实现思路。
    (1)思路一

    '''思路一,采用贪婪算法构造初始解'''
    #SA参数
    Tend = 0.1
    T = 100
    beta = 0.99
    

    最优解为[8, 28, 15, 18, 11, 47, 32, 17, 7, 4, 2, 12, 5, 27, 25, 23, 49, 45, 29, 43, 40, 35, 9, 20, 31, 26, 34, 14, 39, 6, 19, 41, 1, 0, 33, 10, 48, 44, 22, 46, 13, 37, 16, 30, 21, 24, 36, 3, 42, 38],其适应度值为635.0,路径图和迭代图如下。
    在这里插入图片描述
    在这里插入图片描述
    讨论】这里存在一个问题:在第一次迭代之后就取得最优解,之后的搜索都是无效的(多次运行结果都是这样),深入分析后发现,是直接应用Metropolis准则所导致,裂解在random.random() < math.exp(-(new_value-value)/T)中被频繁接受(即math.exp(-(new_value-value)/T)概率太大导致,也与新解new_value和当前最优解value之差有很大关系),这导致搜索不具备趋向性(不在目前最优解附近寻优),收敛较差,随机性太强。亟待寻找替他合适函数改进/替代。

    (2)思路二

    '''思路二'''
    #SA参数
    Tend = 0.01
    T = 100
    beta = 0.98
    

    最优解为[42, 3, 38, 11, 18, 15, 28, 8, 36, 46, 22, 48, 44, 10, 13, 37, 16, 30, 21, 24, 33, 0, 1, 19, 41, 6, 14, 34, 39, 26, 31, 20, 9, 45, 29, 43, 49, 40, 35, 23, 25, 27, 5, 12, 4, 2, 7, 17, 32, 47],其适应度值为595.2,路径图如下:

    在这里插入图片描述

    2.4 蚁群算法

    #参数
    iterMax = 500#迭代次数
    #ACO参数
    antNum = 50#蚂蚁数量
    alpha = 2#信息素重要程度因子
    beta = 1#启发函数重要程度因子
    rho = 0.2#信息素挥发因子
    Q = 100.0#常数
    

    最优解为[4, 2, 12, 5, 27, 25, 23, 49, 43, 45, 29, 40, 35, 9, 20, 31, 26, 39, 34, 14, 6, 19, 41, 33, 0, 1, 22, 48, 44, 10, 13, 37, 16, 30, 21, 24, 46, 28, 8, 15, 36, 18, 11, 3, 38, 42, 32, 47, 17, 7],其适应度值为 625.7,路径图和迭代图如下:

    在这里插入图片描述
    在这里插入图片描述
    讨论】城市数量从20增加50,运算时间增加特别明显,50个数据运算时间了得有几个小时,其他的算法都是几分钟级别的。。。原因大概是算法设计导致的,原算法设计在每一次迭代中,针对每一只蚂蚁,有四个操作(如下面代码所示):轮盘赌选择后续城市、计算适应度、更新当前蚂蚁信息素增量、更新转移概率,其中轮盘赌选择后续的操作效率是比较低的,或许可以尝试采用锦标赛算子减少计算量,其次每一只蚂蚁完成城市旅行后都进行更新蚂蚁信息素和更新转移概率,计算量也是比较大的,可以调整为每一代蚂蚁都完成城市旅行后在进行更新,这可以大大减少计算量,但是可能会影响收敛效果,亟待改进测试。

    for i in range(antNum):#根据转移概率选择后续途径城市,并计算适应值
    	antCityList[i] = select(antCityList[i],antCityTabu[i],trans_p)#轮盘赌选择后续城市
    	fitList[i] = calFitness(antCityList[i],dis_matrix)#计算适应度,即路径长度
    	pheromone = updatePheromone(pheromone,fitList[i],antCityList[i],rho,Q)#更新当前蚂蚁信息素增量
    	trans_p = calTrans_p(pheromone,alpha,beta,dis_matrix,Q)#更新转移概率
    

    2.5 粒子群算法

    #参数
    iterMax = 1000#迭代次数
    #PSO参数
    birdNum = 100#粒子数量
    w = 0.2#惯性因子
    c1 = 0.4#自我认知因子
    c2 = 0.4#社会认知因子
    

    最优解为[6, 14, 34, 39, 26, 31, 20, 9, 35, 40, 43, 45, 29, 49, 23, 25, 27, 5, 12, 2, 4, 7, 17, 32, 47, 11, 3, 38, 42, 28, 8, 15, 18, 36, 46, 22, 44, 48, 10, 13, 37, 16, 30, 21, 24, 33, 0, 1, 41, 19],其适应度值为564.0,路径图和迭代图如下:

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

    3. 总结

    算法设计和参数的选择很大程度上影响优化算法的求解效果和效率,在比较算法效果的时候也应在特定的算法设计和参数组合下讨论。在本实验的五种算法求解中,20个城市数据基本都能取得较好的效果,当城市规模扩大到50时,求解效果最好的是禁忌搜索算法(563.5)和粒子群算法(564.0),模拟退火算法中,算法设计思路二取得不错的效果(595.2),而蚁群算法( 625.7)和遗传算法(681.3)则表现不佳。当然,如果不采用贪婪算法构造初始解,禁忌搜索算法和模拟退火算法搜索解的效果也会大打折扣,反过来想,遗传算法和蚁群算法如果引入贪婪策略进行改进,求解质量上应该会较大的提升。

    TSP系列目录
    智能优化算法类别启发式算法求解TSP问题系列博文
    进化算法遗传算法求解TSP问题
    仿人智能优化算法禁忌搜索算法求解TSP问题
    仿自然优化算法模拟退火算法求解TSP问题
    群智能优化算法蚁群算法求解TSP问题
    群智能优化算法粒子群算法求解TSP问题
    总结篇五种常见启发式算法求解TSP问题
    改进篇遗传-粒子群算法&遗传-禁忌搜索算法求解TSP问题

    记录学习过程,欢迎指正

    展开全文
  • 启发式规则使车辆通过交叉路口而不会发生碰撞。 基于启发式规则,DDPG用于优化车辆的协同控制并提高交通效率。 仿真结果表明,与现有方法相比,所提算法在不发生碰撞的情况下可将多个路口的出行效率提高4.59倍。 ...
  • 遗传算法:交叉算子的分类

    千次阅读 2020-05-15 12:52:09
    1.Cut-Point Based:这种方式的交叉操作非常简单,但是效果并不是很好,因为相同的基因集合在父代与子代中流转 one-point, two-point and the n-point crossover M-X (M) Crossover 2013:对父代基因分成3个block...
  • 启发式算法和元启发式算法

    千次阅读 2019-10-13 12:08:59
    启发式算法(Heuristic Algorigthm): 是一种基于直观或经验构造的算法,在可接受的花费(指计算时间、计算空间等)给出待解决优化问题的每一实例的一个可行解,该可行解与与最优解的偏离程度一般不可以事先预计。 启发...
  • 启发式算法 定义:启发式算法(heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指计算...
  • 五种典型启发式算法对比总结

    千次阅读 2021-08-24 16:42:49
    五种启发式算法包括:遗传算法,粒子群算法,蚁群算法,禁忌搜索,模拟退火 之前的博文中已经写了五种启发式算法的偏应用的总结,避开背景知识和代码,已经尝试从问题和解的角度去总结五种算法的流程和思路 其中: ...
  • 启发式算法

    千次阅读 2021-08-07 20:45:11
    启发式算法写在前面在这里插入图片描述传统启发式算法贪心算法局部搜索爬山算法元启发式算法禁忌搜索模拟退火算法遗传算法蚁群算法粒子群优化算法超级启发式算法参考 想了好久,还是准备要写下这篇文章,好好总结...
  • 启发式算法介绍

    千次阅读 2019-08-10 16:30:53
    启发式算法(Heuristic Algorithm)有不同的定义:一种定义为,一个基于直观或经验的构造的算法,对优化问题的实例能给出可接受的计算成本(计算时间、占用空间等)内,给出一个近似最优解,该近似解于真实最优解的...
  • 启发式搜索算法

    2021-08-24 21:57:55
    遗传算法:遗传算法本质上,是一种高效的启发式搜索算法。   算法步骤:(1)产生种群,在此,相当于产生染色体,本质上是对问题的解进行编码。常见的编码方案有:二进制编码,浮点编码等。 (2)计算适应度:...
  • 【图论学习笔记四】启发式算法

    千次阅读 2020-06-24 16:35:15
    启发式算法的上下文中,启发式将是执行小的修改的一种方法,或一系列的修改,对给定解或部分解的修正,为了得到不同的解或部分解决方案。实际的修改这些工作将涉及到邻居搜索。按照一定的设计策略,一个启发式算法...
  • 启发式算法(Heuristic)概述

    千次阅读 2020-10-13 10:29:47
    启发式算法(Heuristic)概述 一个启发式的例子。 驾驶汽车到达某人的家,写成算法是这样的:沿167 号高速公路往南行至Puyallup;从South Hill Mall 出口出来后往山上开 4.5 英里;在一个杂物店旁边的红绿灯路口右转...
  • 启发式算法详解——遗传算法算法原理算法详解算法详解算法总结 算法原理       遗传算法(Genetic Algorithm)遵循『适者生存』、『优胜劣汰』的原则,是一类借鉴生物界自然选择和自然遗传机制的随机...
  • matlab启发式算法

    千次阅读 2020-10-06 10:40:30
    启发式算法 (Heuristic Algorithm) 是一种基于直观或经验的局部优化算法.。 启发式算法的定义: 人们常常把从大自然的运行规律或者面向具体问题的经验和规则中启发出来的方法称之为启发式算法. 现在的启发式算法也...
  • 旅行商问题的启发式算法 遗传算法 生成染色体的随机种群 计算每个染色体的适应度 重复步骤 使用选择方法选择父母对 以概率 Pc 通过对父母的交叉生成一个孩子 通过以概率 Pm 交换基因来突变孩子 使用精英主义用新的...
  • 基于最短路径问题提出了带有启 发信息的遗传算法思想,将启发信息加入到了初始种群生成过程中,提出了新的交叉方法。通 过模拟仿真得到了算法的性能参数,并将本文算法和Dijkstra算法进行比较,结果表明,在求 解数据规模...
  • 数学建模(二) 启发式算法

    千次阅读 2019-07-31 11:49:34
    启发式算法 在很长一段时间里,提起数学建模,我就能想到遗传算法,模拟退火,粒子群。提起遗传算法,我就能想到函数GA()。我打开CSDN,输入这些关键字,就可以很轻松的看到这些算法的原理,过程清楚明白。然而,...
  • 使用贪心算法可以获得最高质量的k-D树基于表面积启发式(SAH)的成本优化。而高质量使得光线跟踪时间非常快,这是一个关键的缺点是k-D树建设时间仍然昂贵。这个成本对于渲染动态场景是不合理的未来的视觉计算应用在...
  • 启发式算法是一种技术,这种技术使得在可接受的计算成本内去搜寻最好的解,但不一定能保证所得的可行解和最优解,甚至在多数情况下,无法阐述所得解同最优解的近似程度。 就是说这种算法的全局最优解只是理论上可行...
  • 来源:人机与认知实验室一般而言,机器常常被设定从已知推未知,而人们不时会从未知(假设)推未知,特殊情形下也有从未知推已知的,这些推导中常见的有产生式和启发式,那么究竟什么是产生式和启发式...
  • 启发式算法(Heuristic Algorithm)

    千次阅读 2019-01-17 10:56:42
    启发式算法(Heuristic Algorithm)有不同的定义:一种定义为,一个基于直观或经验的构造的算法,对优化问题的实例能给出可接受的计算成本(计算时间、占用空间等)内,给出一个近似最优解,该近似解于真实最优解的...
  • 经典的启发式算法

    千次阅读 2020-05-03 23:09:35
    启发式算法一般用于解决NP-hard问题,其中NP是指非确定性多项式。 启发式算法是相对于最优化算法提出的,是基于直观或者经验构造的算法,在可接受的开销(时间和空间)内给出待解决组合优化问题的一个可行解。 例子...
  • matlab遗传算法锦标赛选择
  • 各种元启发式算法(Metaheuristics)介绍前言一、模拟退火算法(Simulated Annealing)1.二、使用步骤1.引入库2.读入数据总结 前言 元启发式算法能够在一定程度上在全局进行搜索,找到最优解的近似解。元启发式算法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,944
精华内容 5,177
关键字:

启发式交叉