Aperçu des sections

  • Généralités

  • Présentation du cours

    Un problème d'optimisation combinatoire consiste à trouver la solution optimale (la meilleure solution) à partir d'un ensemble fini E de solutions possibles. Le défi majeur est que l'ensemble E contient un nombre énorme de solutions et parcourir toutes les solutions pour trouver la meilleure nécessite des siècles de temps de calcul.

    En mathématiques appliquées et en informatique, les problèmes d'optimisation combinatoire sont problèmes difficiles. En effet, on trouve les problèmes d'optimisation non seulement en informatique et en mathématiques appliquées mais aussi en logistique, en santé, en engineering etc…

    Pour faire face à ces problèmes, il existe plusieurs méthodes dont le but est de trouver une solution de bonne qualité (pas nécessairement optimale) dans un temps de calcul très réduit.

    Dans ce cours intitulé "optimisation combinatoire et métaheuristique", nous allons présenter ces méthodes afin de vous permettre de résoudre les problèmes d'optimisation combinatoire d'une manière efficace.

    Voici la carte conceptuelle de ce cours :


    Carte conceptuelle


    • Informations générales & Fiche-contact

      info-img

      Institut : des Sciences et de la Technologie

      Département: de mathématiques et informatique

      Public cible : 1ère année Master, Spécialité : Sciences et Technologies de l’Information et de la Communication (STIC).

      Intitulé du cours : Optimisation combinatoire et métaheuristique

      Crédit:06

      Coefficient:03

      Durée : 14-16 semaines, avec un VHS = 67.5 heures.

      Horaire: Dimanche: 10h00-12h00

      Amphi : A2

      Enseignant : Cours, TD et TP: Dr. Oualid GUEMRI

      Contact : par email o.guemri@centre-univ-mila.dz.

      Disponibilité : via l’email et je m’engage à répondre dans les 72 heures qui suivent la bonne réception du message (en général c’est moins de 24 heures).


      • Communications

        commu-img

      • Objectifs du cours

        Obj-img


        A la fin de ce cours, vous serez capables de :

        1. Identifier et connaître les problèmes d’optimisation.

        2. Modéliser une solution pour un problème d’optimisation en proposant la structure de données la plus adéquate.

        3. Appliquer une méthode d’optimisation pour la résolution d’un problème d’optimisation.

        4. Concevoir de nouvelles méthodes pour l’optimisation combinatoire.

        5. Analyser le comportement d’un algorithme utilisé pour résoudre un problème.

        6. Évaluer l’efficacité d’un algorithme pour un problème d’optimisation


        • Prérequis

          Avant de commencer ce cours :

          • Il faut avoir de bonnes connaissances en algorithmique et en programmation.

          • Il est recommandé aux étudiants d’avoir des connaissances de base en mathématiques discrètes.


          • Contenu

             - Chapitre 1 :  Introduction à l'optimisation  combinatoire 

                 . La complexité algorithmique 

                 . Classes de problèmes

                 . Optimisation combinatoire : Concepts de base

             - Chapitre 2 :  Les heuristiques 9

                 . Définition générale d'une heuristique  

                 . Codage et représentation de la solution  

                 . Les heuristiques gloutonnes de construction  

                 . Les recherches locales 

            - Chapitre 3 : Les Métaheuristiques

                . Partie 1 : Concepts de base et définitions

                . Partie 2 : Métaheuristiques à base de solution unique 

                  => Recherche tabou

                  => Recuit simulé

                . Partie 3 : Métaheuristiques à base de population de solutions

                  => Algorithme  génétique.

            - Chapitre 4 : 

                . Introduction.

                . La méthode de "branch and bound" (B&B) : Définition.

                . Borne inférieure et Borne supérieure.

                . La méthode de B&B : Eléments de base de la méthode B&B,  Algorithme et illustration de la méthode B&B sur le problème de TSP



            • Chapitre 1 : Introduction à l'optimisation combinatoire

              La première partie de ce chapitre présente la complexité algorithmique ainsi les différentes classes des problèmes (classification des problèmes à base de la complexité). Ensuite, La deuxième partie présente les problèmes d’optimisation combinatoire.

            • Chapitre 2 : Les heuristiques

              Dans le deuxième chapitre, il s’agit d’étudier comment représenter une solution d’un problème et ensuite de présenter les heuristiques gloutonnes de construction et les recherches locales.


            • Chapitre 3 : Les métaheuristiques

              Dans ce troisième chapitre, des différentes métaheuristiques sont présentées, y compris les métaheuristiques à base de solution unique (La méthode de recherche tabou et la méthode de recuit simulé) et les métaheuristiques à base de population de solutions (l’algorithme génétique).


            • Chapitre 4 : Les méthodes exactes

              Dans le quatrième chapitre, les méthodes exactes sont présentées.


            • Test de sortie

            • Bibliographie


              [1] E. A Feigenbaum and J. Feldman. Computers and thought. McGraw-Hill, Inc. New York, NY, USA, 1963.

              [2] I.H. Osman and G. Laporte, Metaheuristics : a bibliography. Annals of Operations Research 63, 513-623, 1996.

              [3] S. Voß, S. Martello, I.H. Osman and C. Roucairol (Eds), Meta-Heuristics - Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands, (1999).

              [4] Kirkpatrick, S., Gelatt, C., et Vecchi, M. Optimisation by simulated annealing. Science, tome 220, n o 4598, pages 671-680, 1983.

              [5] Glover F., 1986. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13, p. 533-549.

              [6] Guemri, O. (2017). Proposition de solutions pour l'optimisation des chaînes logistiques (Doctoral dissertation, Université d’Oran 1).


              • Evaluation du Cours