Recherche bibliographique portant sur la " Contribution à la réalisation du problème d'emploi de temps par une approche évolutionnaire "

Chapitre II

METHODES D'OPTIMISATION

Afin d'améliorer le comportement d'un algorithme de recherche lorsque ils parcoure un espaces de solutions assez grand, on fait appel à des heuristiques qui ont l'aptitude de guider le processus de recherche pendant son exploration de l'espace de recherche, et de sélectionner la solution qui semble être optimales.

Selon Feignebaum et Feldman (1963) « Une heuristique est définie comme une règle d'estimation, une stratégie, une astuce, une simplification, ou tout autre sorte de système qui limite drastiquement la recherche des solutions dans l'espace des configurations possibles ». Selon Shaw et Simon (1957) « Un processus heuristique peut résoudre un problème donné, mais n'offre pas la garantie de le faire ».

Dans la pratique, certaines heuristiques sont visées à résoudre des problèmes particuliers. En revanche, une méta-heuristique se place à un niveau plus général, et intervient dans toutes les situations où on ne connaît pas d'heuristique efficace, ou lorsqu'il estime qu'il ne dispose pas du temps nécessaire pour en déterminer une.

Selon I.H.Osman et G.Laporte (En 1996) « Une méta-heuristique est un processus itératif qui subordonne et qui guide une heuristique, en combinant intelligemment plusieurs concepts pour explorer et exploiter tout l'espace de recherche. Des stratégies d'apprentissage sont utilisées pour structurer l'information afin de trouver efficacement des solutions optimales, ou presque optimales ».

Selon le site « metaheuristics.org »(2006) « Une méta-heuristiques est un ensemble de concepts utilisés pour définir des méthodes heuristiques, pouvant être appliqués à une grande variété de problèmes. On peut voir la méta-heuristique comme une boîte à outils algorithmique, utilisable dans la résolution des problèmes d'optimisation, et ne nécessitant que peu de modification pour qu'elle puisse s'adapter à un problème particulier ».

9

CHAPITRE II. METHODES D'OPTIMISATION

II.1 Classification des méta-heuristiques

Les méta-heuristiques n'étant pas, a priori, spécifiques à la résolution d'un problème particulier, et leur classification reste assez arbitraire.

selon le nombre de solution que retient l'algorithme a chaque cycle on peut distinguer : - Les approches en trajectoire. qui partent d'une solution initiale s0 et s'en éloignent progressivement, pour réaliser un parcours progressif dans l'espace des solutions. Dans cette catégorie, on trouve : la méthode de descente, le recuit simulé, la méthode Tabou. . . etc.

- Les approches en population. qui travaillent sur un ensemble de solutions, que l'on fait évoluer graduellement. L'utilisation de plusieurs solutions simultanément permet naturellement d'améliorer l'exploration de l'espace des configurations. Dans cette seconde catégorie, on recense : les algorithmes génétiques, les algorithmes de colonies de fourmi, la méthode d'évolution différentielle, la méthode GRASP. . . etc.

selon les domaines d'inspiration on distingue ainsi :

- Les approches inspirées de la sélection naturelle.

- Les approches inspirées de la physique.

- Les approches inspirées des insectes sociaux.

- Les approches inspirées de réseau de neurones.

- Les approches inspirées de système immunitaire.

- ...etc.

On peut également raisonner par rapport à l'usage que font les méta-heuristiques de la fonction objectif. Certaines la laissent telle quelle est, tandis que d'autres la modifient en fonction des informations collectées au cours de l'exploration. L'idée étant toujours de s'échapper de l'optima local, pour avoir davantage de chance de trouver l'optimum global. La recherche locale guidée est un exemple de méta-heuristique qui modifie la fonction objectif.

Enfin, il faut distinguer les méta-heuristiques qui ont la faculté de mémoriser des informations à mesure que leur recherche avance, de celles qui fonctionnent sans mémoire, en aveugle, et qui peuvent revenir sur des solutions qu'elles ont déjà examiné. Le meilleur représentant des méta-heuristiques avec mémoire est la recherche Tabou, dans les sans mémoire, on trouve le recuit simulé.