Des algorithmes… génétiques ?

Certains problèmes pourtant faciles à énoncer se révèlent parfois effroyablement complexes à résoudre, au point de nécessiter des siècles de temps de calcul, même pour des ordinateurs extrêmement performants !

 

Nous partirons d’un casse-tête classique qui consiste à placer 8 dames sur un échiquier de telle sorte qu’elles ne soient pas en conflit. Nous montrerons ensuite que si on généralise ce problème sur de plus grands échiquiers, le nombre de configurations à tester dépasse très vite le nombre d’atomes dans l’univers. C’est en s’inspirant de la théorie de l’évolution de Darwin que des informaticiens ont développé des algorithmes d’un genre nouveau, qui permettent de trouver des solutions à une vitesse prodigieuse : les algorithmes génétiques. Ces algorithmes ont été notamment utilisés par la NASA pour concevoir la forme de certains engins spatiaux. En ce qui nous concerne, nous les utiliserons pour résoudre le problème des dames.