Dans cette thèse, nous nous intéressons aux problèmes du knapsack multidimensionnel à choix multiple. Ils interviennent essentiellement en télécommunication. Nous proposons de nouvelles méthodes hybrides de résolution exacte et approchée. Dans un premier temps, nous proposons des méthodes heuristiques en se basant sur les techniques de génération de colonnes et d'arrondi. Ensuite, nous abordons une méthode de recherche locale, dite méthode de branchement local, où des contraintes linéaires sont introduites pour intensifier et diversifier la recherche. Cette méthode est ensuite hybridée avec la génération de colonnes et une technique d'arrondi. Concernant la résolution exacte, nous nous basons sur une méthode de "Branch and cut". Nous commençons par proposer de nouvelles contraintes valides pour le problème. Ensuite, nous les associons à des contraintes de couverture locales et globales dans un schéma énumératif. Les approches heuristiques et l'algorithme exact que nous proposons sont comparés à d'autres heuristiques de la littérature et au Solveur de programmes linéaires Cplex . L'ensemble de ces tests numériques ont été menés sur des instances ardues de la littérature ainsi que sur des instances générées aléatoirement de taille modérée.

Un objectif de cette thèse est de fournir des outils d'analyse, de conception et d'implantation des approches métaheuristiques pour l'optimisation combinatoire en les formulant dans le cadre des systèmes multi-agents. L'accent est mis sur la potentialité de mise en œuvre distribuée des approches et sur l'utilisation de techniques d'apprentissage permettant d'adapter dynamiquement des méthodes de recherche.<br /><br />Dans le cadre de cette thèse nous proposons tout d'abord, un framework organisationnel et multi-agent pour la modélisation et l'implantation de métaheuristiques. Ce framework nommé AMF (Agent Metaheuristic Framework), introduit un modèle organisationnel de métaheuristiques qui décrit le système sous la forme d'une organisation composée de rôles en interaction. Le premier objectif de ce modèle est de donner un cadre d'analyse et de comparaison des différentes métaheuristiques existantes. Ensuite, il doit faciliter la conception de nouveaux algorithmes en encourageant une approche multi-agent. L'intérêt de l'approche organisationnelle, actuellement utilisée dans les systèmes multi-agents, est de pouvoir décrire un système aussi bien comme un tout, le système multi-agent, que comme un assemblage de composants, les agents. De plus, cette approche permet de distinguer l'analyse des fonctions du système, de l'analyse de son architecture. Enfin, l'approche organisationnelle encourage la modularité et la réutilisation des modèles. Nous proposons en complément de ce modèle un guide méthodologique. Il définit un ensemble d'étapes permettant de passer du modèle organisationnel à une méthode d'optimisation exprimée en termes d'agent.<br /><br />Ensuite, nous présentons une métaheuristique fondée sur la métaphore de la coalition, CBM (Coalition Based Metaheuristic), mettant en avant l'intérêt d'utiliser les systèmes multi-agents pour la conception de métaheuristiques. Dans cette métaheuristique, la recherche de solution est effectuée par un ensemble d'agents regroupés dans une coalition. Chaque agent est capable d'effectuer indépendamment des autres une recherche dans l'espace des solutions à l'aide d'opérateurs de déplacement dans un voisinage de la solution courante et d'adapter sa stratégie par apprentissage par renforcement. Des mécanismes de coopération entre agents permettent d'améliorer l'efficacité de la recherche. La structure de coalition permet d'intégrer naturellement au système de résolution des aspects de distribution et de décentralisation du contrôle, de même que des procédés d'apprentissage individuels et collectifs. L'efficacité de notre approche est évaluée expérimentalement en traitant deux problèmes d'optimisation combinatoire : un problème de tournées de véhicules et un problème de positionnement.

Étant donnes un graphe g=(v,e) et une fonction cout définie sur les arêtes de ce graphe, cette thèse étudie le problème du voyageur de commerce relaxe qui consiste a trouver une tournée sur G, de longueur minimum, telle que chaque sommet soit visite au moins au fois

