Création d'un algorithme génétique (en Java)

Rédigé par Slauncha Aucun commentaire
Classé dans : Développement, Howto Mots clés : Algorithme, Génétique, Java

Un algorithme génétique (GA) est idéal pour trouver des solutions aux problèmes de recherche complexes. Ils sont souvent utilisés dans des domaines tels que l'ingénierie pour créer des produits avec des propriétés et une qualité très élévées, grâce à la recherche de combinaisons de paramètres pour obtenir la meilleure composition. Par exemple, ils peuvent chercher dans différentes combinaisons de matériaux et de modèles pour trouver la combinaison parfaite des deux pour obtenir un composant léger et robuste à la fois.

Ils peuvent également être utilisés pour concevoir des algorithmes informatiques, pour planifier des tâches ou pour résoudre d'autres problèmes d'optimisation. Les algorithmes génétiques sont basées sur le processus d'évolution par sélection naturelle qui a été observé dans la nature. Ils reproduisent essentiellement la manière dont la vie utilise l'évolution pour trouver des solutions aux problèmes du monde réel.

Nous avons déjà abordé ce sujet au travers d'un article précédent. Dans cet article nous allons implémenter (pour l'exemple, le langage utilisé sera Java), voyons ça plus en détails.

Pour ceux désirant une version développé en C, vous pouvez consulter cet article.

Avant de rentrer dans le vif du sujet, je souhaite rappeler les principales phases de l'algorithme (basé sur la modélisation de l'évolution) :

  1. Le codage  : Nous précisons d'abord un "code génétique" pour chaque solution potentielle x. Pour cela nous allons écrire chaque solution en base 2.

  2. La population initiale : Un petit ensemble de chaînes est choisi au hasard dans le pool de solution pour former la population initiale, ou génération o; sur cet ensemble, l'adaptabilité f(x) de chaque x est évaluée. La composition d'une population initiale de six chaînes est donnée ci-dessous.

  3. Le clonage : Deux chaînes ou plus de la population actuelle sont choisies au hasard pour "s'accoupler".

  4. La reproduction : Les chaînes qui s'accouplent disons S1 et S2 échangent des segments de gènes consécutifs par croisement un enfant.

  5. La mise à jour de la population : La progéniture qui résulte de l'accouplement remplace soit des chaînes dont l'adaptabilité est faible soit des membres de la population choisis au hasard.

L'obtention de la solution ou d'une solution acceptable répondant à des critères fixés est trouvée à la suite d'itération de cet algorithme.

Le cas d'exemple

Nous allons créer un algorithme qui permet de trouver au sein d'une population un individu ayant la meilleure aptitude, dans notre cas possédant un code génétique identique à celui recherché (solution optimale).

Pour ce faire nous allons créer les classes suivantes :

  • Population : Traite l'ensemble des individus d'une population
  • Individual : Traite un individu
  • Skill : Permet de savoir si un individu est le plus apte, compétent, au vu de la solution à trouver.
  • Algorithm : S'occupe de gérer l'évolution : reproduction, mutation ...
  • Ga : Le programme principal permettant de lancer l'évolution sur notre population initiale.

Population

package org.dyndns.slauncha.simpleGa;

public class Population {

	Individual[] individuals;

	/*
	 * Constructor
	 */
	// Create a population
	public Population(int populationSize, boolean initialise) {
		individuals = new Individual[populationSize];
		// Initialise population
		if (initialise) {
			// Loop and create individuals
			for (int i = 0; i < size(); i++) {
				Individual newIndividual = new Individual();
				newIndividual.generateIndividual();
				saveIndividual(i, newIndividual);
			}
		}
	}

	/* Getters */
	public Individual getIndividual(int index) {
		return individuals[index];
	}

	public Individual getMoreCompetent() {
		Individual moreCompetent = individuals[0];
		// Loop through individuals to find more competent
		for (int i = 0; i < size(); i++) {
			if (moreCompetent.getCompetence() <= getIndividual(i).getCompetence()) {
				moreCompetent = getIndividual(i);
			}
		}
		return moreCompetent;
	}

