Első labor

Contents

Futásidő jellemzése

1.feladat Egy program futásidejére a 2,3, .. , 10 hosszú bemenetekre rendre 5, 16, 39, 76, 131, 209, 312, 444, 610 mp-t kaptunk. Feltéve, hogy polinomidejű algoritmusról van szó, adjunk becslést a kitevőre.

%{
 t=2:10;
 v=[5, 16,  39, 76,  131,  209,  312, 444, 610];
 plot(log(t),log(v)), tools-> basic fitting-> linear & show equations
%}

Első tesztfeladat a hátizsák-problémára

% Súlyok    1, 10,  1, 10,...

% Értékek: 10,  1, 10,  1,...

% Kapacitás: a tárgyak számának 2.5-szöröse

targyakszama=30;
sulyok=ones(1, targyakszama);
sulyok(2:2:end)=10;

ertekek=ones(1, targyakszama);
ertekek(1:2:end)=10;

kapacitas=targyakszama*2.5;
% ekkor az optimális pakolás 5.2*n lesz (156 itt)
generacio=100;
populaciomeret=30;
keresztezesvaloszinusege=0.9;
mutaciovaloszinusege=0.01;

[fit, vege]=hatizsak_elitista(sulyok,ertekek,kapacitas,...
    keresztezesvaloszinusege, mutaciovaloszinusege, generacio, populaciomeret,4);
vege(1,:)
max(max(fit))
plot(1:generacio, sum(fit)/populaciomeret,'b', 1:generacio, max(fit,[],1),'g' )
xlabel('generációk száma')
ylabel('fitnesz')

ans =

  Columns 1 through 13

     1     1     1     0     1     1     1     0     1     0     1     0     1

  Columns 14 through 26

     1     1     0     1     0     1     1     1     0     1     1     1     0

  Columns 27 through 30

     1     0     1     1


ans =

   156

Második tesztfeladat

kapacitas=targyakszama*0.5;

[fit, vege]=hatizsak_elitista(sulyok,ertekek,kapacitas,...
    keresztezesvaloszinusege, mutaciovaloszinusege, generacio, populaciomeret,4);
vege(1,:)
max(max(fit))
plot(1:generacio, sum(fit)/populaciomeret,'b',...
    1:generacio, max(fit,[],1),'g' )

% Hogyan lehetne ezen javítani?

ans =

  Columns 1 through 13

     1     1     1     1     1     1     0     0     1     1     0     1     1

  Columns 14 through 26

     0     0     1     1     1     1     0     0     0     1     1     0     0

  Columns 27 through 30

     1     0     0     1


ans =

     0

Statisztika készítése Matlabban

Tegyük fel, hogy megváltoztatunk egy operátort egy genetikus algoritmusban. Hogyan tudnánk mérni, hogyan változott az algoritmus teljesítménye? Mivel a genetikus algoritmusok véletlent is használhat, lehet hogy a változás mértéke belefér a véletlen szórásba.

a=randn(1,10); %10 darab normális eloszlosú véletlen szám
b=randn(1,10); %0 várható értékkel

Vehetjük a mintafuttatások átlagát a mean() parancssal, de ha az egyik nagyobb, az lehet az adatok véletlen szórásából (ami kicsi mintaméretnél relatíve nagy).

mean(a) %mean egyben a legjobb tippünk a várható értékre is, azaz arra,

ans =

    0.3340

mean(b) %hogy nagyon sok próbálkozás esetén mennyi lesz az átlag

ans =

   -0.2135

aa=randn(1,100);
bb=randn(1,100);

mean(aa)

ans =

   -0.0803

mean(bb)

ans =

    0.0643

Legyen v és w két normális eloszlásból származó vektor (például futásidők vagy megtalált legjobb megoldások lehetnek benne egy genetikus algoritmus futásaiból). Ekkor annak eldöntésére, hogy ugyanannyi-e a várható értékük 2 mintás t-próbát alkalmazunk.

ttest2(a,b) %0 jenetése: azonos várhatóértékűek 95%-os valószínűséggel

ans =

     0

ttest2(aa,bb) %1 jelentése: különböző várható értékűek 95%-os valószínűséggel

ans =

     0

Ez érzékeny a különböző átlagokra, de figyelembe veszi a természetes ingadozást is. Vegyük az alábbi véletlen változókat, ezek várható értéke -0.5.

a2=a-0.5;
ttest2(a2,b)

ans =

     0

a3=a-2;
ttest2(a3,b)

ans =

     1

Ezeké -0.5, viszont:

aa2=aa-0.5;

ttest2(aa2,bb)

ans =

     1

A megoldó forráskódja

