Algorithmes génétiques : quand l'optimisation dépasse l'intuition
Certains problèmes offrent trop de combinaisons pour être réglés à la main et trop peu de structure pour une optimisation classique. Les algorithmes génétiques maintiennent une population de solutions, conservent les plus prometteuses et créent de nouvelles variantes. Leur puissance dépend moins de la métaphore biologique que de la qualité de l'encodage et de l'évaluation.
Décider ce qui peut évoluer
Une solution doit être représentée sous une forme que les opérateurs peuvent modifier sans produire constamment des cas invalides. Il peut s'agir d'une suite de choix, d'un ordre, de paramètres ou d'une structure. L'encodage doit préserver les contraintes fortes ou prévoir une réparation claire.
La population initiale peut combiner solutions aléatoires et bonnes pratiques connues. Cette diversité évite de commencer dans une zone trop étroite. Si tous les candidats se ressemblent, la sélection converge vite vers une solution locale sans explorer d'alternatives.
Écrire la fonction qui gouverne réellement
Le fitness exprime ce que le système cherchera, pas ce que l'équipe espère implicitement. Optimiser seulement le coût peut dégrader le délai ou la qualité. Les contraintes peuvent être intégrées par pénalités, filtres ou objectifs multiples, avec des échelles comparables.
Il faut tester la fonction sur des cas fabriqués et vérifier que les solutions manifestement meilleures obtiennent un meilleur score. Les candidats surprenants sont particulièrement utiles : ils révèlent souvent une faille dans la mesure. Corriger le fitness vaut alors davantage que modifier l'algorithme.
Contrôler exploration, coût et arrêt
La sélection exploite les bons candidats, tandis que mutation et recombinaison entretiennent l'exploration. Trop peu de variation bloque la recherche ; trop de variation détruit les acquis. Plusieurs exécutions avec des graines différentes donnent une vision plus honnête de la stabilité.
Chaque évaluation peut être chère. On fixe donc un budget, on met en cache les candidats déjà testés et on arrête si le progrès stagne. La meilleure solution doit ensuite être comparée à une base simple et testée sur des scénarios qui n'ont pas guidé l'optimisation.
Avant de lancer l'évolution
- Encoder les solutions sans multiplier les cas invalides
- Conserver une population initiale diverse
- Tester le fitness sur des exemples évidents et adverses
- Équilibrer sélection, recombinaison et mutation
- Fixer budget, cache, critère d'arrêt et base de comparaison
Un algorithme génétique est pertinent quand l'évaluation est claire et l'espace difficile à parcourir autrement. Il automatise l'exploration, mais ne remplace jamais la définition responsable de ce qui compte comme une bonne solution.