samedi 20 octobre 2007

Les algorithmes génétiques contre l'idéologie nazie

Les algorithmes génétiques sont une manière de programmer s'inspirant des grands concepts de l'évolution darwinienne et servant à résoudre des problèmes d'explosion combinatoire. Ceux-ci ne proposent pas la solution exacte mais une solution acceptable.


Prenons l'exemple du problème du voyageur de commerce : Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ? Il peut être résolu par les algorithmes génétiques.


On génère aléatoirement une population d'individus, chaque individu représentant une solution potentielle au problème. Pour 100 villes, un individu X possède un code génétique sous la forme d'une suite de 100 villes distinctes.


On évalue ensuite le facteur d'adaptation de chaque individu, c'est à dire, si son code génétique représente un début de bonne solution au problème. Dans notre exemple, on calcule, pour chaque individu, la longueur du chemin proposé dans son code génétique pour, partir d'une ville, parcourir toutes les autres et revenir au point de départ.


Ensuite on sélectionne les meilleurs individus, ceux dont le code génétique propose un chemin plus court que les autres. On réalise ensuite le processus de reproduction entre les individus sélectionnés. Pour deux individus, on découpe leur code génétique en segments que l'on inter-change pour créer deux nouveaux individus.


On n'oublie pas, à cette étape, de faire jouer un processus très important de l'évolution, la mutation. On modifie aléatoirement le code génétique de certain individu en intervertissant des villes. Ceci est très important pour ne pas tomber dans des minima locaux. En effet, imaginons ce qui se produirait sans mutation. Si les solutions de départ, générées aléatoirement, n'étaient pas assez variées, alors l'algorithme convergerait rapidement vers une solution peut-être très éloignée de la solution exacte. L'algorithme converge lorsque 95% des individus possèdent le même code génétique. La mutation aléatoire peut faire sortir un nouveau code génétique représentant une solution meilleure que toutes celles ayant été trouvées avant. Et c'est ici que réside toute la beauté du processus d'évolution darwinien ainsi que le lien avec l'idéologie nazie.


Le processus de mutation génère des individus « différents » comparés aux individus d'une population étant en voie de converger. Le concept de race aryenne des nazis impliquent de se débarrasser de tous ces gens « différents ». Si cette idée avait été mise en application pour une longue durée, cette soi-disant race aryenne aurait tout simplement déclinée, incapable de s'adapter à un environnement changeant faute de renouveau dans son code génétique. Ceci revient à dire que le nature aime la diversité et que les différences existent pour la survie de notre espèce. L'évolution comprend deux mécanismes différents mais complémentaires. La reproduction, qui est un processus guidé et lent s'inscrivant dans le très long terme et la mutation, qui permet d'introduire une dynamique à court terme favorisant la survie de l'espèce lors de changements majeurs et rapides de l'environnement.


On peut dire bien d'autres choses sur les algorithmes génétiques, ceci est un article de vulgarisation. Pour en connaître plus sur le sujet, je vous conseille le très bon livre « Vie artificielle » de Jean-philippe Rennard.

vendredi 12 octobre 2007

[Australie, reggae] The Cat Empire - Rhyme and reason


"The Cat Empire est un groupe de rock australien de Melbourne formé en 1999. Constitué à l'origine de trois membres, puis de six, ce groupe mélange les influences jazz, funk, Latin, Hip Hop, rock, Ska et de musique tzigane."