<jupyter_start><jupyter_text>Algorithmes génétiquesVous souhaitez partir dans l'espace et trouvez un manuel un peu étrange. Ce manuel contient un message en 32 caractères qui n'est plus lisible. Le manuel vous fournit en revanche une fonction Python (!) qui, à partir d'un message passé en paramètre (chaîne de caractère) renvoit le nombre de caractères correctement placés par rapport au message d'origine.<jupyter_code>from stochastic.data import score
score("Hi guys!")<jupyter_output><empty_output><jupyter_text>Bon, c'est déjà ça... La fonction fournie permet de faire des tests avec une autre solution, ce qui va nous permettre de mettre au point un algorithme de résolution.<jupyter_code>score("plop", solution="ploc")<jupyter_output><empty_output><jupyter_text>Nous allons mettre au point un algorithme de résolution de type « algorithmes génétiques » pour résoudre le décodage du message "Hello world!".<jupyter_code>score_hello = lambda x: score(x, solution="Hello world!")
score_hello("Hello world!")<jupyter_output><empty_output><jupyter_text>Tout d'abord, considérons l'ensemble des caractères qui forment notre mot. On a le droit: - aux vingt-six lettres de l'alphabet minuscules; (message en anglais, sans accent!) - aux mêmes lettres en majuscules; - à la ponctuation.<jupyter_code>import string

letters = string.ascii_uppercase + string.ascii_lowercase + string.punctuation + ' '
letters<jupyter_output><empty_output><jupyter_text>Puisqu'on travaille avec un problème plus petit, on stocke cette taille:<jupyter_code>length = score_hello("Hello world!")
length<jupyter_output><empty_output><jupyter_text>La bibliothèque `random` nous sera utile pour cette séance. Elle propose notamment la fonction `choice`:<jupyter_code>import random

