Carnet du petit Tom : Physique, biologie et évolution...

09 janvier 2007

Le "No Free Lunch Theorem"

Il existe beaucoup de théorèmes d'impossibilités dans les sciences dures. L'exemple le plus connu est le fameux "théorème d'incomplétude de Gödel", affirmant en gros que certains énoncés ne peuvent être démontrés ou réfutés (voir aussi sur ce blog ce billet). Un des théorèmes assez récents dans le domaine de l'optimisation numérique ferait le malheur de Mike Slackenerny : il s'agit du "No Free Lunch Theorem". Ce théorème concerne les algorithmes d'optimisation numérique.
On passe notre vie à essayer optimiser quelque chose, à arbitrer entre plusieurs contraintes pour choisir ce qui nous semble le plus adapté. Par exemple, toute la microéconomie est basée sur l'idée d'optimisation sous contrainte, et le but du marché libre est de trouver un optimum collectif. Dans un registre plus légers, certains essaient de minimiser le nombre de mouvements à faire pour aller aux toilettes...
Mathématiquement, on définit alors une fonction de coût associée à un problème donné. La fonction de coût peut être très simple à définir : imaginons par exemple que vous soyez un représentant devant visiter plusieurs villes, et souhaitant minimiser votre fatigue, votre fonction de coût sera alors la distance totale parcourue. Il serait très utile, étant donnée une liste de villes, de connaître alors un moyen simple de minimiser cette distance totale. C'est un problème très classique en optimisation numérique : le problème du voyageur de commerce.
La plupart des scientifiques sont de gros paresseux, et aimeraient bien disposer de recettes toutes faites pour aborder ce genre de problème d'optimisation. Il serait formidable d'avoir une méthode générale, applicable à tous les problèmes sans exception, permettant d'optimiser à coup sûr une fonction de coût, quelle que soit sa forme, quel que soit le problème. Tout serait tellement plus simple... Et bien c'est peine perdue : le "No Free Lunch Theorem" affirme qu'une telle méthode n'existe pas. Le monde est trop complexe, et il n'existe pas de recette générale permettant d'optimiser n'importe quel problème. On peut formuler ce théorème de deux autres façons différentes :
  • sur le gigantesque ensemble de tous les problèmes d'optimisation numérique, aucun algorithme n'est meilleur que les autres, i.e. le coût moyen (sur l'ensemble des problèmes) trouvé par un algorithme ne dépend pas de l'algorithme (et n'est donc pas le coût minimum a priori)
  • Le seul moyen de trouver un algorithme plus efficace qu'un autre est d'adapter l'algorithme au problème, i.e. de connaître certaines structures mathématiques sous-jacente du problème d'optimisation permettant d'améliorer la performance de celui-ci.
La conclusion de tout ça, 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. Ce genre de résultats affirme donc également que certains algorithmes très utilisés (par exemple les algorithmes génétiques, ou le recuit simulé) ne peuvent pas marcher de façon générale : ils ne seront efficaces que sur des problèmes avec des structures mathématiques bien précises. Je trouve également cette idée intéressante du point de vue de l'évolution : "l'algorithme" d'évolution darwinienne n'est efficace que s'il est adapté au problème ("sélection du plus adapté"). Si on connaît l'algorithme, cela signifie qu'on peut avoir des informations théoriques sur la structure du problème, et sur la fameuse "fitness function" chère aux biologistes...

Références :

Le papier original (merci Timothée) : Wolpert, D.H., Macready, W.G. (1997), No Free Lunch Theorems for Optimization, IEEE Transactions on Evolutionary Computation 1, 67.
Une démonstration assez simple du NFLT est proposée dans Ho, Y.C., Pepyne, D.L. (2002), Simple Explanation of the No-Free-Lunch Theorem and Its Implications, Journal of Optimization Theory and Applications 115, 549.

6 commentaires:

Matthieu a dit…

C'est tres interessant ca ! est-ce que tu sais comment ce theoreme est demontre ?

par contre, sur l'evolution, qu'est ce qui prouve que c'est le meilleur "algorithme d'optimisation' ? apres tout, c'est le seul accessible a la nature, et le processus n'a pas evolue (ou peut-etre que si ?)

Tom Roud a dit…

Le théorème est démontré assez simplement dans la deuxième référence ci-dessus. Je n'ai pas vérifié en détail pour l'instant, mais ça m'a l'air assez simple (un simple argument du genre "théorème des pigeons" en fait, reposant sur la constatation élémentaire que tout processus d'optimisation se fait en fait sur un espace discret dans l'ordinateur). Il faut que je regarde le papier original en détail par contre (Merci Timothée de me l'avoir trouvé !).

Pour l'évolution, c'était un peu une idée un peu en l'air. En fait, si je parle de ce théorème aujourd'hui, c'est parce que je suis en train de me pencher très sérieusement là-dessus pour mon travail.

Anonyme a dit…

"il n'existe pas de recette générale permettant d'optimiser n'importe quel problème" > Si ! Mais dans un temps infini... Le NFL theoreme ne dit pas que des algorithmes generalistes ne peuvent pas exister, mais qu'ils ne sont pas les plus rapides, les plus performants pour un probleme donne...
Et encore, le theoreme ne prend en compte que le temps de calcul, pas le temps de developpement de l'algorithme.. Pour prendre un exemple, mieux vaut ne pas perdre 3 jours a developper un algo pour resoudre en probleme en 10 minutes quand un algo genetique, par exemple, aurait resolu le meme probleme en 24h. Certes le gain est enorme en temps de calcul (un facteur 144 !), mais pas en temps total (pas besoin de perdre du temps a developper un algo genetique, vous en trouvez tout prets dans n'importe quel langage).

Tom Roud a dit…

Merci pour le commentaire !
C'est en fait une question que je me posais : j'avais l'impression que ce que tu optimisais en fait était justement le temps de calcul (i.e. le temps passé à chercher ce minimum). Si tu me donnes un temps de calcul infini, n'importe quel algorithme fait l'affaire (on peut même aller jusque faire une marche brownienne dans l'espace des paramètres). Donc j'aurais dit a priori que la "vraie" fonction de coût est précisément le temps de calcul. MAis bon, je ne suis pas spécialiste; dans la démonstration que je cite cet aspect "temps d'exploration" n'est pas pris en compte.

dvanw a dit…

Hello !

Ton billet m'a beaucoup intéressé et m'a renvoyé vers d'autres choses, et bref, une chose en entrainant une autre, j'ai fait moi aussi une note sur le même sujet...

http://dvanw.blogspot.com/2007/01/101-no-free-lunch-theorem.html

Je pense que ça ne doublonne pas, car la mienne est plus orientée "grand public" ( enfin, faut le dire vite! ) Je suis aussi tombé sur des choses assez intéressantes du point de vue de vos derniers commentaires. C'est ici :

http://www.greythumb.org/blog/index.php?/archives/54-Incompetent-design-and-the-no-free-lunch-theorem.html

dvanw a dit…

Pour info, Joël Perino, l'auteur du Blog "dernières nouvelles de l'Homme" a fait à son tour un billet sur le théorème sans dej' gratos...

http://blogs.zdnet.fr/index.php/2007/01/19/no-free-lunch/