L’évolutionnisme pour l’aménagement du territoire

Le concours de la nature à l’intelligence artificielle

 C’est à partir des années 1950 que l’on voit croître un intérêt pour l’étude de la nature et de ses capacités d’adaptation et de reconfiguration vis-à-vis de quelque problème que ce soit. Cette première section est consacrée à une rapide revue de plusieurs techniques existantes (Cornuéjols et Miclet, 2002) dont les algorithmes évolutionnistes, outils de notre étude sur les TAD. Sont ainsi décrits dans un premier temps les réseaux de neurones, les colonies de fourmis, les essaims particulaires, trois techniques majeures de l’intelligence artificielle inspirées de la nature. 

Les réseaux de neurones

Également appelés réseaux neuromimétiques ou encore réseaux connexionnistes, les réseaux de neurones s’inspirent du fonctionnement du cerveau et de ses connexions synaptiques pour produire des modèles capables de tirer des conclusions à partir de données en entrée. Unités de traitement très simples, les cellules nerveuses constituant le cerveau sont par-contre extrêmement nombreuses (environ cent milliards de neurones pour un cerveau humain), et bénéficient d’une interconnexion très dense (aux alentours de dix 90 mille connexions par neurone). Le mécanisme d’apprentissage et le comportement du réseau, issus de cette schématisation, sont déterminés par l’architecture et le nombre de neurones, et leurs connexions. Une connexion entre deux neurones se distingue par son poids, i.e. un arc indiquant le degré d’influence d’un neurone vers un second. La modification des poids de ces connexions revient à modifier la connaissance générale d’un problème, autrement dit à tirer de nouvelles conclusions avec des données identiques en entrée. Initialement, un jeu d’exemples permet de mettre en mémoire ces nouvelles informations. Ainsi, l’apprentissage d’un réseau de neurones se fait par propagation d’informations échangées entre des unités élémentaires aux possiblités restreintes, mais aux interconnexions très développées, permettant de résoudre des problèmes complexes. Le neurone formel Les données d’entrée sont des vecteurs x = (x1, …, xn) de R n . Nous nous intéressons aux réseaux multicouches. Description : Un neurone formel n’est capable que de quelques opérations élémentaires. Dans un réseau, les neurones sont classés selon trois types : – les neurones d’entrée prenant en charge le vecteur initial x 0 , et constituant la couche d’entrée ; – les neurones de sortie fournissant des hypothèses d’apprentissage. C’est la couche de sortie ; – les neurones cachés, n’étant ni des neurones d’entrée, ni des neurones de sortie. État : Chaque neurone a un état de fonctionnement permettant ainsi de décrire le réseau à un moment précis. Cet état est calculé par une règle de propagation. Un neurone i d’entrée a pour état σi = xi . Fonctionnement : Un neurone dispose d’une fonction de sortie f calculant la valeur de sortie yi en fonction de l’état σi du neurone i : yi = f (σi). La figure 5.1(a) donne une vue simplifiée d’un réseau de neurones à quatre entrées. La figure 5.1(b) offre quant à elle le schéma de fonctionnement du perceptron reproduisant le fonctionnement de l’opérateur logique booléen XOR (« ou exclusif », ⊕, table de calcul 5.1). 91 Chapitre 5. L’évolutionnisme pour l’aménagement du territoire Notons par ailleurs qu’il existe un seuil d’activation pour chaque neurone, permettant de propager une valeur si et seulement si ce seuil est atteint. Ainsi dans l’exemple du perceptron, la valeur -2 est propagée seulement lorsque le seuil fixé à 2 est atteint, i.e. lorsque x et y valent chacun 1 et que leurs valeurs sont cumulées.

Apprentissage 

Les réseaux de neurones sont multicouches, c’est-à-dire que chacune des couches i, à l’exception de la dernière, constitue l’entrée de la couche i + 1. Le mécanisme d’apprentissage s’effectue grâce à des jeux de tests fournis comme bases de connaissances, à partir desquelles le réseau tend à généraliser des hypothèses. Une fois ces hypothèses clairement posées, le réseau est a priori en mesure de conclure sur tout problème posé. La connaissance du réseau de neurones est distribuée dans les poids des connexions neuronales. Ces poids sont fixés par apprentissage (exemple par rétropropagation de gradient pour le perceptron). Supervision : On peut forcer le réseau à généraliser et à tendre vers un vecteur final précis. On parle dans ce cas d’« apprentissage supervisé ». A contrario, si le réseau tire lui  même ses conclusions, i.e. tend vers un vecteur final quelconque, l’apprentissage est dit « non-supervisé ».

 Surapprentissage : Le réseau tire des conclusions à partir d’exemples fournis initialement. Supposons que les données prises en base d’apprentissage soient approximatives voire confuses, le réseau de neurones se trouve dans ce cas incapable de statuer une décision pour un problème dont les paramètres seraient tout aussi confus que les jeux de test. Bruit à l’apprentissage : De même, il arrive qu’en donnant des connaissances de base, le réseau en tire de mauvaises hypothèses, non pas en raison d’un caractère erronné de ces informations, mais à cause d’informations parasites qui n’étaient pas anticipées. On parle dans ce cas de bruit. Limites Les réseaux connexionistes se prêtent peu voire pas du tout à la résolution de problèmes de tournées, notamment en raison du besoin de connaissances initiales à travers des exemples représentatifs et à l’effet « boîte noire » du à la méconnaissance sémantique des poids de la couche cachée des neurones. 

