Scribd
Importer
255 vues2 pages

Controle Ratt

Le document contient trois exercices portant sur l'optimisation combinatoire et les métaheuristiques. Le premier exercice pose des questions sur les problèmes NP, NP-complets et sur le choix des métaheuristiques. Le deuxième exercice propose de résoudre un problème de plus court chemin. Le troisième exercice traite d'un problème d'affectation résolu avec différentes méthodes.

Transféré par

ayoub benosmane
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
255 vues2 pages

Controle Ratt

Le document contient trois exercices portant sur l'optimisation combinatoire et les métaheuristiques. Le premier exercice pose des questions sur les problèmes NP, NP-complets et sur le choix des métaheuristiques. Le deuxième exercice propose de résoudre un problème de plus court chemin. Le troisième exercice traite d'un problème d'affectation résolu avec différentes méthodes.

Transféré par

ayoub benosmane
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

Centre Universitaire de Mila

Institut des sciences et de la technologie

1ère Master STIC


Année : 2018-2019
Module : d’optimisation combinatoire et métaheuristique

Contrôle de rattrapage
Exercice 1: 6 points
1. Citer les caractéristiques des problèmes de la classe NP.
2. Quelle est la différence entre un problème NP et un problème NP-complet.
3. Dans quel cas on doit s’orienter vers les métaheuristiques pour résoudre un problème donné.
4. Quels problèmes nous essayons d’éviter par l’utilisation des recuits simulés et de la recherche taboue.
5. Nous cherchons à trouver le maximum d’une fonction f (x) sur l’intervalle [0, 2.56] en utilisant un
algorithme génétique. Calculer la taille du chromosome (représentation binaire) dans le cas où x est un
réel avec deux nombre après la virgule.

Exercice 2: 4 points
On cherche à trouver le plus court chemin entre le nœud A et G.
1. Résoudre ce problème par l’algorithme A* et un autre heuristiques.
2. Est-ce qu’on peut confirme que les solutions trouvées sont optimales ou non. h(n0)
50
A
30
20 40
20 B 50 20
C 10 D
70
10 20
E 30
20 F

40 40
G 0

Exercice 3: 11 points (1.5+4+ 2 +2.5)

Soit le problème d’affectation suivant : nous avons n personnes à affecter à n tâches (n=4). Le coût de
l’affectation de la personne i à la tâche j est noté par c ij. Le problème consiste à affecter chaque personne à
une seule tâche de telle manière à minimiser le coût total. Une tâche ne peut être faite que par une seule
personne. La matrice des coûts est la suivante.

Taches T1 T2 T3 T4
Personnes
P1 10 3 8 9
P2 7 5 4 8
P3 6 9 2 9
P4 8 7 10 5
1. En précisant le critère de choix d’un élément de la solution, résoudre ce problème en utilisant
l’algorithme glouton.
2. En choisissant le parcours best-first, appliquer l’algorithme branch and bound pour la résolution de ce
problème. Préciser la méthode de calcule de la borne inferieure pour les deux premiers nœuds dans
l’arbre.
3. Nous considérons que la solution initiale s est (T1P1, T2P4, T3P3, T4P2) et que le voisin
d’une solution est généré par la permutation de l’affectation entre une tache i et une tache (i+1) mod n.
a. Si on utilise la méthode de recuits simulés avec T=10. Calculer pour chacun des voisins de la
solution s la probabilité d’être choisi comme solution& courante.
b. En appliquant la méthode de recherche taboue, donner pour deux itérations différentes l’état de la
liste taboue, l’ensemble N(s) généré, la solution choisie et son évaluation et la meilleure solution.

Vous aimerez peut-être aussi