\chapter{Problème discret : les phrases réflexives}

\section{Description du problème}

Le  problème que  nous  allons essayer  de  résoudre est  celui des  phrases réflexives. Une phrase réflexive est  définie comme une phrase annonçant le nombre de lettres ou de chiffres qu'elle contient.
\begin{quote}
  Il y a 6 poules et 1 coq  dans le poulailler. Dans cette phrase il y a: 1 0, 7 1, 4 2, 1 3, 2 4, 1 5, 2 6, 2 7, 1 8, 1 9.
\end{quote}

La phrase ci-dessus est une phrase réflexive comptant les chiffres. La phrase est composée de deux  parties, la première partie introduit le contexte et peut être considérée comme une initialisation. C'est la partie statique de la phrase. Dans notre cas c'est: \textit{Il y a 6 poules et 1 coq dans le poulailler}. La deuxième partie annonce le décompte des chiffres.

Un \emph{coefficient} désigne le nombre de fois qu'apparaît un chiffre, par exemple dans la phrase d'exemple 7 a pour coefficient 2.

Le but de notre programme est de trouver une solution au problème pour une initialisation donnée.

\section{Rappels sur les algorithmes génétiques}

Les algorithmes génétiques se sont inspirés du fonctionnement de l'évolution des espèces.

L'algorithme est basé sur la manipulation d'une population, c'est à dire d'un ensemble d'individus. Chaque individu est caractérisé par un génome et représente une solution au problème.

Le génome est un vecteur de gènes. La taille de ce vecteur et la forme des gènes sont dépendantes du problème. Par exemple, pour le problème du voyageur de commerce, chaque gène représenterait une ville à visiter, et la taille du génome serait le nombre de villes à visiter.

On doit aussi avoir une fonction appelée \emph{fitness}, qui est fonction du génome, et que l'algorithme cherchera à maximiser. La plupart des problèmes sont à la base des problèmes de minimisation de fonctions (fonctions d'erreur très souvent), mais il est très simple de transformer la fonction à minimiser pour en faire une fonction fitness ($\frac{1}{f(x)}$, par exemple).

A l'initialisation de l'algorithme, on crée N individus pour former la population. Ces individus peuvent être générés au hasard ou selon certaines heuristiques, selon le problème, afin de faciliter la convergence.

