public class City {
  private int x;
  private int y;

  public City(int x, int y) {
    this.x = x;
    this.y = y;
  }

  // Getters et Setters ...

  // Calcul de la distance entre 2 villes
  public double distanceFrom(City city) {
    double deltaXSq = Math.pow((city.getX() - getX()), 2);
    double deltaYSq = Math.pow((city.getY() - getY()), 2);
    double distance = Math.sqrt(Math.abs(deltaXSq + deltaYSq));

    return distance;
  }
}

public class Route {
  private City route[];
  private double distance = 0;

  // Création de la route à partir de l'individu
  public Route(Individual individual, City cities[]) {
    int chromosome[] = individual.getChromosome();
    route = new City[cities.length];

    for (int geneIndex = 0; geneIndex < chromosome.length; geneIndex++) {
      route[geneIndex] = cities[chromosome[geneIndex]];
    }
  }

  // Calcul de la distance totale
  public double getDistance() {
    if (distance > 0) {
      return distance;
    }

    double totalDistance = 0;

    for (int cityIndex = 0; cityIndex + 1 < route.length; cityIndex++) {
      totalDistance += route[cityIndex].distanceFrom(route[cityIndex + 1]);
    }

    totalDistance += route[route.length - 1].distanceFrom(route[0]);
    distance = totalDistance;

    return totalDistance;
  }
}

public class Individual {

  private int[] chromosome;
  private double fitness = -1;

  public Individual(int chromosomeLength) {
    int[] individual = new int[chromosomeLength];

    for (int gene = 0; gene < chromosomeLength; gene++) {
      individual[gene] = gene;
    }

    chromosome = individual;
  }

  // Présence d'une ville donnée au sein des gènes du chromosome
  public boolean containsGene(int gene) {
    for (int i = 0; i < chromosome.length; i++) {
      if (chromosome[i] == gene) {
        return true;
      }
    }
	
    return false;
  }

  // Reste de la classe identique à la première partie de l'article ...
}

public boolean isTerminationConditionMet(int generationsCount, int maxGenerations) {
  return (generationsCount > maxGenerations);
}

public double calcFitness(Individual individual, City cities[]){
  Route route = new Route(individual, cities);
  double fitness = 1 / route.getDistance();
	
  // Stockage de la valeur d'adaptabilité pour une route donnée
  individual.setFitness(fitness);

  return fitness;
}

public void evalPopulation(Population population, City cities[]){
  double populationFitness = 0;

  for(Individual individual : population.getIndividuals()) {
    populationFitness += calcFitness(individual, cities);
  }

  double avgFitness = populationFitness / population.size();
  population.setPopulationFitness(avgFitness);
}

public Individual selectParent(Population population) {
  // Tournoi de sélection
  Population tournament = new Population(tournamentSize);
  // Brassage de la population actuelle
  population.shuffle();

  for (int i = 0; i < tournamentSize; i++) {
    Individual tournamentIndividual = population.getIndividual(i);
    tournament.setIndividual(i, tournamentIndividual);
  }

  // On renvoie le plus prometteur
  return tournament.getFittest(0);
}

public Population crossoverPopulation(Population population){
  Population newPopulation = new Population(population.size());

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

    // Critère d'application du crossover
    if (crossoverRate > Math.random() && populationIndex >= elitismCount) {
      // Sélection du parent 2 via tournoi de sélection
      Individual parent2 = selectParent(population);

      // Création du nouvel individu
      int offspringChromosome[] = new int[parent1.getChromosomeLength()];
      Arrays.fill(offspringChromosome, -1);
      Individual offspring = new Individual(offspringChromosome);

      // Préparation des index
      int substrPos1 = (int) (Math.random() * parent1.getChromosomeLength());
      int substrPos2 = (int) (Math.random() * parent1.getChromosomeLength());

      final int startSubstr = Math.min(substrPos1, substrPos2);
      final int endSubstr = Math.max(substrPos1, substrPos2);

      // Copie de la partie centrale du parent 1 sur le nouvel individu
      for (int i = startSubstr; i < endSubstr; i++) {
        offspring.setGene(i, parent1.getGene(i));
      }

      // Parcours des gènes du parent 2
      for (int i = 0; i < parent2.getChromosomeLength(); i++) {
        int parent2Gene = i + endSubstr;

        if (parent2Gene >= parent2.getChromosomeLength()) {
          parent2Gene -= parent2.getChromosomeLength();
        }

        // Si l'individu n'a pas la ville, on l'ajoute
        if (!offspring.containsGene(parent2.getGene(parent2Gene))) {
          // On cherche la position de rechange
          for (int ii = 0; ii < offspring.getChromosomeLength(); ii++) {
            if (offspring.getGene(ii) == -1) {
              offspring.setGene(ii, parent2.getGene(parent2Gene));
              break;
            }
          }
        }
      }

      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);

    // On préserve les individus élites
    if (populationIndex >= elitismCount) {   
      for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {   
        // Critère d'application de la mutation
        if (mutationRate > Math.random()) {
          // Position d'échange pour la mutation
          int newGenePos = (int) (Math.random() * individual.getChromosomeLength());
          // Echange
          int gene1 = individual.getGene(newGenePos);
          int gene2 = individual.getGene(geneIndex);
          individual.setGene(geneIndex, gene1);
          individual.setGene(newGenePos, gene2);
        }
      }
    }

    newPopulation.setIndividual(populationIndex, individual);
  }

  return newPopulation;
}

public class PbVoyageurDeCommerce {

  public static int MAX_GENERATIONS = 10000;

  public static void main(String[] args) {
    // Création des villes avec leurs coordonnées cartésiennes sur une grille de 100 par 100
    int numCities = 100;
    City cities[] = new City[numCities];

    for (int cityIndex = 0; cityIndex < numCities; cityIndex++) {
      int xPos = (int) (100 * Math.random());
      int yPos = (int) (100 * Math.random());
      cities[cityIndex] = new City(xPos, yPos);
    }

    // Création instance de GeneticAlgorithm
    GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.001, 0.9, 2, 5);
    // Init Population
    Population population = ga.initPopulation(cities.length);
    // Première Evaluation
    ga.evalPopulation(population, cities);

    Route startRoute = new Route(population.getFittest(0), cities);
    System.out.println("Distance meilleure route initiale : " + startRoute.getDistance());

    int generation = 1;

    // Boucle de création de générations
    while (!ga.isTerminationConditionMet(generation, MAX_GENERATIONS)) {
      // Meilleure route après n générations
      Route route = new Route(population.getFittest(0), cities);
      System.out.println("Distance meilleure route Génération " + generation + " : " + route.getDistance());

      population = ga.crossoverPopulation(population);
      population = ga.mutatePopulation(population);
      ga.evalPopulation(population, cities);

      generation++;
    }

    System.out.println("Arrêt de la recherche après " + MAX_GENERATIONS + " générations.");
    Route route = new Route(population.getFittest(0), cities);
    System.out.println("Distance meilleure route : " + route.getDistance());
  }
}