%xy=pobieranieDanych;
load('kwiatek.mat');
%load('tarcza.mat');

%liczba miast
nmiast=size(xy,1);

%macierz odleglosci miedzy miastami
odleglosci = zeros(nmiast, nmiast);
for i=1:nmiast
    for j=1:nmiast
        odleglosci(i,j) = sqrt((xy(i,1)-xy(j,1))^2 + (xy(i,2)-xy(j,2))^2);
    end
end

%liczba osobnikow w populacji
nosobnikow = 80;

pMut = 0.2;%UZUPEŁNIJ       %p-wo mutacji
pCross =0.1; %UZUPEŁNIJ     %p-wo krzyżowania

%inicjalizacja populacji
pop = zeros(nosobnikow,nmiast);
for n=1:nosobnikow
    pop(n,:)=randperm(nmiast); %każdy osobnik to losowa trasa
end

newpop = zeros(size(pop));


maxepochs = 10000;
historia = zeros(1,maxepochs);

%wyświetlenie dwóch okien obok siebie
h1 = gcf;
set(h1,'Units','normalize');
outerpos = get(h1,'OuterPosition');
outerpos(1) = (1-2*outerpos(3))/2;
set(h1,'OuterPosition',outerpos);
h2 = figure;
set(h2,'Units','normalize');
outerpos(1) = (1-2*outerpos(3))/2+outerpos(3);
set(h2,'OuterPosition',outerpos);

showInterval = 50;

%główna pętla algorytmu
for epoka=1:maxepochs

    %ocena
    dlugosciTras = zeros(1,nosobnikow);

    %UZUPEŁNIJ TUTAJ
     for i=1:nosobnikow
        sum=0;
        for j=1:nmiast-1
            sum = sum + odleglosci(pop(i,j),pop(i,j+1));
        end
        sum = sum + odleglosci(pop(i,nmiast),pop(i,1)); %dodanie odl pomiedzy ostatnim i 1
        dlugosciTras(i) = sum;
    end

    %znalezienie i zapisanie najlepszej trasy (dla elitaryzmu)
    [historia(epoka),bestidx] = min(dlugosciTras);
    besttrasa = pop(bestidx,:);


    %selekcja turniejowa (lub ruletkowa)

    %UZUPEŁNIJ TUTAJ (newpop uzupełniona wyselekcjonowanymi osobnikami z pop)
     for i=1:nosobnikow
        a_rand = randi(nosobnikow);
        b_rand = randi(nosobnikow);
        if(dlugosciTras(a_rand) < dlugosciTras(b_rand))
            newpop(i,:) = pop(a_rand,:);
        else
            newpop(i,:) = pop(b_rand,:);
        end
    end

%     krzyzowanie
%    for n = 1:ceil(pCross*nosobnikow/2)
%        [newpop(2*n-1,:), newpop(2*n,:)] = ...
%            orderedCrossover(newpop(2*n-1,:), newpop(2*n,:));
%    end


    %mutacje

    %mutacja rodzaj 1 (switching)
    %np. [1 2 3 4 5 6] -> [1 5 3 4 2 6]

    %UZUPEŁNIJ TUTAJ
     for i=1:nosobnikow
        if(rand(1) < pMut)
            a_rand = randi(nmiast);
            b_rand = randi(nmiast);
            tmp = newpop(i, a_rand);
            newpop(i, a_rand) = newpop(i, b_rand);
            newpop(i, b_rand) = tmp;
        end
    end


    %mutacja rodzaj 2 (inversion)
    %np. [1 2 3 4 5 6] -> [1 5 4 3 2 6]

    %UZUPEŁNIJ TUTAJ
    for i=1:nosobnikow
        if(rand(1) < pMut)
            aRand = randi(nmiast);
            bRand = randi(nmiast);
            while(aRand > bRand) %wycinek a do b
                aRand = randi(nmiast);
                bRand = randi(nmiast);
            end
            temp = newpop(i, aRand:bRand);
            fliplr(temp);
            newpop(i, aRand:bRand) = temp;

        end
    end
    %mutacja rodzaj 3 (translation)
    %np. [1 2 3 4 5 6] -> [1 5 6 2 3 4]

    %UZUPEŁNIJ TUTAJ
     for i=1:nosobnikow
        if(rand(1) < pMut)
        aRand = randi(nmiast);
        bRand = randi(nmiast);
        while(aRand > bRand)
            aRand = randi(nmiast);
            bRand = randi(nmiast);
        end
       b_rand = newpop(i, bRand:nmiast);
       a_rand = newpop(i, aRand:(bRand-1));
       newpop(i, aRand:(aRand+size(b_rand,2)-1)) = b_rand;
       newpop(i, (aRand+size(b_rand,2)):(aRand+size(b_rand,2)+size(a_rand,2)-1)) = a_rand;
        end
    end

    %zmiana pokolenia
    pop = newpop;

    %elitaryzm
    pop(nosobnikow,:) = besttrasa;

    if mod(epoka,showInterval) == 0
        %wyswietlenie najlepszego (trasa)
        %wyczyszczenie poprzedniej trasy
        set(0,'CurrentFigure',h1)
        clf(h1);
        %narysowanie nowej
        plot(xy(:,1),xy(:,2),'ro');
        line([xy(besttrasa,1)' xy(besttrasa(1),1)],[xy(besttrasa,2)' xy(besttrasa(1),2)])
        axis([0 10 0 10])

        set(0,'CurrentFigure',h2)
        plot(historia(1:epoka))
        title('Zmiana długości trasy najlepszego osobnika w kolejnych populacjach.');
        xlabel('Epoka');
        ylabel('Długość trasy');
        pause(0.01)
    end
end