Genetic algorithm study
Le programme miel-abeille est une classe dont l'appel génère un algorithme génétique qui simule plusieurs générations d'abeilles au travers de diverses sélections. Le principe d'un tel algorithme repose sur un ensemble de données de départ qui constituent une population dont chaque membre a un génome. En fonction de la nature du problème on détermine la performance des génomes de la population grâce au 'score de fitness'. On opère ensuite une sélection des individus sur la population, cette sélection peut être caractérisée de diverses manières. Dans notre cas on a choisi une sélection aléatoire en attribuant une probabilité de choix plus importante aux individus les plus performants. Après cette étape on fait un croisement depuis la population sélectionnée afin d'obtenir de nouveaux individus et reconstituer une population avec une meilleure performance, c'est la nouvelle génération. Dans notre cas on a opté pour deux types de croisement, le croisement par simple enjambement et le croisement par décalage de génome. Le croisement par simple enjambement consiste, à partir de deux parents, à coller deux blocs de génomes de parents différents qu'on a coupé au même endroit. Le croisement par décalage consiste à prendre le génome d'un individu et de le décaler d'un certain nombre de gènes vers la droite de telle sorte que les gènes de fin se retrouvent au début. Dans les deux cas on obtient un nouvel individu avec des caractéristiques meilleures. On recommence alors le processus jusqu'au point d'arrêt choisi, soit selon une condition donnée soit en précisant à l'avance le nombre de génération. Au bout d'un certain temps la performance des individus peut avoir tendance à stagner et on peut avoir recours à une mutation, la mutation peut consister à remplacer un gène par un autre ou plusieurs gènes par d'autres.
Dans le programme miel-abeille on dispose d'un fichier .xls qui contient les 50 coordonnées d'un champ de fleurs que des abeilles doivent polliniser. Le programme se charge alors d'importer ces données dans un dataframe du module pandas puis il créé à partir de ces dernières une ruche de 100 abeilles dont les génomes sont des combinaisons aléatoires des coordonnées des fleurs. Le fichier beehive.py contient la classe Bee, un ensemble de méthodes qui va générer plusieurs générations d'abeilles et afficher les performances des générations successives dans un graphique du module Matplotlib. La méthode generation() condense en une chaîne toutes les opérations nécessaires à la selection, le calcul de performance et le croisement de la population dont la mise en boucle va permettre la production des diverses générations. Pour déterminer la performance des abeilles on calcul la distance totale de leurs coordonnées successives, on a choisi pour ce faire la fonction sq_euclidean(la distance euclidienne au carré) du module scipy.spatial.distance qui offre le calcul le plus rapide parmi toutes ses distances (0.16s pour calculer les distances de toute la ruche). Pour calculer le socre de fitness on somme les distances successives de chaque abeille, le plus petit résultat représente alors l'abeille la plus performante. On opère ici la sélection selon la méthode probabiliste décrite plus haut (on sélectionne 50 abeilles dans notre cas) puis on passe au croisement. Pour le croisement par décalage, on décale toute les valeurs du vecteur génome vers la droite sur la population d'abeilles sélectionnées(dans le programme on a opté pour une valeur de 5) puis on ajoute les 50 abeilles créées de la sorte à celles sélectionnées initialement pour faire une nouvelle ruche, on garde ainsi un taux de performance suffisament élevé mais pas excessif. Pour le croisement par simple enjambement on a choisi de faire la coupe sur une seule abeille afin d'éviter les doublons de gènes. On prend une abeille de la population sélectionnée, on choisi un pivot autour du quel on va échanger les blocs pour faire un nouveau génome, on applique cela sur 50 abeilles puis on ajoute ces 50 abeilles à celles sélectionnées initialement pour créer la nouvelle ruche. Enfin on recommence le processus avec cette nouvelle ruche et les performances doivent augmenter. On affiche la moyenne des scores de fitness de la ruche pour représenter le résultat des générations successives.
On constate bien une baisse du score de fitness moyen mais le programme mérite bien des améioration. Tout d'abord, en ce qui concerne les méthodes de croisement il faudrait que le taux de décalage ou le pivot d'enjambement puisse varier en fonction des générations (avec de la récursion par exemple), cela pourrait être lié à la mutation. Pour la mutation nous avions l'idée mais pas assez de temps pour l'implémenter correctement, le point délicat de la mutation concerne le moment du déclenchement. Pour cela nous avons penser à un calcul de dérivée qui se ferait toutes les 10 générations environ et sur ces 10 dernières générations. Si la dérivée ne dépasse pas un certain seuil pendant x générations alors on déclenche la mutation. Dans la classe Bee on a écrit une méthode derivative() qui est une dérivée simplifiée qui devrait fonctionner pour une telle utilisation. Cependant le problème avec la dérivée est que le nombre de générations doit être très élevé pour être efficace, en effet sur un petit nombre de générations (100-200) les amplitudes du score de fitness moyen peuvent être très élevées, pour les méthodes de croisement utiisées dans notre programme en tout cas. Une autre manière de procéder consiste à déterminer un seuil qui, s'il n'est pas dépassé pendant une certain nombre de génération, alors la mutation est déclenchée. Pour cette technique il y a deux problèmes principaux: soit il faut connaître le comportement de l'algorithme en avance i.e avoir étudié plusieurs productions de générations afin d'estimer quels nombres seraient utiles pour déterminer un seuil; soit ne pas connaître ces nombres à l'avance et intégrer un appareil analytique consistant dans une boucle récursive. Cette dernière option ferait gagner le programme en 'organicité' et serait un premier pas vers quelque chose d'"intelligent".