LITA - Laboratoire d'Informatique Théorique et Appliquée - Université de Lorraine
Université de Lorraine - Laboratoire d'Informatique Théorique et Appliquée (LITA)
Université de Lorraine - Site de Metz - Île du Saulcy
57045 METZ CEDEX 1
Tel. : 03 87 31 54 45 - Fax : 03 87 31 53 09

Laboratoire d'Informatique Théorique et Appliquée (LITA)

Equipe "Optimisation, Apprentissage et Algorithmes" (OAA)

Présentation

Les projets scientifiques de l'équipe OAA s'appuient sur la recherche à la fois fondamentale et appliquée, le développement des collaborations au sein de l’équipe et du LITA, des collaborations nationales et une forte ouverture internationale.

Le développement des projets de recherche finalisée au niveau régional, national et international est un des points forts de l'équipe. Celle-ci maintient et renforce une politique de recherche reposant sur le développement des outils théoriques et algorithmiques pour la modélisation et le traitement numérique des problèmes concrets de la vie courante avec le souci constant de leurs applications aux problèmes industriels.

Les activités de recherche visent et viseront l’objectif principal "Optimisation des systèmes complexes", en particulier :

La base des méthodologies de recherche repose sur les compétences complémentaires des thèmes de l’équipe, tandis que les domaines d’applications sont choisies volontairement, d’une part par les besoins de la société et de destinataires de nos recherches, et d’autre part, par les intérêts communs avec nos partenariats.

Actions

Action 1 : développement des nouvelles méthodes performantes d’Optimisation & Recherche Opérationnelle et leurs applications dans les systèmes complexes de grandes tailles.

Optimisation & Recherche Opérationnelle étant le 1er des deux thèmes porteurs de l’équipe, cette action joue un rôle central. Les activités de l’équipe couvrent toutes les branches de l’Optimisation et Recherche Opérationnelle : de l’Optimisation Linéaire à l’Optimisation Non Convexe Non Différentiable et Optimisation Globale en passant par Optimisation Convexe, Optimisation Combinatoire et Optimisation dans les Réseaux.

L'équipe garde le souci constant de les appliquer à la résolution numérique des problèmes concrets industriels dans différents domaines : Transport-Logistique, Télécommunication, Allocations des Ressources, Gestion de Production, Economie & Finance, Vision par Ordinateur & Traitement d'Image, Fouille de données & extraction de connaissance, Génie des Procédés Industriels, Biophysique et Biologie Moléculaire, Génomique, Sécurité informatique (Cryptologie), Mécanique.

Cette démarche privilégie des projets de recherche et des collaborations dans différents contextes : industriel, régional, national et international.

Les points forts de l’équipe portent sur l’Optimisation Globale et ses applications, un domaine très difficile et en pleine explosion un peu partout dans le monde au cours de ces dernières années. Au coeur de l’Optimisation Globale et la programmation non convexe se situent la programmation DC (Différence de deux fonctions Convexes) et DCA (DC optimisation Algorithmes) et leurs applications qui sont intensivement développés au sein de l’équipe et de plus en plus utilisés par des chercheurs et praticiens de par le monde.

De nombreux travaux durant ces dernières années ont montré le grand intérêt et l’efficacité indiscutable de la programmation DC et DCA développés par H.A. Le Thi et ses collaborateurs dans la résolution de plusieurs problèmes de grande taille dans différents systèmes complexes. Sur le plan théorique nous envisageons une étude approfondie sur la convergence de DCA dans les problèmes DC sous-analytiques.

Sur le plan algorithmique nous allons exploiter un nouveau résultat marquant sur la pénalité exacte en programmation DC pour développer DCA à la résolution de plusieurs problèmes d’optimisation combinatoire dont la fonction objectif est non linéaire ou non convexe.

Action 2 : Apprentissage & Fouille de données et leurs applications dans les systèmes financiers, biologiques, de communication et dans les réseaux sociaux.

