Algorithme génétique

L'objetif de cette page est de présenter assez simplement les enjeux des algorithmes génétiques.

	
	# le probleme : One-max
# on cherche une entier sur 8bit qui contient le maximum de 1 dans son ecriture
# binaire
# On sait deja que l'optimal c'est 0b11111111 = 255 mais on veut le faire par
# algorithme genetique

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:])))