Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée

Génome et fitness, sélection par tournoi, croisement à un point, mutation et élitisme, théorème des schémas et convergence prématurée — sur un problème du sac à dos à l’optimum connu, de la tente à FunSearch et AlphaEvolve.

14 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 27 sur 52

Programme complet de la série 52 sur 83 sujets publiés

Ce que vous retiendrez

Comment coder une solution sous forme de génome et comment la sélection, le croisement et la mutation améliorent toute une population.
Pourquoi, sans mutation, l’évolution converge prématurément, et à quoi sert le croisement.
Où l’on utilise aujourd’hui les algorithmes génétiques — même avec un modèle de langage dans le rôle de la mutation.

Utile à connaître avant : Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques

La nature n’a pas d’ingénieur, et pourtant elle a produit l’œil, l’aile et le cerveau. Trois choses lui ont suffi : les individus diffèrent les uns des autres, ils transmettent leurs caractères à leurs descendants, et les plus aptes ont plus de descendants. Dans les années 1970, John Holland, de l’université du Michigan, a montré que ces trois mêmes choses fonctionnent aussi dans un ordinateur — comme méthode générale pour chercher de bonnes solutions à des problèmes que l’on ne sait pas résoudre astucieusement. Un algorithme génétique n’a besoin ni de gradient ni de formule ; il lui suffit de savoir dire laquelle de deux solutions est la meilleure.

Cette partie fait suite à la partie Recherche locale et recuit simulé. Le recuit améliorait une seule solution ; un algorithme génétique en améliore toute une population à la fois.

1. Le problème : un sac à dos pour la randonnée

Vous vous préparez pour une randonnée de plusieurs jours. Chez vous, vous avez 24 objets — une tente, un sac de couchage, un réchaud, un appareil photo, un livre… — et chacun pèse quelque chose et sert à quelque chose. Le sac ne doit pas peser plus de 10 kg. Que prendre pour que l’utilité soit la plus grande possible ?

Définition — le problème du sac à dos (0/1)

On se donne n objets de masses w_i > 0 et d’utilités u_i > 0, ainsi qu’une capacité W. On cherche x ∈ {0, 1}ⁿ qui maximise ∑_i u_ix_i sous la contrainte ∑_i w_ix_i ≤ W.

En termes simples

Chaque objet est une question « je le prends ou pas » — un un ou un zéro. Il y a 2²⁴ possibilités, soit 16 777 216 sacs. La stratégie gloutonne « d’abord le plus utile par kilo » fonctionne souvent, mais ne garantit pas l’optimum : un objet lourd peut en chasser trois légers qui, ensemble, valaient davantage.

Pour des masses entières, l’optimum peut se calculer exactement par programmation dynamique — avec les 24 objets et une capacité de 1 000 décagrammes (1 dag = 10 g), cela fait 24 000 étapes. Le meilleur sac a 727 points d’utilité et pèse 9,9 kg ; restent à la maison la nourriture en plus, l’appareil photo, le livre, les sandales et la crème solaire. Grâce à cela, nous verrons exactement à quel point l’évolution s’en approche. Un algorithme génétique est toutefois surtout utile là où une telle méthode exacte n’existe pas.

La programmation dynamique remplit un tableau T[i][c] — la meilleure utilité que l’on peut atteindre avec les seuls i premiers objets quand ils ne doivent pas peser plus de c. Chaque case se calcule à partir de la ligne du dessus :

T[i][c] = max( T[i − 1][c] , T[i − 1][c − w_i] + u_i )

T[i][c]: la meilleure utilité des i premiers objets pour une capacité c ; la case T[n][W] est la réponse au problème entier
T[i − 1][c]: l’option « je ne prends pas le i-ième objet » — le mieux est alors ce qu’on pouvait composer avec les objets précédents pour la même capacité
T[i − 1][c − w_i]: l’option « je le prends » — l’objet occupe w_i, il ne reste donc que c − w_i pour le reste ; la meilleure utilisation de ce reste est déjà dans le tableau (seulement pour c ≥ w_i)
u_i: l’utilité de l’objet que nous avons ajouté dans cette seconde option

Le sac optimal contient le i-ième objet ou ne le contient pas — et dans les deux cas, le reste est un sac optimal d’un problème plus petit. On commence par la ligne T[0][c] = 0.

Exemple — le tableau pour quatre objets et une capacité de 50 dag

