Que faire face à un problème NP-complet ? On peut tester la totalité des résultats possibles : c'est la méthode de la force brute, qui peut prendre des siècles (ou des millénaires) de calcul... On peut aussi explorer ce gigantesque espace des résultats à l'aide d'un algorithme d'optimisation numérique. Il y en a pour tous les goûts, du recuit simulé à la cross-entropy en passant par la GRASP ( ben oui : la Greedy randomized adaptive search procedure ! )
Et le free lunch alors ? J'y viens. Un théorème démontré par David H. Wolpert et William G. Macready en 1995 prouve qu'aucun algorithme d'optimisation numérique n'est plus efficace qu'un autre en général. Celui qui sera le meilleur sur une classe particulière de problèmes sera le moins bon sur une autre, etc... Donc, pas de recette miracle. No free lunch ! D'où le nom du théorème. La vraie conclusion de tout ça, note Tom Roud, c'est que les numériciens et les spécialistes d'optimisation numérique ne seront jamais au chômage : chaque problème nécessite une étude approfondie et un algorithme spécifique pour être résolu. (3)
Là où l'histoire devient amusante, c'est que certains néocréationnistes ( encore eux ! ) ont prétendu se servir du théorème en question pour attaquer le mécanisme de l'évolution... (4) J'avoue ne pas avoir approfondi, mais le contresens semble flagrant : d'abord parce que la sélection naturelle a tout son temps ( 4 milliards d'années et quelques d'années ! ) et peut donc très bien se passer d'optimisation. Et puis parce que, comme l'explique Adam Ierymenko, personne ne prétend que la vie sur Terre soit parfaitement optimisée...
Certaines choses ont évolué d'une façon qui nous semble inefficiente. Nous pouvons imaginer un meilleur design. En effet, nos cerveaux sont, tout comme le processus d'évolution, des algorithmes. Mais ce sont des algorithmes différents et pour cette raison, conformément au no free lunch theorem, il y a des problèmes que nos cerveaux vont résoudre mieux que ne l'a fait l'évolution... Et réciproquement. (5)(1) Wikipedia : Complexity classes P and NP
(2) Wikipedia : Problème_du_voyageur_de_commerce
(3) Tom Roud : Le "No Free Lunch Theorem"
(4) William A. Dembski : No Free Lunch: Why Specified Complexity Cannot Be Purchased without Intelligence
(5) GreyThumb.Blog ; Incompetent design and the no free lunch theorem
7 commentaires:
Salut !
Le lien vers le site d'Intelligent Design est incroyable. Je soupçonne de plus en plus Dembski de mauvaise foi éhontée (normalement, il est loin d'être un imbécile scientifiquement, il a fait sa thèse avec Kadanoff et le NFLT est, je pense, assez facile à comprendre pour quelqu'un qui doit bien savoir ce que c'est qu'un verre de spin ou un recuit simulé)...
De quel site parles tu ? GreyThumb.Blog ? Ca a l'air en effet plein de choses intéressantes. Grâce à un lien trouvé chez eux, je viens d'installer un économiseur d'écran très chouette :
The breve Simulation Environment
Sinon, as-tu vu cette petite video dont la profondeur conceptuelle m'a laissé un peu sur le cul ?
IDsong
Pour Dembski, franchement je ne savais pas qui c'était hier. Mais espérer vendre l'Intelligent Design avec ce NFLT, franchement... Il est peut-être très très intelligent ET de très très mauvaise foi ?
Salut!
Le problème du voyageur de commerce n'avait pas été résolu une fois avec des brins d'ADN qui s'hybridaient (il me semble que c'est ce problème la, et en tout cas la description était particulièrement belle)?
J'essaierai de retrouver la source ce week-end
Je confirme ce qu'écrit Timothée, on doit cette résolution du problème du voyageur de commerce à Adelman (le Adelman du cryptage RSA !!) en novembre 1994, un des premiers exemples d'ordinateur à ADN...
Je trouve ça fascinant ces histoires d'ordinateurs moléculaires.
Est-ce que qqun a entendu parler de Computationnal Life Science ? On en cause ici. Y a même une conférence internationale sur le sujet : 2nd International Symposium on
Computational Life Science
TANSTAAFL There Ain't No Such Thing As A Free Lunch
Que je traduirais librement par :
INYAPJDBG Il n’y a jamais de bouffe gratuite
Je ne connaissais pas ce théorème. Je me souviens d’avoir lu jadis pas mal de choses sur les problèmes P et NP. Depuis je lis plus facilement Psycholgie Magazine que Pour la Science. Encore que le visite de ce site me donne envie de relire un "Sciences et Vie" ou deux…
Je n’aime pas le nom du théorème, ce qu’il me rappelle est plutôt quelque chose de désagréable lié à des gens que je n’aiment guère : à savoir les économistes libéraux… Chez eux c’est un postulat (donc ils n’ont pas à le démontrer) qui pose que l’acte gratuit n’existe pas, ce qui dans leur monde est tout à fait vrai… enfin, en supposant que leur monde soit aussi idéal qu’ils le prétendent. En effet si on y regarde de plus près il y a pas mal de gens qui bouffent gratos ou qui mangent la laine sur le dos des moutons.
Bon, je sais, je suis hors sujet…
Sur le sujet comment peut-on dire à la fois que le problème du représentant de commerce est un problème NP et qu’il a été résolu ? « Je confirme ce qu'écrit Timothée, on doit cette résolution du problème du voyageur de commerce à Adelman (le Adelman du cryptage RSA !!) en novembre 1994, un des premiers exemples d'ordinateur à ADN... » Je suis allé sur le site en question mais c’est trop compliqué.
Est-il possible de l’expliquer simplement ici ? Sinon tant pis, je suis prêt à mourir idiot.
C'est pas du tout hors sujet... Le NFLT tire son nom du TANSTAAFL des économistes libéraux, qui sortait lui-même d'un bouquin de SF (cf. Wikipedia) Mais le théorème ne partage pas les orientations idéologiques des promoteurs du TANSTAAFL !
Quant au problème du voyageur de commerce, il est NP parce que la longueur des calculs nécessaires à le résoudre augmente exponentiellement avec le nombre de villes prises en compte... Si on prend 3 villes, je peux m'en sortir tout seul. Si il y en a 300... C'est moins simple. L'ordinateur à ADN de Timothée a résolu UN problème de voyageur de commerce, pas LE problème dans l'absolu (c'est pas un théorème)...
Enregistrer un commentaire