#Algorithmes génétiques 101

Voici une présentation très élémentaire des algorithmes génétiques autour d'un problème trivial : trouver l'entier sur 8 bit qui contient le maximum de 1 dans son écriture binaire.

Bien entendu, la solution de ce problème est l'entier 0b11111111 i.e. 255 mais ici on cherche à le faire émerger à travers un algorithme génétique.

Pour cela on commence avec une population constituée de nombres générés aléatoirement.

A chaque étape on fait deux types d'opérations pour passer à la génération suivante :

  • des croisements on choisit deux nombres au hasard 0bABCDEFGH et 0bIJKLMNOP et on produit un enfant 0bABCDMNOP prenant les quatre bits de poids forts du premier nombre et les quatre de poids faibles du second (le choix de faire le croisement ainsi est arbitraire)
  • des mutations on choisit un nombre aléatoirement et on choisit un bit aleatoirement dans ce nombre dont on change la nature (0 devient 1 et réciproquement)

Ensuite, on applique une procédure de selection naturelle en ne gardant que la partie de la population ayant le plus de 1 dans son écriture binaire.

Par exemple on pourrait avoir la première génération : 00110011 01000100 11100110 après trois croisements on produit les nouveaux nombres 11100100 00110110 11100011 et après mutation deux autres nombres 10110011 00000100 et on ne garde que les trois meilleurs : `10110011 11100011 11100110

Puis on itère cela pour un certain nombre de générations. Voici un exemple de programme Python effecutant cela :

N = 100 # la population d'une generation
G = 10 # le nombre de generation
M = 10 # le nombre de mutations par generation
C = 50 # le nombre de croisements

from random import randint, choice
def genere(): # genere une solution aleatoire
    return randint(0,255)

# evalue la solution en comptant le nombre de 1
def evalue(n):
    c = 0
    while n != 0:
        c += n % 2
        n //= 2
    return c

# effectue une mutation 
def mute(n):
    k = randint(1,4) # un nombre de bit a muter
    for i in range(k):
        j = randint(0,7) # un bit aleatoire a modifier
        n ^= 1 << j # on bascule le jeme bit
    return n

# croise deux solutions en prenant les 4 premiers bits 
# de l'une et les 4 derniers de l'autre
def croise(n, m):
    return (n % 16) + (m & 240)

population = [ genere() for _ in range(N) ]
for g in range(G):
    enfants  = []
    for _ in range(C):
        a, b = choice(population), choice(population)
        enfants.append( croise(a,b) )
    for _ in range(M):
        i = randint(0,N-1)
        population[i] = mute(population[i])
    for e in enfants:
        population.append(e)

    population.sort(key = evalue)
    population = population[-N:]
    # les dix meilleurs
    print("Generation {} : {}".format(g, repr(population[-10:])))