|
Excel-Store contient une classe permettant d'implémenter un algorithme génétique en VBA. Les algorithmes génétiques permettent de trouver des solutions intéressantes à des problèmes ayant un nombre important de possibilité à condition qu'ils se prètent à ce type de modélisation.
En premier lieu, il faut arriver à coder une solution potentielle à un problème sous forme de chaîne de caractères que l'on nomme en général chromosones par analogie à la biologie. Avant, il faut donc définir un alphabet, si le codage d'un individu doit se faire en binaire, il faudra indiquer "01" comme caractères autorisés.
En définissant le nombre de caractères et l'alphabet, on peut créer au hasard toute une population d'individus. Dans notre programme, il faudra indiquer la taille de cette population de départ.
Cela ne sert à rien si on ne peut pas savoir ce que vallent tous ces individus, il vous faudra donc programmer une fonction qui calculera pour un individu une valeur que le programme cherchera à maximiser.
Pour passer à une nouvelle génération, on va ajouter des enfants. Un enfant est créé en choisissant deux parents en en choisissant pour chaque caractères au hasard celui de l'un ou l'autre des parents. Si vous pensez que ce n'est pas la bonne manière de procéder, vous pouvez indiquer une autre procédure que vous aurez écrite.
En plus des enfants, on va ajouter des clones mutants, c'est à dire des copies d'individus avec un pourcentage de gènes modifiés. Vous pouvez indiquer le nombre de mutants le % de gènes modifiés et si ce type de mutation ne vous semble pas adapté, vous pouvez créer une autre procédure que vous aurez écrite.
En plus des enfants et des mutants, on peut aussi ajouter des individus créés au hasard.
On se retrouve avec une nouvelle population = population de départ + enfants + mutants + génération spontanée.
Pour la génération suivante, on ne garde que l'équivallent de la population de départ en gardant ceux qui ont eu les meilleures notes. Cette manière de faire permet une convergence rapide mais peut s'enfermer dans des minima locaux. Pour la tempérer une procédure peut être lancée périodiquement pour supprimer les doublons ainsi que les individus de faible diversité génétique.
Pour pouvoir utiliser cette fonctionnalité d'ExcelStore, vous devez l'installer et y faire référence via le menu outils/références de l'interface vba :
Un premier exemple va consister à trouver un mot sans dictionnaire. Cela peut sembler simple, mais pour toutes les combinaisons d'un mot de n lettres, on se retrouve à tester 26^n combinaisons. Ce qui fait plus de 8 milliards de combinaisons pour un mot de 7 lettres.
Télécharger Motus
Il s'agit d'aller le plus loin possible dans un parcours fléché en devant suivre un chemin. Chaque pavé est marqué d'un nombre allant croissant vers 95 qui est le but à atteindre.
Les murs sont représentés par la valeur -1
Les déplacements sont donnés par 4 sens Haut Bas Gauche Droite. Le chromosome va donc être un texte de 120 caractères parmi "GHDB".
A partir d'une position de départ sur la feuille Excel et d'un déplacement on va trouver la nouvelle position qui va être décalée dans le sens indiqué. Dans le cas où la cellule désignée est un mur, on reste sur place.
Télécharger labyrinthe
Il s'agit dans cet exemple de créer une image qui restitue le plus fidèlement un tableau de 26*26 avec un dégradé de 26 valeurs. Pour cela, on va dans notre toile de 26*26 mettre 100 carreaux de 3*3 unis.
26 permet de coder sur un alphabet de A à Z.
On va mettre les valeurs dans chaque cellule et utiliser une plage de cellule qui va faire la différence. C'est la somme de ces écarts qui va être notre fonction à optimiser. La fonction d'évaluation d'un individu va consister à le dessiner et à récupérer le résultat de la cellule.
pour dessiner un rectangle de 3*3, on va partir d'un texte de 3 caractères : ligne/colonne/valeur. Chaque valeur étant trouvée par la place de la lettre dans l'alphabet...
Télécharger Peinture
Il s'agit de disposer huit reines sur un plateau de 8 * 8 de telle manière qu'il y en ait jamais plus d'une sur une ligne une colonne ou une diagonale.
Télécharger n reines
|
Motus