Ensuite, chaque génération (itération de l'algorithme) comporte deux phases : la diversification et la sélection.

\subsection{Diversification}
Durant cette phase, l'algorithme crée de nouveaux individus par \emph{cross-over} ou par \emph{mutation}. La taille de la population augmente de M, le nombre d'individus créés.

Le \emph{cross-over} (croisement) prend deux individus et les mélange pour en fabriquer deux nouveaux. Typiquement, il utilise un ou deux pivots sur les génomes des parents, et fabrique les enfants en alternant les génomes des parents.

La \emph{mutation} fabrique un enfant à partir d'un parent. Elle est indispensable à la convergence de l'algorithme, sans elle la plupart du temps, on ne peut pas couvrir tout le domaine des solutions.

En général, elle se contente de copier chez l'enfant le génome du parent en en altérant un gène.

La mutation est appliquée en général avec une probabilité moindre que celle du cross-over.

\subsection{Sélection}
Après la phase de diversification, la sélection a pour but de réduire la taille de la population pour qu'elle redevienne la même qu'au début de l'algorithme. Pour ça on choisi un à un N individus parmi les N+M individus disponibles, sans remise et avec une probabilité fonction  du \emph{fitness} de l'individu : plus l'individu était bon, meilleures sont ses chances d'être conservé.

Deux mécanismes spéciaux sont couramment utilisés durant la phase de sélection : l'élitisme oblige le meilleur individu de la population à être sélectionné pour passer à la génération suivante, et la diversification empêche que trop d'individus  soient identiques au sein d'une même population.

\subsection{Récapitulatif des paramètres}
Pour chaque problème que l'on voudra résoudre à l'aide d'un algorithme génétique, on aura donc besoin de donner les paramètres suivants :

\begin{itemize}
  \item Taille du génome, type des gènes.
  \item Fonction de fitness. (ou d'erreur, et la transformer)
  \item Nombre maximal de génération.
  \item N : Taille initiale de la population.
  \item M : Nombre d'individus générés à chaque génération.
  \item Probabilité d'effectuer une mutation plutôt qu'un cross-over.
  \item Utilisation de l'élitisme (vrai ou faux).
  \item Utilisation de la diversification (vrai ou faux).
  \item On pourra aussi vouloir  redéfinir les opérateurs de mutation et de cross-over.
\end{itemize}

\section{Implémentation}

Notre algorithme génétique est codé en java. Un individu (Biomorph en anglais) est représenté par une classe abstraite. Pour coder notre problème particulier, nous avons donc eu à dériver cette classe.

\subsection{Initialisation de la population}
Les premiers individus créés par l'algorithme ont un génome généré au hasard. La seule règle à suivre est que la valeur d'un gène est supérieure ou égale à la valeur de l'initialisation, afin de ne pas sortir du domaine de définition.

\subsection{Choix des paramètres}
Pour paramétrer l'algorithme, nous avons fait les choix suivants :
\begin{itemize}
  \item Le génome représente une solution : dans notre cas c'est donc un vecteur d'entier. Sa taille est de  dix (nombre de chiffres en décimal).
  \item La fonction de fitness est fabriquée 'artificiellement' à partir de la fonction d'erreur (cf plus bas).
  \item La taille de la population et le nombre d'individus générés à chaque itération sont fixés par l'utilisateur au lancement de l'algorithme, ainsi que la probabilité des mutations. Cela permet de faire plus facilement des tests pour ces paramètres.
  \item Le nombre maximal de générations peut être fixé par l'utilisateur. Sinon il peut choisir de faire tourner l'algorithme jusqu'à ce qu'il trouve une solution optimale.
\end{itemize}

\subsection{Fonction d'erreur}
La fonction d'erreur que nous avons choisi est la somme des carrés des erreurs de chaque gène :
$$
  erreur(\textrm{g\'enome}) = \sum_{i=1}^{\textrm{g\'enome}.\textrm{taille}}(\textrm{g\'enome}[i] - \textrm{r\'eelles}[i])^{2})
$$

Avec $\textrm{r\'eelle}$ un vecteur de même taille que le génome et qui contient le nombre réel de chaque chiffre (ou lettre) de la phrase représentée par l'individu.

Cette fonction d'erreur est bien sûr à minimiser. Notre fonction fitness vaut donc:

$$fitness(\textrm{g\'enome}) = \frac{1}{erreur(\textrm{g\'enome}) + 1}$$

Le '$+1$' étant là uniquement pour éviter une division par zéro quand la solution est optimale ($erreur = 0$).

\subsection{Opérations sur le génomes}
Nous n'avons pas touché sur ce problème à l'opérateur de cross-over. Il effectue l'opération basique en utilisant un pivot.

Pour la mutation, nous altérons un gène au hasard en lui ajoutant ou retirant un nombre aléatoire entre 1 et une constante. (Cette constante peut valoir 1...). Cette opération est effectuée évidement dans la limite du domaine du problème (par exemple, pas de nombres négatifs).

\section{Résultats obtenus}

\subsection{Résultats des tests}
Dans cette partie, nous nous proposons de montrer les résultats obtenus sur ce problème, en fonction des différents paramètres donnés à l'algorithme.

Les tests que nous avons effectués ne comporte pas de phrase d'initialisation, mais les résultats avec ou sans initialisation sont sensiblement identiques.

Nous avons pour chaque test lancé vingt fois l'algorithme avec les mêmes paramètres. Les valeurs de nos résultats sont la moyenne des résultats des vingt exécutions.

Le tableau suivant montre pour un certains nombre de combinaisons de parametres les résultats de l'algorithme : le nombre de générations moyen qu'il a fallu pour trouver le résultat et le nombre moyen d'individus qui ont été créés pour y parvenir.\\

\begin{center}
\begin{tabular}{|c|c|c|c|c||c|c|c||c|}
\hline
N & M & E & D & P(m) & G moy & G max & G min & I \\
\hline
200 & 200 & oui & oui & 0.2 & 94.35 & 156 & 22 & 18870 \\
200 & 200 & non & oui & 0.2 & 89.1 & 207 & 33 & 17820 \\
200 & 200 & oui & oui & 0.4 & 74.6 & 131 & 21 & 14920 \\
200 & 200 & oui & oui & 0.6 & 56.1 & 97 & 20 & 11220 \\
200 & 200 & non & oui & 0.6 & 59.05 & 107 & 31 & 11810 \\
50 & 200 & oui & oui & 0.2 & 166.7 & 424 & 31 & 33340 \\
200 & 50 & oui & oui & 0.2 & 388.4 & 649 & 210 & 19420 \\
50 & 50 & oui & oui & 0.2 & 444.15 & 1177 & 154 & 22207.5 \\
50 & 200 & oui & oui & 0.6 & 64.9 & 173 & 11 & 12980 \\
200 & 50 & oui & oui & 0.6 & 197.1 & 358 & 71 & 9855 \\
50 & 50 & oui & oui & 0.6 & 169.65 & 370 & 53 & 8482.5 \\
100 & 100 & oui & oui & 1 & 64.25 & 102 & 24 & 6425 \\
100 & 100 & non & oui & 1 & 63.55 & 124 & 31 & 6355 \\
\hline
\end{tabular}
\end{center}

avec :
\begin{enumerate}
\item[\textbf{N}:] Taille de la population initiale.
\item[\textbf{M}:] Nombre d'individus créés par génération.
\item[\textbf{E}:] Utilisation du mécanisme d'élitisme.
\item[\textbf{D}:] Utilisation du mécanisme de diversification.
\item[\textbf{P(m)}:] Probabilité de mutation.
\item[\textbf{G moy}:] Nombre moyen de générations effectuées pour arriver au résultat.
\item[\textbf{G max}:] Nombre maximal de générations effectuées pour arriver au résultat.
\item[\textbf{G min}:] Nombre minimal de générations effectuées pour arriver au résultat.
\item[\textbf{I}:] Nombre moyen d'individus créés pour arriver au résultat.
\end{enumerate}


\subsection{Conclusions}
On remarque que tous les tests utilisent le mécanisme de diversification. En fait, aucun des tests que nous avons lancé sans ce mécanisme n'a réussi à trouver de bonne solution, ils stagnaient tous avec une erreur de 1. On voit donc l'importance de ce mécanisme. Quand il n'est pas utilisé, tous les individus ont tendance à se regrouper dans un ou plusieurs minima loacaux et ont beaucoup de mal à s'en sortir (s'ils s'en sortent).

Des autres résultats listés ci-dessus, on remarque plusieurs choses : déjà que l'algorithme converge plus vite avec une probabilité de mutation plus forte. Ensuite, on voit que la taille de la population initiale (et donc la taille de la population au cours de l'algorithme) ne doit pas être trop petite, l'algorithme converge moins bien avec une population initiale de 50 individus qu'avec une population initiale de 200 individus. On voit aussi que le mécanisme d'élitisme a tendance à améliorer légérement la convergence.

Au final, l'annalyse des deux derniers tests montre qu'un algorithme génétique n'était peut être pas la meilleure solution pour régler ce problème : le fait de mettre la probabilité de mutation à 1 a considérablement améliorer la convergence. Or cela signifie perdre le principe de la génétique : on n'a plus que des mutations et aucuns croisements. On est alors dans une sorte de recuit simulé avec plusieurs solutions examinées en parallèle. On aurait donc peut être eu intérêt à tenter de résoudre ce problème à l'aide d'un recuit simulé et non d'un algorithme génétique...