Mise à jour
Mise à jour de la base de données, veuillez patienter...
Ceci est un post invité de golgotha posté sous licence creative common 3.0 unported.
Qui n’a jamais rêvé de cloner des moutons clara morgane et de s’adonner à des expérimentations scientifiques de haut niveau ?
Bon ici, nous n’avons pas de clara morgane sous la main pour notre expérience mais, avec le python et les théories scientifiques de Darwin, on peut faire quelques trucs sympas : On va essayer de déterminer le plus court chemin à prendre pour relier plusieurs points entre eux, le truc cool c’est que pour solutionner le problème on va utiliser un algorithme génétique.
De la génétique dans du python ?!
En fait c’est assez simple (encore des termes barbares pour épater les copains..), écoutez bien, je vous explique le concept : on va faire des individus, chaque individu va faire un parcours en fonction des points du tracé en paramètre. A la fin, on note chaque individu avec un score, le score étant la longueur du parcours de l’individu. Vous suivez toujours ? Bien. On prend les meilleurs (Normal) et on les accouple avec des moins bons (faut les pousser un peu, au début ils sont timides mais, après ça va tout seul, c’est même l’orgie parfois…) ce qui donne une nouvelle population, normalement un poil meilleure que l’ancienne qu’on va vite mettre à la poubelle. On recommence le processus n fois et à la fin, on devrait arriver à des super individus, genre blonds aux yeux bleus qui parlent 14 langues : ça c’est notre solution.
Passons aux travaux pratiques !
Je commence par déclarer deux variables globales, la population et la liste de points.
population = [] a_map = []
Ensuite on créer une classe Point standard :
class Point(object): COUNT = 0 def __init__(self, x, y): self.X = x self.Y = y def __str__(self): return "Point(%s,%s)"%(self.X, self.Y) def distance(self, other): dx = self.X - other.X dy = self.Y - other.Y return sqrt(dx**2 + dy**2)
Rien de particulier ici, l’objet nous sera utile plus tard.
class Individu(object): # le constructeur de l'objet. # on met le score à zéro. # on peut aussi lui passer la liste de points # pour qu'il initialise une route au hasard. def __init__(self, init = False, map_point = []): self.score = 0 self.route = [] if init : self.set_route(map_point) # ici on créé une route avec un mélange des points # on utilise shuffle pour mélanger les points. # ensuite on calcul le score, c'est à dire la longueur du trajet. def set_route(self, map_point) : shuffle(map_point) self.route = map_point for p in range(len(map_point) - 1) : self.score += map_point[p].distance(map_point[p+1]) # ici on donne à l'objet la capacité de faire un enfant # ça prend comme paramètre l'objet (lui même), et un autre individu. # on prend la moitié du trajet de l'objet et on complète avec # les points de l'autre individu. # on retourne un enfant, qui est un individu. def croisement(self, other): child = Individu() # je prends la moitier de moi-même. wdth = len(self.route)/2 first_segment = self.route[:wdth/2] last_segment = [] # je complète avec l'autre for i in range(len(self.route)) : if other.route[i] not in first_segment : last_segment.append(other.route[i]) child.set_route(first_segment + last_segment) return child # ici on défini une fonction pour que l'objet puisse se dessiner. # pour cela on utilisera Turtle de python. def show_me(self): turtle.clearscreen() pen = turtle.Turtle() pen.speed(0) pen.up() pen.setpos(self.route[0].X, self.route[0].Y) for point in self.route : pen.goto(point.X, point.Y) pen.down() pen.dot() pen.goto(self.route[0].X, self.route[0].Y)
Voilà pour l’objet individu (pas très inspiré sur le nom j’avoue..) qui est donc capable maintenant de faire pas mal de choses qui sera utile: se montrer, faire un petit (capacité que beaucoup d’objet lui envie déjà) et choisir une route parmi une liste de points.
La suite, j’ai écris ça dans des fonctions, il y a surement plus propre mais bon, le but est de vous montrer comment fonctionne un algo génétique, je laisserai le soin aux pro du python d’améliorer le code en lui-même (je ne vais pas faire tout le boulot non plus !)
# initialisation des points de la carte. # prend en paramètre un nombre de points. def init_map(nb): global a_map del a_map[:] for i in range(nb): p = Point(randint(1, 300), randint(1, 300)) a_map.append(p)
# initialisation de la population. # prend en paramètre le nombre d'individus à créer. def init_pop(nb, map_point): global population del population[:] for i in range(nb): i = Individu(True, map_point) population.append(i)
# fonction qui sert à trier les individus suivant leur score. # utile pour trouver les meilleurs. def selection(pop): pop.sort(key=lambda x: x.score, reverse=True)
# dans cette fonction, on sélectionne les 15 meilleurs individus de la population # que l'on croise avec les autres individus. # la nouvelle population est constituée des 15 meilleurs plus les enfants. def croisement(pop): new_pop = [] best_pop = population[85:] for i in range(len(pop)-15) : new_pop.append(choice(best_pop).croisement(choice(population[20:85]))) return new_pop + best_pop
# la fonction principal. # on passe en paramètre le nombre de générations que l'on souhaite faire # et le nombre de points. # Ensuite, on itère selon un algorithme précis : # Création d'une population initiale. # Sélection puis croisement de la population # à chaque génération on regarde si on a un meilleur score # si oui, on l'affiche. def play(nb_gene, nb_point) : init_map(nb_point) init_pop(100, a_map) best_score = 1000000 for i in range(nb_gene) : global population population = croisement(population) selection(population) if best_score > population[99].score : best_score = population[99].score print 'meilleur score : ' + str(population[99].score) population[99].show_me()
Voilà le morceau, je pense que j’ai laissé assez de commentaires dans le code pour bien comprendre comment ça fonctionne et au niveau du python en lui-même il n’y a vraiment rien de spécial, ici ce qui compte c’est que vous voyez rapidement comment fonctionne l’algorithme.
Alors, maintenant : Pourquoi s’emmerder à accoupler des objets à 2,78 Ghz ?
Le problème ci-dessus, un problème dit np-complet, c’est-à-dire que c’est la merde pour trouver une solution dans un temps raisonnable si on l’a fait de façon traditionnelle : pour trouver le meilleur trajet sur 10 points, on sera obligé dans un premier temps de trouver tous les trajets possibles, avec N villes on a (N-1)!/2 trajet possible, le nombre de trajets explose littéralement si N augmente. Avec 100 points il est déjà pratiquement impossible de calculer tous les trajets possibles en un temps raisonnable.
C’est là que l’algorithme génétique est très fort, on arrive très vite à une solution approchée, il est tout de même à noter que le résultat obtenu par l’algorithme génétique n’est pas LA solution exact au problème, il donne une solution approchée.
Dernier point sur le code ci-dessus, ce n’est que les bases de l’algorithme génétique, avec ce code vous ne pourrez pas venir à bout d’un parcours de plus de 20 ou 30 villes, pour cela il faut améliorer l’algorithme, par exemple le croisement entre deux individus peut être fait de plusieurs façons différentes, dans mon exemple je prends la moitié du “code génétique” d’un individu que je colle à une autre moitié, on peut aussi faire du crossover : c’est-à-dire qu’on prend des bouts du code génétique des deux individus alternativement. Ensuite, il y a aussi des mutations génétiques à introduire dans le croisement, à un certain taux, par exemple 1% des croisements entre individus produira une mutation génétique, concrètement : on fait le croisement puis on change aléatoirement des données du code génétique, dans notre exemple on échangera deux points sur le parcours. Cela a pour effet de produire des individus potentiellement meilleurs que les autres, en terme mathématique ça permet aussi de ne pas s’enfermer dans une solution locale, ce qui est souvent le cas.
J’espère ne pas vous avoir complètement perdu avec mes explications et vous avoir donné envie de regarder de plus près cet algorithme que je trouve très élégant.