Les colonies de fourmis 

S’inspirant du comportement collectif des fourmis, Marc Dorigo propose dans les années 1990 des algorithmes à métaheuristiques (Dorigo, 1992) pour trouver les chemins optimaux dans un graphe. Bien que leur comportement et leurs capacités soient très limités, les fourmis sont capables de résoudre des problèmes complexes grâce à la collaboration des unes avec les autres. On retrouve ici l’idée que l’on avait déjà avec les réseaux de neurones où l’élément de base est très limité mais son interconnexion avec les autres éléments permet de résoudre simplement des problèmes. Ici, l’élément de base est la fourmi, et celle-ci n’est capable que de déposer des phéromones, qui se révèlent volatiles avec le temps.

Recherche du meilleur chemin

 En observant le chemin emprunté par une colonie de fourmis pour se rendre à une source de nourriture, l’on se rend vite compte que celles-ci exploitent le chemin optimal. Leur comportement peut se résumer au schéma suivant :

1. Une fourmi explore son environnement aléatoirement, et sitôt qu’elle trouve une source de nourriture elle rentre au nid en marquant son chemin de retour de phéromones ; 
2. Les fourmis à proximité des phéromones les ressentent et remontent la piste jusqu’à la source de nourriture. De retour au nid, elles déposent également des phéromones attractives renforçant la piste précédemment empruntée par leurs congénères ; 
3. Si plusieurs chemins sont marqués par les phéromones attractives, le chemin le plus court sera également le chemin le plus marqué, car durant le même temps de parcours, plus de fourmis auront renforcé la piste ; 
4. Au cours du temps, les phéromones se dispersent, et comme les chemins les plus marqués en phéromones (les plus courts) sont également les plus entretenus, les chemins les moins marqués (les plus longs) disparaissent progressivement. Avec un comportement somme toute assez simpliste, les fourmis ont été capables d’isoler rapidement le meilleur chemin pour assurer leurs besoins. L’échange d’informations se fait via l’environnement et cet échange a une portée locale, en effet seules les fourmis à proximité des phéromones prennent connaissance de ces informations. Leurs diffusions se font par propagation successive suite aux dépôts successifs de phéromones. Dans l’exemple de la figure 5.2, une colonie de fourmis explore tous les chemins possibles pour se rendre vers S (5.2(a)). Petit à petit, au fil des évaporations des phéromones sur les moins bons chemins et à la persistence des phéromones sur les meilleurs chemins (5.2(b)), les fourmis finissent par isoler un chemin optimal, celui qui est seul marqué par les phéromones (5.2(c)). Limites Bien que les colonies de fourmis soient adaptées à la recherche de chemins optimaux, ces algorithmes n’offrent pas de solutions multiples en une simulation. Pour offrir plusieurs solutions, l’on doit recourir à un ensemble de simulations. 

Les essaims particulaires 

Autres algorithmes à métaheuristiques reproduisant les comportements des insectes sociétaux ou des animaux vivant en groupe, comme les essaims d’abeilles ou les bancs de poissons, les essaims particulaires partent du principe que le groupe reproduira le comportement d’un invidividu qui semble avoir trouvé la meilleure solution à un instant précis (Kennedy et Eberhart, 1995). Imaginons un banc de poissons, dans ce groupe un individu détecte la présence d’un prédateur et emprunte la direction de déplacement opposée pour fuir le danger. Ce comportement est propagé aux autres individus qui adoptent quasiment aussitôt la même attitude. D’autre part, ce même essaim peut adopter une attitude exploratoire, i.e. chaque particule dispose d’une marge de déplacement aléatoire pour explorer son environnement. Mais le comportement général demeure influencé par l’ensemble des particules. Les individus collaborent donc entre eux. Pour résoudre un problème, les particules sont positionnées aléatoirement ou non dans l’espace de recherche des solutions et leur sont affectées des vitesses de déplacement (vélocité). Chaque particule connaît sa meilleure position et la position optimale de l’essaim. Ensuite, les particules communiquent à leurs proches leurs bonnes positions pour que chaque particule se repositionne et adapte sa vélocité compte tenu des meilleures indications.