Une lampe frontale (10 dag, 25 points), un couteau (10 dag, 18), un réchaud (40 dag, 30) et un tapis de sol (50 dag, 45). Toutes les masses sont des multiples de dix, des colonnes de 10 en 10 dag suffisent donc :

objets	10	20	30	40	50
aucun	0	0	0	0	0
+ frontale	25	25	25	25	25
+ couteau	25	43	43	43	43
+ réchaud	25	43	43	43	55
+ tapis de sol	25	43	43	43	55

Couteau, c = 20 : max(T[1][20], T[1][10] + 18) = max(25, 25 + 18) = 43

Réchaud, c = 40 : max(T[2][40], T[2][0] + 30) = max(43, 0 + 30) = 43 — le réchaud ne vaut pas la peine

Réchaud, c = 50 : max(T[2][50], T[2][10] + 30) = max(43, 25 + 30) = 55 — le réchaud et la frontale

Tapis de sol, c = 50 : max(55, T[3][0] + 45) = max(55, 45) = 55

La stratégie gloutonne prendrait les objets par utilité par décagramme : la frontale (2,5 points/dag), le couteau (1,8), puis ni le tapis de sol (0,9) ni le réchaud (0,75) ne tiendraient dans les 30 dag restants — seulement 43 points. Dans le grand problème à 24 objets, la stratégie gloutonne s’arrête à 702 points : elle remplit le sac de petites choses et il ne reste plus de place pour la tente (220 dag).

def batoh(w, u, W):                       # w, u: masses et utilités, W: capacité
    T = [0] * (W + 1)                     # la ligne « aucun objet »
    for i in range(len(w)):
        for c in range(W, w[i] - 1, -1):  # à rebours : T[c − w[i]] est encore de la ligne i − 1
            T[c] = max(T[c], T[c - w[i]] + u[i])
    return T[W]                           # n · W étapes : 24 · 1000 = 24 000

2. Individu, génome et fitness

Définition — génome, population, fitness

Un génome (chromosome) est une solution codée — ici une chaîne x ∈ {0, 1}²⁴, un bit (gène) par objet. Une population est un multiensemble P de génomes de taille fixe μ.

La fitness (adaptation) est une fonction F : {0, 1}ⁿ → ℝ que l’algorithme maximise. Pour le sac

F(x) = ∑ u_ix_i si le sac tient dans la limite, sinon ∑ u_ix_i − 3 · (∑ w_ix_i − W).

En termes simples

Un individu est un sac précis, écrit comme une suite de uns et de zéros. La fitness dit à quel point il est bon. Nous n’interdisons pas un sac surchargé, nous le pénalisons seulement — trois points de moins pour chaque décagramme en trop. L’algorithme découvre ainsi peu à peu la limite de capacité, et même un sac surchargé peut porter des gènes qui serviront plus tard.

F(x) = ∑ u_ix_i − 3 · max(0, ∑ w_ix_i − W)

F(x): la fitness du sac x — le seul nombre d’après lequel la sélection compare les individus
∑ u_ix_i: l’utilité des objets emballés (x_i = 1 compte l’objet, 0 l’omet) — ce que nous voulons vraiment maximiser
3: le prix d’un décagramme au-delà de la limite — il est supérieur au meilleur rapport utilité/masse (la frontale, 2,5 points/dag), si bien qu’ajouter quoi que ce soit à un sac déjà surchargé fait toujours baisser la fitness
max(0, ∑ w_ix_i − W): la surcharge en décagrammes ; le max avec zéro garantit qu’un sac qui respecte la limite n’est pas pénalisé et qu’un sac plus léger n’est pas avantagé

Les deux cas de la définition en une seule formule : la pénalité est nulle tant que le sac respecte la limite, puis elle croît avec chaque décagramme en trop.

Exemple — la fitness de deux sacs

Optimum : utilité 727, masse 990 dag ≤ 1 000 ⇒ F = 727 − 3 · 0 = 727

Optimum + appareil photo (80 dag, 20 points) : utilité 747, masse 1 070 dag ⇒ F = 747 − 3 · 70 = 537

L’appareil photo ajoute 20 points, mais la surcharge de 70 dag coûte 210 — la sélection écarte sûrement un tel sac.

3. Sélection

Définition — sélection par tournoi et par roulette

Sélection par tournoi de taille k : tire au hasard k individus de la population et renvoie celui dont la fitness est la plus élevée.

Sélection par roulette : choisis l’individu x avec la probabilité F(x) / ∑_{y ∈ P} F(y) (exige une fitness positive).

