|
REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET
POPULAIRE
Ministère de l'enseignement supérieur et de la
recherche scientifique
Université M'HAMED BOUGUERRA - Boumerdes
Facultés des sciences
Département d'informatique
LMD
Recherche Bibliographique
Option : MASTER2
Ingénierie de Logiciel et Traitement de l'Information
(ILTI)
Thème
Contribution à la réalisation du
problème d'emploi de
temps par une approche évolutionnaire
Proposé et Dirigé par :
Mme D.HADJIDJ réalisé et
Présenté par : M.Boukerroucha Exposé le
: 10/04/2012
Devant le jury composé de :
Mr BOULIF Université de Boumerdes
Mr BERRICHI Université de Boumerdes
Année universitaire 2012/2013
i
Résumé
Les problèmes d'optimisation combinatoire sont des
problèmes difficiles à résoudre. Ainsi, la nature
discrète des variables forme un espace non dérivable qui rend
inutiles les techniques classiques. Le problème de la production des
emplois de temps appartient effectivement à la famille des
problèmes combinatoires discrets. Il renferme un ensemble d'objectifs
conflictuels, un ensemble de contraintes non linéaires et un nombre de
combinaisons potentielles très élevé. En revanche, un
certain nombre d'institutions académiques produisent encore des emploi
de temps d'une manière manuelle ou semi-automatique ce que rend la
tâche pénible et difficile. L'automatisation peut donc
éliminer les aspects déplaisants de cette tâche. Cette
recherche bibliographique porte sur l'optimisation combinatoire par des
approches évolutionnaires pa-rallèles.Dans un premier temps, les
problèmes d'optimisation combinatoire mono-objectif et multi-objectif
sont décrits d'une manière formelle afin d'en établir les
principales caractéristiques et de présenter certains notions
préliminaires.
Les méthodes qui ont été proposées
pour la résolution de TTP, tels que la recherche Tabou, le recuit
simulé et les algorithmes génétiques ont fait l'objet
d'une revue de la littérature. Afin de faire un lien avec les
méthodes de résolutions multi-objectif, il sera prouvé
qu'un TTP est lui aussi un problème d'optimisation multi-objectif.
Ainsi, notre recherche bibliographique s'est concentrée sur les
différentes techniques d'optimisation multi-objectif envisageables pour
la résolution de TTP d'une manière parallèle. Parmi les
algorithmes évolutifs multi-objectif les plus populaires, ceux de la
famille des algorithmes génétiques NSGA-II de Deb, mecro- GA de
Goldberg et GA|PM de Sorensen et Sevaux et ceux de la famille des algorithmes
utilisent des schémas d'évolution stationnaire SPEA-II de Zitzler
c-MOEA et IBEA de Deb qui sont susceptibles d'être adapté à
des modèles parallèles. La mise en oeuvre d'un PEA dépend
des caractères du problème à traiter. La première
intention sera de lancé le calcule de fitness en parallèle et
donc de trouver un'algorithme parallèle implémentant les
fonctions objectifs. Ceci est parfois demande plus de connaissance en terme de
la programmation parallèle et peut être inabordable face au
caractère de certains fonctions mathématiques. l'idée est
donc de lancé un calcule distribué. Les modèles
adoptés dans cette situation selon notre recherche bibliographique
commence par des simple modèle comme le modèle de distribution
synchrone ou asynchrone et le modèle ni maître ni dieu. Ces
derniers soufrent de certains inconvénients face aux contraintes qu'ils
exigent (contrainte de précédance par exemple). en effet
l'émergence de modèle en îlot qui permet de diviser la
population en sous-population dont chacune s'évolue sur sa propre
processeur permet de donnée un autre aspect aux PEAs, c'est l'aspect de
migration. En fin, le modèle le plus adapté au caractère
des PEAs reste le modèle cellulaire qui permet de distribuer une
population sur l'ensemble des processeurs et d'effectuer les opérateurs
génétique entre voisinages.
ii
| 
