// Algoritm genetic pentru rezolvarea problemei rucsacului in varianta discreta
// Parametrii de intrare:
//    m - volumul populatiei (ex: 50)
//    n - numarul total de obiecte (ex: 5)
//    gen - numarul de generatii (ex: 100)
//    pm - probabilitate de mutatie (ex: 0.01)
//    alfa - coeficient de penalizare al termenului corespunzator incalcarii
//           restrictiei (ex: 0.8)
//    V - vector cu valorile obiectelor (ex: [3,4,1,5,2])
//    W - vector cu greutatile obiectelor (ex: [10,8,3,6,5])
//    C - capacitatea rucsacului (ex: 20)
// Exemplu de apel:  knapsack(50,5,100,0.01,0.8, [3,4,1,5,2],[10,8,3,6,5],20); 
function pop=knapsack(m,n,gen,pm,alfa,V,W,C)
    pop=initpop(m,n); // initializarea populatiei
    for k=1:gen       // ciclu de evolutie
        copii=zeros(m,n);       
        val=evalpop(pop,alfa,V, W, C);
        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),:);
          parinte2=pop(indici2(i),:);
          [copil1,copil2]=incrucisare(parinte1,parinte2);
          copii(i,:)=copil1;
          copii(m-i+1,:)=copil2;
        end  
        for i=1:m                      // aplicarea mutatiei
          if grand(1,1,"unf",0,1)<pm
             copii(i,:)=mutatie(copii(i,:));
          end
        end   
        pop=copii; disp(pop);          // constituirea noii generatii 
    end   
    indBest=findBest(val);
    disp(pop(indBest,:),"Cel mai bun element:");
    valBest=sum(V.*pop(indBest,:));
    weightBest=sum(W.*pop(indBest,:));
    disp(valBest,"Valoare obiecte selectate:"); 
    disp(weightBest,"Greutate obiecte selectate:"); 
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 fitnessului pentru problema rucsacului
function val=evalpop(pop,alfa,V, W, C)
[m,n]=size(pop);
val=[];
for i=1:m
   // calcul valoare totala si greutate totala pentru fiecare element al populatiei
   vrucsac=0; wrucsac=0;
   for j=1:n
      vrucsac=vrucsac+V(j)*pop(i,j);
      wrucsac=wrucsac+W(j)*pop(i,j);
   end   
   if wrucsac<=C
      val(i)=vrucsac;   
      // daca e satisfacuta restrictia valoare fitnessului coincide cu valoarea totala
   else
      val(i)=alfa*vrucsac+(1-alfa)*(C-wrucsac); 
      // daca nu e satisfacuta restrictia se penalizeaza valoarea totala cu un termen proportional cu gradul de incalcare a restrictiei
   end   
end   
endfunction

function indBest=findBest(val)
    indBest=1;
    for i=2:length(val)
        if val(i)>val(indBest)
            indBest=i;
        end
    end
endfunction    

//calcul probabilitati
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
knapsack(50,5,200,0.01,0.5, [3,4,1,5,2],[10,8,3,6,5],20); 
//v=[92,57,49,68,60,43,67,84,87,72]
//w=[23,31,29,44,53,38,63,85,89,82]
//knapsack(100,10,300,0.1,0.25, v,w,165);