La pression de sélection mesure à quel point la sélection favorise les individus plus aptes ; pour un tournoi, elle croît avec k.

En termes simples

Un tournoi : vous tirez trois sacs au hasard, et le meilleur d’entre eux devient parent. Les meilleurs sacs ont ainsi plus d’enfants, mais même un sac moyen a sa chance s’il tombe sur des plus faibles. Si seuls les tout meilleurs se reproduisaient, la population dégénérerait vite en copies d’un seul individu — et avec elle disparaîtrait la diversité dont vit l’évolution.

La force d’un tournoi se calcule exactement. Notre programme tire k individus avec remise (le même individu peut entrer deux fois dans le tournoi). Classons la population du meilleur (i = 1) au pire (i = μ) :

P(le i-ième gagne) = ( (μ − i + 1)^k − (μ − i)^k ) / μ^k

P(le i-ième gagne): la probabilité que ce soit précisément le i-ième meilleur individu qui devienne parent
(μ − i + 1)^k: le nombre de tournois où personne n’est meilleur que le i-ième — les k tirages tombent sur lui ou sur des moins bons
(μ − i)^k: on en retire les tournois où le i-ième n’est pas du tout présent — ceux-là, un moins bon les gagnerait ; la différence, ce sont les tournois où le i-ième est le meilleur présent
μ^k: le nombre de tous les tournois possibles (k tirages, chacun parmi μ individus) — en divisant, on obtient une probabilité

La probabilité ne dépend que du rang, pas de l’écart de qualité — c’est pourquoi le tournoi fonctionne même avec une fitness négative, et la roulette non.

Exemple — un tournoi à trois parmi 40 sacs

μ^k = 40³ = 64 000. À chaque génération, on sélectionne 38 parents (deux places sont prises par les individus d’élite) :

le meilleur : (40³ − 39³) / 64 000 = (64 000 − 59 319) / 64 000 ≈ 7,31 %, en moyenne 38 · 0,0731 ≈ 2,78 sélections

le 20^e meilleur : (21³ − 20³) / 64 000 = (9 261 − 8 000) / 64 000 ≈ 1,97 %, en moyenne ≈ 0,75 sélection

le pire : (1³ − 0³) / 64 000 ≈ 0,0016 %, en moyenne ≈ 0,0006 sélection

Un individu moyen reçoit 38/40 = 0,95 sélection, le meilleur presque trois fois plus. En général, dans une grande population, le meilleur reçoit environ k fois plus que la moyenne — c’est pourquoi la pression de sélection croît avec k.

4. Croisement et mutation

Définition — croisement à un point

Pour des parents a, b ∈ {0, 1}ⁿ, choisis au hasard un point c ∈ {1, …, n − 1}. Les descendants sont

(a₁, …, a_c, b_c+1, …, b_n) et (b₁, …, b_c, a_c+1, …, a_n).

Le croisement a lieu avec la probabilité p_c ; sinon, les descendants sont des copies des parents. D’autres variantes sont le croisement à deux points et le croisement uniforme (chaque gène vient d’un parent tiré au hasard).

En termes simples

Vous coupez deux sacs au même endroit et vous échangez les fins. L’enfant reçoit le début de la liste d’un parent et la fin de l’autre. Si un parent a bien résolu le sommeil et l’autre la nourriture, l’enfant a une chance d’hériter des deux.

Définition — mutation par inversion de bits

Chaque gène du descendant est inversé (0 ↔ 1) indépendamment avec la probabilité p_m, habituellement p_m = 1/n — en moyenne un gène par individu.

En termes simples

De temps en temps, un enfant diffère de ses parents par un petit détail : il emporte un objet qu’aucun des parents n’avait, ou en retire un. La mutation est la seule source de gènes entièrement nouveaux — le croisement ne sait que réarranger ce qui est déjà dans la population.

Exemple — combien de gènes la mutation inverse

Le nombre de gènes inversés suit une loi binomiale : P(j gènes) = C(n, j) · p_m^j · (1 − p_m)^n−j. Pour n = 24 et p_m = 1/24 :

nombre attendu : n · p_m = 24 · 1/24 = 1

aucun changement : (23/24)²⁴ ≈ 0,360 (pour n grand, cela tend vers 1/e ≈ 0,368)

exactement un gène : 24 · (1/24) · (23/24)²³ ≈ 0,376