.

Cette thèse aborde le problème de la résolution des problèmes combinatoires à l'aide d'algorithmes génétiques. Ce type d'algorithme présente en effet nombres d'avantages. Cependant, ils sont généralement relativement lents. Cette thèse est donc centrée sur les algorithmes hybrides, c'est-à-dire des algorithmes construits à l'aide de plusieurs méthodes différentes. Dans notre cas, nous étudions les algorithmes qui réunissent algorithmes génétiques et heuristiques. Il existe deux méthodes pour générer de tels algorithmes qui sont la représentation directe et la représentation indirecte. Ces deux méthodes sont étudiés au travers de trois problèmes distincts : l'ordonnancement statique de programmes parallèles, le placement de composants électroniques et la planification de réseaux cellulaires. Pour chacun des trois problèmes, les algorithmes hybrides ont montrés leur efficacité. Pour le problème de la planification de réseaux cellulaires, une nouvelle modélisation a été faite. Cette modélisation permet d'effectuer en même temps le placement des émetteurs et l'allocation de fréquences.

Le travail présenté dans cette thèse traite de l'extraction de connaissances à l'aide de métaheuristiques et de ses applications à des problématiques en génomique. Dans un premier temps, nous donnons un état de l'art des métaheuristiques utilisées pour l'extraction de connaissances et plus particulièrement de l'utilisation des algorithmes génétiques en orientant notre présentation sur trois aspects fondamentaux des métaheuristiques : la représentation d'une solution, la fonction d'évaluation et le choix des opérateurs. Nous présentons ensuite deux problématiques issues d'une collaboration avec l'Institut de Biologie de Lille autour de la recherche de facteurs génétiques de prédisposition à certaines maladies multifactorielles (diabète de type II, obésité). Nous proposons une modélisation de ces problèmes en problèmes d'extraction de connaissances. Nous traitons ensuite les différentes taches d'extraction de connaissances identifiées comme des problèmes d'optimisation et proposons un schéma d'algorithme génétique possédant des mécanismes avancés d'intensification et de diversification pour les résoudre. Les apports de ces mécanismes sont testés modulairement afin de montrer leurs performances. Nous intégrons également des connaissances du domaine biologique afin de répondre aux problématiques posées. Cette intégration s'effectue aussi bien au niveau des fonctions d'évaluation proposées qu'au niveau de certains mécanismes utilisés. Enfin, différents modèles de parallélisme sont utilisés.

La demande croissante de puissance de calcul est telle que des ordinateurs de plus en plus performants sont fabriques. Afin que ces machines puissent etre facilement exploitees, les lacunes actuelles en terme d'environnements de programmation doivent etre comblees. Le but a atteindre est de trouver un compromis entre recherche de performances et portabilite. Cette these s'interesse plus particulierement au placement statique de graphes de taches sur architectures paralleles a memoire distribuee. Ce travail s'inscrit dans le cadre du projet INRIA-IMAG APACHE et du projet europeen SEPP-COPERNICUS (Software Engineering for Parallel Processing). Le graphe de taches sans precedence est le modele de representation de programmes paralleles utilise dans cette these. Un tour d'horizon des solutions apportees dans la litterature au probleme de l'ordonnancement et du placement est fourni. La possibilite d'utilisation des algorithmes de placement sur des graphes de precedence, apres une phase de regroupement, est soulignee. Une solution originale est proposee, cette solution est interfacee avec un environnement de programmation complet. Trois types d'algorithmes (gloutons, iteratifs et exacts) ont ete concus et implementes. Parmi ceux-ci, on retrouve plus particulierement un recuit simule et une recherche tabu. Ces algorithmes optimisent differentes fonctions objectives (des plus simples et universelles aux plus complexes et ciblees). Les differents parametres caracterisant le graphe de taches peuvent etre affines suite a un releve de traces. Des outils de prise de traces permettent de valider les differentes fonctions de cout et les differents algorithmes d'optimisation. Un jeu de tests est defini et utilise. Les tests sont effectue sur le Meganode (machine a 128 transputers), en utilisant comme routeur VCR de l'universite de Southampton, les outils de generation de graphes synthetiques ANDES du projet ALPES (developpe par l'equipe d'evaluation de performances du LGI-IMAG) et l'algorithme de regroupement DSC (Dominant Sequence Clustering) de PYRROS (developpe par Tao Yang et Apostolos Gerasoulis). Mapping task graphs on distributed memory parallel computers

