1.30. QUELQUES CONCEPTS DE BASE
Avant de s'intéresser aux algorithmes de fourmis
artificielles, il convient tout
d'abord de présenter quelques concepts de base qui
seront utilisées tout au long de cette
section.
5.1.8. Problème d'optimisation
Un problème d'optimisation est tout problème
définit par un espace de recherche
des solutions, une fonction objectif qui associe un coût
à chaque solution possible et un
ensemble de contraintes. On cherche alors à trouver la
solution optimale qui correspond
à une solution de coût minimum ou maximum selon
qu'il s'agit de minimiser ou de
maximiser la fonction objectif. Un problème
d'optimisation combinatoire est tout
problème d'optimisation pour lequel il faut trouver une
solution optimale avec un
espace de recherche de solutions fini mais extrêmement
grand. Ce type de problème est
dit « difficile ».
5.1.9. Méthodes de résolution
Les méthodes de résolution des problèmes
d'optimisation sont de deux types :
Les méthodes exactes (déterministes) : elles
fournissent une solution optimale au
prix d'un temps de résolution qui risque d'être
exponentiel en fonction de la taille des
données du problème. Les méthodes
approchées : pour un problème d'optimisation dit «
difficile » aucune méthode exacte n'est capable de
le résoudre exactement en un temps
raisonnable. Dans ce cas on fait appel à ses
méthodes permettant une optimisation
approchée. Ce type de méthodes retourne une
solution contenue dans un certain
intervalle autour de la solution optimum avec un temps de
calcul acceptable. Elles
représentent un compromis entre la qualité de la
solution trouvée et le temps de calcul
nécessaire. Parmi les méthodes de résolution
approchées, on trouve :
5.1.10. Les heuristiques
Une heuristique est une méthode approchée simple,
rapide et dédiée à un
problème donné. Elle exploite les
propriétés structurelles d'une solution et tente de la
rendre rapidement une solution admissible par des
critères de décision déduits de la
connaissance du problème. Aucune garantie quant à
l'optimalité de la solution trouvée
ne peut être fournie.
5.1.11. Les méta heuristiques
Une métaheuristique est une méthode
approchée générique dont le principe de
fonctionnement repose sur des mécanismes
généraux indépendants de tout problème.
Les méta heuristiques sont stochastiques et donc peuvent
éviter d'être piégés dans des
minimums locaux. Elles sont principalement guidées par
le hasard (exploration aléatoire
de l'espace de recherche), cependant elles sont souvent
alliées à d'autres algorithmes
afin d'en accélérer la convergence.
| 