	/* Public methods */
	// Get population size
	public int size() {
		return individuals.length;
	}

	// Save individual
	public void saveIndividual(int index, Individual indiv) {
		individuals[index] = indiv;
	}
}

 

Individual

package org.dyndns.slauncha.simpleGa;

public class Individual {

	static int defaultGeneLength = 64;
	private final byte[] genes = new byte[defaultGeneLength];
	// Cache
	private int competence = 0;

	// Create a random individual
	public void generateIndividual() {
		for (int i = 0; i < size(); i++) {
			byte gene = (byte) Math.round(Math.random());
			genes[i] = gene;
		}
	}

	/* Getters and setters */
	// Use this if you want to create individuals with different gene lengths
	public static void setDefaultGeneLength(int length) {
		defaultGeneLength = length;
	}

	public byte getGene(int index) {
		return genes[index];
	}

	public void setGene(int index, byte value) {
		genes[index] = value;
		competence = 0;
	}

	/* Public methods */
	public int size() {
		return genes.length;
	}

	public int getCompetence() {
		if (competence == 0) {
			competence = Skill.getSkill(this);
		}
		return competence;
	}

	@Override
	public String toString() {
		String geneString = "";
		for (int i = 0; i < size(); i++) {
			geneString += getGene(i);
		}
		return geneString;
	}
}

 

Skill

package org.dyndns.slauncha.simpleGa;

public class Skill {

	static byte[] solution = new byte[64];

	/* Public methods */
	// Set a candidate solution as a byte array
	public static void setSolution(byte[] newSolution) {
		solution = newSolution;
	}

	// To make it easier we can use this method to set our candidate solution
	// with string of 0s and 1s
	static void setSolution(String newSolution) {
		solution = new byte[newSolution.length()];
		// Loop through each character of our string and save it in our byte
		// array
		for (int i = 0; i < newSolution.length(); i++) {
			String character = newSolution.substring(i, i + 1);
			if (character.contains("0") || character.contains("1")) {
				solution[i] = Byte.parseByte(character);
			} else {
				solution[i] = 0;
			}
		}
	}

	// Compute skill by comparing it to our candidate solution
	static int getSkill(Individual individual) {
		int skill = 0;
		// Loop through our individuals genes and compare them to our candidates
		for (int i = 0; i < individual.size() && i < solution.length; i++) {
			if (individual.getGene(i) == solution[i]) {
				skill++;
			}
		}
		return skill;
	}

	// Get optimum skill
	static int getMaxSkill() {
		int maxSkill = solution.length;
		return maxSkill;
	}
}

 

Algorithm

package org.dyndns.slauncha.simpleGa;

public class Algorithm {

	/* GA parameters */
	private static final double uniformRate = 0.5;
	private static final double mutationRate = 0.00015;
	private static final int tournamentSize = 5;
	private static final boolean elitism = true;

	/* Public methods */

	// Evolve a population
	public static Population evolvePopulation(Population pop) {
		Population newPopulation = new Population(pop.size(), false);

		// Keep our best individual
		if (elitism) {
			newPopulation.saveIndividual(0, pop.getMoreCompetent());
		}

		// Crossover population
		int elitismOffset;
		if (elitism) {
			elitismOffset = 1;
		} else {
			elitismOffset = 0;
		}
		// Loop over the population size and create new individuals with
		// crossover
		for (int i = elitismOffset; i < pop.size(); i++) {
			Individual indiv1 = tournamentSelection(pop);
			Individual indiv2 = tournamentSelection(pop);
			Individual newIndiv = crossover(indiv1, indiv2);
			newPopulation.saveIndividual(i, newIndiv);
		}

		// Mutate population
		for (int i = elitismOffset; i < newPopulation.size(); i++) {
			mutate(newPopulation.getIndividual(i));
		}

		return newPopulation;
	}

