algorithm - 如何在 Matlab 代码中为旅行商问题实现轮盘选择和排名选择？

Question

我有一项任务是为旅行商问题编写遗传算法。我写了一些代码，使用锦标赛选择给出了正确的结果。 问题是，我必须执行 Wheel 和 Rank，但我得到的结果不正确。

这是我使用锦标赛选择的代码:

clc;
clear all;
close all;

nofCities = 30;
initialPopulationSize = nofCities*nofCities;
generations = nofCities*ceil(nofCities/10);

cities = floor(rand([nofCities 2])*100+1);

figure;
hold on;
scatter(cities(:,1), cities(:,2), 5, 'b','fill');
line(cities(:,1), cities(:,2));
line(cities([1 end],1), cities([1 end],2));
axis([0 110 0 110]);

population = zeros(initialPopulationSize ,nofCities);

for i=1:initialPopulationSize 
   population(i,:) = randperm(nofCities);
end

distanceMatrix = zeros(nofCities);
for i=1:nofCities
    for j=1:nofCities
        if (i==j)
            distanceMatrix(i,j)=0;
        else
            distanceMatrix(i,j) = sqrt((cities(i,1)-cities(j,1))^2+(cities(i,2)-cities(j,2))^2);
        end
    end
end

for u=1:generations     
    tourDistance = zeros(initialPopulationSize ,1);
    for i=1:initialPopulationSize 
       for j=1:length(cities)-1
           tourDistance(i) = tourDistance(i) + distanceMatrix(population(i,j),population(i,j+1));
       end
    end
    for i=1:initialPopulationSize 
        tourDistance(i) = tourDistance(i) + distanceMatrix(population(i,end),population(i,1));
    end

    min(tourDistance)

    newPopulation = zeros(initialPopulationSize,nofCities);

    for k=1:initialPopulationSize
        child = zeros(1,nofCities);
        %tournament start
        for i=1:5
           tournamentParent1(i) = ceil(rand()*initialPopulationSize);
        end
        p1 = find(tourDistance == min(tourDistance([tournamentParent1])));
        parent1 = population(p1(1), :);
        for i=1:5
           tournamentParent2(i) = ceil(rand()*initialPopulationSize);
        end
        p2 = find(tourDistance == min(tourDistance([tournamentParent2])));
        parent2 = population(p2(1), :);
        %tournament end
        %crossover
        startPos = ceil(rand()*(nofCities/2));
        endPos = ceil(rand()*(nofCities/2)+10);

        for i=1:nofCities
           if (i>startPos && i<endPos) 
               child(i) = parent1(i);
           end
        end

        for i=1:nofCities
            if (isempty(find(child==parent2(i))))
                for j=1:nofCities
                    if (child(j) == 0)
                        child(j) = parent2(i);
                        break;
                    end
                end
            end
        end

        newPopulation(k,:) = child;
    end

    %mutation
    mutationRate = 0.015;
    for i=1:initialPopulationSize
       if (rand() < mutationRate)
           pos1 = ceil(rand()*nofCities);
           pos2 = ceil(rand()*nofCities);
           mutation1 = newPopulation(i,pos1);
           mutation2 = newPopulation(i,pos2);
           newPopulation(i,pos1) = mutation2;
           newPopulation(i,pos2) = mutation1;           
       end
    end

    population = newPopulation;
    u
end

figure;
hold on;
scatter(cities(:,1), cities(:,2), 5, 'b','fill');
line(cities(population(i,:),1), cities(population(i,:),2));
line(cities([population(i,1) population(i,end)],1), cities([population(i,1) population(i,end)],2));
axis([0 110 0 110]);

%close all;

我想要的是用轮盘和排名代码替换锦标赛代码。

这是我为 Wheel Selection 写的:

 fitness = tourDistance./sum(tourDistance);
        wheel = cumsum(fitness);
        parent1 = population(find(wheel >= rand(),1),:);
        parent2 = population(find(wheel >= rand(),1),:);

Answer 1

这是在 Matlab 中轮盘赌选择的矢量化实现:

[~,W] = min(ones(popSize,1)*rand(1,2*popSize) > ((cumsum(fitness)*ones(1,2*popSize)/sum(fitness))),[],1);

这里假设选择方案中的适应度输入是一个大小为 (popSize x 1) 的矩阵(或与种群成员数量大小相同的列向量)。

而 popSize 显然是您的人口中成员的数量。 W 是获胜者或被选为 parent /交叉的种群成员。

选择的输出将是 selected_pa​​rents，这是一个大小为 2*popSize 的双行向量，其中包含将在交叉阶段使用的种群成员的所有索引。

然后可以将该行向量输入到向量化的交叉方案中，该方案看起来像这样:

%% Single-Point Preservation Crossover
    Pop2 = Pop(W(1:2:end),:);                       % Pop2 Winners 1
    P2A  = Pop(W(2:2:end),:);                       % Pop2 Winners 2
    Lidx = sub2ind(size(Pop),[1:popSize]',round(rand(popSize,1)*(genome-1)+1));
    vLidx = P2A(Lidx)*ones(1,genome);
    [r,c]=find(Pop2==vLidx);
    [~,Ord]=sort(r);
    r = r(Ord); c = c(Ord);
    Lidx2 = sub2ind(size(Pop),r,c);
    Pop2(Lidx2) = Pop2(Lidx);
    Pop2(Lidx) = P2A(Lidx);

此交叉假定选择方案中的 W 变量输入。它还使用 Pop，它是按基因组矩阵存储在 popSize 中的种群成员。 (基因组是一次旅行中的城市数量，也恰好是基因组的大小)。基因组存储为一个整数数组，每个整数代表一个城市，旅行被定义为从基因组数组的值从数组的第一个索引到数组的最后一个索引的顺序。

当我们这样做的时候，我们还可以为置换遗传算法(就是这样)包含一个很好的矢量化变异方案。

     %% Mutation (Permutation)
        idx = rand(popSize,1)<mutRate;
        Loc1 = sub2ind(size(Pop2),1:popSize,round(rand(1,popSize)*(genome-1)+1));
        Loc2 = sub2ind(size(Pop2),1:popSize,round(rand(1,popSize)*(genome-1)+1));

        Loc2(idx == 0) = Loc1(idx == 0);
        [Pop2(Loc1), Pop2(Loc2)] = deal(Pop2(Loc2), Pop2(Loc1));

这个突变随机翻转了我们旅行(基因组)中 2 个城市的顺序。

最后确保在我们完成所有这些工作后更新您的人口!

%% Update Population!
Pop = Pop2; % updates the population to include crossovers and mutation.

所以我知道这个回复对于你的任务来说可能太晚了，但希望它能帮助其他有类似问题的人。

我真的非常推荐任何对 Matlab 中的矢量化遗传算法感兴趣的人阅读这篇论文:UCL: Efficiently Vectorized Code for Population Based Optimization Algorithms

这是我在示例中基于所有代码的基础，它会告诉您为什么要这样编写代码。这是一个很好的资源，也是我开始使用 GA 的原因。