Algorithmes génétiques

Exemples

Démos

De nombreux sites proposent des applets utilisant les algorithmes génétiques, nous en avons séléctionné quelques-uns:

• http://www.caplet.com/MannaMouse.html smiulation de vie artificielle, adaptation a l'environnement.
• http://www.rennard.org/alife/french/gav.html recherche de motif, simulation avec une codegae des gènes en abstrait ou bit à bit.
• http://www.lalena.com/AI/Ant/Ant.aspx mise en oeuvre d'un algorithme paramétrable avec des fourmis qui vont chercher de la nourriture.
• http://magnin.plil.net/anciensite/coursag/voyageur/voyageur.html le problème classique du voyageur de commerce, comparaison avec un brute force.

Nous avons également réalisé un petit exemple d'application des algorithmes génétiques en utilisant la librairie Java JGAP.
Pour cela nous reprenons le problème défini précédemment :

Soit f(x0, x1, ... , x100) = x0 + x1 / x2 ... *x100
On cherche x0, x1, ... , x100 tel que:
f(x0,x1,...,x100) = K (dans notre cas, K = 10000)

Pour cela nous avons réalisé les classes suivantes:

• CalculChromosome: Population (ensemble des x)
• CalculGene: Individu de notre population (x)
• CalculFitnessFunction: Fonction cout (K - f(population))
• Operation: Classe utilitaire permettant le calcul de f()
• Lanceur: Classe initialisant et lançant l'algorithme

// Nombre maximum de générations
int numEvolutions = 10000;

Configuration gaConf = new DefaultConfiguration();
Configuration.reset();
gaConf.setFitnessEvaluator(new DeltaFitnessEvaluator()); // Fonction objectif
gaConf.setPreservFittestIndividual(true); // Elitisme
gaConf.setKeepPopulationSizeConstant(true);
Genotype genotype = null;
try {
	IChromosome sampleChromosome = new CalculChromosome(gaConf, SIZE);
	gaConf.setSampleChromosome(sampleChromosome);
	
	// Population size
	gaConf.setPopulationSize(20); 

	// Cost function
	gaConf.setFitnessFunction(new CalculFitnessFunction(VALUE_TO_FOUND)); // VALUE_TO_FOUND = K
	
	genotype = Genotype.randomInitialGenotype(gaConf);
} catch (InvalidConfigurationException e) {
	e.printStackTrace();
	System.exit(-2);
}
int progress = 0;
int percentEvolution = numEvolutions / 10;

// Evolution LOOP
for (int i = 0; i < numEvolutions; i++) {
	genotype.evolve();
	if (percentEvolution > 0 && i % percentEvolution == 0) {
		progress++;
		IChromosome fittest = genotype.getFittestChromosome();
		double fitness = fittest.getFitnessValue();
		System.out.println("Generation " + i + ": Currently fittest Chromosome has fitness " + fitness);
		if (fitness < 0.0001) break;
	}
}
IChromosome fittest = genotype.getFittestChromosome();
System.out.println("Fittest Chromosome has fitness " + fittest.getFitnessValue());
System.err.println(fittest);
Gene[] genes = fittest.getGenes();
double d = 0;
for (Gene gene : genes) {
	Operation op = (Operation) gene.getApplicationData();
	d += op.calcul(d, ((Double) gene.getAllele()));
}
System.err.println("Result: " + d);