# quelque question de cours poser #
#Problème NP-Complet
voyageur de commerce
coloriage de graphe
sac-à-dos
SAT satisfiabilité booléenne
Placement
#méthode de résolution exacte :
branche and bound
programmation linéaire
programmation dynamique
#But méthodes d'optimisation
introduire le principe de la résolution d'un probleme donné en utilisant un espace de
recherche. cet espace de recherche permet de recenser les etats d'un systeme donné et de
trouver parmis ces états une ou plusiers solutions
#Structure de base DFS & BFS:
BFS largeur d'abord utilise la structure de file
DFS profondeur d'abord utilise la structure de pile
#donner les deux grande famille des méthodes d'optimisation
Les méthodes stochastique
les méthodes déterministe
#différence entre heuristique et meta-heuristique
l'heuristique donne une solution approximative a un probleme, on ne peut savoir a quelle
point cette solution ce rapproche de la solution optimal. l'heuristique dependent
fortement du probleme posé.
la méta-heuristique donne des solution qui approche la solution optimal, c'est a dire
qu'on peut prouver a quelle point cette solution ce rapproche de l'optimum. en general
les méta-heuristique sont independent du probleme donc général et peuvent etre appliquer
a tout probleme
#différence entre la recherche local et taboue:
la principal difference entre les deux est l'absence de mémoire dans la recherche local,
contrairement a la recherche taboue qui est caracteriser par la presence d'une liste
taboue.
#difference entre la méthode de trajectoire et la méthode basé sur la popualtion :
La Methodes de trajectoire manipulent une seule solution a la fois et tentent
iterativement d’ameliorer cette solution. Elles construisent une trajectoire dans
l’espace des solutions en tentant de se diriger vers des solutions [Link]
Méthodes qui travaillent avec une population de solutions en tout temps on dispose d’une
“base” de plusieurs solutions, appelée population
#representation mathematique
maximiser / minimiser f(n) pour
gi(n) <= 0 pour i€{1..m}
hj(n) = 0 pour j€{1..m}
avec f:R^p --> R : fonction objectif
gi(n) et hj(n) : R^p -> R fonction de contraite
{x€R^p / gi(n) <= 0, hj(n) = 0} ensemble des condidats
#caracterisation d'un probleme d'optimisation
un probleme d'optimisation est caracteriser par un espace d'etats, une ou plusiers
-1-
fonction objectif et un ensemble de contrainte
#difficulté probleme reel
* probleme complexe
- grand nombre de solution possible dans l'espace de recherche (recherche exhaustive
impossible)
- utilisation de modele simple
-> focntion d'evalutation qui decrit la qualité de la solution à trouver
-> plusieurs fonction a trouver
* probleme avec contrainte forte
- construction d'une solution réalisable devient difficile
#Liste Taboue
Pour eviter de boucler sur des solutions deja visité, la liste tabou interdit tout
mouvement conduisant vers ces solutions. ces solutions sont dite non permise où
interdite et sont recensé dans la liste taboue
#carateristique algo evolutionnaire (algo genetique)
- fonder sur des mecanismes de selection naturelle et génétique
- utilise des operateurs evolutionnaire
- ne travaille qu'avec la valeur de la fonction étudiée pas sa deriver ou une
connaissance ameliorer
- utilisent des regles de transitions probabilistes et non deterministe
#algo mimétique
le mimétisme est un algo génétique generalisé dans le quel la recherche local ou bien
une recherche taboue est incorporée
-2-
