xy=pobieranieDanych;

%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;

%inicjacja populacji
pop = zeros(nosobnikow,nmiast);
for n=1:nosobnikow
pop(n,:)=randperm(nmiast);
end

newpop = zeros(size(pop));

maxepochs = 5000;
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);

for epoka=1:maxepochs

%ocena
dlugosciTras = zeros(1,nosobnikow);

%UZUPELNIJ TU
%wyliczanie trasy korzystajac z tab dlugosc tras

for i=1:nosobnikow
for j=1:nmiast-1
dlugosciTras(i)= dlugosciTras(i) + odleglosci(pop(i,j),pop(i,j+1));
end
dlugosciTras(i) = dlugosciTras(i) + odleglosci(pop(i,1),pop(i,nmiast));
end


%zapisanie najlepszej trasy
[~,bestidx] = min(dlugosciTras);
besttrasa = pop(bestidx,:);
%i aktualizacja historii
historia(epoka) = dlugosciTras(bestidx);


%selekcja (ruletkowa lub turniejowa)

%UZUPELNIJ TU
ocena=ones(1,nosobnikow);
for i=1:nosobnikow
ocena(1,i)=ocena(1,i)/dlugosciTras(1,i);
end

dys=dlugosciTras;
for i=2:nosobnikow
dys(1,i)=dys(1,i)+dys(1,i-1);
end

for i=1:nosobnikow
dys(1,i)=dys(1,i)/dys(nosobnikow);
end

for i=1:nosobnikow
tmp=rand();
for j=1:nosobnikow
if dys(j)>tmp
zm=j;
break;
end
end
newpop(i,:)=pop(zm,:);
end
%krzyzowanie
for i=1:nosobnikow/2 % polowa osobnikow jest krzyżowana
parent1 = randi(nosobnikow); %losowanie
parent2 = randi(nosobnikow);
miejsce_krzyzowania = randi(nmiast-2)+1; %miejsce krzyżowania
PARENT1=newpop(parent1,:);
PARENT2=newpop(parent2,:);
temp = zeros(1,nmiast);
temp1 = zeros(1,nmiast);
temp(1:miejsce_krzyzowania) = pop(parent1,1:miejsce_krzyzowania);
c=miejsce_krzyzowania+1;
for k=1:nmiast
if(isempty(find(temp==PARENT2(k), 1))) %funkcja isempty zwraca 1 jesli tablica pusta, czyli kod można przetłumaczyć "jeśli nie wystąpiła wartość PARENT2(k) w tablicy to rób"
temp(c) = PARENT2(k);
c=c+1;
end
end
temp1(1,(miejsce_krzyzowania+1):end)=pop(parent2,(miejsce_krzyzowania+1):end);
w=1;
for l=1:nmiast
if(isempty(find(temp1==PARENT1(l), 1)))
temp1(w) = PARENT1(l);
w=w+1;
end
end

newpop(parent1,:)=temp(1,:);
newpop(parent2,:)=temp1(1,:);
end


%UZUPELNIJ TU


%mutacja rodzaj 1 (switching)
for i=1:(nosobnikow/4)
osobnik_do_mutacji=randi(nosobnikow);
gen1=randi(nmiast);
gen2=randi(nmiast);
while (gen1==gen2) % dopoki te same geny - wylosuj drugi
gen2=randi(nmiast);
end
temp_mut = newpop(osobnik_do_mutacji,:);

temp_gentomut = temp_mut(1,gen1); %zamiania
temp_mut(1,gen1) = temp_mut(1,gen2);
temp_mut(1,gen2) = temp_gentomut;

newpop(osobnik_do_mutacji,:) = temp_mut; %zapisuje zm osobnika
end

pop=newpop;
%I TU

%mutacja rodzaj 2 (inversion)

%LUB TU

%mutacja rodzaj 3 (translation)

%LUB TU

%elitaryzm
pop(nosobnikow,:) = besttrasa;


%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

Wyszukiwarka

Podobne podstrony:
ALG GEOM
zmiana genetyczna
Phir Bhi Dil Hai Hindustani cd1 Moje Serce Bije Po Indyjsku
Maria Simma Moje przeżycia z duszami czysccowymi
Algorytmy genetyczne a logika rozmyta
SZCZEGÓŁY MOJE
23 eng alg

więcej podobnych podstron