// Algoritm genetic pentru rezolvarea problemei ONEMAX
// Parametrii de intrare:
//  m - volumul populatiei (ex: 20)
//  n - dimensiunea problemei (ex:10)
//  gen - numarul de generatii (ex: 50)
//  pm - probabilitatea de mutatie (ex: 0.01)
// Exemplu de apel:  onemaxGA(20,10,50,0.01)
function pop=onemaxGA(m,n,gen,pm)
    pop=initpop(m,n); // initializarea populatiei
    for k=1:gen       // ciclu de evolutie
        copii=zeros(m,n);              // alocare spatiu populatie de copii
        val=evalpop(pop);               
        prob=calculprob(val);          // evaluare si calculul probabilitatilor de selectie
        indici1=ruleta(prob);          // generare indici pentru parinti folosind selectie de tip ruleta
        indici2=ruleta(prob);
        for i=1:m/2                    // construirea populatiei de copii prin incrucisare
          parinte1=pop(indici1(i),:);  // la fiecare parcurgere a ciclului se genereaza doi copii
          parinte2=pop(indici2(i),:);
          [copil1,copil2]=incrucisare(parinte1,parinte2);
          copii(i,:)=copil1;
          copii(m-i+1,:)=copil2;
        end  
        for i=1:m                      // aplicarea mutatiei (varianta la nivel de cromozom)
          if grand(1,1,"unf",0,1)<pm
             copii(i,:)=mutatie(copii(i,:));
          end
        end   
        pop=copii;               // constituirea noii generatii (toti copii sunt acceptati)
        disp(pop);               // afisarea populatiei
    end   
    indBest=findBest(val);
    disp(pop(indBest,:),"Cel mai bun element:");
endfunction

// initializare populatie
function pop = initpop(m,n)
    for i=1:m
        for j=1:n
            pop(i,j)=grand(1,1,"uin",0,1);
        end
    end    
endfunction

//  evaluarea populatiei pt. ONEMAX

function val=evalpop(pop)
[m,n]=size(pop);
val=[];
for i=1:m
   val(i)=0;
   for j=1:n
      val(i)=val(i)+pop(i,j);
   end
end   
endfunction
// identificarea celui mai bun element din populatie 
function indBest=findBest(val)
    indBest=1;
    for i=2:length(val)
        if val(i)>val(indBest)
            indBest=i;
        end
    end
endfunction    

// calcul probabilitati de selectie

function prob=calculprob(val)
m=length(val);
prob=zeros(m);
s=0;
for i=1:m
   s=s+val(i);
end
for i=1:m
   prob(i)=val(i)/s;
end     
endfunction

// selectie proportionala folosind metoda ruletei
// Parametru intrare: vector cu probabilitati de selectie
// Iesire: lista cu elementele selectate
function indici=ruleta(prob)
    indici=zeros(length(prob));
    for k=1:length(prob)
        i=1;
        s=prob(1);
        u=grand(1,1,"unf",0,1);
        while u>s
           i=i+1;
           s=s+prob(i);
        end
        indici(k)=i;
    end
endfunction

// incrucisare cu un punct de taietura
// Parametri intrare:  
//      parinte1 - un element al populatiei curente
//      parinte1 - un element al populatiei curente
// Rezultat:  doi vectori (copii) generati prin incrucisare
function [copil1,copil2]=incrucisare(parinte1, parinte2)
    n=size(parinte1,2); 
    copil1=zeros(1,n);copil2=zeros(1,n);
    poz=grand(1,1,"uin",1,n-1); // determinarea punctului de taietura
    for i=1:poz                 // completarea primelor componente ale copiilor   
      copil1(1,i)=parinte1(1,i);
      copil2(1,i)=parinte2(1,i);
   end
   for i=poz+1:n            // completarea ultimelor componente ale copiilor 
      copil1(1,i)=parinte2(1,i);
      copil2(1,i)=parinte1(1,i);
   end
endfunction

// mutatie simpla:  complementarea unei pozitii selectate aleator
function copil=mutatie(parinte)
    n=size(parinte,2);
    copil=parinte;
    poz=grand(1,1,"uin",1,n);
    copil(poz)=1-copil(poz);
endfunction

onemaxGA(30,10,50,0.01)

