Optimisation : Différence entre versions

De WikiUpLib
Aller à : navigation, rechercher
(Page créée avec « http://fr.wikipedia.org/wiki/Optimisation_%28math%C3%A9matiques%29 Cette page recense un peu d'infos + bibliographie sur les techniques d'optimisation par calcul distrib... »)
 
Ligne 1 : Ligne 1 :
 +
 +
Mots-clés : optimisation, calcul collectif, calcul distribué,
  
 
http://fr.wikipedia.org/wiki/Optimisation_%28math%C3%A9matiques%29
 
http://fr.wikipedia.org/wiki/Optimisation_%28math%C3%A9matiques%29
Ligne 18 : Ligne 20 :
 
==La démarche==
 
==La démarche==
  
1/ Le premier point à saisir est que à tout problème d'optimisation proprement formalisé
+
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.
 
il est possible (et obligatoire) d'associer une fonction mathématique.
 
Les extréma de la fonction sont les solutions du problème.
 
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.
 
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.<br>
 
Une fonction très simple, par exemple un simple bol, comporte un seul minimum qu'il est facile de déterminer.<br>
Une fonction plus complexe peut comporter des milliers d'extrémas locaux
+
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 ces leurres.<br>
+
... il devient alors bien plus difficile de découvrir les extréma globaux au milieu de tous les leurres.<br>
  
 
2/ A un système de particules connectées,
 
2/ A un système de particules connectées,
Ligne 45 : Ligne 47 :
 
Une méthode par calcul distribué consiste à considérer chaque case de l'échiquier comme un élément de calcul,
 
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
 
à munir les cases de relations entre elles
... et à regarder comment évolue le plateau.
+
... et à faire évoluer l'état du plateau.
 +
 
 +
 
 +
 
 +
 
 +
==Bibliographie sommaire (et un peu éclectique)==
 +
 
 +
* http://fi.khi.fr/bib/OPTIM/
 +
 
 +
* http://fi.khi.fr/bib/OPTIM/nq_slide_en.pdf (voir les 2 1° transparents)
 +
 
 +
* http://fi.khi.fr/bib/OPTIM/orn1990_fr.pdf (voir la biblio à la fin)
 +
 
 +
* http://fi.khi.fr/bib/OPTIM/271_bonabeau.pdf
 +
 
 +
* http://fi.khi.fr/bib/OPTIM/006_kauffman.pdf
 +
 
 +
* http://fi.khi.fr/bib/OPTIM/254_nadal.pdf
 +
 
 +
* http://fi.khi.fr/bib/OPTIM/024_arthur.pdf
  
 +
* http://fi.khi.fr/bib/OPTIM/Hopfield_and_Tank.pdf
  
 +
* http://fr.wikipedia.org/wiki/Recuit_simul%C3%A9
  
 +
* http://fr.wikipedia.org/wiki/Optimisation_par_essaims_particulaires
  
==Bibliographie==
+
* etc, etc, pour plus de références, me demander.
  
http://fi.khi.fr/bib/OPTIM/
+
Peterson, Soderberg 1989
http://fi.khi.fr/bib/OPTIM/nq_slide_en.pdf (voir les 2 1° transparents)
 
  
  
http://fr.wikipedia.org/wiki/Recuit_simul%C3%A9
+
NB : je n'ai pas surveillé l'évolution de ce domaine de recherche depuis un bail,
http://fr.wikipedia.org/wiki/Optimisation_par_essaims_particulaires
+
les derniers développements ne sont donc probablement pas ici.

Version du 12 juillet 2013 à 09:09

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

http://fr.wikipedia.org/wiki/Optimisation_%28math%C3%A9matiques%29

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.

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 millénaires.


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%C3%A8me_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 probablement pas ici.