Dans ce chapitre nous allons décrire comment programmer l'exemple (optimisation de x->x² sur [0;31]) en Delphi (Pascal Objet). Le choix du langage Delphi est motivé par la clarté du langage Pascal et la facilité de Delphi pour faire une interface utilisateur conviviale, mais les algorithmes proposés seront aisément transposables dans d'autre langages (C/C++, Java, Basic,...). Vous pouvez télécharger le projet Delphi complet. Les détails de l'interface ne seront pas explicités ici, veuillez consulter directement le source du projet.
Télécharger le projet (source)
Télécharger l'exécutable
(si vous n'avez pas Delphi pour le compiler)
1) Structures de données utilisées, déclarations et initialisations
Nous allons commencer par définir les types de données dont on aura besoin, de l'intérieur vers l'extérieur :
Chaque gène (ou allèle) sera codé sur un bit.
Un chromosome sera un tableau de bits.
Un individu sera une structure contenant les informations suivantes :
- Chromosome
- Valeur de x
- Adaptation
- Parents 1 et 2 ainsi que le point de croisement.
Une population sera un tableau d'individus.
Ceci donne le code suivant :
type allele=boolean;
chromosome=array of allele;
individu=record
Chrom:chromosome;
x:extended;
Adaptation:extended;
Parent1,Parent2,PtCross:integer
end;
population=array of individu;
Puis vient la phase de déclaration des variables globales :
var OldPop,NewPop:population;
TaillePop,LongChrom,MaxGen:integer;
PCross,PMut:extended;
NbMut,NbCross:integer;
SommeAdapt,Moy,Min,Max:extended;
OldPop et NewPop sont respectivement l'ancienne et la nouvelle population.
TaillePop représente le nombre d'individus de nos populations.
LongChrom est la longueur de chaque chromosome.
MaxGen est le nombre maximum de génération avant la fin de l'algorithme.
PCross et PMut représentent respectivement la probabilité de croisement
et de mutation.
Ces cinq dernières variables sont à rentrer par l'utilisateur
dans l'interface.
NbMut et NbCross représentent respectivement le nombre de mutations et
de croisement dans une génération.
SommeAdapt, Moy, Min et Max stockent les statistiques de chaque génération.
SommeAdapt servira pour la construction de la roulette de croisement.
Voici enfin les déclarations des fonctions et procédures que nous utiliserons :
Tout d'abord celles qui concernent explicitement l'algorithme génétique :
function f(u:extended):extended;
function decode(chromo:chromosome;lc:integer):Extended;
procedure InitPop(var pop:population;Taille:integer);
function select(var Pop:Population;Taille:integer;
Somme:extended):integer;
function mutation(AlleleVal:Allele;pmutation:extended;
var nmutation:integer):allele;
procedure crossover(var par1,par2,fils1,fils2:chromosome;
var
Taille,ncross,nmutation,icross:integer;
pcros,pmutation:extended);
procedure generation(OldPop:Population;var NewPop:population; TaillePop:Integer;
var SommeAdapt:extended;
var
LongChrom,nbcross,nbmut:integer;
pcross,pmut:extended);
Puis quelques fonctions mathématiques dont nous aurons besoin :
function power(a:extended;b:integer):extended;
procedure statistique(pop:population;Taille:Integer;
var Mini,Maxi,Somme, Moye:extended);
function flip(p:extended):boolean;
function rnd(a,b:integer):integer;