Apprentissage & Fouille de données constitue le 2eme thème porteur de l’équipe, de par son rôle important dans tous les domaines d’applications. L'équipe OAA travaille dans les quatre grandes lignes suivantes :

  1. La programmation DC et DCA pour différentes thématiques de fouille de données et apprentissage : les outils DC Programming et DCA donnent lieu actuellement à des algorithmes très performants qui sont utilisés par un nombre sans cesse augmenté des chercheurs en Data mining. Nous avons développé DCA, avec grand succès, pour plusieurs modèles de classification non supervisée (clustering), classification supervisée et sélection des variables. Très récemment, une collaboration de H.A. Le Thi et B Conan-Guez a porté sur les cartes auto-organisatrices (SOM), et l'apprentissage de ces modèles SOM par l'algorithme DCA. Une poursuite naturelle de ce travail serait de s'intéresser au problème de la sélection de variables pour les SOM. Un deuxième travail récent en commun de H.A Le Thi, B. Conan-Guez et leur thésard M.C. Nguyen a porté sur la détection de communautés dans des réseaux sociaux (partitionnement de graphes). L'optimisation du critère de partitionnement (critère de modularité) est réalisée par DCA. Suite à ce travail, différentes pistes peuvent être envisagées: adaptation de l'algorithme afin d'opérer une bissection récursive du graphe, couplage de l'algorithme avec des meta-heuristiques, adaptation de l'algorithme afin d'optimiser le critère de modularité organisée (cartes auto-organisatrices adaptées aux données de type graphe). Ces travaux feront partie de la thèse de M.C. Nguyen intitulée « la programmation DC et DCA pour la fouille de données et ses applications aux réseaux sociaux ». Une autre direction est d’exploiter l’efficacité de DCA pour clustering dans le cadre des données évolutives et temporelles. Ceci fait partie de la thèse de M.T. Ta sur « Techniques d’optimisation et de recherche opérationnelle en fouille de données évolutives et temporelles », co-encadrée par H.A. Le Thi et L. Boudjeloud. Toujours dans le cadre de la classification non supervisée, A. Blansché et H.A Le Thi va investir DCA pour la pondération de variables. L'objectif est d'utiliser DCA pour l'optimisation des plusieurs variantes des modèles de K-means et Fuzzy-C-means qui introduisent une pondération des attributs Le but est à la fois d'améliorer l'efficacité des modèles classiques, mais également de simplifier la description des données à traiter pour faciliter l'interprétation des résultats. En apprentissage et classification supervisée, plusieurs collaborations entre H.A Le Thi & son groupe avec l’équipe ABC (Apprentissage et Biologie Computationnelle) du LORIA sont commencées et/ou envisagées : apprentissage par les fonctions linéaires par morceaux via la programmation DC et DCA, DCA pour M-SVM (Multiples séparateurs à vaste marge), … De plus, nous allons développer plusieurs schémas de DCA pour « Compressed Sensing » - une thématique très important attirant l’attention de nombreux chercheurs du domaine de traitement d’image. Ceci fait partie de la thèse de B.T. Nguyen encadrée par H.A. Le Thi.
  2. Méthodes biomimétiques (évolutionnaires) et leur adaptation en vue de résoudre des problèmes en fouille de données dont sélection de variables, clustering, bi-clustering, visualisation. Dans la problématique du bi-clustering, où un groupe d’individus peut être décrit par plusieurs sous ensembles de variables, la collaboration de L. Boudjeloud et A. Blansché vise l’adaptation d’une méthode fondée sur une approche évolutionnaire pour la sélection de variables ainsi que la mesure d’évaluation. Ce qui permettra l’étude de plusieurs groupes d’individus pouvant se chevaucher, contrairement aux sous ensembles de variables pour lesquels on interdit le chevauchement. Son originalité est que les espaces de représentation des classes sont distincts, mais les classes elles-mêmes peuvent s'intersecter. Ainsi, chaque classe est définie dans un sous-espace des données différentes des autres. Cette propriété permettra à terme d'utiliser des algorithmes d'analyse de concepts formels afin de construire un treillis de Galois pour représenter les classes extraites (éventuelle collaboration avec A. Gély). L'interprétation visuelle des résultats obtenus des différentes approches proposées est très importante, l’intégration de la visualisation dans les différents processus de fouille l’est également. Dans ce cadre précis, nous avons développé deux outils interactifs de visualisation (un algorithme génétique semi-interactif et un arbre couvrant minimal sur un graphe représentant les classes empiétante). Nous envisageons dans la suite d’améliorer cette dernière méthode de visualisation pour intervenir dans la partie représentation de classe sous forme de treillis en perspective du bi-clustering.
  3. La troisième ligne, sur un plus long terme, porte sur des méthodes génériques de transformation linéaires ou non linéaires plus complexe que la sélection et la pondération de variables, permettant de traiter des données présentant des relations complexes entre les variables descriptives. Une poursuite de travaux initiés lors du passage de A. Blansché dans l'équipe Orpailleur du LORIA dans le cadre du projet CyWiki est également envisagée. Ces travaux portent sur l'utilisation de méthodes de fouille de données pour l'aide à la réorganisation du contenu d'un Wiki sémantique. Les travaux préliminaires ont suscité des réactions très positives au sein de la communauté du Web sémantique et seront probablement poursuivi en collaboration avec le LORIA.
  4. La quatrième ligne concerne des structures discrètes pour la fouille de données (en particulier graphes et ensembles ordonnés). L'étude des systèmes de classes parcimonieux de F. Brucker a permis de mettre en avant des liens entre les graphes fortement triangulés et les treillis démantelables. Ces résultats permettent une forte assise structurelle et algorithmique aux systèmes de classes parcimonieux, grâce à un transfert de connaissances des domaines des ensembles ordonnés et de la théorie des graphes vers celui de la classification. De même, la structure de treillis est au coeur de problèmes d'informatiques théoriques (ensembles ordonnés) aussi bien que de problèmes de représentation de connaissances. Pour cette structure de treillis, des rapprochements récents avec l’équipe d’Amedeo Napoli (LORIA), autour des notions d'encodage de l'information devront être développés. Les différentes familles d’objets considérées précédemment sont au centre de la problématique de l’extraction et de la représentation de connaissances. Dans la suite, d'autres objets combinatoire étudiés classiquement en théorie des graphes, comme les modules d’un graphe, seront étudiés (intérêt pour les réseaux sociaux). De même, pour traiter la problématique de grands ensembles de données, il devient nécessaire de s’intéresser à des méthodes de décompositions de structures (typiquement un graphe ou un ordre) qui devront être explorées. Dans cette direction, une collaboration avec le thème « Graphes » de D Kratsch (équipe CGL) est envisageable. Les projets associés prévus : un projet émergent CPE Lorraine, un projet ANR, un projet INTERREG.
