Optimisation : Différence entre versions

De WikiUpLib
Aller à : navigation, rechercher
(La démarche)
 
Ligne 14 : Ligne 14 :
 
mais plutôt d'essayer de saisir la philosophie de ces méthodes de résolution.
 
mais plutôt d'essayer de saisir la philosophie de ces méthodes de résolution.
  
NB: le cerveau animal, ensemble de millions de neurones interconnectés, fonctionne bel et bien ainsi, et de façon satisfaisante, depuis des millénaires.
+
NB: le cerveau animal, ensemble de millions de neurones interconnectés, fonctionne bel et bien ainsi, et de façon satisfaisante, depuis des millions d'années.
 
 
  
 +
<br>
  
 
==La démarche==
 
==La démarche==
Ligne 76 : Ligne 76 :
 
Peterson, Soderberg 1989  
 
Peterson, Soderberg 1989  
  
 +
NB : je n'ai pas surveillé l'évolution de ce domaine de recherche depuis un bail,
 +
les derniers développements ne sont donc pas ici.
 +
 +
<br>
 +
 +
==Citations==
  
NB : je n'ai pas surveillé l'évolution de ce domaine de recherche depuis un bail,
+
* « l’optimisation prématurée est la source de tous les maux » - Donald Knuth
les derniers développements ne sont donc probablement pas ici.
+
 
 +
<br>

Version actuelle datée du 25 juillet 2018 à 17:00

Mots-clés : optimisation, calcul collectif, calcul distribué,

http://fr.wikipedia.org/wiki/Optimisation_(mathématiques)

Cette page recense un peu d'infos + bibliographie sur les techniques d'optimisation par calcul distribué.
Calcul distribué : le calcul n'est pas effectué par un processeur central, mais est réparti sur une multitude de petits agents, et sans coordination centralisée forte.
On n'est pas en présence d'une entité centrale qui se contente de découper un gros calcul sur des sous-unités. On est en présence d'une multitude d'agents indépendants, dont le nombre peut varier, dont la participation peut varier, mais qui coopèrent à la résolution d'un problème. (La coopération peut être simplement locale, ie chaque agent coopère avec ses voisins proches, mais sans plus. ie tout le monde ne coopère pas avec tout le monde.)

Il est recommandé de ne pas s'appesantir sur les détails calculatoires et d'implémentation etc, mais plutôt d'essayer de saisir la philosophie de ces méthodes de résolution.

NB: le cerveau animal, ensemble de millions de neurones interconnectés, fonctionne bel et bien ainsi, et de façon satisfaisante, depuis des millions d'années.


La démarche

1/ Le premier point (simple) à saisir est que à tout problème d'optimisation proprement formalisé il est possible (et obligatoire) d'associer une fonction mathématique. Les extréma de la fonction sont les solutions du problème. La complexité du problème est directement liée à la complexité de cette fonction. Une fonction très simple, par exemple un simple bol, comporte un seul minimum qu'il est facile de déterminer.
Une fonction plus complexe peut comporter des milliers d'extrémas locaux dans un espace de grandes dimensions ... il devient alors bien plus difficile de découvrir les extréma globaux au milieu de tous les leurres.

2/ A un système de particules connectées, il est possible d'associer une (ou plusieurs) fonctions "énergie" qui réalisent différentes mesures de l'état de ce système, par exemple sa température globale. La mesure globale de l'état du système sera une fonction mathématique d'un ensemble de mesures individuelles sur toutes les particules du système.
Si on est capable de simuler correctement (sur un ordinateur) l'évolution du système, il suffit alors de laisser se dérouler la simulation pour que le système finisse par converger vers un extréma (en général local).

3/ Dans les méthodes d'optimisation par calcul distribué, le jeu consiste à identifier/découvrir/fabriquer une architecture de système de particules connectées, (la nature des connections étant précisément l'un des enjeux), muni d'une fonction "énergie" intéressante (ie pas avec 1 million d'extréma) et dont les extréma globaux coïncident avec les extréma de la fonction qu'on cherche à optimiser.

Cela semble peut-être un peu abstrait, mais peut être assez bien illustré par le problème d'optimisation dit des N-reines. https://fr.wikipedia.org/wiki/Problème_des_huit_dames . Evidemment, on ne va pas se contenter de 8 reines, mais plutôt 1000 ou 10.000.
Il y a un paquet de méthodes algorithmiques classiques (et qui marchent bien).
Une méthode par calcul distribué consiste à considérer chaque case de l'échiquier comme un élément de calcul, à munir les cases de relations entre elles ... et à faire évoluer l'état du plateau.

Bibliographie sommaire (et un peu éclectique)

  • etc, etc, pour plus de références, me demander.

Peterson, Soderberg 1989

NB : je n'ai pas surveillé l'évolution de ce domaine de recherche depuis un bail, les derniers développements ne sont donc pas ici.


Citations

  • « l’optimisation prématurée est la source de tous les maux » - Donald Knuth