Nous proposons des méthodes et des outils pour l'aide à la conception stratégique de réseaux de transports publics en milieu urbain. Un état de l'art des problèmes de synthèse de réseaux est suivi par la définition du problème de synthèse de réseaux de mobilité avec demande élastique (dépendante de la qualité de service) . Nous déclinons différentes modélisations et des extensions étudiées de manière exacte sur de modestes instances. Les métaheuristiques GRASP et Tabou permettent d'obtenir de bonnes solutions sur des instances plus grandes. Nous utilisons pour cela la "géodésique", une description particulière de circuit. La résolution est accélérée en introduisant une fonction objectif auxiliaire. Enfin, nous utilisons une méthode inspirée du schéma de Benders. En annexe, nous formalisons des schémas de conception de composants logiciels flexibles et performants avec la programmation générique. Nous présentons aussi le couplage par enrichissement, entre optimisation et simulation.

Cette thèse d'Habilitation à Diriger des Recherches revient sur une dizaine d'années de contributions théoriques et pratiques à l'optimisation combinatoire, contributions dont le domaine d'application privilégié est l'optimisation des systèmes de télécommunications (principalement les autocommutateurs pour la téléphonie cellulaire) et informatiques (en particulier les architectures de processeur parallèles, dites multi-cœurs). Ces travaux se caractérisent également par la résolution bout-en-bout de nombreux cas d'applications industriels concrets et difficiles, de la modélisation mathématique initiale jusqu'à la mise en œuvre d'algorithmes de résolution opérationnels en passant par les développements théoriques nécessaires à leurs fondements.

Ce travail de thèse de doctorat traite de l'étude d'un problème d'ordonnancement NP-difficile au sens fort à contraintes de ressource : le problème de la programmation des déplacements de processus. Ce problème, issu de l'industrie des télécommunications, est lié à l'opérabilité de certains systèmes temps réel répartis à haute disponibilité tels le BSCe3, un autocommutateur pour la téléphonie cellulaire commercialisé par Nortel.<br />En quelques mots, ce problème consiste, étant donnée une répartition arbitraire admissible de processus sur les processeurs d'un système réparti, à trouver une séquence d'opérations (migrations de processus sans effet sur le service ou arrêts temporaires) de moindre impact par le biais de laquelle une autre répartition arbitraire, et fixée à l'avance, peut être obtenue. La principale contrainte réside dans le fait que la capacité des processeurs du système ne doit pas être dépassée durant la reconfiguration.<br />Nous avons abordé ce problème d'ordonnancement sous différents angles. Tout d'abord, nous avons établi son caractère NP-difficile au sens fort et exhibé quelques cas particuliers polynomiaux. Puis, sur le plan de la résolution exacte dans le cas général, nous avons conçu deux algorithmes de recherche arborescente : le premier trouve ses fondements dans l'étude de la structure combinatoire du problème, le second dans des considérations polyédrales. De nombreux résultats expérimentaux illustrent la pertinence pratique de ces deux algorithmes. Enfin, en raison des contraintes imposées par le caractère temps réel de notre application industrielle, nous avons mis au point un algorithme efficace de résolution approchée basé sur la métaheuristique du recuit simulé et, en capitalisant sur nos travaux en résolution exacte, empiriquement vérifié sa capacité pratique à produire des solutions acceptables, en un sens bien défini.