Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$18,000.00
Métaheuristiques et satisfaction de contraintes
FY 2006-07
Summary
Le programme de recherche proposé vise à contribuer au développement des techniques d'optimisation appelées 'métaheuristiques'. Il s'agit de techniques de résolution qui visent à trouver des solutions approchées (non nécessairement optimales) pour des exemplaires de grande taille de problèmes difficiles (NP-difficiles). Une métaheuristique (par exemple, la recherche avec tabou, le recuit simulé, l'algorithme génétique, etc.) constitue un schéma d'algorithme générique, c'est-à-dire applicable à de nombreux problèmes. Le programme de recherche proposé comporte les trois axes suivants. Le premier axe consiste à proposer de nouvelles métaheuristiques, à compléter et améliorer les techniques déjà connues, à les hybrider et à étudier leur comportement. Il se rapporte aussi à la manière d'adapter une métaheuristique à un problème particulier ou une famille donnée de problèmes : ceci concerne la définition de fonctions de voisinage pour le problème cible et la spécialisation des opérateurs de recherche (par exemple, les opérateurs de recombinaison dans un algorithme évolutionniste). Un des projets proposés consiste à étudier le problème de k-partitionnement de graphe. Le deuxième axe porte sur la résolution des problèmes de satisfaction de contraintes (CSP) à l'aide de méthodes de réparation. Il s'agit de techniques de recherche locale fondées sur la minimisation de pénalités attribuées pour la violation des contraintes et qui utilisent des voisinages simples. Nous poursuivrons le développement d'un système logiciel générique de résolution de CSP - bibliothèque en langage C++. Un autre projet consistera à approfondir et appliquer l'approche originale que nous avons proposée récemment et qui permet de détecter, dans un CSP irréalisable (sur-contraint), un sous-problème lui-même irréalisable mais 'minimal'. Le troisième axe porte sur l'utilisation de métaheuristiques pour la résolution d'applications dans le domaine des réseaux de télécommunications.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
251139-2006
Name nom
Galinier, Philippe
Department département
Génie informatique
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2006
Competition year année de concours
2006
Award amount
18000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
Métaheuristiques et satisfaction de contraintes
Keyword
NA
Application summary
Le programme de recherche proposé vise à contribuer au développement des techniques d'optimisation appelées 'métaheuristiques'. Il s'agit de techniques de résolution qui visent à trouver des solutions approchées (non nécessairement optimales) pour des exemplaires de grande taille de problèmes difficiles (NP-difficiles). Une métaheuristique (par exemple, la recherche avec tabou, le recuit simulé, l'algorithme génétique, etc.) constitue un schéma d'algorithme générique, c'est-à-dire applicable à de nombreux problèmes. Le programme de recherche proposé comporte les trois axes suivants. Le premier axe consiste à proposer de nouvelles métaheuristiques, à compléter et améliorer les techniques déjà connues, à les hybrider et à étudier leur comportement. Il se rapporte aussi à la manière d'adapter une métaheuristique à un problème particulier ou une famille donnée de problèmes : ceci concerne la définition de fonctions de voisinage pour le problème cible et la spécialisation des opérateurs de recherche (par exemple, les opérateurs de recombinaison dans un algorithme évolutionniste). Un des projets proposés consiste à étudier le problème de k-partitionnement de graphe. Le deuxième axe porte sur la résolution des problèmes de satisfaction de contraintes (CSP) à l'aide de méthodes de réparation. Il s'agit de techniques de recherche locale fondées sur la minimisation de pénalités attribuées pour la violation des contraintes et qui utilisent des voisinages simples. Nous poursuivrons le développement d'un système logiciel générique de résolution de CSP - bibliothèque en langage C++. Un autre projet consistera à approfondir et appliquer l'approche originale que nous avons proposée récemment et qui permet de détecter, dans un CSP irréalisable (sur-contraint), un sous-problème lui-même irréalisable mais 'minimal'. Le troisième axe porte sur l'utilisation de métaheuristiques pour la résolution d'applications dans le domaine des réseaux de télécommunications.