function [xo,Ot,nS] = alg_gen(fun, nvi, valmin, valmax, prec, tol, ...
   nind, sind, nger, reptx, muttx, rep, nfilhos, maxd, felitismo, nelite, ...
   freset, nindot, greset)

% Função ALG_GEN - Acha o mínimo de uma função utilizando algoritmo genético
% para funções contínuas - codificação real
%
%		xo = alg_gen(fun,nvi,valmin,valmax,prec)
%
%	onde:   fun - função objetivo (string)
%		nvi - número de variáveis independentes (inteiro, >0)
%		valmin - vetor ou escalar com os valores mínimos para variáveis 
%					independentes
%		valmax - vetor ou escalar com os valores máximos para variáveis 
%					independentes
%		prec - passo para geração das variáveis independentes (vetor ou escalar)
%				 para gerar a primeira geração (pais)	 
% 
%  sendo: xo - o valor da(s) variável(is) independente(s) onde o
% 					  valor mínimo foi encontrado
%
% Na formulação anterior uma série de parâmetros de ajuste foi suprimida.
% Subsequentemente mostra-se a chamada completa da função:
% [xo,Ot,vetxmin,vetymin] = ag_r(fun, nvi, valmin, valmax, prec, tol, nind, sind, nger, ...
%					reptx, muttx, rep, nfilhos, maxd, felitismo, nelite, ...
%					freset, nindot, greset)
%		
% Onde:
%		tol - tolerância relativa na variável de decisão (default 1e-4)
%		nind - Número de indivíduos (default: 200)	
%		sind - Algoritmo de escolha da geração inicial (pais) 
%				 1 - roleta (default)
%				 2 - torneio
%		nger - Número máximo de gerações (default: 20)
%		reptx - Taxa de cruzamento (default: 70 %)
%		muttx - Taxa de mutação: (default: 5 %)
%		rep - Tipo de cruzamento: 
%			1 - Igual aos pais
%			2 - Média aritimética entre os pais
%			3 - Média ponderada com pesos aleatórios entre pai e mãe
%		nfilhos - Número de filhos por cruzamento: (default: 2)
%		maxd -  maxima porcentagem de deslocamento para mutacao 		
%		felitismo - flag de ativação do elitismo 
%				1 - ligado (default) 
%				0 - desligado 
%		nelite - Número de indivíduos da elite: (default: 5)
%		freset - Flag relativo ao Drift(reset periódico da população menos apta)
%				1 - ligado  
%				0 - desligado (default)
%		nindot - Número de individuos carregados para a geracao seguinte (default: 10)
%		greset - Número de geração a cada reset da população (default: 5)

% Marcelo Farenzena - 12/2004
% GIMSCOP - DEQUI - UFRGS
% Modified by Giovani Tonel(giovani.tonel@ufrgs.br) on September 2006


% =================================================
% selecao da primeira geracao (pais)
% =================================================
nS=0;
ntind = abs(valmax - valmin)./prec;			% calculo do numero total de individuos

% verifica se ha reset 
if freset
   nciclos = ceil(nger/greset);			% quantas vezes ocorrera reset
   nger = greset;
else
   nciclos = 1;
end

