Faire tourner un algorithme évolutionnaire

Exercice supplémentaire · niveau 2 · enseignement scientifique (terminale), chapitre 8 — L'évolution comme grille de lecture du monde

Énoncé

On cherche l'entier $x$ compris entre $0$ et $14$ qui maximise $f (x) = 50 - (x - 7)^{2}$ . On applique l'algorithme suivant : partir de six candidats ; garder les trois meilleurs ; chacun produit deux « enfants » valant $x - 1$ et $x + 1$ . Population initiale : $1$ , $3$ , $5$ , $10$ , $12$ , $14$ . 1. Calculer $f$ pour les six candidats et désigner les trois meilleurs. 2. Écrire la génération $1$ et calculer les $f$ . 3. Écrire la génération $2$ et conclure. 4. À aucun moment l'algorithme n'utilise l'expression de $f$ autrement que pour l'évaluer. Pourquoi est-ce intéressant ? 5. Quelle différence essentielle sépare cet algorithme de l'évolution biologique ?

Corrigé

1. $f (1) = 50 - 36 = 14$ ; $f (3) = 50 - 16 = 34$ ; $f (5) = 50 - 4 = 46$ ; $f (10) = 50 - 9 = 41$ ; $f (12) = 50 - 25 = 25$ ; $f (14) = 50 - 49 = 1$ . Les trois meilleurs sont $x = 5$ ( $46$ ), $x = 10$ ( $41$ ) et $x = 3$ ( $34$ ).

2. Enfants : $5 \to 4$ et $6$ ; $10 \to 9$ et $11$ ; $3 \to 2$ et $4$ . Génération $1$ : ${4, 6, 9, 11, 2, 4}$ , avec $f (4) = 41$ , $f (6) = 49$ , $f (9) = 46$ , $f (11) = 34$ , $f (2) = 25$ . Les trois meilleurs : $x = 6$ ( $49$ ), $x = 9$ ( $46$ ), $x = 4$ ( $41$ ).

3. Enfants : $6 \to 5$ et $7$ ; $9 \to 8$ et $10$ ; $4 \to 3$ et $5$ . Génération $2$ : ${5, 7, 8, 10, 3, 5}$ , avec $f (7) = 50$ . L'optimum est atteint en deux générations, sans qu'on ait jamais résolu l'équation.

4. Parce que beaucoup de problèmes réels ne se résolvent pas algébriquement : on sait simuler la performance d'une antenne, d'une aile ou d'un emploi du temps, mais on ne sait pas écrire l'équation dont la solution serait le meilleur dessin. L'algorithme évolutionnaire ne demande qu'une chose : savoir comparer deux solutions. C'est très peu, et cela suffit.

5. La fonction objectif. Ici, un humain a écrit $f$ : le système sait ce qu'il cherche. La sélection naturelle n'a rien de tel : aucun critère n'est fixé à l'avance, et ce qui est « bon » dépend d'un environnement qui change lui-même. L'algorithme est donc une imitation du mécanisme, non de l'absence de but qui en fait toute la particularité.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.