function [fitneszek, populacio]=hatizsak_elitista(sulyvektor,ertekvektor,...
    sulykorlat,keresztezesval,mutacioval,generaciokszama,populaciomeret,...
    tournamentmeret)

% Hátizsák probléma: adott n db tárgy, s1,s2,..sn súlyok, v1,v2,...,vn
% értékek, és egy K teherbírású hátizsák. A cél, hogy kiválasszunk néhány 
% tárgyat, hogy azok összsúlya súlykorlátot ne haladja meg, és az 
% összértékük maximális legyen.
% A függvény meghívásának módja: hatizsak_egyszeru(sulyvektor,ertekvektor,sulykorlat,...
%    keresztezesval,mutacioval,generaciokszama,populaciomeret,tournamentmeret),
%    ahol
% sulyvektor: egy sorvektor, amelyben lévő pozitív valósak a tárgyak súlyai
% ertekvektor : egy sorvektor, amelyben lévő pozitív valósak a tárgyak
% értékei
% Ezen két vektor elemszámának egyformának kell lennie
% sulykorlat: pozitív valós szám, a kapacitást adja meg
% keresztezesval, mutacioval, generaciokszama, populaciomeret: a genetikus
% algoritmus kötelezően megadandó paraméretei
% tournamentmeret: az egy körben kiválasztott potenciális szülők száma

if length(sulyvektor)~=length(ertekvektor) || mutacioval<0 || mutacioval>1 ...
        || keresztezesval<0 || keresztezesval>1 || generaciokszama <0 ||...
        populaciomeret<0 || mod(populaciomeret,2)==1
     error('Rossz bemeneti paraméterek'); 
end 

%A kezdeti populáció létrehozása
targyakszama=length(sulyvektor); 
populacio=ceil(rand(populaciomeret,targyakszama)-0.5);  
% a populáció egy mátrix, benne soronként vannak az egyes egyedek

fitneszek=zeros(populaciomeret, generaciokszama);

for i=1:generaciokszama 
    
    populaciofitnesz=fitnesz(populacio,sulyvektor,ertekvektor,sulykorlat);
    fitneszek(:,i)=populaciofitnesz;
    [elitertek, elitpoz]=max(populaciofitnesz);
     elitegyed=populacio(elitpoz, :);
    populacio=kivalaszt_tournament(populacio,populaciofitnesz,tournamentmeret);
    populacio=keresztez_egypontos(populacio,keresztezesval);
    populacio=mutacio_egybit(populacio,mutacioval);
    populacio(1,:)=elitegyed;
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function populaciofitnesz=fitnesz(populacio,sulyvektor,ertekvektor,sulykorlat)

populaciofitnesz=zeros(size(populacio,1),1); 

for i=1:size(populacio,1)
    
    if dot(populacio(i,:),sulyvektor)>sulykorlat
        populaciofitnesz(i)=0;
    else
        populaciofitnesz(i)=dot(populacio(i,:),ertekvektor);
    end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function szulok=kivalaszt_tournament(populacio,populaciofitnesz,tournamentmeret)

szulok=zeros(size(populacio,1),size(populacio,2));

for i=1:size(populacio,1)
    poziciok=ceil(size(populacio,1)*rand(tournamentmeret,1));
    [~,legjobbhely]=max(populaciofitnesz(poziciok));
    szulok(i,:)=populacio(poziciok(legjobbhely),:);
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


function utod=keresztez_egypontos(populacio,keresztezesval)

utod=populacio;
n=size(populacio,2);

for i=1:2:size(populacio,1)

    if rand<keresztezesval
    
        vagopont=ceil((n-1)*rand);
        utod(i,:)=[populacio(i,1:vagopont), populacio(i+1,vagopont+1:n)];
        utod(i+1,:)=[populacio(i+1,1:vagopont), populacio(i,vagopont+1:n)];
    else
        utod(i,:)=populacio(i,:); 
        utod(i+1,:)=populacio(i+1,:);
    end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function utod=keresztez_uniform(populacio,keresztezesval)

utod=populacio;

for i=1:2:size(populacio,1)
    if rand<keresztezesval
        for j=1:size(populacio,2)
            if rand<0.5
            utod(i,j)=populacio(i+1,j); 
            utod(i+1,j)=populacio(i,j);
            end
        end
    end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function utod=mutacio_egybit(populacio,mutacioval)

utod=populacio;

n=size(populacio,2);

for i=1:size(populacio,1)
    if rand<mutacioval 
        pozicio=ceil(n*rand); 
        if populacio(i,pozicio)==0
            utod(i,pozicio)=1; 
        else
            utod(i,pozicio)=0;
        end
    end
end

Published with MATLAB® R2018b