public class Individual {
   private int[] chromosome;
   private double fitness = -1;

   public Individual(int[] chro) {
      chromosome = chro;
   }

   public Individual(int chromosomeLength) {
      chromosome = new int[chromosomeLength];
		
      for (int gene = 0; gene < chromosomeLength; gene++) {
         setGene(gene, 0.5 < Math.random() ? 1 : 0);	
      }
   }
   // Getters et Setters …
}

public class Population {
   private Individual population[];
   private double populationFitness = -1;
  
   public Population(int populationSize) {
      population = new Individual[populationSize];
   }
   
   public Population(int populationSize, int chromosomeLength) {
      population = new Individual[populationSize];
      
      // Création des individus
      for (int individualCount = 0; individualCount < populationSize; individualCount++) {
         population[individualCount] = new Individual(chromosomeLength);
      }
   }

   // Getters et Setters …

   // Retourne l’individu le plus adapté situé à la position offset
   public Individual getFittest(int offset) {
      // Tri de la population par valeur d’adaptabilité
      Arrays.sort(population, new Comparator<Individual>() {
         @Override
         public int compare(Individual o1, Individual o2) {
	if (o1.getFitness() > o2.getFitness()) {
	   return -1;
	} else if (o1.getFitness() < o2.getFitness()) {
	   return 1;
}
	
             return 0;
           }
        });

      return population[offset];
   }

   // Brassage de la population
   public void shuffle() {
      Random r = new Random();
  
      for (int i = population.length - 1; i > 0; i--) {
         int index = r.nextInt(i + 1);
         Individual a = population[index];
         population[index] = population[i];
         population[i] = a;
      }
   }
}

public class GeneticAlgorithm {
  private int populationSize;
  private double mutationRate;
  private double crossoverRate;
  private int elitismCount;

  public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount) {
    this.populationSize = populationSize;
    this.mutationRate = mutationRate;
    this.crossoverRate = crossoverRate;
    this.elitismCount = elitismCount;
  }

  public Population initPopulation(int chromosomeLength) {
    Population population = new Population(populationSize, chromosomeLength);
    return population;
  }

  public double calcFitness(Individual individual) {
    int correctGenes = 0;
	
    for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {
      // Ajout de 1 si un gène est correct
      if (individual.getGene(geneIndex) == 1) {
        correctGenes += 1;
      }
    }
    
     // Calcul de la valeur d'adaptabilité
     double fitness = (double) correctGenes / individual.getChromosomeLength();    
     individual.setFitness(fitness);
     return fitness;
  }

  public void evalPopulation(Population population) {
    double populationFitness = 0;

    // Parcours de la population et calcul du niveau d'adaptabilité
    for (Individual individual : population.getIndividuals()) {
      populationFitness += calcFitness(individual);
    }

    population.setPopulationFitness(populationFitness);
  }

  public boolean isTerminationConditionMet(Population population) {
    for (Individual individual : population.getIndividuals()) {
      if (individual.getFitness() == 1) {
        return true;
      }
    }
   
    return false;
  }

  public Individual selectParent(Population population) {
    Individual individuals[] = population.getIndividuals();
    double populationFitness = population.getPopulationFitness();
    double rouletteWheelPosition = Math.random() * populationFitness;

    // Recherche d'un parent
   double spinWheel = 0;
		
   for (Individual individual : individuals) {
     spinWheel += individual.getFitness();
			
     if (spinWheel >= rouletteWheelPosition) {
       return individual;
     }
  }
  
  return individuals[population.size() - 1];
 }

  public Population crossoverPopulation(Population population) {
    // Création de la nouvelle population
    Population newPopulation = new Population(population.size());

    for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
      Individual parent1 = population.getFittest(populationIndex);

      // Critère d'application du crossover
      if (crossoverRate > Math.random() && populationIndex >= elitismCount) {
        Individual offspring = new Individual(parent1.getChromosomeLength());
        Individual parent2 = selectParent(population);
	
        for (int geneIndex = 0; geneIndex < parent1.getChromosomeLength(); geneIndex++) {
          // Utilisation moitié gènes parent 1 et parent 2
          offspring.setGene(geneIndex, 0.5 > Math.random() ? 
            parent1.getGene(geneIndex) : parent2.getGene(geneIndex));
        }
    
        newPopulation.setIndividual(populationIndex, offspring);
      } else {
        newPopulation.setIndividual(populationIndex, parent1);
      }
    }
    
     return newPopulation;
  }

  public Population mutatePopulation(Population population) {
    Population newPopulation = new Population(populationSize);

    for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
      Individual individual = population.getFittest(populationIndex);

      for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {
        // On préserve les meilleurs individus des mutations
        if (populationIndex > elitismCount) {
          if (mutationRate > Math.random()) {
            int newGene = individual.getGene(geneIndex) == 1 ? 0 : 1;	
            individual.setGene(geneIndex, newGene);
          }
        }
      }

      newPopulation.setIndividual(populationIndex, individual);
    }

     return newPopulation;
  }
}

public class AllOnesProblem {

  public static void main(String[] args) {
    // Création de l'instance de GeneticAlgorithm
    GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.001, 0.95, 2);
    // Initialisation population
    Population population = ga.initPopulation(50);
    // Evaluation
    ga.evalPopulation(population);

    // Index génération
    int generation = 1;

    // Boucle de création
    while (!ga.isTerminationConditionMet(population)) {
      System.out.println("Meilleure solution à la génération " + generation +  "  : " + population.getFittest(0).toString());

      // Crossover
      population = ga.crossoverPopulation(population);

      // Mutation
      population = ga.mutatePopulation(population);

      // Evaluation
      ga.evalPopulation(population);

      // Nouvelle génération
      generation++;
    }

    System.out.println("Solution trouvée en " + generation + " générations");
    System.out.println("Meilleure solution : " + population.getFittest(0).toString());
  }
}