for nc = 1:nciclos   
   for i = 1 : nind
      if sind == 1                    	% roleta
         npind = 5; 								% numero de individuos da roleta
         pind = rand(npind,nvi);			% escolhe os indivíduos 
         
         pind = adeqscal(pind,valmax-valmin,valmin);            
         
         for j = 1:npind						% avalia a aptidao dos provaveis indivíduos
            aptpi(j) = feval(fun,pind(j,:));                  
         end
         
         if min(aptpi > 0)
            aptpi = 1./(aptpi);				% defini aptidão como inverso do val da func objetivo
         else
            aptpi = 1./(aptpi - 2*min(aptpi));
         end
         
         prob = aptpi./sum(aptpi);			% normaliza as aptidoes, para obter-se a faixa de probabilidades
         
         for j = 1:npind
            proba(j) = sum(prob(1:j));		% calcula as probabilidades acumuladas
         end
         
         indesc = rand(1);					% individuo escolhido
         
         indmen = find(proba < indesc);
         if isempty(indmen)
            ind(i,:) = pind(1,:);
            apt(i) = aptpi(1);
         else
            ind(i,:) = pind(max(indmen) + 1,:);
            apt(i) = aptpi(max(indmen) + 1);
         end      
         
      elseif sind == 2
         npind = 5; 								% numero de individuos da roleta
         pind = rand(npind,nvi);			% escolhe os indivíduos 
         
         pind = adeqscal(pind,valmax-valmin,valmin);            
         for j = 1:npind						% avalia a aptidao dos provaveis indivíduos
            aptpi(j) = feval(fun,pind(j,:));                  
         end
         
         if min(aptpi > 0)
            aptpi = 1./(aptpi);				% defini aptidão como inverso do val da func objetivo
         else
            aptpi = 1./(aptpi - 2*min(aptpi));
         end
         
         % acha o individuo mais apto
         
         ind(i,:) = pind(find(aptpi == min(aptpi)),:);
         apt(i) = min(aptpi);      
      else
         error('Defina corretamente a seleção da primeira geração')
         break
      end 
      
   end
   
   if nc > 1
      ind(end-nindot+1:end,:) = indold;   
   	apt(end-nindot+1:end) = aptold;        
   end      
   
   % =================================================
   % geraçao das próximas gerações
   % =================================================
   ger = 1;
   aptnew = 1000;
   tolc = 10;
   nS=nS+1;
   while ger <= nger & nind > 20 & tolc > tol
    
      % determinacao dos cruzamentos
      apto = sort(apt);   						% ordena as aptidões
      nindrep = ceil(reptx/100*nind);		% determina o numero de ind que irao ficar
      pcorte = apto(end - nindrep);
      
      [ninapt,inapt] = find(apt > pcorte);  
      
      for j = 1:length(inapt)/2
         switch rep
         case 1			% igual ao pai (coisinha do papai)
            switch nfilhos 
            case 1
               newind(j,:) = ind(inapt(1 + (j-1)*2),:);
            case 2
               newind(2*j-1,:) = ind(inapt(1 + (j-1)*2),:);
               newind(2*j,:) = ind(inapt(2 + (j-1)*2),:);               
            otherwise
               newind(nfilhos*(j-1)+1,:) = ind(inapt(1 + (j-1)*2),:);
               newind(nfilhos*(j-1)+2,:) = ind(inapt(2 + (j-1)*2),:);               
               
               for k = 1 : nfilhos - 2
                  p = rand(1);
                  newind(nfilhos*(j-1) + k + 2,:) = p*ind(inapt(1 + (j-1)*2),:) + (1-p)*ind(inapt(1 + (j-1)*2),:);
               end
            end            
            
         case 2			% média aritimética entre o pai e mãe
            switch nfilhos 
            case 1            
               newind(j,:) = 0.5*(ind(inapt(1 + (j-1)*2),:) + ind(inapt(2 + (j-1)*2),:));                  
            otherwise
               newind(nfilhos*(j-1)+1,:) = 0.5*(ind(inapt(1 + (j-1)*2),:) + ind(inapt(2 + (j-1)*2),:));                              
               for k = 1 : nfilhos - 1
                  p = rand(1);
                  newind(nfilhos*(j-1) + k + 1,:) = p*ind(inapt(1 + (j-1)*2),:) + (1-p)*ind(inapt(2 + (j-1)*2),:);
               end  
            end   
         case 3			% média ponderada (mais parecido com a mãe)
            for k = 1 : nfilhos
               p = rand(1);
               newind(nfilhos*(j-1) + k ,:) = p*ind(inapt(1 + (j-1)*2),:) + (1-p)*ind(inapt(2 + (j-1)*2),:);
            end  
         end      
      end
      
      % ============================================================================
      % determinacao das mutações 
      % altera-se uma porcentagem do indivíduo, para mais ou menos, aleatoriamente)
      % ============================================================================
      
      nindm = floor(muttx/100*nind); % numero de individuos mutados
      
      if nindm > 0
         for k = 1 : nindm
            pnewind = ind(ceil(nind*rand(1)),:);		%escolha do provavel indivíduo
            pnewind = pnewind + 2*(rand(1)-0.5)*pnewind*maxd/100;
            while any(pnewind > valmax) | any(pnewind < valmin)
               pnewind = pnewind + 2*(rand(1)-0.5)*pnewind*maxd/100;      % verifica se não é um individuo expurio   
            end      
            newind(nfilhos*j+k,:) = pnewind;
         end
      end
      
      % ============================================================================   
      % verifica se será utilizado elitismo
      % ou seja, clona-se os individuos mais aptos
      % ============================================================================
      
      if felitismo
         [ninapt,inapt] = find(apt > apto(end - nelite));         
         newind(nfilhos*j+k+1:nfilhos*j+k+nelite,:) = ind(inapt,:);
      end
      
      clear ind  apt
      ind = newind;
      
      % calculo das novas aptidoes
      for j=1:size(ind,1)
         apt(j) = feval(fun,ind(j,:));
      end
      
      if min(apt > 0)
         apt = 1./(apt);				% defini aptidão como inverso do val da func objetivo
      else
         apt = 1./(apt - 2*min(apt));
      end      
      
      nind = size(newind,1);      
      clear newind
      
      %disp(['Geração numero ',int2str(ger)])
      ger = ger + 1;  
      nS=nS+1;
      aptold = aptnew;
      aptnew = max(apt);
      
      % calcula a diferença relativa entre as aptidões
      tolc = abs(aptnew/aptold - 1);
      
   end
   
   if freset
      apto = sort(apt);
      aptold = apto(end-nindot+1:end);
      for k=1:length(aptold)
         aptf(k) = find(apt == aptold(k));
      end      
      indold = ind(aptf,:);			% guarda os individuos q passarão pelo drift
   end         
end

[val,pos] = max(apt);
xo = ind(pos,:);
Ot = feval(fun,xo); 
vetxmin = ind;

for i=1:size(ind,1)
	vetymin(i) = feval(fun,vetxmin(i,:));      
end

% ===============================================
% Funções auxiliares
% ===============================================

function matres = adeqscal(mat,coefa,coefl) 

for i = 1:length(coefa)
   matres(:,i) = mat(:,i) * coefa(i) + coefl(i);
end