Aller au contenu

Minimisation de fonctions non convexes

Ajouter des liens
Un article de Wikipédia, l'encyclopédie libre.

Beaucoup de problèmes complexes peuvent être modélisés à l'aide de fonctions non convexes. Par exemple, une tournée de distribution de colis par un livreur peut se modéliser par le Problème du voyageur de commerce qui est une modélisation courante de ce type de problème. Le Problème SAT est un autre exemple de problème ne pouvant pas être résolu en utilisant une fonction convexe.

Explications[modifier | modifier le code]

Une fonction non convexe est une fonction qui admet un optimal global ainsi que des optimaux locaux. Ce type de fonction pose problème lorsqu’il s’agit de les minimiser car les algorithmes traditionnels ont tendance à tomber dans ces optimaux locaux, et donc d’autres techniques doivent être mises en place afin de leur échapper et de trouver l’optimal global. Cependant, une résolution mathématique n’est souvent pas possible car ces fonctions ne sont pas dérivables.

Dans le cas d’une fonction discrète relativement petite, il est possible de faire une recherche totale du minimal, simplement en parcourant l’ensemble des solutions. Par exemple le Problème du sac à dos utilise la Programmation dynamique pour trouver des solutions.

Pour les problèmes plus complexes, il est nécessaire d’utiliser des approches non exhaustives.

Mesurer la qualité d’un algorithme dans le cas général est très difficile . Comme les performances des heuristiques dépendent directement du problème, il est difficile de réaliser des expériences avec un nombre limité de problèmes qui soit représentatif du cas général.

Sans a priori sur le problème que l’on souhaite résoudre, les résultats obtenus par différents algorithmes seront les mêmes (voir No Free Lunch Theorem (en)[1])

C’est pourquoi le choix d’un algorithme est directement lié aux caractéristiques du problème : domaine de définition, problème discret ou continu, dimension, modélisation.

Problèmes continus[modifier | modifier le code]

On définit les problèmes continus comme des problèmes dont la fonction objectif est continue. Leur difficulté réside surtout dans l'espace de définition qui est infini. Cependant, on peut se restreindre à un espace borné afin de pouvoir minimiser certaines fonctions.

Somme de fonctions différentiables[modifier | modifier le code]

Algorithme du gradient stochastique : Le gradient d’une fonction différentiable de score est égal à la somme des gradients des fonctions élémentaires qui la composent[2].

Par exemple, dans l'étude cinétique chimique, une telle optimisation peut être mise en place.

Problèmes de petite dimension[modifier | modifier le code]

Méthode de Nelder-Mead[3] : il s’agit d'utiliser un simplexe polytope sur lequel on effectue des transformations pour que les sommets se rapprochent d’un minimal. Cette méthode simple assure une décroissance de la solution trouvée.

Attention toutefois, l’algorithme peut être inefficace dans le cas où le problème est défini dans l’ensemble complexe, ou lorsque le nombre de dimensions augmente.

Variable régionalisée[modifier | modifier le code]

Lorsque le problème est une variable régionalisée, par exemple la topographie d'une ville, Krigeage[4] s'avère extrêmement efficace car cette technique permet une estimation de la fonction avec une très faible variance.

Problèmes discrets[modifier | modifier le code]

La particularité des problèmes discrets est la garantie qu’il existe une ou plusieurs solutions optimales globales. Il est alors possible d’utiliser des algorithmes de recherche qui garantissent une solution optimale, et d’autres qui garantissent un temps de recherche convenable en contrepartie d'une solution approchée. Les méthodes de recherches exactes ne peuvent pas être applicables en temps raisonnable sur des problèmes de grande taille. On parle alors d'explosion combinatoire.

Recherche exacte[modifier | modifier le code]

La majorité des méthodes de résolution exactes se base sur de la programmation dynamique. Les méthodes les plus utilisées sont :

  • Séparation et évaluation (Branch-and-Bound) : Cette méthode représente les solutions sous forme d’un arbre. L’algorithme estime les bornes minimales et maximales de l’ensemble des solutions du sous-arbre afin de ne pas les parcourir s’il est garanti que la solution optimale n’y est pas.
  • Branch-and-cut[5] : Cet algorithme ajoute au Branch-and-Bound la méthode Cutting-plane afin de déterminer les régions faisables via programmation linéaire.

