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.
Encore un délire de barbu d’université ça !
On trouvera vraiment de tout sur ce blog.
Solution élégante effectivement.
J’aime beaucoup l’article, beaucoup moins l’intro.
Il y a des actrices tellement plus intéressantes à cloner que l’insipide Clara Morgane …
Miss Cash avait plus de chien. Cétémieuxavant.
@Marc, Qu’est ce que tu veux, j’ai grandi avec ! En essayant tant bien que mal de programmer le magnétoscope le premier samedi du mois sur la cassette de la petite sirène (et faut pas oublier le petit bout de scotch sur le coté de la cassette pour éviter la catastrophe !) :D
@Golgotha : si ce sont des souvenirs d’enfance, je ne pourrai pas lutter ;)
A l’époque, moi c’étaient Draghixa et Fovéa ;)
haaaaa fovea ! la scene avec le pilote d’avion en extérieur, elle se prend une éjac faciale anthologique !
la belle époque…
A propos des algos génétiques :
http://lkdjiin.github.io/blog/categories/algorithme-genetique/
et du clonage d’actrice (SJ Parker) :
http://www.slate.fr/life/81079/cheval-clone-vainqueur-championnat-polo
La série de lkdjiin est excellente, d’ailleurs je l’ai tweeté il me semble.
http://boxcar2d.com/
Attention, ça peut être chronophage. En fait, soit on est complètement pris, soit on se dit que ça sert à rien en 10 secondes.
Je ne fais pas partie de la deuxième catégorie.
Ce truc est génial !
Je crois que je suis également tombé dedans.
Adieu productivité !
Article intéressant en effet. J’aimerais bien voir aussi des algos décortiqués du genre ceux des labyrinthes parfaits et la résolution des chemins.
Heu, étant de l’infrastructure plus que dans le code, je dis peut-être une connerie, mais dans ce petit bout de code:
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]
Y’aurait-y pas une division par 2 de trop?
J’ai l’impression que first segment ne reprend que 25% des points de l’individu, du coup.
C’est bine, mais là, vous rentrez dans le monde géospatial et il y a de nombreux modules Python pour traiter ce genre de problèmes.
Problème: que faire si on veux moins de 100 itérations ?
population[99]
Heu martin, tu as bien pigé que le but c’est de présenter le principe de la prog génétique et que l’exemple est bidon exprès, hein ?
oui, mais il y a aussi moyen de le faire avec les modules géospatiaux (classes, points, individu) et là l’application de la méthode devient très, très intéressante
Mais implique un niveau d’indirection supplémentaire.
http://sametmax.com/bien-expliquer-quelque-chose-les-regles-de-base/
J’ai l’impression qu’il y a une imperfection dans l’algorithme :
en effet, la première moitié du chemin (ou premier quart selon e-Jim), ne va jamais évoluer (puisque celle-ci est directement héritée d’un des parents).
Ainsi, dans la solution donnée par l’algorithme la première moitié du trajet aura été générée aléatoirement à la première génération, mais jamais améliorée !!
Un correctif simple serait de “retourner” (miroir) le chemin des enfants (pas de changement de score, mais une remise en cause de la première moitié du chemin)
C’est bien beau tout ça mais la recherche du plus court chemin dans un graphe c’est juste l’algorithme de Dijkstra qui à une complexité polynomiale…
lien wiki:
Ok, tampon parce que non seulement t’es relou, mais en plus relou après qu’un autre ait fait pareil et que je l’ai poliment corrigé.
@etno712, le problème du voyageur du commerce est plus complexe que cela, il ne peux pas être résolut dans un temps polynomiale. On utilise l’algorithme de Dijkstra quand ont est pas obligé de passer par tout les noeuds du graphe.
Cool de voir qu’on parle des algorithmes génétiques ailleurs que chez moi ;)
Oui, désolé, je vais essayer d’y remédier avec un exemple
Si tu veux écrire un truc complet, on peut même le publier sous forme d’article si tu veux.
C’est sans doute le truc le plus soporifique qu’il m’est été donné de lire en 2013.
12 ème génération… score 792 max
Merci glandu, j’ai perdu 24h…
Moi je préfère les moutons.
@Max : 136è génération, je stagne à 777.3
Je relance en autorisant plus de roues, avec un facteur de mutation supérieur.
Je crois que je suis accro …
Moi je dis, clonez Dillion Harper…
Quand aux commentaires spatiaux, de Martin ou etno712, il faut juste comprendre qu’il y a jonctions de communautés sur ce joli blog!
Des barbus pythoniens d’une discipline X, et des utilisateurs de python en géomatique (la science des données géographiques, ie des tables de base de données avec une colonne géométrie) dans laquelle le python est très utile. Chercher par exemple les posts dudit Martin sur , le portail d’un des forums francophone dédié à la discipline.
J’adore ce portail, j’ai juste horreur des personnes qui postent un commentaires de “correction” qui est complètement à côté de la plaque. Si l’article s’intitulait “comment calculer le meilleur trajet”, il sera apprécié. Mais là on est clairement dans un truc qui n’a rien à voir.
“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.”
En fait, il est possible que l’algo donne la solution optimale. Par contre, il n’y aucune garantie que ce soit le cas (et le cas général, ça ne l’est pas).
et au passage : « solution exact » -> « solution exacte »
Merci golgotha pour cet article, beau boulot pédagogique et je me suis bien éclaté a décortiquer tout ça !
J’ai juste une petite question de rien du tout…
Dans la fonction :
def set_route(self, map_point)– tu mélange la liste de point pour que l’individu explore une nouvelle route.
Ensuite quand tu fais un “croisement”:
– tu garde la moitie de la route d’un superman
– tu complète avec les points d’un trainard pour avoir la map complète
– et tu mélange a nouveau… (appel a
set_routepour le nouvel individu)Donc ce que je ne comprend pas c’est l’intérêt du croisement. Si j’ai bien suivi, je peux obtenir la même chose en créant un nouvel individu sans croisement (puisqu’au bout du compte on mélange tout les points)…
Du coup, l’algo se résumerai a:
– je prend 100 individu avec des routes aléatoires
– je garde les 15 meilleurs
– j’en prend 85 nouveaux aléatoirement
– je croise les doigts pour que le dieu random me fasse un petit génie du plus court chemin a la prochaine iteration
Alors, soit j’ai rien compris (ça m’arrive souvent !), soit je peux proposer un petit patch (je metterai mon bout de code si ca interesse):
– on randomize la route dans le constructeur des Individus et seulement quand init=True:
– on vire le shuffle dans la fonction set_route
Pour le croisement:
– on garde une partie de la route de l’individu (un segment aléatoire histoire de ne pas avoir tout le temps que le début du chemin)
– on ajoute les points qui manque dans l’ordre de parcours du deuxieme individu (ce que tu fais)
Comme ça on garde une trace des deux individus pour le petit larbin que l’on vient de créer.
Désolé j’ai menti, c’était pas une petite question… Mais j’aimerai bien comprendre !
Il me semble que tu as tout à fait raison Mantisse, je regarde ça et je corrige :)
Si l’anglais ne vous rebute pas trop…
je considère se site comme une perle en la matière!
http://rosalind.info/problems/locations/