ga.txt

GA TSP问题

function [bestpath,minpathlong]=GATSP(TSPMatrix,Popsize,MaxGeneration,Pc,Pm)
%遗传算法解决旅行商问题
path=Initialize(Popsize,TSPMatrix);%初始化路径
for i=1:MaxGeneration
    FP=Fitness(path,TSPMatrix);%计算适应度
    path=Select(path,FP);%轮盘赌选择
    for j=1:2:Popsize
        [path(j,:),path(j+1,:)]=Crossover(path(j,:),path(j+1,:),Pc);%交叉,可选共四种交叉方式可供选择CX,OX,EX
    end
    path=Mutation(path,Pm);%变异,有两种方式可供选择
    avgpathlong(i)=sum(pathlong(path,TSPMatrix))/Popsize;%平均长度;
    bestpathlong(i)=min(pathlong(path,TSPMatrix));%最短长度
end
[bestpath,minpathlong]=Output(path,TSPMatrix);%输出结果
%绘图
plot(avgpathlong);
hold on
plot(bestpathlong,'r');



function path=Initialize(Popsize,TSPMatrix)
%初始化路径
for i=1:Popsize
    path(i,:)=randperm(length(TSPMatrix));%randperm(n),生成1到n的随机数
end


function FP=Fitness(path,TSPMatrix)
%计算适应度
[row,col]=size(path);
for i=1:row
    pathlong(i)=0;
    for j=1:(col-1)
        pathlong(i)=pathlong(i)+TSPMatrix(path(i,j),path(i,j+1));
    end
    pathlong(i)=pathlong(i)+TSPMatrix(path(i,j+1),path(i,1));
end
FP=length(TSPMatrix)*max(max(TSPMatrix))-pathlong;
FP=FP./sum(FP);


function pathlong=pathlong(path,TSPMatrix)
%计算路径长度
[row,col]=size(path);
for i=1:row
    pathlong(i)=0;
    for j=1:(col-1)
        pathlong(i)=pathlong(i)+TSPMatrix(path(i,j),path(i,j+1));
    end
    pathlong(i)=pathlong(i)+TSPMatrix(path(i,j+1),path(i,1));
end



function path=Select(path,FP)
%轮盘赌选择
[row,col]=size(path);%

roulette=cumsum(FP);
for i=1:row
    tempP=rand(1);
    for j=1:length(roulette) %length（roulette）的值跟row应该是相等的
        if tempP<roulette(j)
            break;
        end
    end
    selectedpath(i,:)=path(j,:);
end
for i=1:row                         %以下三行我加的
    if FP(i)==max(FP)
        selectedpath(i,:)=path(i,:);%………………
    end
end
path=selectedpath;%适应值大的path将被重复选择，选择后的规模与初始种群规模相同




function [childpath1,childpath2]=Crossover(parentpath1,parentpath2,Pc)
%部分影射交叉PMX
[row,col]=size(parentpath1);
tempP=rand(1);
childpath1=parentpath1;
childpath2=parentpath2;
if(tempP<Pc)
    point=randperm(col-1);
    point1=min(point(1),point(2));
    point2=max(point(1),point(2));
    for j=point1+1:point2
        [rowindex,colindex]=find(parentpath1(j)==parentpath2);
        childpath1(j)=parentpath1(colindex);
        childpath1(colindex)=parentpath1(j);
        [rowindex,colindex]=find(parentpath2(j)==parentpath1);
        childpath2(j)=parentpath2(colindex);
        childpath2(colindex)=parentpath2(j);
        parentpath1=childpath1;
        parentpath2=childpath2;
    end
end




function [childpath1,childpath2]=CXCrossover(parentpath1,parentpath2,Pc)
%循环交叉
tempP=rand(1);
if(tempP<Pc)
    col=length(parentpath1);
    A=zeros(1,col);
    i=1;
    A(i)=1;
    k=1;
    childpath1(1)=parentpath1(1);
    [rwoindex,colindex]=find(parentpath1(1)==parentpath2);
    k=colindex;
    while(not(length(find(k==A))))
        childpath1(colindex)=parentpath1(colindex);
        i=i+1;
        A(i)=k;
        [rwoindex,colindex]=find(parentpath1(colindex)==parentpath2);
        k=colindex;        
    end
    for j=1:col
        if(not(length(find(j==A))))
            childpath1(j)=parentpath2(j);
        end
    end
    childpath2=parentpath2;
    for j=1:col
        if(not(length(find(j==A))))
            childpath2(j)=parentpath1(j);
        end
    end
else
    childpath1=parentpath1;
    childpath2=parentpath2;
end



