Slauncha

Nous avons déjà abordé cette problématique il y a quelques mois, je vous proposais de créer un algorithme génétique en Java.

Aujourd'hui, je vous propose le même programme mais developpé en C.

Pour rappel, le cas d'exemple étudié sera le suivant :

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 fichiers suivants :

• t_bool.h : Déclare le type t_bool, un type booléen.
• population.h et population.c : Déclare et donne l'implémentation des différentes méthodes permettant de traiter l'ensemble des individus d'une population.
• t_individual.h et t_individual.c : Déclare et donne l'implémentation des différentes méthodes permettant de traiter un individu.
• t_skill.h et t_skill.c : Déclare et donne l'implémentation des différentes méthodes permettant déterminer la compétence d'un individu.
• runtime_algo.c: S'occupe de gérer l'évolution : reproduction, mutation ...
• main.c : Le programme principal permettant de lancer l'évolution sur notre population initiale.

Voyons en détail l'implémentation de ces différents fichiers.

• t_bool.h

#ifndef T_BOOL_H_INCLUDED
#define T_BOOL_H_INCLUDED

/* Valeurs booleenes pour le type : t_bool */
#ifndef true
#define true    1
#endif
#ifndef false
#define false   0
#endif
#ifndef TRUE
#define TRUE    1
#endif
#ifndef FALSE
#define FALSE   0
#endif

/* Type : t_bool */
typedef unsigned char t_bool;

#endif // T_BOOL_H_INCLUDED

Population

• population.h

#ifndef HEADERS_POPULATION_H_
#define HEADERS_POPULATION_H_

#include ".\t_individual.h"
#include ".\population.h"


typedef struct {
	t_individual * element[50];
} t_population;

t_population * createPopulation(int populationSize, t_bool initialise);
t_individual * getIndividual(t_population * population, int index);
t_individual * getMoreCompetent(t_population *population, t_individual *solution);
int sizePopulation(t_population *population);
void saveIndividual(int index, t_individual individual);
t_individual * getMoreCompetentTournamant(t_population * population, t_individual * solution);


#endif /* HEADERS_POPULATION_H_ */

• population.c

#include <stdlib.h>
#include "..\headers\t_individual.h"
#include "..\headers\population.h"

/*
 * Constructor
 */
// Create a population
t_population * createPopulation(int populationSize, t_bool initialise) {

	t_population * population = malloc(sizeof(t_individual) * populationSize);

	// Initialise population
	if (initialise == true) {
		// Loop and create individuals
		int i = 0;
		t_bool doRand = true;
		for (; i < populationSize; i++) {
			t_individual * newIndividual = generateIndividual(64, doRand);
			doRand = false;
			population->element[i] = newIndividual;
		}
	}
	return population;
}

// Get population size
int sizePopulation(t_population * population) {
	return 50;
}

t_individual * getIndividual(t_population * population, int index) {
	return population->element[index];
}

t_individual * getMoreCompetent(t_population * population, t_individual * solution) {
	t_individual * moreCompetent = population->element[0];
	int i = 1;
	// Loop through individuals to find more competent
	for (; i < sizePopulation(population); i++) {
		if (getCompetence(moreCompetent,solution)  <= getCompetence(getIndividual(population, i), solution)) {
			moreCompetent = getIndividual(population, i);
		}
	}
	return moreCompetent;
}

t_individual * getMoreCompetentTournamant(t_population * population, t_individual * solution) {
	t_individual * moreCompetent = population->element[0];
	int i = 1;
	// Loop through individuals to find more competent
	for (; i < 5; i++) {
		if (getCompetence(moreCompetent,solution)  <= getCompetence(getIndividual(population, i), solution)) {
			moreCompetent = getIndividual(population, i);
		}
	}
	return moreCompetent;
}

Individual

• t_individual.h

#ifndef HEADERS_T_INDIVIDUAL_H_
#define HEADERS_T_INDIVIDUAL_H_

