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.

On peut objecter aux hommes de trop se décharger devant youjizz (il est où le rouleau de sopalin ??) mais cela a un avantage indéniable… On acquiert un bac+8 en porn à force d’étudier les arts de combat des autres mecs, on apprend des techniques plus ou moins efficaces et devenir maître dans l’art de la galipette n’est pas chose aisée ! ça ne vient pas comme ça, en claquant des doigts.

Les femmes ayant longtemps été considérée comme des objets pour les hommes, en leur inculquant une morale chrétienne et la culpabilité d’une sexualité libérée, elles doivent aujourd’hui surmonter ce passé pour apprécier une vidéo porno, qui je le rappelle n’est pas forcément vulgaire. Le truc c’est que les femmes qui s’interdisent tout accès à la pornographie pour la simple raison que ce n’est pas catholique, auront plus de mal d’une manière général à comprendre ce que désire un homme, par manque de curiosité et par manque d’expérience, expérience que l’on peux acquérir justement en allant à droite et à gauche regarder quelques vidéos amateurs. De plus, on voit maintenant fleurir sur les sites des catégories moins hard, plus pour les femmes curieuses de voir quelques vidéos soft genre dimanche soir sur M6.

Exemple n°1 : je branle mon mec comme un cheval, très vite et très fort, ça va lui faire du bien. WTF, mais arrêtez de nous prendre pour un animal quoi, déjà niveau plaisir ce n’est pas ça, pire ça peut faire mal ! Un peu de sensualité, de délicatesse, combien de femmes savent qu’on peut faire jouir un mec sans même le toucher ? Et oui… Et ça c’est vraiment un manque de culture érotique, message pour les femmes : Allez regarder du porn !!

Exemple n°2, la pipe mécanique, genre je regonfle mon pneu… Une bonne fois pour toute : un pipe comme ça, sans regard échangé, de façon mécanique, c’est ZERO sur l’échelle du plaisir pour un mec. Désolé de vous décevoir mais ça fait autant d’effet que de la crème solaire sur le dos d’une tortue. Pourtant,ce ne sont pas les idées qui manquent, encore une fois le plaisir d’une pipe sera décuplé par la sensualité, par le jeu amoureux, une femme qui masturbe lentement son mec avec sa bouche juste à coté, qui induit qu’elle pourrait le lécher sans le lécher, ça c’est l’extase pour le mec.

Les femmes : Allez voir du porn amateur (pas des gangbangs pro, ça, ça ne sert à rien), il y a pas mal de vidéos soft et sensuelles qui donnent des idées et surtout qui vous feront changer d’avis sur la manière de faire bander un mec, parce que vraiment, parfois il y a du boulot…

On a parfois du mal à localiser l’origine d’un bug dans une longue requête sql ou un code spaghetti de 5000 lignes écris en 1999 par un biologiste recruté dans une SSII. Bien sur vous pouvez tenter la méthode traditionnelle, essayer de comprendre d’où viens le bug, de façon logique… ou bien gagner du temps et appliquer la méthode que je préfère dans ce genre de situation : la dichotomie.

Le principe est simple, couper en deux le code défectueux (commenter la moitié), re-faire un test, si le code marche, l’erreur viens de la partie commentée ou inversement, ensuite prenez la partie défectueuse et recommencez. Vous tomberez assez rapidement sur le bug, généralement en quelques minutes grand max, sans avoir réfléchi, c’est pratique quand vous devez trouver un bug rapidement en prod dans la panique générale.