Action 3 : Conception d'algorithmes parallèles et routage de données dans les systèmes parallèles.

Les systèmes parallèles et distribués (SPD) sont des systèmes informatiques qui doivent leur avènement au développement de deux technologies que sont l'intégration des composants électroniques et la télécommunication. Ce sont en effet des unités de calcul et de stockage de données interconnectées par des réseaux de communication à très haut débit dont les unités de calcul peuvent aller de la simple station de calcul à un calculateur parallèle c'est-à-dire un ensemble de processeurs qui communiquent et coordonnent leurs activités pour la résolution d'un même problème. Les activités de recherche du groupe concernent tous les aspects, aussi bien théoriques qu'applicatifs, des SPD avec en toile de fonds la recherche des modèles mathématiques idoines des problèmes et de leurs méthodes de résolution. C'est à ce titre que nous nous intéressons, outre les problèmes liés aux outils de base pour leur utilisation, à ceux que soulève leur exploitation efficace en tant que moyens de calcul.

En tant que systèmes communicants un des principaux problèmes d'utilisation des SPD est la communication entre nœuds de calcul/stockage et particulièrement le routage des données c'est-à-dire leur acheminement entre nœuds non directement interconnectés. Dans ce cadre nos activités de recherche concernent le routage correct c'est-à-dire avec la garantie de livraison dans des temps finis et efficace c'est-à-dire sur les plus courts chemins des données et ce dans des réseaux d'interconnexion qui peuvent être statiques avec des connexions arbitraires ou régulières et des réseaux d'interconnexion dynamique soit parce qu'utilisant des switches de commutation soit parce que les noeuds sont mobiles et sans autres infrastructures de communication comme les réseaux ad hoc. Dans les réseaux à interconnexion statique les problèmes sous jacents relèvent principalement des problèmes fondamentaux de la théorie des graphes comme les problèmes de cheminement, d'extraction de structures de routage particulières comme les arbres recouvrant de hauteur minimale, les parcours euleriens et les parcours hamiltoniens. Dans les réseaux à interconnexion dynamique ils relèvent plutôt de la théorie des graphes dynamiques et notamment le calcul et la gestion de cliques optimales et d'ensembles de nœuds dominants dans les réseaux à nœuds mobiles appelés également réseaux MANET. Dans les réseaux à interconnexion statique régulière, propres aux calculateurs parallèles, ces problèmes se déclinent en problèmes de routage implicite c'est-à-dire sans tables de routage dont la formulation la plus restrictive la réarrangeabilité à savoir leur capacité à réaliser toute permutation et ce sans interblocage. Dans des réseaux comme les hypercubes il s'agit d'un problème dont la combinatoire en fait un véritable défi. Après avoir montré que pour des classes particulières de permutations le partitionnement par couplages optimaux dans des graphes bipartis sur les hypercubes permet de résoudre efficacement le problème, nos travaux se poursuivent avec les permutations arbitraires. Le but est de montrer que le paradigme de partitionnement par couplages parfaits dans des graphes bipartis convient dans ce cas également permettant ainsi l'unification des différentes méthodes de routage développées dans la littérature.