#include "..\headers\t_bool.h"


typedef struct {
	int gene[64];
	int competence;
} t_individual;

t_individual * generateIndividual(int size, t_bool doRand);
void setDefaultGeneLength(int length);
int getGene(t_individual *individual, int index);
void setGene(t_individual *individual, int index, int value);
int sizeIndividual(t_individual *individual);
int getCompetence(t_individual *individual, t_individual *solution);
void toString(t_individual * individual);



#endif /* HEADERS_T_INDIVIDUAL_H_ */

• t_individual.c

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>

#include "..\headers\t_individual.h"
#include "..\headers\t_skill.h"
#include "..\headers\t_bool.h"


int defaultGeneLength = 64;
t_bool randomAlreadyDone = false;
int competence = 0;

// Create a random individual
t_individual * generateIndividual(int size, t_bool doRand) {

	if (doRand == true) {
		srand(time(NULL));
	}

	//generate the individual
	t_individual * new_arr = malloc(sizeof(t_individual));
	int i = 0;
	for (; i < size; i++) {
		new_arr->gene[i] = (int)rand() % 2;
	}
	new_arr->competence = 0;
	return new_arr;
}

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

int getGene(t_individual *individual, int index) {
	return individual->gene[index];
}

void setGene(t_individual *individual, int index, int value) {
	individual->gene[index] = value;
	individual->competence = 0;
}

int sizeIndividual(t_individual *individual) {
	//return sizeof(individual->gene) / sizeof (int);
	return 64;
}

int getCompetence(t_individual * individual, t_individual * solution) {
	//if (individual->competence == 0) {
		individual->competence = getSkill(individual, solution);
	//}
	return individual->competence;
}

void toString(t_individual *individual) {
	int i = 0;
	for (; i < (sizeof(individual->gene) / sizeof(int)); i++) {
		printf("%i", individual->gene[i]);
	}
	printf("\n");
}

Skill

• t_skill.h

#ifndef HEADERS_T_SKILL_H_
#define HEADERS_T_SKILL_H_

#include "t_individual.h"

// To make it easier we can use this method to set our candidate solution
// with string of 0s and 1s
t_individual * setSolution(char * newSolution);

// Compute skill by comparing it to our candidate solution
int getSkill(t_individual * individual, t_individual *solution);
// Get optimum skill
int getMaxSkill();

#endif /* HEADERS_T_SKILL_H_ */

• t_skill.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "..\headers\t_skill.h"
#include "..\headers\t_individual.h"

// To make it easier we can use this method to set our candidate solution
// with string of 0s and 1s
t_individual * setSolution(char * newSolution) {
	// Loop through each character of our string and save it in our byte
	// array
	t_individual * result = malloc(sizeof(t_individual));

	char to[1];
	int i = 0;
	for (; i < strlen(newSolution); i++) {
		to[0] = newSolution[i];
		if (to[0] == 49) {
			result->gene[i] = 1;
		} else {
			result->gene[i] = 0;
		}
	}
	return result;
}

// Compute skill by comparing it to our candidate solution
int getSkill(t_individual * individual, t_individual * solution) {
	int skill = 0;
	int i = 0;
	// Loop through our individuals genes and compare them to our candidates
	for (; i < sizeIndividual(individual) ; i++) {
		if (individual->gene[i] == solution->gene[i]) {
			skill++;
		}
	}
	return skill;
}

// Get optimum skill
int getMaxSkill() {
	return 64;
}

Algorithm

• runtime_algo.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "..\headers\t_bool.h"
#include "..\headers\t_individual.h"
#include "..\headers\population.h"

/* GA parameters */
double uniformRate = 0.5;
double mutationRate = 0.00015;
int tournamentSize = 5;
t_bool elitism = true;