Environ un tiers des descendants reste donc inchangé, un tiers diffère d’un gène et le reste de deux ou plus.

Les deux meilleurs sacs de la population initiale, leurs descendants et une mutation

Les parents sont les deux meilleurs sacs de la population initiale (423 et 398 points), et la coupure se trouve après le douzième objet. Aucun des descendants n’est meilleur que le meilleur des parents — ils ont 403 et 418 points. Le croisement ne garantit pas d’amélioration ; il propose seulement de nouvelles combinaisons, et la sélection décide ensuite lesquelles survivent. Chez le premier descendant, la mutation a ajouté un filtre à eau (15 dag, 32 points), et il a d’un coup 435 points — plus que ses deux parents.

Exemple — recalcul du croisement de la figure

L’utilité s’additionne gène par gène ; il suffit donc d’additionner séparément l’utilité du début (objets 1–12) et de la fin (objets 13–24) :

parent 1 : 310 + 113 = 423, parent 2 : 305 + 93 = 398

descendant 1 = début du parent 1 + fin du parent 2 : 310 + 93 = 403

descendant 2 = début du parent 2 + fin du parent 1 : 305 + 113 = 418

la mutation ajoute le filtre à eau : 403 + 32 = 435

Le parent 1 est meilleur dans les deux moitiés (310 > 305 et 113 > 93) ; avec cette coupure, aucun descendant ne peut donc le dépasser — le croisement n’a rien à partir de quoi composer un meilleur ensemble. L’amélioration n’est venue que de la mutation.

5. L’algorithme complet

Algorithme — algorithme génétique

Crée une population initiale aléatoire de μ individus et évalue-les.
Copie sans changement les e meilleurs individus dans la nouvelle génération (élitisme).
Tant que la nouvelle génération n’a pas μ individus : sélectionne deux parents, croise-les avec la probabilité p_c, fais muter les descendants et ajoute-les.
Évalue la nouvelle génération et reprends à l’étape 2 jusqu’à épuisement du nombre de générations.

En termes simples

Génération après génération : les deux meilleurs survivent directement, les autres places sont occupées par les enfants de parents aptes, un peu réarrangés et un peu modifiés. L’élitisme garantit que le meilleur sac trouvé ne se perd jamais.

import random

def evoluce(zdatnost, n, velikost=40, generaci=60, p_krizeni=0.9, elita=2):
    pop = [[int(random.random() < 0.3) for _ in range(n)] for _ in range(velikost)]
    for _ in range(generaci):
        pop.sort(key=zdatnost, reverse=True)
        dalsi = [g[:] for g in pop[:elita]]            # élitisme
        while len(dalsi) < velikost:
            a, b = turnaj(pop, zdatnost), turnaj(pop, zdatnost)
            if random.random() < p_krizeni:
                bod = random.randrange(1, n)
                a, b = a[:bod] + b[bod:], b[:bod] + a[bod:]
            dalsi += [mutuj(a), mutuj(b)]
        pop = dalsi[:velikost]
    return max(pop, key=zdatnost)

def turnaj(pop, zdatnost, k=3):
    return max(random.choices(pop, k=k), key=zdatnost)   # k tirages avec remise

def mutuj(g):
    return [1 - x if random.random() < 1 / len(g) else x for x in g]

Nous mesurons le coût de l’algorithme au nombre d’évaluations de la fitness — dans les problèmes réels (simulations, mesures), c’est l’étape la plus coûteuse. On évalue la population initiale, puis chaque génération : μ + G · μ = 40 + 60 · 40 = 2 440 évaluations pour μ = 40 individus et G = 60 générations. Les individus d’élite sont réévalués alors qu’ils n’ont pas changé ; un programme plus malin mémoriserait leur fitness.

6. L’évolution du sac à dos

Lançons l’algorithme : 40 sacs, 60 générations, tournoi à trois, croisement avec la probabilité 0,9, mutation 1/24 et deux individus d’élite. La figure montre la population aux générations 0, 5, 15, 30 et 60 — chaque ligne est un sac, chaque colonne un objet, et en haut, pour comparaison, l’optimum :

Population de sacs au fil de l’évolution ; en orange les sacs surchargés