Comme moyens de calcul nous nous intéressons, outre la parallélisation d'algorithmes séquentiels, à la conception d'algorithmes parallèles et au développement de méthodes, techniques et outils de conception d'algorithmes parallèles pour différentes classes d'architectures parallèles et pour différents domaines d'application. C'est par exemples le cas en CAO avec le problème de la comparaison de pièces, en métallurgie avec la simulation de la recristallisation de grains de métaux et celle du laminage des métaux, en mécanique des matériaux avec la conception de stratifiés et sandwiches et en calcul scientifique avec principalement les problèmes de base de l'analyse numérique. Dans ce dernier cas les activités vont jusqu'à la conception de réseaux réguliers pour les principaux problèmes de l'algèbre linéaire et dont l'intérêt dans les systèmes embarqués est bien connu. Les problèmes théoriques que soulève un tel processus de conception relèvent en général de l'optimisation combinatoire et de manière non exhaustive couvrent des problèmes de pliage de graphes, de placement et de répartition de charges avec la contrainte d'optimiser et le temps de calcul et le nombre de processeurs de la machine idéale d'exécution de l'application. Les projets associés prévus : projet ANR-FNR en collaboration avec Luxembourg

Action 4 : Approximation et optimisation des courbes et surfaces fermées.

Les activités sur ce sujet ont pour objectif principal de s'investir dans les directions suivantes :

  1. L'approximation et l'optimisation des courbes et surfaces fermées et leur applications à l'imagerie médicales. Nous avons introduit un modèle de splines trigonométriques uniforme avec tension pour l'approximation de contours fermées courbes. Nous projetons de le généraliser aux surfaces fermées. L'intérêt est de disposer d'un modèle flexible pour manipuler ce type de surface tel le coeur, le poumon. Ce projet s'intègre dans le PHC Volubilis « Segmentation, Approximation et Optimisation de courbes et surfaces fermées : applications à l’imagerie médicale » soumis par notre laboratoire en collaboration avec l'Université d'Oujda (Maroc), l'Université de Tizi-Ouzou (Algérie), l'Université d'Orléans, l'INSA de Rouen (France) et l'Université de Grenade (Espagne).
  2. Les modèles splines pour l'optimisation globale : si durant ces 4 dernières années nous avions l'ambition d'utiliser de nouvelles techniques d'optimisation pour résoudre des problèmes issus de la reconstruction de surfaces optimales, notre projet dans les 5 années qui viennent vise à exploiter les modèles splines pour l’optimisation globale. Cette démarche est motivée par le rôle important indiscutable des méthodes d’optimisation globale dans différents domaines d’application et la nouveauté de l’utilisation de l’approche géométrique en optimisation globale. Nous avons pour projet d'intégrer les modèles splines largement répandus dans le domaine de l'approximation pour la résolution des problèmes d'optimisation. En effet, le réseau de contrôle est une approximation grossière des polynômes. En manipulant le réseau de contrôle par des subdivisions successives, nous évitons le coût de l'évaluation d'un polynôme de degré élevé.
  3. Dans une collaboration interne, nous projettons de paralléliser en collaboration avec les chercheurs en Systèmes Parallèles et Distribués deux algorithmes de recherche des zéros d'un polynômes dans la base Bernstein développés dans nos récents travaux.