t_bool check(t_individual * solution) {
	int i = 0;
	if (solution == NULL) {
		printf(" ... NULL DETECTED ... ");
		return false;
	}
	for (; i < 64; i++) {
		if (solution->gene[i] != 1 && solution->gene[i] != 0) {
			printf("An individual is invalid (a gene not equals 1 or 0) : ");
			toString(solution);
			return false;
		}
	}
	return true;
}

// Select individuals for crossover
t_individual * tournamentSelection(t_population * pop, t_individual * solution) {
	// Create a tournament population
	t_population * tournament = malloc(sizeof(t_population)); // * sizeInd(pop));
	// For each place in the tournament get a random individual
	int i = 0;
	for (; i < tournamentSize; i++) {
		int randomId = (int) ((rand() % 50));
		tournament->element[i] = pop->element[randomId];
	}
	// Get the fittest
	t_individual * fittest = getMoreCompetentTournamant(tournament, solution);
	check(fittest);
	return fittest;
}

// Crossover individuals
t_individual * crossover(t_individual * indiv1, t_individual * indiv2) {
	t_individual * newSol = malloc(sizeof(t_individual));
	// Loop through genes
	int i = 0;
	for (; i < sizeIndividual(newSol); i++) {
		// Crossover
		if (rand() <= (RAND_MAX / 2)) {
			newSol->gene[i] = indiv1->gene[i];
		} else {
			newSol->gene[i] = indiv2->gene[i];
		}
	}
	return newSol;
}

// Mutate an individual
void mutate(t_individual * indiv) {
	int i = 0;
	// Loop through genes
	for (; i < sizeIndividual(indiv); i++) {
		int rvalue = rand();
		double value = rvalue * 0.0000001;
		if (value <= mutationRate) {
			if (indiv->gene[i] == 1) {
				indiv->gene[i] = 0;
			} else {
				indiv->gene[i] = 1;
			}
		}
	}
}

// Evolve a population
t_population * evolvePopulation(t_population * pop, t_individual * solution) {
	t_population * newPopulation = malloc(sizeof(t_population));

	// Keep our best individual
	if (elitism) {
		newPopulation->element[0] = getMoreCompetent(pop, solution);
		printf("Keep our best individual : ");
		toString(newPopulation->element[0]);
		printf("Searching a way for      : ");
		toString(solution);
	}

	// Crossover population
	int elitismOffset;
	if (elitism) {
		elitismOffset = 1;
	} else {
		elitismOffset = 0;
	}
	// Loop over the population size and create new individuals with
	// crossover
	int i = elitismOffset;
	for (; i < sizePopulation(pop); i++) {
		t_individual * indiv1 = tournamentSelection(pop, solution);
		t_individual * indiv2 = tournamentSelection(pop, solution);
		t_individual * newIndiv = crossover(indiv1, indiv2);
		newPopulation->element[i] = newIndiv;
	}

	i = elitismOffset;
	// Mutate population
	for (; i < sizePopulation(newPopulation); i++) {
		mutate(newPopulation->element[i]);
	}

	return newPopulation;
}

Main

• main.c

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include "..\headers\t_skill.h"
#include "..\headers\t_individual.h"
#include "..\headers\population.h"

int main(void) {
	
	printf("Generation population and mutation :\n");
	printf("1 - Generate optimal solution :\n");
	t_individual * solution = setSolution(
			"0101111011101011011011010000000001111110000000000111111111100000");
	toString(solution);

	// Create an initial population
	int nbIndividualInPopulation = 50;
	t_population * population = createPopulation(nbIndividualInPopulation,
			true);

	printf("Create population :\n");
	int i = 0;
	for (; i < nbIndividualInPopulation; i++) {
		getCompetence(population->element[i], solution);
	}

	int generationCount = 0;
	t_individual * entity = getMoreCompetent(population, solution);

	// Evolve our population until we reach an optimum solution
	while (entity->competence < getMaxSkill()) {
		generationCount++;
		printf("generation : %i competence %i\n", generationCount,
				entity->competence);
		population = evolvePopulation(population, solution);
		//printf("Computation entity done\n");
		entity = getMoreCompetent(population, solution);
	}
	printf("Solution found ! \n");
	printf("The number of generation is %i\n", generationCount);
	entity = getMoreCompetent(population, solution);
	printf("Our solution : ");
	toString(entity);
	printf("The solution : ");
	toString(solution);

	return 0;
}