Au début, la population est variée et les sacs sont plutôt à moitié vides : chaque objet y est entré avec la probabilité 0,3, si bien qu’ils pèsent environ quatre kilos (la masse attendue est 0,3 · ∑ w_i = 0,3 · 12,75 kg ≈ 3,8 kg). Le meilleur a 423 points, la moyenne 231. Après cinq générations, 36 sacs sur 40 portent la tente, 35 la gourde, et le meilleur sac a 634 points. Vers la quinzième génération, la population bute sur la capacité — 12 sacs sont surchargés — et commence à apprendre quoi sacrifier : la nourriture en plus et les sandales ont presque disparu, mais 39 sacs portent encore l’appareil photo. L’algorithme trouve l’optimum, 727 points, pour la première fois à la génération 26 ; à la génération 30, l’appareil photo ne reste plus que dans un seul sac. La population ne se fond pourtant jamais en une solution unique — la mutation continue d’essayer de petits écarts.

Fitness au fil des générations meilleur moyenne de la population meilleur sans mutation

Pour cela, l’algorithme a évalué 2 440 sacs — pas tout à fait deux centièmes de pour cent des 16 777 216 possibilités. Une recherche aléatoire avec le même nombre d’essais n’a pas trouvé l’optimum une seule fois en cent répétitions et s’est arrêtée en moyenne à 574 points.

Exemple — pourquoi la recherche aléatoire ne trouve pas l’optimum

Un sac aléatoire prend chaque objet indépendamment avec la probabilité 0,3. L’optimum contient 19 objets et en laisse 5 de côté, donc

P(sac aléatoire = optimum) = 0,3¹⁹ · 0,7⁵ ≈ 1,16 · 10⁻¹⁰ · 0,168 ≈ 1,95 · 10⁻¹¹

nombre attendu de réussites en 2 440 essais : 2 440 · 1,95 · 10⁻¹¹ ≈ 4,8 · 10⁻⁸

Même avec un tirage uniforme (chaque objet avec la probabilité 1/2), la chance serait d’une sur 16 777 216 par essai. Un algorithme génétique ne tire pas l’optimum d’un coup — il l’assemble morceau par morceau à partir de sacs déjà bons.

7. À quoi servent le croisement et la mutation

La ligne orange du graphique est la même exécution avec la mutation désactivée. Après onze générations, elle reste bloquée à 573 points et ne bouge plus. Pourquoi ? Une comparaison de cent exécutions avec des graines différentes le montre :

Variante	A trouvé l’optimum	Utilité moyenne
Sélection + croisement + mutation	88 sur 100	726,6
Sélection + mutation (sans croisement)	70 sur 100	725,0
Sélection + croisement (sans mutation)	0 sur 100	596,8
Recherche aléatoire, autant d’essais	0 sur 100	573,5

Sans mutation, la population perd sa diversité : quand un gène n’existe chez aucun individu, le croisement ne peut pas le produire, et la sélection chasse en plus rapidement tout sauf les meilleurs. C’est ce qu’on appelle la convergence prématurée. Sans croisement, l’algorithme fonctionne — c’est au fond une population d’algorithmes de la colline avec sélection —, mais il est plus lent. Le croisement aide à assembler de bons morceaux apparus chez des individus différents.

Théorème — le théorème des schémas de Holland

Un schéma H est un motif sur {0, 1, ∗}, où ∗ signifie « n’importe quoi » ; son ordre o(H) est le nombre de positions fixées et sa longueur utile δ(H) la distance entre la première et la dernière position fixée. Pour m(H, t) individus correspondant à H à la génération t et une sélection par roulette, on a

E[m(H, t + 1)] ≥ m(H, t) · F(H) / F̄ · [1 − p_c · δ(H) / (n − 1) − o(H) · p_m],

où F(H) est la fitness moyenne des individus du schéma et F̄ la moyenne de la population.

En termes simples

Un schéma est une « brique », par exemple « je prends la tente et le sac de couchage, le reste m’est égal ». Le théorème dit que les briques courtes de fitness supérieure à la moyenne se répandent dans la population — et ce, exponentiellement vite, car à chaque génération leur nombre est à peu près multiplié par le rapport F(H) / F̄. Courtes, parce que le croisement les coupe moins souvent. Le théorème n’est qu’une borne inférieure, et la question de savoir à quel point l’algorithme fonctionne bien fait encore débat aujourd’hui.

E[m(H, t + 1)] ≥ m(H, t) · F(H) / F̄ · [1 − p_c · δ(H) / (n − 1) − o(H) · p_m]

