function [Bestchrom] = ga(Pdata, Tdata, BUDGET)

[npro, natt] = size(Pdata);

%MAXGEN = 1000*natt;        % maximum Number of generations
Cc = [npro,0,0];  % components of the chromosome
Lc = (2*(natt-1))+npro;      % number of features 
% Nc = 10*natt;        % Number of individuals per populations
Nc = BUDGET; % Equal to # guesses
Ni = 0;              % Number of choromosomes in Inherit set
Proc = 0.7;          % probability of crossover
Prom = 0.1;          % probability of mutation
Proi = 0.5;         % probability of population initiate

MAXGEN = ceil(sqrt(1 + Lc) - (1 / 2));

Inherit(:,Lc+1) = 0;  % Inherit set of choromosomes which containing the 
                      % choromosomes surviving from one generation to
                      % another
Fit(Nc,1) = 0;        % Fitness values vector of the population


% Initialise population
[Chrom,Lc] = popu_init(Nc,Lc,Proi,Cc);

% Reset counters
   Best = zeros(MAXGEN,Lc+1);	% best in current population
   gen = 0;			% generational counter
   genstop = 0;     % generaation stop scalar

% Evaluate initial population
[Fit] = fit_func(Chrom, Inherit, Pdata, Tdata);

gen = gen + 1;

% Track best individual
Best(gen,Lc+1) = min(Fit);
for i = 1:Nc
   if Fit(i) == Best(gen,Lc+1)
   
       Best(gen,1:Lc) = Chrom(i,:);
       
   end
end

% the evolution loop   
while gen < MAXGEN && genstop < 100*natt
 % Select individuals for mating
  NewChrInx = rw_selc(Fit,Nc);

  SelcChrom = Chrom(NewChrInx,:);

  % perform crossover 
  SelcChrom = cross_over(SelcChrom, Proc);
  
  % perform mutation
  SelcChrom = mute(SelcChrom,Prom, Cc);

  % the chromosomes surviving from one generation to another are stroed in
  % Inherit matrix with Fitness value
  for i = 1:Nc
      for j = 1:Nc
      % if find same chromosome in Chrom set and SelcChrom set
          if Chrom(i,:) == SelcChrom(j,:)
              Ni = Ni + 1;
              Inherit(Ni,:) = [Chrom(i,:),Fit(i)];
          end
      end
  end

  % Evaluate current population
  [FitSel] = fit_func(SelcChrom, Inherit, Pdata, Tdata);

  % Elitist strategy
  % if the minimum fitness value of the new population is less than that of
  % the old population
  if min(FitSel) > min(Fit)
      
   minFit=min(Fit);
   maxFit=max(FitSel);
   % replace the chromosome of the minimum fitness value with the old
   % chromosome of the maximum fitness value
   for i = 1:Nc
      if Fit(i) == minFit
          minIndi = [Chrom(i,:),Fit(i)];
      end
      if FitSel(i) == maxFit
          maxIndex = i ;
      end
   end
   
   SelcChrom(maxIndex,:) = minIndi(1:Lc);
   FitSel(maxIndex) = minIndi(Lc+1);
   
  end

  % move to the next generation
  Chrom = SelcChrom;
  Fit  =  FitSel;

  % Increment generational counter
  gen = gen + 1;

  % Track best individual
  Best(gen,Lc+1) = min(Fit);
  for i = 1:Nc
      if Fit(i) == Best(gen,Lc+1)
         Best(gen,1:Lc) = Chrom(i,:);
      end
  end
  
  if Best(gen,Lc+1) == Best(gen-1,Lc+1)
      
      genstop = genstop + 1;
      
  else
      
      genstop = 0;
      
  end
  
  
end

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

% return the best chromosome
% Bestchrom = Best(genstop,:);

[a,b] = min(Best(:,end));
Bestchrom = Best(b,:);