function [childpath1,childpath2]=EXCrossover(parentpath1,parentpath2,Pc);
%边重组交叉,EX
tempP=rand(1);
if(tempP<Pc)
    col=length(parentpath1);
    adjtable=zeros(col,4);
    for i=1:col
        [rowindex,colindex]=find(i==parentpath1);
        if(colindex==1)
            adjtable(i,1)=parentpath1(col);
            adjtable(i,2)=parentpath1(colindex+1);
        elseif(colindex==col);
            adjtable(i,1)=parentpath1(colindex-1);
            adjtable(i,2)=parentpath1(1);
        else
            adjtable(i,1)=parentpath1(colindex-1);
            adjtable(i,2)=parentpath1(colindex+1);
        end
        [rowindex,colindex]=find(i==parentpath2);
        if(colindex==1)
            if(not(find(parentpath2(col)==adjtable(i,:))))
                adjtable(i,3)=parentpath2(col);
            end
            if(not(find(parentpath2(colindex+1)==adjtable(i,:))))
                adjtable(i,4)=parentpath2(colindex+1);
            end
        elseif(colindex==col)
            if(not(find(parentpath2(colindex-1)==adjtable(i,:))))
                adjtable(i,3)=parentpath2(colindex-1);
            end
            if(not(find(parentpath2(1)==adjtable(i,:))))
                adjtable(i,4)=parentpath2(1);
            end
        else
            if(not(find(parentpath2(colindex-1)==adjtable(i,:))))
                adjtable(i,3)=parentpath2(colindex-1);
            end
            if(not(find(parentpath2(colindex+1)==adjtable(i,:))))
                adjtable(i,4)=parentpath2(colindex1);
            end
        end
    end
    adjtable1=adjtable;
    childpath1(1)=parentpath1(1);
    [rowindex,colindex]=find(parentpath1(1)==adjtable);
    for j=1:length(rowindex)
        adjtable(rowindex(j),colindex(j))=0;
    end
    randvector=randperm(4);
    point=randvector(1);
    while(adjtable(parentpath1(1),point)==0)
        randvector=randperm(4);
        point=randvector(1);
    end
    temp=adjtable(parentpath1(1),point);
    for i=2:col-1
        childpath1(i)=temp;
        [rowindex,colindex]=find(temp==adjtable);
        for j=1:length(rowindex)
            adjtable(rowindex(j),colindex(j))=0;
        end
        randvector=randperm(4);
        point=randvector(1);
        while(adjtable(temp,point)==0)
            randvector=randperm(4);
            point=randvector(1);
        end
        temp=adjtable(temp,point);
    end
    childpath1(col)=temp;
    childpath2(1)=parentpath2(1);
    [rowindex,colindex]=find(parentpath2(1)==adjtable1);
    for j=1:length(rowindex)
        adjtable1(rowindex(j),colindex(j))=0;
    end
    randvector=randperm(4);
    point=randvector(1);
    while(adjtable1(parentpath2(1),point)==0)
        randvector=randperm(4);
        point=randvector(1);
    end
    temp=adjtable1(parentpath2(1),point);
    for i=2:col-1
        childpath2(i)=temp;
        [rowindex,colindex]=find(temp==adjtable1);
        for j=1:length(rowindex)
            adjtable1(rowindex(j),colindex(j))=0;
        end
        randvector=randperm(4);
        point=randvector(1);
        while(adjtable1(temp,point)==0)
            randvector=randperm(4);
            point=randvector(1);
        end
        temp=adjtable1(temp,point);
    end
    childpath2(col)=temp;
else
    childpath1=parentpath1;
    childpath2=parentpath2;
end


function [childpath1,childpath2]=OXCrossover(parent1,parent2,Pc)
%顺序交叉,OX
col=length(parent1);
childpath1=parent1;
childpath2=parent2;
tempP=rand(1);
if(tempP<Pc)
    point=randperm(col)-1;
    point1=min(point(1),point(2));
    point2=max(point(1),point(2));
    temppath1=parent1(point1+1:point2);
    temppath2=parent2(point1+1:point2);
    tempparent1=parent1;
    tempparent2=parent2;
    for j=point1+1:point2
        [rowindex,colindex]=find(parent2(j)==parent1);
        tempparent1(colindex)=0;
        [rowindex,colindex]=find(parent1(j)==parent2);
        tempparent2(colindex)=0;
    end
    parent1=tempparent1;
    parent2=tempparent2;
    temppath=parent1;
    while(parent1(point1+1)~=0)
        for j=1:col-1
            temppath(j)=parent1(j+1);
        end
        temppath(col)=parent1(1);
        parent1=temppath;
     end
     temppath=parent2;
     while(parent2(point1+1)~=0)
         for j=1:col-1
             temppath(j)=parent2(j+1);
         end
         temppath(col)=parent2(1);
         parent2=temppath;
        end
        
     
     for j=1:length(find(0==parent1))
         [rowindex,colindex]=find(0==parent1);
         parent1(colindex(1))=[];
     end
     for j=1:length(find(0==parent2))
         [rowindex,colindex]=find(0==parent2);
         parent2(colindex(1))=[];
     end
     if(point1>0)
         childpath1(1:point1)=parent1(1:point1);
         childpath2(1:point1)=parent2(1:point1);
     end
     childpath1(point1+1:point2)=temppath2;
     
     childpath2(point1+1:point2)=temppath1;
         
     if(point2<col)
        childpath1(point2+1:col)=parent1(point1+1:col-(point2-point1));
        childpath2(point2+1:col)=parent2(point1+1:col-(point2-point1));
    end
end


function path=Mutation(path,Pm)
%位对调变异
[row,col]=size(path);
childpath=path;
for i=1:row
    point=randperm(col);
    tempP=rand(1);
    if(tempP<Pm)
        childpath(i,point(1))=path(i,point(2));
        childpath(i,point(2))=path(i,point(1));
    end
end
path=childpath;



function path=MutationReverse(path,Pm)
%逆转变异
[row,col]=size(path);
childpath=path;
for i=1:row
    point=randperm(col)-1;
    point1=min(point(1),point(2));
    point2=max(point(1),point(2));
    tempP=rand(1);
    if(tempP<Pm)
        for j=point1+1:point2
            childpath(i,j)=path(i,(point2+point1+1-j));
        end
    end
end
path=childpath;