Algorithme Bien choisir ses fonctions - manuel impratique - Etant donné un carré de côté 4 contenant 15 carrés numérotés pouvant coulisser les uns contre les autres, comment arriver à une configuration fixée à partir d'une configuration donnée ? Il s'agit dans un premier temps de convertir le problème algorithmique en problème analytique. Pour ce faire, considérons une fonction f de l'ensemble E des configurations possibles dans un ensemble F telle que : - l'ensemble F soit totalement ordonné - l'ensemble image de E admette un plus petit élément - l'image réciproque du plus petit élément soit la configuration à laquelle on veut arriver Le problème se réduit à présent à la construction de proche en proche d'un minimum de f. De la nature de f va bien sûr dépendre la difficulté d'optimisation (i.e. recherche et construction d'un minimum) : - une fonction peu subtile donne une surface multimodale ex : f(C) = "nombre de carrés mal placés" - une fonction déjà plus élaborée donne des surfaces plus lisses ex : f(C) = "somme du nombre de carrés séparant tout nombre de sa place voulue" - enfin, certaines fonctions sont particulièment appropriées... mais présentent quelques difficultés de calcul ex : f(C) = "nombre de mouvements séparant C de la configuration voulue". On peut bien évidemment exiger d'autres propriétés à la fonction f que celles que nous imposons, en général : - continuité (ce qui suppose la définition d'une topologie autant dans E que dans F) - considérer une fonction F de ExE dans F qui soit un écart, voire une famille d'écarts pour en considérer la limite uniforme... Revenons au problème de la construction de solutions approchées et de leur amélioration à l'aide de la fonction f. Nous avons parlé de surfaces... ce qui laissait entendre que E -l'ensemble des configurations possibles- était de dimension entière ; il n'en est pas tout à fait ainsi : Dans notre cas précis, on peut définir quatre fonctions de succession (haut, bas, gauche et droite) ou transformations de E ; on dira donc qu'une configuration A est le successeur en haut de B si l'on passe de B à A en poussant un carré vers le haut. (On rappelle qu'étant donnée une configuration, il y a au plus quatre mouvements possibles et au moins deux). Ces fonctions ont l'avantage d'être presque définies sur E et d'être presques bijectives (mais on ne s'intéressera pas aux cas limites). On s'assure que l'on peut aller de toute configuration à une autre par composition des fonctions de succession et de leur fonctions réciproques... bref, que l'on peut parcourir convenablement l'espace E. Attention, digression droit devant ! C'est la plupart du temps tout simplement FAUX! et c'est d'ailleurs le problème du pousse-pousse: il est impossible de retrouver la "configuration naturelle" à partir de la configuration de départ donnée par son inventeur... La seule chose dont on est sûr est que l'on ne pourra atteindre que les configurations de la fermeture réflexive-transitive de la configuration initiale pour les transformations permises... Cela revient finalement à considérer l'ensemble L* des mots à valeurs dans un alphabet L de même cardinal que l'ensemble des transformations permises (et éventuellement leurs réciproques si elles sont définies à peu près correctement), enfin une application de L x E dans E dite fonction d'accessibilité... en n'oubliant pas de retirer de L les mots qui n'ont pas d'image... bref, encore une histoire d'automates, de langages reconnus, et ce n'est pas notre propos aujourd'hui. Quant à la représentation de la fonction d'accessibilité, dans le cas le plus général on peut la représenter comme un arbre min-max pondéré par F (où min est le nombre minimal de transformations réalisables à partir de toute configuration, max le nombre maximal), c'est-à-dire un arbre où chaque sommet a au moins min fils et au plus max. Il existe à ce stade déjà de nombreux algorithmes qui pourraient être applicables pour la recherche d'éléments donnés, mais elles exigent des connaissances non nulles en informatique contrairement à la méthode plus loin exposée. Dans certains cas particuliers, on peut trouver des représentations plus efficaces ; si le problème du pousse-pousse avait été commutatif (c'est une condition suffisante), on aurait pu plonger notre arbre dans un espace vectoriel à quatre dimensions (d'où l'expression recherche de minima de la surface... car on s'y ramène dès que possible). Enfin, le calcul des fermetures d'un ensemble pour un certain nombre de transformations fait partie des problèmes qui commencent à être algorithmiquement intéressants. Mais bien plus intéressante encore est la question de savoir si toutes les transformations qui sont permises sont nécessaires... En effet, interviennent alors les notions de monoÔde libre (plus généralement magma libre) et de décompositions réduites... (bref, enfin de la véritable informatique...) Essayons d'en donner une image plus tangible, quand vous réordonnez un Rubix Cube, il y a un très grand nombre de transformations possibles (toutes les permutations) mais vous n'en utilisez qu'un certain nombre (décomposition de la permutation initiale-finale en une suite de permutations réalisables concrètement : "un mot"), enfin les meilleurs algorithmes sont ceux qui n'introduisent pas trop de permutations élémentaires (pour retenir aisément "l'alphabet") tout en ayant un nombre de mouvements à faire réduit (réduction d'un mot en un mot équivalent (i.e. tel que l'image par la fonction d'accessibilité soit identique) mais d'une "longeur" inférieure). Méthodes d'optimisation de fonctions Il existe -vous vous en doutez -une multitude de méthodes pour trouver le minimum d'une fonction ; elles seront plus ou moins efficaces selon la forme générale de la surface ; en voici quelques-unes : - minimisation par dérivation Quand la fonction est toute gentille (par exemple un cône) celle-ci est certainement la méthode qui aboutit le plus rapidement au minimum. Il suffit de prendre un point au hasard, de calculer la dérivée de la fonction dans le voisinage de ce point (il faut entendre ici voisinage comme ensemble des successeurs) et de réitérer l'opération à partir du point du voisinage dont la dérivée sera la plus petite... - minimisation par dérivation et saut aléatoire Parfois les fonctions ne sont pas aussi aimables que l'on aimerait : il suffit de considérer deux cônes côte à côte, l'un d'eux plus haut et à base plus étroite. En utilisant la méthode précédente, vous aboutirez la plupart du temps dans le petit cône. On appelle cela un problème de convergence précoce. Comme nous ne manquons pas d'informaticiens malins, ceux-ci ont eu l'idée d'introduire une notion assez douteuse qu'est celle de saut : au bout d'un certain temps, votre point -au lieu d'aller vers le point du voisinage de dérivée minimale- saute d'une distance aléatoire dans une direction tout aussi aléatoire, et le processus initial est repris. - minimisations par méthodes stochastiques A vrai dire, nous ne nous souvenons pas même du principe... Ce doit encore être un truc fumeux avec de l'aléatoire qui revient aléatoirement de façon aléatoire à des endroits aléatoires... de toute façon, la méthode la plus efficace que l'on connaisse dans les cas les plus généraux (et nous en devons la preuve à De Jong) et celle des algorithmes génétiques. - minimisation à l'aide d'un algorithme génétique De manière très globale, un algorithme génétique se déroule en trois étapes fondamentales : On commence par se donner "une population aléatoire" c'est-à-dire un ensemble de mots à valeurs dans L. On évalue la "population", c'est-à-dire qu'on lui applique la fonction d'accessibilité puis f (généralement composée ensuite avec d'autres fonctions suivant des critères annexes... généralement exp et ln...) qui prend alors le nom de fonction d'adaptation car elle est censée récompenser chaque "individu" selon sa proximité du minimum recherché. On améliore les "individus" existants par "croisement" (il existe de nombreuses méthodes... et de nombreuses théories pour expliquer pourquoi certaines sont meilleures que d'autres...) On les soumet à des UVA (on appelle cela techniquement "mutation"), cela correspond approximativement aux sauts aléatoires des méthodes par dérivation locale. Il s'agit encore d'éviter le phénomène de convergence précoce. On détermine ensuite quelle va-t-être la composition de la "génération" suivante. De fait notre première étape n'est pas considérée comme une étape proprement dite dans les manuels scolaires, autant que cette notion puisse avoir une quelconque signification ! Nous ne pouvons entrer dans le détail des raisons pour lesquelles les algorithmes génétiques sont les plus appropriés pour les recherches d'extrema dans les fonctions peu orthodoxes... Nous recommandons au lecteur désireux de se cultiver de se renseigner à propos des travaux de Holland (et de sa théorie des schémas) tout comme ceux de De Jong. Surtout ne pas poser de questions Dans ce problème, il faut déterminer la trajectoire optimale d'un satellite... il va falloir vous prémunir d'une petite modélisation et résolution du problème à n corps (à un prix très modique dans les laboratiores de recherche spécialisés). Il s'agit donc d'envoyer un satellite sur les trottoirs de Saturne... Il y a bien sûr (au moins) une trajectoire optimale pour ce faire. Donc d'un point purement formel, il s'agit de trouver cette trajectoire, ou, présenté autrement, de construire une trajectoire qui minimise l'intégrale de la fonction e = | fo(x) - f(x) | c'est-à-dire la fonction d'erreur... ce qui peut sembler au premier abord assez difficile puisque nous méconnaissons la trajectoire optimale fo. Introduisons donc des variables auxiliaires (ici l'intuition jouera grandement, mais pour les problèmes difficiles il est souvent plus sain de laisser place à l'intuition qu'à la réflexion, du moins pour le commun des mortels) : -nous allons prétendre que notre satellite possède deux moteurs (ce qui n'est pas si faux) dirigés suivant x et y respectivement (et à tout instant). - nous allons discrétiser le problème aussi bien spatialement que temporellement. - nous allons définir notre alphabet à savoir la quantité de combustible consommée par un moteur à un instant t (disons entre 0 et 256 pour simplifier) - nous allons définir notre fonction d'accessibilité c'est à dire une fonction qui, à partir de notre modèle de problème à n corps et le vecteur propulsion, calcule le point où sera le mobile à l'instant suivant, puis son prolongement de l'ensemble des mots dans l'ensemble des positions. - nous allons définir la fonction d'adaptation à savoir somme sur le temps du carburant consommé (plus une pénalité infinie pour les trajectoires dont la limite quand le temps tend vers l'infini n'est pas un quelconque trottoir de Saturne) On applique un algorithme génétique, et le tour est joué. Le cas était relativement simple : nous savions avec assez de précision quelle fonction nous étions en train d'optimiser ; il y a des cas où cela est nettement moins facile... pour ne pas dire dans lesquels nous n'avons pas la moindre idée de la fonctions sous-jacente au problème, pas plus que les variables pertinentes à sa description. On peut néamoins mettre des algorithmes génétiques en oeuvre tant que l'on peut juger le résultat final. C'est pour cela que ces algorithmes sont sans relâche utilisés en intelligence artificielle et d'autres domaines où la compréhension des phénomènes reste limitée. Vous pouvez par exemple créer une mémoire associative distribuée (comprendre réseau neuronal bien que d'autres modèles existent) -c'est-à-dire une fonction qui chaque fois que vous lui présentez une image tente de lui associer une étiquette générique- sans avoir la moindre connaissance dans le domaine : il suffit de créer des fonctions au hasard et de sélectionner celles qui répondent le plus souvent juste aux séries-test que vous leur soumettez... là vous minimisez clairement une fonction d'erreur par rapport à la réponse type, mais quant à en connaître ne serait-ce que les paramètres pertinents sans étude mathématique approfondie...