m(H, t): combien d’individus portent la brique maintenant — la génération suivante part d’eux, c’est pourquoi on multiplie par ce nombre
F(H) / F̄: de combien les porteurs du schéma sont plus aptes que la moyenne — la roulette leur donne proportionnellement plus de descendants ; au-dessus de 1, le schéma se multiplie, en dessous de 1, il s’éteint
p_c · δ(H) / (n − 1): la probabilité que le croisement coupe le schéma : le croisement a lieu avec p_c, et le point de coupure tombe entre les positions fixées avec la probabilité δ/(n − 1) — c’est pourquoi les schémas longs posent problème
o(H) · p_m: la probabilité (majorée) que la mutation inverse l’une des o(H) positions fixées — c’est pourquoi les schémas d’ordre élevé posent problème

La sélection multiplie un schéma, le croisement et la mutation peuvent le détruire ; soustraire les deux pertes donne une borne inférieure, car un schéma coupé peut aussi réapparaître.

Exemple — un schéma court et un schéma long sur le sac à dos

Le crochet pour les réglages de notre exécution (p_c = 0,9, n = 24, p_m = 1/24). Les deux schémas sont d’ordre 2 :

« la tente et le sac de couchage » (gènes 1 et 2, δ = 1) : 1 − 0,9 · 1/23 − 2/24 ≈ 1 − 0,039 − 0,083 = 0,878

« la tente et des chaussettes de rechange » (gènes 1 et 24, δ = 23) : 1 − 0,9 · 23/23 − 2/24 ≈ 1 − 0,9 − 0,083 = 0,017

Pour le schéma court, il suffit que ses porteurs soient 14 % plus aptes que la moyenne (1/0,878 ≈ 1,14), et selon le théorème il se répand déjà. Le schéma long devrait être soixante fois plus apte — le théorème ne promet pratiquement rien à son sujet. Notre algorithme utilise un tournoi, pas une roulette ; seul le crochet s’applique donc à lui, les deux premiers facteurs se calculeraient autrement.

8. Les algorithmes génétiques en pratique

Conception de formes. L’antenne des satellites ST5 de la NASA (lancés en 2006) a été conçue par un algorithme évolutionnaire : un bout de fil étrangement tordu qui ne serait venu à l’idée d’aucun ingénieur, mais qui a rempli le cahier des charges au moins aussi bien qu’une antenne conçue à la main (et même mieux lors d’essais ultérieurs).
Emplois du temps et logistique. Emplois du temps, plannings d’équipes ou agencement d’un entrepôt — des problèmes à nombreuses contraintes où la fitness se calcule, mais où un algorithme exact tournerait une éternité.
Apprentissage automatique. L’évolution règle les hyperparamètres des modèles et, dans la neuroévolution, à laquelle le programme consacre une partie à part, même les poids et les architectures des réseaux de neurones.
Évolution avec des modèles de langage. Des systèmes comme FunSearch (2023) et AlphaEvolve (2025) de Google DeepMind entretiennent une population de programmes et utilisent comme mutation un modèle de langage qui modifie un programme. La sélection est assurée par une évaluation automatique. On a ainsi trouvé de nouvelles constructions mathématiques et des algorithmes plus rapides.

9. Résumé

Un algorithme génétique améliore toute une population de solutions : par la sélection des plus aptes, par le croisement et par la mutation.
La fitness est la seule chose qu’il a besoin de savoir sur le problème ; les contraintes violées peuvent se traiter par une pénalité.
La sélection par tournoi maintient la pression de sélection, l’élitisme empêche de perdre la meilleure solution.
Sur un sac à dos à 16,7 millions de possibilités, il a trouvé l’optimum dans 88 exécutions sur 100 après avoir évalué 2 440 sacs ; la recherche aléatoire avec le même budget, pas une seule fois.
La mutation apporte la diversité — sans elle, la population converge prématurément. Le croisement assemble de bonnes briques et accélère l’évolution.

Envie de mettre la main à la pâte ? Demandez à un agent d’IA d’écrire un algorithme génétique pour votre propre sac de randonnée — puis essayez de désactiver la mutation, d’agrandir le tournoi ou de réduire la population, et observez ce qu’il advient de la diversité.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.

Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée

1. Le problème : un sac à dos pour la randonnée

2. Individu, génome et fitness

3. Sélection

4. Croisement et mutation

5. L’algorithme complet

6. L’évolution du sac à dos

7. À quoi servent le croisement et la mutation

8. Les algorithmes génétiques en pratique

9. Résumé

Un Agent sur votre ordinateur, piloté depuis votre téléphone