101011001001101

Accueil > Enseignement > Cours gratuits > Optimisation et algorithmes génétiques > Convergence de l’AG

Convergence de l’AG

vendredi 7 juillet 2006, par Vincent MAGNIN

Convergence et temps de calcul

On peut constater figure 11 que l’amélioration de la population est très rapide au début (recherche globale) et devient de plus en plus lente àmesure que le temps passe (recherche locale) . Le bruit dans la moyenne est essentiellement dà» aux mutations.

Figure 11
Exemple de convergence de l’AG. On a reporté la valeur de la fonction d’adaptation de l’individu le plus adapté de chaque génération (trait), et la moyenne des fonctions d’adaptation (pointillés), pour une population de 200 individus.

On voit que la valeur moyenne de la fonction d’adaptation a tendance àse rapprocher de celle de l’individu le plus adapté. Cela correspond àune uniformisation croissante de la population. Nous avons donc introduit dans notre logiciel une fenêtre graphique (Figure 12) permettant de visualiser la totalité de la population [Dessales, 1996]. Chaque ligne représente le génotype d’un individu, autrement dit les bits qui conduisent aux valeurs des paramètres d’un composant. Chaque pixel représente la valeur d’un bit dans son chromosome principal (blanc pour 0, et noir pour 1). Chaque groupe de 32 bits, entre deux graduations de la Figure 12, correspond àun gène. Les individus sont triés selon leur fonction d’adaptation : les plus adaptés correspondent aux lignes du haut, les moins adaptés aux dernières lignes. Dans cet exemple, nous avons représenté une population aux générations 1, 3, 10, 20, 50 et 130 (de gauche àdroite, et de haut en bas). La taille de la population est de 200 individus (dispositifs) et le chromosome principal comprend 8 gènes (paramètres) de 32 bits.







Figure 12 : générations 1, 3, 10, 20, 50 et 130. Chaque pixel représente un bit du chromosome principal d’un individu. Optimisation comportant 8 variables et 200 individus.

Ce genre de représentation permet de mieux comprendre le fonctionnement de l’algorithme. Tout d’abord la première image représente la population initiale tirée aléatoirement et ne présente donc aucun motif apparent. Les images suivantes (génération 3, 10 et 20) montrent l’apparition progressive de schémas, ce qui signifie que certaines valeurs des paramètres du composant se propagent dans la population parce qu’elles procurent un avantage aux individus qui en sont porteurs. Sur les deux dernières images (générations 50 et 130), on voit que la population s’est àpeu près uniformisée. L’utilisateur peut alors stopper l’algorithme.

En chargeant le fichier suivant, vous pourrez voir le film entier : charger le film au format AVI (1,3 Mo !) (cliquez sur le bouton droit de votre souris pour télécharger le fichier)

Un des intérêts des AE et AG est que le temps de calcul ne croît pas exponentiellement avec le nombre n de variables, mais plutôt en n.ln(n). D’autre part, ce temps de calcul est proportionnel au temps de calcul de la fonction d’adaptation, donc du modèle utilisé, et àla taille de la population.

Réglage des paramètres de l’AG

Quelle doit être la taille de cette population ? Une population trop petite évoluera probablement vers un optimum local peu intéressant. Une population trop grande sera inutile car le temps de convergence sera excessif. La taille de la population doit être choisie de façon àréaliser un bon compromis entre temps de calcul et qualité du résultat.

Pour le problème qui nous intéressait et avec les moyens de calcul dont nous disposions, nous avons pu constater qu’une population de 100 individus constituait un bon compromis. Nous pouvions ainsi calculer 100 à200 générations en une nuit sur un Pentium Pro 200 MHz.

Mais il faut être conscient que cette taille de population dépend de la puissance de calcul dont on dispose, des méthodes utilisées (sélection, opérateurs génétiques…), du nombre de variables considérées et de la fonction d’adaptation. Si la fonction àoptimiser comporte peu d’optima locaux et un optimum global net, la population nécessaire sera plus petite que dans le cas d’une fonction beaucoup plus compliquée comportant de nombreux optima locaux.

Nous touchons làau délicat problème du réglage des paramètres de l’algorithme. Celui-ci doit être optimisé pour chaque type de problème traité, ce qui constitue une part importante du travail de l’utilisateur. Les caractéristiques de l’algorithme doivent être adaptées àla topologie du paysage dessiné par la fonction (fitness landscape) . L’ensemble problème-méthodes-paramètres constitue donc un tout. En témoigne certaines études où les paramètres d’un Algorithme Génétique sont réglés et optimisés par un autre Algorithme Génétique [Goldberg, 1994]. Dans la pratique, les méthodes et paramètres des AG sont tout d’abord réglés approximativement par tâtonnement avec des fonctions de n variables couramment utilisées pour tester les algorithmes d’optimisation. Le temps de calcul de ces fonctions étant minime, on peut ainsi régler rapidement les paramètres. Nous avons ainsi utilisé une fonction sphérique, une fonction de Fletcher-Powell et une fonction fractale [Bäck, 1996]. Nous avons ensuite réglé plus finement les paramètres en fonction des problèmes traités.


Chapitre suivant