Как реализовать выбор колесика рулетки и раскол на коде Matlab для коммивояжера Problom?

Question

У меня есть назначение, кодирующее генетический алгоритм для проблемы коммивояжера. Я написал код, который дает правильные результаты с помощью выбора турнира. Проблема в том, что мне нужно сделать Wheel and 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; 

То, что я хочу, чтобы заменить код турнира с колесом и рангом кода.

Вот что я написал для выбора колеса:

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

Answer 1

Для выбора колес для работы, вы должны начать с проектирования фитнес-мера с слесарно лиц, имеющих большую ценность. В отличие от расстояния, где лучшие люди имеют меньшую ценность. Тогда ваш подход с cumsum должен работать.

Где проблема с выбором рейтинга?

Answer 2

Вот Векторизованное осуществление выбора колеса рулетки в Matlab:

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

Это предполагает, что пригодность вход в схему выбора представляет собой матрицу размера (popSize х 1) (или вектор-столбец такого же размера, как и число членов населения).

И popSize - это, очевидно, количество членов вашего населения. И W - победители или члены населения, которые выбраны для того, чтобы стать родителями/кроссоверами.

Результат выбора будет выбран_parents, который представляет собой вектор двойной строки размером 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)); 

Эта мутация случайным образом переворачивает порядок из двух городов в нашем туре (геноме).

Наконец-то обязательно обновите свое население после всей нашей работы!

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

Так я знаю, что этот ответ, вероятно, слишком поздно для вашего назначения, но, надеюсь, это поможет кому-то еще с подобной проблемой.

Я действительно рекомендую всем, кто интересуется векторизованных генетических алгоритмов в Matlab, чтобы прочитать эту статью: UCL: Efficiently Vectorized Code for Population Based Optimization Algorithms

Это то, что я на основе всего кода прочь в примерах и она научит вас, почему вы пишете код таким образом. Это отличный ресурс и то, что меня начала с GA.