Les méta-heuristiques

LES MÉTA-HEURISTIQUES : quelques conseils pour en faire bon usage Alain HERTZ Ecole Polytechnique – GERAD Département de mathématiques et de génie industriel CP 6079, succ. Centre-ville, Montréal (QC) H3C 3A7, Canada E-mail address: [email protected]

1.

Introduction

La solution optimale à un problème d’optimisation ne peut que très rarement être déterminée en un temps polynomial. Ilest donc souvent nécessaire de trouver des modes de résolution qui fournissent une solution de bonne qualité dans un laps de temps raisonnable : c’est ce que font les heuristiques. Depuis une vingtaine d’années, les heuristiques les plus populaires, et également les plus efficaces, sont des techniques générales, appelées méta-heuristiques, qu’il s’agit d’adapter à chaque problème particulier. Parmices techniques générales, nous nous pencherons dans ce chapitre sur deux approches ayant clairement démontré leur utilité dans de nombreux domaines, y compris la gestion des systèmes de production. La première de ces approches, appelée Recherche Locale, est couramment utilisée depuis plus de 20 ans et comprend, entre autres, la technique du Recuit Simulé [Kirkpatrick et al., 1983] et la RechercheTaboue [Glover, 1986]. La deuxième approche, appelée Méthode Évolutive, est plus récente puisqu’ elle date du début des années 90. Elle s’ est particulièrement faite connaître par l’ intermédiaire des algorithmes génétiques dont l’ origine remonte aux travaux de Holland [Holland, 1975]. Le but de ce chapitre n’ est pas de donner une description précise de l’ ensemble des métaheuristiquescouramment utilisées en optimisation. Nous visons plutôt à guider toute personne désirant adapter une méta-heuristique à un problème particulier d’ optimisation. Pour ce faire, nous décrivons tout d’ abord brièvement, dans la prochaine section, les 2 approches susmentionnées. Dans la Section 3, nous commençons par indiquer les concepts les plus importants qu’ il s’ agit d’ adapter adéquatement pourpouvoir résoudre un problème d’ optimisation particulier à l’ aide d’ une méta-heuristique. Ce travail d’ adaptation d’ une approche générale à un problème particulier peut être réalisé de diverses manières. C’ est pourquoi, dans la suite de la Section 3, nous présentons diverses stratégies d’ adaptation, en mettant en relief les avantages et les inconvénients de chacune d’ elles. La Section 4 contientun résumé des conseils délivrés dans ce chapitre.

1

2.

Description générale des principales méta-heursitiques

Soit S un ensemble de solutions à un problème d’ optimisation, et soit f une fonction qui associe une valeur f(s) à chaque solution s?S. L’ ensemble S est défini de telle sorte qu’ une solution n’ en fait partie que si elle respecte l’ ensemble des contraintes du problèmeconsidéré. L’ objectif d’ un algorithme d’ optimisation est de déterminer une solution dans S qui minimise la fonction f. En d’ autres termes, il s’ agit de déterminer une solution s*?S telle que f(s*)= min f (s)
s?S

Le but de cette section n’ est pas de donner une description précise et détaillée des principales techniques de Recherche Locale et des Méthodes Évolutives. Nous nous en tiendrons àl’ essentiel, et nous mettrons en relief quelques difficultés que l’ on peut rencontrer lors de leur utilisation. Le lecteur désirant obtenir plus de détails sur ces techniques peut consulter le célèbre ouvrage de Reeves [Reeves, 1995] dans lequel les principales méta-heuristiques sont présentées de manière très didactique, avec des exemples d’ applications tel que l’ ordonnancement de la production.Comme le domaine des méta-heuristiques évolue très vite, le lecteur préférera peut-être consulter des ouvrages plus récents, tel que celui de Dréo et al. qui est écrit en français [Dréo, 2003]. 2.1 La Recherche Locale

Les techniques de Recherche Locale associent un voisinage N(s) à chaque solution s?S, et construisent une séquence s0, s1, … de solutions où s0 est une solution initiale…