Une résolution plus orthodoxe du problème du jeu de Taquin : i) Le nombre de configurations possibles est fini, tout comme le nombre de transformations autorisées. On peut donc construire un graphe dont les sommets seront les configurations et les arcs les mots à valeur dans l'alphabet des transformations (au fait, le nombre d'arcs du graphe risque d'être infini, mais comme au bout d'un certain moment on atteint toutes les configurations et qu'au delà les mots sont de longueur strictement supérieure, on peut s'arrêter) ii) On pondère tous les arcs par le nombre de lettres du mot qui leur est associé. iii) On construit un arbre couvrant des chemins minimaux (par un algorithme de Dijkstra par exemple puisque tous les coefficients sont positifs) iv) On identifie la configuration à laquelle on veut se ramener (par un parcours par exemple) et on suit le chemin (unique) dans l'arbre couvrant précédemement construit. L'algorithme (mis à part la construction du graphe) se fait donc en un temps équivalent à max( |arcs|, |sommets| log |sommets|).

Qui veut la peau des tangles rationnels ? Cet exemple de problème où il existe une fonction miracle (calculable de surcroît) qui permet de résoudre très facilement un problème de núuds est dû à Conway : On appelle tangle rationnel tout núud obtenu à partir d'une position initiale (en =) de deux brins de ficelle par torsion (de deux bouts, disons ceux de droite) et rotations d'angle p/2 du tout. Deux tangles rationnels sont considérés comme égaux s'ils découlent l'un de l'autre par des transformations laissant invariantes les quatre extrémités. Maintenant, étant donné un tangle rationnel, démèlez-le ! Conway propose de considérer l'application qui à tout tangle rationnel lui associe un rationnel n (nul en position initiale) tel que : - pour toute torsion, n est incrémenté de 1 - pour toute rotation, n prend la valeur -1/n n est bien sûr dit le nombre de Conway... Le lecteur attentif a tout de suite remarqué que l'application en question est une bijection dans Q, et que l'algorithme de minimisation est trivial... Par ailleurs, le calcul de ce nombre pour un tangle quelconque n'est pas bien difficile bien que nous n'exhibions pas de méthode. Nous aimerions surtout la méthode pour trouver d'aussi belles fonctions. Avis aux lecteurs !

Virus - trimestriel du lycée Louis-le-Grand - Novembre 98