105 lines
3.2 KiB
TeX
105 lines
3.2 KiB
TeX
\section{Chapitre 4: Au-delà de l’exploration classique}
|
||
\label{sec:ch4}
|
||
|
||
\subsection{Amélioration itérative}
|
||
\label{sec:ch4amelioration}
|
||
|
||
\begin{itemize}
|
||
\item Espace de recherche: configuration complètes
|
||
\item On part d'une configutation complète et on itère pour améliorer la qualité de la solution (optimalité ou satisfaction de contraintes)
|
||
\item Exemple: problème des n reines
|
||
\end{itemize}
|
||
|
||
\subsection{Escalade}
|
||
\label{sec:ch4escalade}
|
||
|
||
\begin{itemize}
|
||
\item À chaque tour, choisis le noeud ayant la meilleure valeur de la mesure de performance
|
||
\item Arrête quand plus aucun successeur n'a de valeur plus grande
|
||
\item Aucune prospection
|
||
\item Problèmes:
|
||
\begin{itemize}
|
||
\item Maximum local
|
||
\item Plateaux
|
||
\item Crête
|
||
\end{itemize}
|
||
\item Solutions:
|
||
\begin{itemize}
|
||
\item Redémarrage aléatoire:
|
||
\begin{itemize}
|
||
\item Point de départ différent
|
||
\item Sauvegarde de la meilleure solution
|
||
\item Solution dépend de la surface d'états:
|
||
\begin{itemize}
|
||
\item Rapide si peu de minima locaux
|
||
\item Lent (exponentiel) si surface en porc-épic
|
||
\end{itemize}
|
||
\item Solution raisonnable obtenue rapidement
|
||
\end{itemize}
|
||
\item Recuit simulé:
|
||
\begin{itemize}
|
||
\item Déplacements perturbateurs
|
||
\item Démonstration: faire rebondir une balle sur une surface en agitant celle-ci.
|
||
\item On commence en agitant fort et on diminue l'intensité.
|
||
\item Algorithme: si successeur est meilleur $\Delta E > 0$, on y va. Sinon, avec une probabilité $e^{\Delta E/T}$, on y va aussi. $T$ est une fonction décroissante du temps ($t \mapsto T$).
|
||
\end{itemize}
|
||
\end{itemize}
|
||
\end{itemize}
|
||
|
||
\subsection{Recherche locale en faisceau}
|
||
\label{sec:ch4faisceau}
|
||
|
||
\begin{itemize}
|
||
\item Choisir k états aléatoirement
|
||
\item Générer leurs successeurs
|
||
\item Arrêter si un but est trouvé
|
||
\item Sinon, choisir les k meilleurs successeurs et recommencer (variante \textsc{ProbCut}, choisir les k successeurs aléatoirement, avec une probabilité proportionnelle à la fonction d'évaluation)
|
||
\end{itemize}
|
||
|
||
\subsection{Algorithmes génétiques}
|
||
\label{sec:ch4algogenetiques}
|
||
|
||
\paragraph{Principes de bases}
|
||
|
||
\begin{itemize}
|
||
\item Un individu fort a plus de chance de survivre.
|
||
\item Deux individus forts donnent généralement des enfants forts
|
||
\item Si l'environnement évolue lentement, les organismes évoluent et s'adaptent
|
||
\item Des mutations surviennent aléatoirement, peuvent être bénéfiques ou mortelles
|
||
\end{itemize}
|
||
|
||
\paragraph{Fonctionnement}
|
||
|
||
\begin{itemize}
|
||
\item Chaînes de bits, expressions symboliques ou programmes
|
||
\item Population initiale séparée en paires
|
||
\item Reproduction (inverser deux sections entre les parents) et mutations (inverser un bit au hasard)
|
||
\item Sélection des enfants avec une fonction d'utilité
|
||
\end{itemize}
|
||
|
||
\begin{figure}[ht]
|
||
\centering
|
||
\includegraphics[width=175px]{algorithme-genetique.png}
|
||
\caption{Algorithme génétique}
|
||
\label{fig:algogenetique}
|
||
\end{figure}
|
||
|
||
\paragraph{Paramétrage}
|
||
|
||
\begin{itemize}
|
||
\item Taille de la population
|
||
\item Taux de mutation
|
||
\item Taux de reproduction
|
||
\item Nombre de générations
|
||
\end{itemize}
|
||
|
||
Se fait habituellement par essais et erreurs
|
||
|
||
|
||
|
||
|
||
|
||
%%% Local Variables:
|
||
%%% mode: latex
|
||
%%% TeX-master: "notes_de_cours"
|
||
%%% End:
|