	// Crossover individuals
	private static Individual crossover(Individual indiv1, Individual indiv2) {
		Individual newSol = new Individual();
		// Loop through genes
		for (int i = 0; i < indiv1.size(); i++) {
			// Crossover
			if (Math.random() <= uniformRate) {
				newSol.setGene(i, indiv1.getGene(i));
			} else {
				newSol.setGene(i, indiv2.getGene(i));
			}
		}
		return newSol;
	}

	// Mutate an individual
	private static void mutate(Individual indiv) {
		// Loop through genes
		for (int i = 0; i < indiv.size(); i++) {
			if (Math.random() <= mutationRate) {
				// Create random gene
				byte gene = (byte) Math.round(Math.random());
				indiv.setGene(i, gene);
			}
		}
	}

	// Select individuals for crossover
	private static Individual tournamentSelection(Population pop) {
		// Create a tournament population
		Population tournament = new Population(tournamentSize, false);
		// For each place in the tournament get a random individual
		for (int i = 0; i < tournamentSize; i++) {
			int randomId = (int) (Math.random() * pop.size());
			tournament.saveIndividual(i, pop.getIndividual(randomId));
		}
		// Get the fittest
		Individual fittest = tournament.getMoreCompetent();
		return fittest;
	}
}

 

Ga

package org.dyndns.slauncha.simpleGa;

public class Ga {

	public static void main(String[] args) {

		// Set a candidate solution
		Skill.setSolution("1111000000000000000000000000001111100000000000000000000000001111");

		// Create an initial population
		Population myPop = new Population(50, true);

		// Evolve our population until we reach an optimum solution
		int generationCount = 0;
		while (myPop.getMoreCompetent().getCompetence() < Skill.getMaxSkill()) {
			generationCount++;
			System.out.println("Generation: " + generationCount + " competence: " + myPop.getMoreCompetent().getCompetence());
			myPop = Algorithm.evolvePopulation(myPop);
		}
		System.out.println("Solution found!");
		System.out.println("Generation: " + generationCount);
		System.out.println("Genes:");
		System.out.println(myPop.getMoreCompetent());

	}
}

 

Exécution

L'exécution de la méthode main dans la classe Ga, produira une sortie console comme celle qui suit.

Gardez à l'esprit que cette sortie console sera foncièrement différente de celle que vous obtiendrez, ceci est dû au côté aléatoire dans la génération de la population etc.

Generation: 1 Fittest: 40
Generation: 2 Fittest: 43
Generation: 3 Fittest: 50
Generation: 4 Fittest: 50
Generation: 5 Fittest: 52
Generation: 6 Fittest: 59
Generation: 7 Fittest: 59
Generation: 8 Fittest: 63
Solution found!
Generation: 8
Genes:
1111000000000000000000000000001111100000000000000000000000001111


Allez plus loin

Nous avons introduit un certains nombres de paramètres de configuration de l'algorithme dans la classe Algorithm, par exemple de taux de mutation, il est possible de modifier ce paramètre et d'en observer les conséquences quant à l'obtention d'une solution.

L'algorithme pourrait être améliorer par exemple pour qu'il s'arrête de lui-même dès lors qu'une solution optimale est obtenue et non quand la solution idéal est trouvée. Par exemple, après un certain nombre d'itérations, ou après un certain nombre d'itération de stagnation (nombre d'itération effectué sans qu'aucune amélioration du meilleur candidat soit trouvé), etc.

Pour approfondir ce sujet, je ne serais que vous conseiller l'excellent ouvrage d'Arturo Sangalli, Éloge du Flou.

Vous pouvez retrouver le descriptif de ce livre (et de bien d'autres) sur cette page.

 

 

 

 

Écrire un commentaire

Quelle est la deuxième lettre du mot h1ynrdi7 ?

Fil RSS des commentaires de cet article