Utilisateur:Pierre falez/Brouillon

Beaucoup de Modélisation de problèmes complexes se rapportent à une fonction non convexe. Il y a de véritables problèmes qui se rapportent à des modélisations courantes et qui sont des 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.

Une fonction non convexe (qui n’est pas une fonction convexe) est une fonction qui admet un optimal global ainsi que des optimaux locaux. Ce type de fonctions 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 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 minimale, 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 dur. 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 à 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)

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 continue, dimension, modélisation.

Nous allons ici essayer d'établir une liste des algorithmes qui fonctionnent bien sur différents types de problèmes. Ainsi, l'article sera structuré en fonction des différents types de problèmes.

Problèmes continues

On définit les problèmes continues comme des problèmes dont leurs Fonction objectif est continue. Leurs difficultés résident surtout dans l'espace de définition qui est infinis. Cependant, on peut se restreindre à un espace borné afin de pouvoir minimiser certaine fonction.

Somme de fonctions différentiables

Algorithme du gradient stochastique : Le gradient d’une telle fonction de score est égale à la somme des gradients des fonctions élémentaires qui la composent.

Par exemple, dans l'étude Cinétique chimique, une telle optimisation peut-être mis en place.

Problèmes de petites dimensions

Méthode de Nelder-Mead 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éfinit dans l’ensemble complexe, ou lorsque le nombre de dimension augmente.

 Fonction regionalisée

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

Problèmes discrets

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’autre 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

La majorité des méthodes de résolution exacte se basent 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  : Cet algorithme ajoute au Branch-and-Bound la méthode Cutting-plane afin de déterminer les régions faisables via la programmation linéaire.

Recherche Approchée

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

Voici quelques heuristiques pour des problèmes connus : TSP, Knapsack

Meta-Heuristique

Les méta-heuristiques fournissent un framework pour résoudre différent type de problèmes. Cependant, il est nécessaire d’adapter certaine fonction (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ère : Population, mémoire, parcours, etc..

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 fait pour tenter de les comparer : AMALGAM ou CMA-ES semble donner de bon résultat sur des instances de grande taille

Hyper-Heuristique

A 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.