Recherche approchée[modifier | modifier le code]

Les heuristiques sont spécifiques aux problèmes, elles nécessitent donc une bonne connaissance de ces derniers. Beaucoup d'entre elles reposent sur les algorithmes gloutons.

Voici quelques heuristiques pour des problèmes connus : TSP[6], Knapsack[7].

Méta-Heuristiques[modifier | modifier le code]

Les méta-heuristiques fournissent un framework pour résoudre différents types de problèmes. Cependant, il est nécessaire d’adapter certaines fonctions (parcours du voisinage, opérateur d'enjambement, mutation, etc.) au problème à résoudre.

Les méta-heuristiques peuvent être classifiées selon divers critères : population, mémoire, parcours, etc.[8],[9]

Les méta-heuristiques reposent sur le principe de diversification-intensification : les différentes méthodes doivent combiner ces deux aspects afin d'explorer efficacement l'espace de recherche tout en se rapprochant des solutions optimales.

Même si l’efficacité des heuristiques dépend fortement des problèmes et des instances, des efforts sont faits pour tenter de les comparer[10] : AMALGAM[11] ou CMA-ES semble donner de bon résultat sur des instances de grande taille.

Hyper-Heuristique[modifier | modifier le code]

À la différence des méta-heuristiques, les hyper-heuristiques (en) travaillent sur l'espace de recherche des heuristiques au lieu de travailler sur l'espace des solutions. Les hyper-heuristiques permettent d'automatiser le réglage des méta-heuristiques utilisées.

Notes & Références[modifier | modifier le code]

  1. ↑ (en) David H. Wolpert et William G. Macready, « No Free Lunch Theorems for Optimization », IEEE Transactions on Evolutionary Computation, vol. 1, no 1,‎ , p. 67–82
  2. ↑ Thomas S. Ferguson, « An inconsistent maximum likelihood estimate », Journal of the American Statistical Association, vol. 77, no 380,‎ , p. 831–834 (DOI 10.1080/01621459.1982.10477894, JSTOR 2287314)
  3. ↑ (en) John Nelder et Roger Mead, « A simplex method for function minimization », Computer Journal, vol. 7, no 4,‎ , p. 308-313 (lire en ligne)
  4. ↑ Krigeage, Gratton Y., Les Articles de l'IAG
  5. ↑ (en) John E. Mitchell, « Branch-and-Cut Algorithms for Combinatorial Optimization Problems », Mathematical Sciences,‎
  6. ↑ (en) Christian Nilsson, « Heuristics for the Traveling Salesman Problem », Link¨oping University,‎
  7. ↑ (en) Hamid Shojaei, Twan Basten, Marc Geilen et Azadeh Davoodi, « A Fast and Scalable Multidimensional Multiple-Choice Knapsack Heuristic », ACM Transactions on Design Automation of Electronic Systems (TODAES),‎
  8. ↑ (en) Mauro Birattari, Luis Paquete, Thomas Stüzle et Klaus Varrentrapp, « Classification of Metaheuristics and Design of Experiments for the Analysis of Components », Design Automation of Electronic Systems,‎
  9. ↑ Jin-Kao Hao, Philippe Galinier et Michel Habib, « Méthaheuristiques pour l’optimisation combinatoire et l’affectation sous contraintes », Revue d’Intelligence Artificielle,‎
  10. ↑ (en) Adam P. Piotrowski, « Regarding the rankings of optimization heuristics based on artificially-constructed benchmark functions », Information Sciences, no 297,‎ , p. 191–201
  11. ↑ (en) Maashi M, Ozcan et Kendall, « A multi-objective hyper-heuristic based on choice function », Expert Systems with Applications, vol. 41, no 3,‎ , p. 4475-4493
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Minimisation_de_fonctions_non_convexes&oldid=209637403 ».