La théorie de Darwin est basée sur les idées de mutations et de sélection naturelle. Pour simplifier,
dans une espèce, un certain nombre d'individus naissent avec des mutations qui
les différencient légerement des autres individus et leur procurent éventuellement
un avantage. La sélection naturelle élimine, au bout d'un certain nombre de générations, les individus
n'ayant pas acquis un avantage donné.
Cette théorie repose entre autres sur deux phénomènes
importants ayant lieu lors de la reproduction : la sélection et les mutations.
Dans le cadre de la reproduction sexuée, il y a une sélection du partenaire. Ainsi, on constate chez de nombreuses espèces animales qu'au début de la saison des amours, les mâles s'affrontent, et que seul le mâle dominant pourra s'accoupler et transmettre ses gènes aux générations futures.
Cela constitue une des parties de la sélection naturelle.
Lors de la création des gamètes, il peut exister des différences entre l'ADN du parent et le fragment d'ADN que contiennent les gamètes. On peut ainsi constater l'apparition chez les enfants de caractéristiques totalement absentes des parents.
Le rôle du hasard est ici préponderant, puisque seule la probabilité d'un gène à muter peut-être déterminée, sans que l'on puisse dire avec certitude s'il mutera avant d'avoir sous les yeux le résultat final, et on ne peut jamais prédire ce qui résultera de la mutation si jamais elle a lieu.
Dans le cadre de notre projet d'implémentation d'algorithmes génétiques de pathfinding, nous avons été amenés à choisir une modélisation de nos chemins, à laquelle nous pourrions appliquer ces principes généraux. Pour cela, nous avons décidé de modeliser un chemin par la structure :
typedef struct {
int genes[nbGenes];
int longueur;
} t_Indiv
Plus précisement, chacun des gènes du tableau contient un entier, compris entre 0 et 3, qui indique un déplacement de l'individu. Le tableau dans son intégralité constitue donc la suite des déplacements qu'effectuera l'individu en partant du point de départ, et en espérant atteindre le point d'arrivée.
L'entier longueur chiffre quand à lui la performance de l'individu, c'est à dire le nombre de déplacements qu'il doit effectuer pour rejoindre l'arrivée. En conséquence, tous les gènes au delà de longueur seront ignorés.