Sources

Vous pouvez retrouver l'ensemble des fichiers présentés plus haut en téléchargeant l'archive : AlgoritmeGenetiqueEnC.zip

Vous pouvez retrouver l'ensemble des autres programmes developpés en C ainsi qu'un aide mémoire sur le C à cette page.

Exécution

L'exécution de la méthode main , 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 population and mutation :
1 - Generate optimal solution :
0101111011101011011011010000000001111110000000000111111111100000
Create population :
generation : 1 competence 40
Keep our best individual : 0110000101101010011001000000000010011110001100110110011000100011
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 2 competence 43
Keep our best individual : 0000001001011010111000011000000000101110001001010011011001100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 3 competence 49
Keep our best individual : 0111111011101011000010011100101000111110001010000111011111110011
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 4 competence 49
Keep our best individual : 0100011010111011011010001000001001100110100001000111101010100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 5 competence 50
Keep our best individual : 0100011011110011001010000000101001110110100010000111101111100001
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 6 competence 54
Keep our best individual : 0101111010101111011010010001000001011010001000000111111111101011
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 7 competence 54
Keep our best individual : 0101111010101111011010010000000101011010001000000111111111101011
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 8 competence 55
Keep our best individual : 0100111001001011011011010000010000111110000000001011111011000000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 9 competence 56
Keep our best individual : 0100111001101011011011010000010000111110000000001011111011000000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 10 competence 58
Keep our best individual : 0100111011101011011011010010000000111110000000000110110111100010
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 11 competence 59
Keep our best individual : 1101111011001011011011010000000001101110000000000111111111000010
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 12 competence 60
Keep our best individual : 0101111011101011011011011000000001011110000000000011111111100010
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 13 competence 60
Keep our best individual : 0101111011101011011011011000000001011110000000000011111111100010
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 14 competence 60
Keep our best individual : 0101111011101011011011011000000001011110000000000011111111100010
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 15 competence 60
Keep our best individual : 0101111011101011011011011000000001011110000000000011111111100010
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 16 competence 61
Keep our best individual : 0101111011001011011011010000000001111110000000000111011111110000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 17 competence 62
Keep our best individual : 0101111011001011010011010000000001111110000000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 18 competence 62
Keep our best individual : 0101111011001011010011010000000001111110000000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 19 competence 62
Keep our best individual : 0101111011001011010011010000000001111110000000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 20 competence 62
Keep our best individual : 0101111011001011010011010000000001111110000000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 21 competence 62
Keep our best individual : 0101111011001011010011010000000001111110000000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 22 competence 62
Keep our best individual : 0101111011001011011011010000000001111110010000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 23 competence 62
Keep our best individual : 0101111011001011011011010000000001111110010000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 24 competence 63
Keep our best individual : 0101111011101011011011010000000001111010000000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 25 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 26 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 27 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 28 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 29 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 30 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 31 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 32 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 33 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 34 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 35 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 36 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
generation : 37 competence 63
Keep our best individual : 0101111011101011011011010000000001111110100000000111111111100000
Searching a way for      : 0101111011101011011011010000000001111110000000000111111111100000
Solution found ! 
The number of generation is 37
Our solution : 0101111011101011011011010000000001111110000000000111111111100000
The solution : 0101111011101011011011010000000001111110000000000111111111100000

Allez plus loin

Vous pouvez retrouver le précédent article concernant la génération d'un algorithme génétique en Java sur cette page.

Nous avons introduit un certains nombres de paramètres de configuration de l'algorithme, 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.

Eloge du flou