Action 5 : Modélisation et Simulation des systèmes physiques complexes.
Zakari A. poursuit ses activités, en collaborations avec les collègues au Maroc sur :
  1. Modélisation multiple d’un même objet physique (multi-modélisation) (collaboration avec laboratoire LISER (Laboratoire d’Informatique, Systèmes et Energies Renouvelables) de l’ENSEM –Université Hassan II de Casablanca.
  2. Modélisation et simulation des systèmes hybrides (en collaboration avec le laboratoire LISER de l’ENSEM de Casablanca et l’INPT (Institut National des Postes et télécommunication) de Rabat).
  3. Modélisation et simulation dans les systèmes de transport et systèmes hospitaliers (en collaboration avec le LISER de l’ENSEM de Casablanca et l’université de Khouribga.
  4. Projet de recherche

    Le projet de recherche de l'équipe se partage en trois composantes : recherche fondamentale, recherche appliquée et transfert de technologie (recherche finalisée). La recherche fondamentale concerne principalement le thème "Optimisation globale" qui a pour but de déplacer les frontières de la connaissance via les nouveaux résultats théoriques et les nouvelles méthodes d’optimisation, et la thématique "Fouille de données et apprentissage par l’approche d’optimisation" via les méthodes innovantes pour diverses branches de la fouille de données et l’apprentissage. Le transfert de technologie (préparation des réponses directes à des enjeux sociaux ou économiques) est lié au thème central de l’équipe "Modélisation, Optimisation et Simulation des systèmes complexes". La participation à l’acquisition de connaissances ouvrant la voie à des applications identifiées concerne tous les thèmes de l’équipe.

    Les principaux destinataires directs de nos projets sont le monde de la recherche d’une part et les acteurs sociaux économiques d’autre part. Par ailleurs, certains thèmes de l’équipe pourraient utiliser les produits d’autres thèmes : une bonne partie de nos nouvelles méthodes d’optimisation sont destinées à la fouille de données et l’apprentissage, certaines d’autres seront utilisées dans les systèmes parallèles et distribués, les outils de courbes et surfaces sont développés pour l’optimisation globale, et de l’autre côté, les algorithmes parallèles et distribués seront développés pour la résolution des problèmes d’optimisation et ceux de courbes et surfaces, ...

    La partie originale innovante à fort caractère de transfert technologique du projet concerne les outils théoriques et algorithmiques développés au sein de notre équipe (en particulier la Programmation DC et DCA). Les fortes retombées scientifiques de ce projet se situent dans le cadre très vaste des différents systèmes complexes : les nouveaux algorithmes performants permettraient le traitement numérique des problèmes de très grande taille dans le cadre de masse de données, de systèmes de communication, transport-logistique, manufacturing, mécanique, biologique, CAO ; l’hybridation de différentes approches ainsi que l’utilisation des calculs parallèles & distribués devraient accélérer la rapidité des algorithmes et augmenter encore la taille des problèmes réels traitables jusqu’à ce jour.

    Comme résultats escomptés, ce projet mettrait à la disposition des professionnels un ensemble de logiciels (plus performants que ceux existants) capables d’atteindre des dimensions réelles très grandes dans différents systèmes cités en haut. Il devrait également fournit au monde de la recherche des nouveaux outils théoriques et algorithmiques plus efficients que ceux existants pour la résolution des problèmes complexes.

    Membres

    Responsable

    Sakho Ibrahima ibrahima.sakho@univ-lorraine.fr responsable équipe OAA

    Membres permanents

    Personnel e-mail Fonction Equipe
    Jung Jean-Pierre jean-pierre.jung@univ-lorraine.fr Professeur des universités OAA
    Le Thi Hoai An hoai-an.le-thi@univ-lorraine.fr Professeur des universités OAA
    Sakho Ibrahima ibrahima.sakho@univ-lorraine.fr Professeur des universités OAA
    Damel Pascal pascal.damel@univ-lorraine.fr MCF Associé OAA
    Blansché Alexandre alexandre.blansche@univ-lorraine.fr MCF OAA
    Boudjeloud-assala Lydia lydia.boudjeloud-assala@univ-lorraine.fr MCF OAA
    Conan-Guez Brieuc brieuc.conan-guez@univ-lorraine.fr MCF OAA
    Gély Alain alain.gely@univ-lorraine.fr MCF OAA
    Michel Dominique dominique.michel@univ-lorraine.fr MCF OAA
    Zakari Abdelouahed abdelouahed.zakari@univ-lorraine.fr MCF OAA
    Zidna Ahmed ahmed.zidna@univ-lorraine.fr MCF OAA

    Membres non permanents

    Personnel e-mail Fonction Equipe
    Le Hoai Minh Post Doctorant OAA
    Nguyen Thi Bich Thuy Post Doctorant OAA
    Ta Minh Thuy Post Doctorant OAA
    Aaid Djamel Doctorant (Co-tutelle) OAA
    Noui Amel Doctorant (Co-tutelle) OAA
    Yagouni Mohamed Doctorant (Co-tutelle) OAA
    Ho Vinh Thanh Doctorant OAA
    Louhi Ibrahim Doctorant OAA
    Nguyen Thi Minh Tam Doctorant OAA
    Phan Duy Nhat Doctorant OAA
    Tran Thi Thuy Doctorant OAA