random.choice(letters)<jupyter_output><empty_output><jupyter_text>On peut également tirer plusieurs lettres (différentes) avec la fonction `sample`:<jupyter_code>random.sample(letters, 3)<jupyter_output><empty_output><jupyter_text>Notons également les deux fonctions suivantes pour transformer une chaîne de caractère en liste, et inversement:<jupyter_code>list("toto")
"".join([random.choice(letters) for _ in range(12)])<jupyter_output><empty_output><jupyter_text>Estimons le temps d'évaluation de la fonction `score_hello`:<jupyter_code>%%timeit
score_hello("Hello,World~")<jupyter_output>The slowest run took 6.60 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 2.19 µs per loop<jupyter_text>**Question : ** Estimer le temps d'évaluation au pire des cas (bruteforce) de tous les messages à 12 (puis à 32) caractères possibles.<jupyter_code>1.7e-6 * len(letters)**12
# en nombre d'années (âge de l'univers: 1.38e10)
"12 letters: {:.3g} yr; 32 letters: {:.3g} yr".format(
    1.7e-6 * len(letters)**12 / 365 / 24 / 60 / 60,
    1.7e-6 * len(letters)**32 / 365 / 24 / 60 / 60)<jupyter_output><empty_output><jupyter_text>Algorithmes**Théorie !**Voir les slides...**En pratique...**Toute la difficulté dans l'utilisation des algorithmes génétiques revient à correctement choisir un relativement grand nombre de paramètres: - comment choisir une taille de la population de départ ; - comment initialiser la population de départ ; - comment procéder aux croisements :     - comment choisir deux éléments à croiser (*la sélection*);     - comment croiser les éléments ; - comment procéder aux mutations :     - quel taux de mutation choisir ;     - comment muter un élément ; - comment arrêter la recherche :     - on peut fixer un nombre d'itérations maximal ;     - comment s'assurer qu'on conserve toujours la meilleure instance (*l'élitisme*) ; - comment optimiser la convergence :     - la distribution (détails en annexe pour les personnes motivées/intéressées/en avance).     **Objectifs de la séance :** La suite de l'exercice consiste à coder des algorithmes génétiques en utilisant votre inspiration pour essayer différents opérateurs de sélection, de croisement et de mutation.Quelques remarques : 1. **Nous sommes là pour vous guider**, pour vous suggérer des pistes d'amélioration, mais aussi pour vous laisser faire vos erreurs/comprendre par vous-même pourquoi une méthode n'est pas forcément pertinente; 1. En paramétrant des méthodes stochastiques, on traverse en général une longue phase de « ça ne fonctionne pas » avant d'arriver aux bons paramètres qui permettent de résoudre le problème de manière efficace à tous les coups; 1. Essayez de **garder une interface générique** pour vos fonctions afin de pouvoir facilement remplacer les opérateurs que vous testerez. **C'est à vous !**<jupyter_code># Selection
# Une seule méthode suffit ; le plus simple à expliquer est `tournament`.

import bisect
import itertools

def tournament(samples, elite_size):
    for _ in samples[elite_size:]:
        yield max(random.sample(samples, 2))
                
def roulette(samples, elite_size):
    cumul_scores = list(
        itertools.accumulate(score for score, _ in samples))
    total = cumul_scores[-1]
    for _ in samples[elite_size:]:
        yield samples[bisect.bisect(cumul_scores, random.uniform(0, total))]
# Mask

# Il faudrait présenter `two_point_crossover` (le classique) mais pour nous,
# c'est finalement `uniform_point_crossover` qui fonctionne le mieux

import itertools

def one_point_crossover(length):
    point = random.randint(0, length)
    yield from itertools.repeat(True, point)
    yield from itertools.repeat(False, length - point)

def two_point_crossover(length):
    point1, point2 = sorted(random.randint(0, length) for _ in range(2))
    yield from itertools.repeat(True, point1)
    yield from itertools.repeat(False, point2 - point1)
    yield from itertools.repeat(True, length - point2)
    
def uniform_point_crossover(length):
    return (random.choice((False, True)) for i in range(length))

# Combine 
# Une seule solution a priori, c'est `mask` qui fait tout le boulot)

def combine(c1, c2, mask):
    for i1, i2, m in zip(c1[1], c2[1], mask):
        if m: yield i1, i2
        else: yield i2, i1
# Mutate 
# Attention à mettre la proba de 5% sur une lettre et pas sur un mot pour avoir assez d'entropie

def mutate(x):
    for i, _ in enumerate(x):
        if random.random() < .05:
            i = random.randint(0, 11)
            x[i] = random.choice(letters)
    return "".join(x)
# New generation (unique solution)

def pairwise(iterable):
    """Trick to get [(a, b), (c, d), ...] from [a, b, c, d, ...]"""
    x = iter(iterable)
    return zip(x, x)

def new_generation(samples, length, mask, selection, elite_size):
    for x, y in pairwise(selection(samples, elite_size)):
        for t in zip(*combine(x, y, mask(length))):
            yield mutate(list(t))
def run(score, length,
        population=150,
        elite_size=2,
        mask=uniform_point_crossover,
        selection=tournament,
        iterations=200):
    
    # Initial population
    population = ["".join(random.choice(letters) for _ in range(length)) for i in range(population)]

    for i in range(iterations):
        # Evaluate a population
        scored_population = sorted(((score(i), i) for i in population), reverse=True)
        max_, best = scored_population[0]
        
        # Start a new generation with the elite
        population = [x[1] for x in scored_population[:elite_size]]

        if max_ == length:
            print()
            print("Found '{}' in {} iterations.".format(best, i))
            break
        if i % 5 == 0:
            print("{} → {}".format(best, max_))
        
        # Then add the crossover/mutation
        population += list(new_generation(scored_population, length, mask, selection, elite_size))

run(score_hello, 12)<jupyter_output>V(bl+>nOA$dc → 2
[XMloJchNld` → 4
}eNloJgoNld! → 7
~emloJwo>ld! → 8
Hellorwoyld! → 10
Hellorworld! → 11
Hello~world! → 11
Hello~world! → 11
Hello~world! → 11

Found 'Hello world!' in 45 iterations.<jupyter_text>**Résolution :** Essayons maintenant avec la fonction reçue par notre ami !Il faudra sans doute rejouer avec différents paramètres de l'algorithme pour trouver une solution...Dans le pire des cas, il faut garder à l'esprit la philosophie des méthodes stochastiques, à savoir « Mieux vaut une solution pas trop mauvaise que pas de solution ».<jupyter_code># Il faut vraiment booster la population pour trouver la solution!
# Sinon, il faudra faire le malin avec la méthode en annexe

run(score, 32, population=700)<jupyter_output>-VV(^MvuY;@oN<rv(][yoii'voX_DI}Q → 4
vTaQb{hGrSFwfQPCytEsDOJnXHP'"IIy → 6
hVaVz>oweS*]w!l (:eR?OB'TLXANIz! → 12
EjabA}Xgr tSwe|<jnd D}J'TzPANIC! → 19
naab yZbr towel;(ne DON'T bSNZC! → 22
O)ab!bourc?owel and DON'T PANIC! → 26
Gzab y&ur to^el and DON'T PANIC! → 29
GrIb yourytowel and DON'T PANIC! → 30
Geab your towel and DON'T PANIC! → 31
Mrab your towel and DON'T PANIC! → 31
Mrab your towel and DON'T PANIC! → 31

Found 'Grab your towel and DON'T PANIC!' in 52 iterations.<jupyter_text>Annexe : calcul distribué, fonctionnement par îlots.Une manière de distribuer les calculs quand on est : - un peu limite en ressource ; - coincé dans des minima locaux ; consiste à lancer plusieurs exécutions du même algorithme en parallèle. Cette méthode permet également d'**avoir un comportement plus stable d'une exécution à l'autre**.Chaque algorithme va alors converger vers différents minima locaux. Le principe des îlots consiste alors à faire voyager les meilleurs éléments de chaque îlot vers les îlots voisins afin qu'ils se croisent avec d'autres populations. Il faut alors trouver un rythme de *voyage* qui permette à chaque îlot de développer des spécificités tout en brassant suffisamment souvent pour aider à la convergence.Nous vous proposons alors le code suivant à base de threads (module `concurrent.futures`) et avec des queues (thread-safe!) pour communiquer. Les particularités du langage Python (rechercher "Global Interpreter Lock" (GIL) pour plus de détails...) ne permettent pas de procéder à un vrai multithreading donc la méthode serait à vrai dire plus efficace dans un autre langage de programmation.<jupyter_code>def run_islands(idx, length=32,
                population=400,
                elite_size=2,
                mask=uniform_point_crossover,
                selection=tournament,
                iterations=200):

    # Initial population
    population = ["".join(random.choice(letters) for _ in range(length)) for i in range(population)]

    for i in range(iterations):
        # Evaluation a population
        scored_population = sorted(((score(i), i) for i in population), reverse=True)
        max_, best = scored_population[0]

        # Start a new generation with the elite
        population = [x[1] for x in scored_population[:elite_size]]

        if max_ == length:
            return (best, i)
        if i % 5 == 0:
            # astuce du \n pour éviter deux threads qui écrivent sur la même ligne
            print("Island {} : {} → {}\n".format(idx, best, max_), end="", flush=True)
            # Pass to next island
            queues[(idx + 1) % n_islands].put(population)
            try:
                # Get from previous island
                population += queues[idx].get(block=True, timeout=5)
                queues[idx].task_done()
            except queue.Empty:
                return (None, i)
            
        # Then add the crossover/mutation
        population += list(new_generation(scored_population, length, mask, selection, 2*elite_size))
            
    return (None, i)
from concurrent import futures
import queue

n_islands = 3
# Attention à bien recréer des queues de communications vides !
queues = [queue.Queue() for _ in range(n_islands)]

executor = futures.ThreadPoolExecutor(max_workers = n_islands)
results = executor.map(run_islands, range(n_islands))

best = None
total_it = 0
for i, r in enumerate(results):
    best_i, it = r
    if best_i is not None:
        best = best_i
        print("Found '{}' in {} iterations on island {}".format(best_i, it, i))
    total_it += it<jupyter_output>Island 0 : G?=^P!AY]%P<a"p}rGd xzzC&VEVvuC_ → 4
Island 1 : Z{lqI*K(^ E+Le;WcMH\ iNt$Pia"T'~ → 3
Island 2 : G*FbM@VyfVtf{~UMq$goM~im,**y}[>$ → 3
Island 0 : z?=Xcyoon(>kH^l:SL",NOXG& ,}md|! → 6
Island 1 : _SMroFAgrha+Z&V affu:[<og qAQI~! → 7
Island 2 : ~B+x WoSHfj\G<Hsks' DG`Fd-d#S)/! → 5
Island 1 : `Sys-xdr| /(LIu andi:O~*g )ANIC! → 12
Island 0 : |-abz*o+ZJvcweR|anK DO)VW uAO:(~ → 12
Island 2 : z"UG\yT]n=&Fwe` ankCC_ZF[ P#NIC! → 12
Island 2 : UwabogaSa@(wwel and DzN'T dA,IS! → 18
Island 1 : w[wb iomr>t[Hew %ndiD[N'g PAoIC! → 18
Island 0 : i+as#-luG Uewel)and}GON'T+PANI*! → 18
Island 2 : xL[b y,"zf%~uel and DON'T PANIC! → 22
Island 1 : urgc aou~ trwel andCDONtT cANIC! → 23
Island 0 : jr:? youM[>Bwel and D[NUT PANIC! → 23
Island 2 : !rwb |Sur : wel and DON'T PANIC! → 26
Island 1 : yra-QS?u[ towel and DON'T PANIC! → 26
Island 0 : GrIbXysEL towel and DON'T PANIC! → 27
Island 2 : arub y,ur t_wel and DON'T PANIC! → 28
Island 1 : |dcb }ou= towel and DON'T PANIC! → 27
Island 0 : Grab y_uK tEwel[...]
{'fraction_non_alphanumeric': 0.10071117228722185, 'fraction_numerical': 0.017435191557696718, 'mean_word_length': 3.942554799697657, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 56, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '13', 'dir': 'jupyter-structured-clean-dedup', 'id': '500836', 'license': 'MIT', 'n_tokens_mistral': 4729, 'n_tokens_neox': 4436, 'n_words': 1503, 'path': 'notebooks/solutions/02-genetic_algorithms.ipynb', 'repo_name': 'poitou/metaheuristics', 'size': '13077'}