<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">  <html>  	<head> 		<meta http-equiv="content-type" content="text/html;charset=ISO-8859-1"> 		<meta name="rating" content="Mathieu Lafourcade"> 		<title>Algorithmes foumis et TALN (analyse)</title> 	</head>  	<body bgcolor="#ffffff"> 		<div align="center"> 			<h1>Algorithmes &quot;fourmis&quot; et TALN</h1> 			<address>Mathieu Lafourcade<br> 				version du 11/10/02</address> 		</div> 		<h2>Introduction</h2> 		<p>L'application d'algorithmes &agrave; base de &quot;fourmis&quot; dans le cadre du TALN permet d'appr&eacute;hender un certain nombre de difficult&eacute;s lors des diff&eacute;rentes phases d'analyse d'un texte. En particulier, l'utilisation conjointe des vecteurs conceptuels offre de perspectives interessantes en ce qui concerne les t&acirc;ches suivantes :</p> 		<ol> 			<li>d&eacute;sambiguisation lexicale : choisir (ou plus g&eacute;n&eacute;ralement pond&eacute;rer) les sens probable des termes d'un segment textuels. Par exemple, dans &quot;l'avocat &agrave; fait acquit&eacute; le pr&eacute;venu&quot;, le sens probable d'&quot;avocat&quot; est celui d'auxilliaire de justice 			<li>rattachement de groupe pr&eacute;positionels : les rattachements possibles sont contr&ocirc;l&eacute;s par la syntaxe, mais en general seul la s&eacute;mantique permet d'exprimer une pr&eacute;f&eacute;rence. Par exemple dans la phrase &quot;<i>Il voit la fille dans le parc avec un t&eacute;lescope</i>&quot; le groupe nominal pr&eacute;positionel (GNPREP) &quot;<i>avec un t&eacute;lescope</i>&quot; sera sans pr&eacute;f&eacute;rentiellement rattach&eacute; au groupe &quot;<i>voir la fille</i>&quot;. 			<li>le transfert lexical dans le cadre de la TA (ce point de sera pas developp&eacute; ici). 		</ol> 		<h3>Principe g&eacute;n&eacute;ral</h3> 		<p>Une analyse morpho-syntaxique fourni un arbre pour le segment textuel consid&eacute;r&eacute;. Il s'agit d'un arbre de constituants, c'est-&agrave;-dire un arbre o&ugrave; il est possible de reconstituer le texte en parcourant les mots des feuilles. Les feuilles de l'arbres sont donc, les termes du textes. A chaque sens d'un terme, on associe une fourmilli&egrave;re dont l'objectif (implicite) est d'imposer son vecteur conceptuel sur l'ensemble de l'arbre d'analyse (et en particulier &agrave; sa racine). Une fourmilli&egrave;re va d'une part, entrer en conflit avec des fourmilli&egrave;res conccurentes (les autres sens du m&ecirc;me terme) et d'autre part, trouver un soutien (involontaire) dans les fourmilli&egrave;res associ&eacute;es aux autres termes. Ce soutien est proportionnel &agrave; la similarit&eacute; entre les deux fourmill&egrave;res (deux fourmilli&egrave;re que se ressemblent se soutiennent mutuellement plus fortement que deux fourmilli&egrave;res diff&eacute;rentes). Par l'interm&eacute;diaire de leurs fourmis, les fourmilli&egrave;res essaye (1) de maintenir leur activation &agrave; un niveau aussi &eacute;lev&eacute; que possible, (2) de construire et de conserver des &quot;ponts&quot; activateurs et/ou inhibiteurs avec d'autres fourmill&egrave;res. L'ensemble du processus se fait sur la base de transfert d'&eacute;nergie dont la quantit&eacute; globale est constante (et finie).</p> 		<p>Quelques notions et notations de base :</p> 		<h3>Vecteurs conceptuels</h3> 		<p>Pour une introduction g&eacute;n&eacute;rale aux vecteurs conceptuels, on peut se r&eacute;f&eacute;rer aux articles r&eacute;cents disponible &agrave; <a href="http://www.lirmm.fr/%7elafourca/ML-biblio/lafourcade-publications.html">http://www.lirmm.fr/~lafourca/ML-biblio/lafourcade-publications.html</a>.  </p> 		<p>On note <tt>sim(A,B)</tt> la similarit&eacute; entre deux vecteurs A et B. Deux vecteurs sont identiques si leur similarit&eacute; est &eacute;gale &agrave; 1, et orthogonaux pour 0. La similarit&eacute; est le produit scalire des deux vecteurs divis&eacute; par le produit de leur norme. La distance agulaire de deux vecteurs est <tt>arccos(sim(A,B))</tt>.</p> 		<h3>Fonction Sigmo&iuml;de</h3> 		<p>La fonctions <tt>Sigmo</tt> est definie comme : </p> 		<div align="center"> 			<p><tt>Sigmo(x) = (+ (/-2 (atan val) *pi*) 0.5)</tt></p> 		</div> 		<p>Cela correspond &agrave; artangente resserr&eacute;e sur un intervale 0,1 . Par exemple :</p> 		<blockquote> 			<p><tt>Sigmo(0) = 1/2<br> 					Sigmo (1) = 0.75<br> 					 					Sigmo (2) = 0.852<br> 					 					Sigmo (-1) = 0.25<br> 					 					Sigmo (-2) = 0.147. </tt></p> 			<p>La fonction est croissante, continue.</p> 		</blockquote> 		<div align="center"> 			<p><img src="sigmo2.gif" width="466" height="195"></p> 			<p>Fonction dite <tt>Sigmoid</tt></p> 			<p></p> 		</div> 		<h3></h3> 		<h3>Arbres d'analyse morpho-syntaxique</h3> 		<p>Voici un exemple d'arbre d'analyse syntaxique. A l'url <tt><a href="http://www.lirmm.fr/%7echauche/ExempleAnlMem.html">http://www.lirmm.fr/~chauche/ExempleAnlMem.html</a></tt> , il est possible d'obtenir de tels arbres &agrave; partir de textes rentr&eacute;s en param&egrave;tres.</p> 		<div align="center"> 			<p><img src="Bribe.gif" width="498" height="374"></p> 			<p>Arbre d'analyse morpho-syntaxique pour le phrase <i>L'avocat est v&eacute;reux.</i></p> 		</div> 		<div align="left"> 			<p>Les noeuds de l'arbre d'analyse contiennent des informations morpholigique et syntaxiques.</p> 		</div> 		<p>En plus d'information lingusitique, un noeud de l'arbre d'analyse a les propri&eacute;t&eacute;s suivantes :</p> 		<ol> 			<li>Un niveau d'&eacute;nergie <tt>E(node)</tt>qui un r&eacute;el. 			<li><tt>Linkable(node)</tt> qui vaut <tt>vrai</tt> alors une fourmi peut produire un pont depuis ce n&#156;ud jusqu'a sa fourmilli&egrave;re, et <tt>faux</tt> sinon. 			<li><tt>Nest(node)</tt> qui vaut <tt>vrai</tt> si le n&#156;ud peut produire des fourmis (c'est alors une fourmilli&egrave;ire). 		</ol> 		<p>On distingue donc les n&#156;uds internes de l'arbre et les fourmilli&egrave;res. Tout noeud dispose d'un niveau d'&eacute;nergie, cependant pour les noeuds internes ce niveau d'&eacute;nergie sera maintenu &gt;= 0 (il peut &ecirc;tre &lt;= 0 pour les fourmilli&egrave;res).</p> 		<div align="center"> 			<p><img src="arbre-vide.gif" width="739" height="609"></p> 		</div> 		<p></p> 		<div align="left"> 			<h3>Simulation et cycles</h3> 			La simulation consiste &agrave; une it&eacute;ration infinie d'un certain nombre d'action. Un tour est app&eacute;l&eacute; un <tt>cycle</tt> . Durant un cycle, on effectue les t&acirc;ches suivantes :  			<ol> 				<blockquote> 					<li>Eliminer les fourmis trop vieilles ; 					<li>Pour chaque fourmilli&egrave;re, soliciter la production d'une fourmi (une fourmi peut ou non voir le jour, de fa&ccedil;on probaliste) ; 					<li>Pour chaque arc, diminuer le taux de ph&eacute;romone (&eacute;vaporation des traces) ; 					<li>Pour chaque fourmi : d&eacute;terminer son type et la d&eacute;placer ; 					<li>Calculer les cons&eacute;quences du d&eacute;placement des fourmis (sur l'activation des arcs et l'&eacute;nergie des n&#156;uds) ;  				</blockquote> 			</ol> 			<p>D'une fa&ccedil;on informelle, on peut r&eacute;sumer le d&eacute;placement d'un fourmi comme suit. Une fourmi qui vient de na&icirc;tre (cad produite par sa fourmilli&egrave;re) par &agrave; la recherche de nourriture. Elle est attir&eacute;e par les n&#156;ud qui porte beaucoup d'&eacute;nergie. Elle ramasse autant d'&eacute;nergie qu'elle peut en porter (et de ce qui est disponible) et se prom&egrave;ne ainsi sur le graphe. Au fur et et &agrave; mesure, elle transporte de plus en plus de nourriture et la probabilit&eacute; de souhaiter rentrer &agrave; la fourmilli&egrave;re augmente. Lorsqu'elle vent rentrer, elle se deplace en suivant (statistiquement) les chemins qui contiennent sa ph&eacute;romone, et reoturne ainsi &agrave; sa froummilli&egrave;re o&ugrave; elle d&eacute;pose son chargement. Si elle rencontre une autre fourmilli&egrave;re (non concurrent) elle d&eacute;pose &eacute;galement une petite partie de son chargement.</p> 			<h2>Les fourmis</h2> 			<p>Les fourmis se d&eacute;placent de fa&ccedil;on pseudo-al&eacute;atoire sur l'arbre d'analyse. Dans certaines conditions, elle peuvent construire des <i>ponts</i> (ou court-circuits) entre certains n&#156;uds de l'arbre (qui devient alors un graphe).</p> 			<p>Une fourmi dispose de plusieurs attributs:</p> 			<ol> 				<li>Un nombre de <i>pt de vie</i> <tt>Life(ant)</tt> (par exemple <tt>Life(ant)=5</tt>). Cette valeur enti&egrave;re correspond au nombre de d&eacute;placements qu'elle peut faire avant de mourir de vieillesse (quand <tt>Life(ant)=0</tt>). De fa&ccedil;on simplifi&eacute;e, &agrave; chaque d&eacute;placement, la valeur de <tt>Life(ant)</tt> de la fourmi <tt>ant</tt>  est decr&eacute;ment&eacute;e de 1. A la cr&eacute;ation d'une fourmi, <tt>Life(ant)</tt> &agrave; une certaine valeur initiale <tt>LifeStart </tt>(exp&eacute;rimentalement<tt> LifeStart = 20</tt>). 				<li>Un niveau d'&eacute;nergie<tt> E(ant)</tt> . Lors de ses d&eacute;placements la fourmi peut ramasser de l'&eacute;nergie. La quantite d'&eacute;nergie totale <tt>MaxE(ant)</tt> qu'elle peut transporter est born&eacute;e (par exemple &agrave; 2). Lorsqu'une fourmis meure (<tt>Life(ant)=0</tt>), elle restitue l'ensemble de l'&eacute;nergie port&eacute; au n&#156;ud o&ugrave; elle se trouve. Dans se cas, l'&eacute;nergie du n&#156;ud consid&eacute;r&eacute; devient : <br> 					<tt>E(node) = E(node) + E(ant)</tt>. Le niveau d'&eacute;nergie d'une fourmi est toujours &gt;= 0. 				<li>Une r&eacute;f&eacute;rence &agrave; sa maison <tt>Home(ant)</tt> qui permet entre autre de conna&icirc;tre sa signature (cad son vecteur conceptuel), que l'on notera <tt>V(ant)</tt>.  				<li>un type <tt>Type(ant)</tt> qui d&eacute;termine son comportement. 			</ol> 			<h3>Fourmis : D&eacute;placements et ponts</h3> 			<p>A chaque instant, une fourmi se trouve sur un noeud k. Si cette fourmi vient d'&ecirc;tre cr&eacute;e par sa forumilli&egrave;re elle se trouve sur cette fourmilli&egrave;re. Il peut y avoir un nombre quelconque de fourmis sur un n&#156;ud. Les fourmis n'int&eacute;ragissent pas directement entre elles. A chaque tour, chaque fourmi doit se d&eacute;placer, et les destinations possibles sont les n&#156;uds accessibles selon la g&eacute;om&eacute;trie de l'arbre.</p> 			<p>Si une fourmi se trouve sur un n&#156;ud tel que <tt>linkable(node) = vrai</tt> elle peut toujours rallier sa propre fourmilli&egrave;re en cr&eacute;ant un pont, s'il n'existe pas d&eacute;j&agrave;.</p> 			<h3>Fourmis : Transfert d'&eacute;nergie</h3> 			<p>Lorsqu'une fourmi se retrouve sur un n&#156;ud, plusieurs situations se produisent selon le type de ce n&#156;ud. En particulier, on distingue quatre types de n&#156;uds :</p> 			<ol> 				<li>la fourmilli&egrave;re maison (<tt>node = Home(ant)</tt>) 				<li>une fourmilliere concurrente (<tt>node = Ennemy(ant)</tt>) : il sagit d'un autre sens du m&ecirc;me mot. Il s'agit de toutes les fourmilli&egrave;res qui ont le m&ecirc;me p&egrave;re que <tt>Home</tt>. 				<li>une autre fourmilli&egrave;re (<tt>Nest(node) = vrai</tt>) 				<li>un n&#156;ud qui n'est pas une fourmilli&egrave;re (<tt>Nest(node) = faux</tt>)  			</ol> 			<p>On notera les quatre cas comme les quatre valeurs possible de la fonction <tt>Status(ant, node)</tt>.</p> 			<p>Les comportements sont les suivants :</p> 			<blockquote> 				<p><tt>(1) Status(ant, node)= Home. </tt>Lorsqu'une fourmi arrive &agrave; <tt>Home</tt> (1), elle restitue l'ensemble de son &eacute;nergie &agrave; Home. Elle repartira avec une &eacute;nergie 0. (On veillera ici &agrave; ne pas confondre l'energie et la dur&eacute;e de vie).</p> 				<p><tt>(2) Status(ant, node)= Ennemy. </tt>Si elle arrive sur une fourmilli&egrave;re concurrente (cas 2), elle lui vole une quantit&eacute; d'&eacute;nergie egale &agrave; <tt>(1-sim(Ant, Enemy))</tt>. On a donc les variations suivantes :</p> 				<blockquote> 					<p><tt>E(node) = E(node) - min (MaxE(ant)-E(ant) , (1-sim(V(Ant), V(node))))<br> 							E(ant) = E(ant) + min (MaxE(ant)-E(ant) , (1-sim(V(Ant), V(node))))</tt></p> 				</blockquote> 				<p>Plus une fourmilli&egrave;re ennemie est diff&eacute;rente, plus la quantit&eacute; d'&eacute;nergie d&eacute;rob&eacute;e tend vers 1. Cependant, la fourmis ne peut jamais d&eacute;passer sa charge maximale.</p> 				<p><tt>(3) Status(ant, node)= Nest. </tt>La fourmi qui arrive sur une autre fourmilli&egrave;re (cas 3) donne une partie de son &eacute;nergie dans la proportion <tt>sim(V(node),V(ant))</tt>.</p> 				<blockquote> 					<p><tt>E(node) = E(node) + sim(V(node), V(ant))* E(ant)</tt><br> 						<tt>E(ant) = E(ant) - sim(V(node), V(ant))* E(ant)</tt>.</p> 				</blockquote> 				<p><tt>(4) Status(ant, node)= Intern. </tt>La fourmi qui arrive sur un n&#156;ud interne de l'arbre (cas 4) prend le plus d'&eacute;nergie possible de fa&ccedil;on &agrave; maximiser l'&eacute;nergie qu'elle porte :</p> 				<blockquote> 					<p><tt>E(ant) = E(ant) + min(MaxE(ant) - E(ant), E(node))<br> 							E(node) = E(node) - min(MaxE(ant) - E(ant), E(node))</tt></p> 				</blockquote> 			</blockquote> 			<p>On remarquera que si un n&#156;ud interne <tt>node</tt> n'a plus d'&eacute;nergie (<tt>E(node)=0</tt>), on ne peut lui en soustraire d'avantage. Par contre, on peut toujours soustraire de l'&eacute;nergie &agrave; une fourmilli&egrave;re, m&ecirc;me si celle-ci a d&eacute;j&agrave; une &eacute;nergie nulle (elle deviendra alors n&eacute;gative).</p> 			<h3>Fourmis : type de fourmi et strat&eacute;gies de d&eacute;placements</h3> 			<p>Avant de se d&eacute;placer, une fourmi va <i>&eacute;valuer</i> les n&#156;uds qui sont des destinations possibles du n&#156;ud o&ugrave; elle se trouve. On note <tt>Val(node)</tt> cette valeur. En toute g&eacute;n&eacute;ralit&eacute;, la probabilit&eacute; qu'une fourmi a de prendre une destination k (un arc k menant au n&#156;ud k) est :</p> 		</div> 		<div align="center"> 			<p><tt>pa(k)= Val(k)/somme[i=1;n]Val(i))</tt></p> 		</div> 		<div align="left"> 			<p>On consid&egrave;re deux types de fourmis:</p> 			<ol> 				<li>les fourmis dites <tt>E</tt> (Exploration) qui recherche de la nourriture. Elles sont attir&eacute; par des n&#156;ud ayant beaucoup d'&eacute;nergie (&agrave; l'exclusion de leur propre fourmilli&egrave;re).				<li>les fourmies dites <tt>R</tt> (Retour) qui cherche &agrave; retourner &agrave; leur fourmilli&egrave;re pour y d&eacute;poser la nourriture qu'elles ont trouv&eacute;.			</ol> 			<p>Une fourmi E &eacute;value les destinations possibles selon la fonction suivante. Pour un n&#156;ud destination <tt>node</tt>, la valuation de ce noeud est :</p> 		</div> 		<div align="center"> 			<p><tt>Val(node) = Sigmo(E(node))</tt></p> 		</div> 		<div align="left"> 			<p>Une fourmi R &eacute;value les destinations possibles selon la fonction suivante. Pour un n&#156;ud destination <tt>node</tt>, la valuation de ce noeud est :</p> 		</div> 		<div align="center"> 			<p><tt>Val(node) = sim(V(ant), V(node))</tt></p> 		</div> 		<div align="left"> 			<p>De plus, et de fa&ccedil;on tout &agrave; fait g&eacute;n&eacute;rale, on consid&eacute;rera quelques heuristiques de d&eacute;placement. Par exemple, on donnera un tr&egrave;s fort malus &agrave; une destination qui est la pr&eacute;c&eacute;dente (<tt>Val(node) = Val(node)/10</tt>) (sauf si la fourmi vient de changer de type). Il s'agit d'encourager une fourmi &agrave; ne pas toujours pr&eacute;f&eacute;rer sa propre fourmilli&egrave;re &agrave; une autre n&#156;ud, et &agrave; parcourir l'arbre selon des cycles.</p> 			<div align="left"> 				<div align="left"> 					<div align="left"> 						<div align="left"> 							<h3>Fourmis : changement de type</h3> 							<p>La fourmi peut porter une charge <tt>MaxE</tt>. Avant chaque d&eacute;placement, la fourmi d&eacute;cide ou non de chnager son type en fonction de ce qu'elle porte. La probabilit&eacute; d'&ecirc;tre du type <tt>R</tt> (de retourner &agrave; la maison) est d&eacute;finie comme :</p> 							<div align="left"> 								<div align="left"> 									<div align="center"> 										<p><tt>p(ant,R)= E/MaxE</tt></p> 									</div> 									<p>Par exemple, si la fourmi porte une charge relative de 1/2 alors elle &agrave; 50% de d&eacute;cider de rentrer &agrave; la maison. Si une fourmi porte d&eacute;j&agrave; sa charge maximale, elle &agrave; alors 100% de chance de d&eacute;cider de rentrer.</p> 								</div> 							</div> 						</div> 					</div> 				</div> 			</div> 			<h3>Fourmis : ph&eacute;romones et stygmergie irrationnelle</h3> 			<p>Lors de chaque d&eacute;placement, la fourmi d&eacute;pose sur l'arc travers&eacute; une petite quantit&eacute; de ph&eacute;romone (<tt>delta = 0.1</tt>). Elle laisse une sorte de trace. Cependant, si une fourmi emprunte un arc dont une des extr&eacute;mit&eacute;s est un n&#156;ud concurrent alors, elle baisse l'activation de cet arc. dans ce cas, on note l'arc k entre node1 et node 2 : k(node1, node2). Les arcs ne sont pas orient&eacute;s.</p> 			<blockquote> 				<p><tt>k(node, ennemy(ant)) : Act(k) = Act(k) - delta<br> 						k(node1, node2) : Act(k) = Act(k) + delta</tt></p> 			</blockquote> 			<p>Le niveau d'activation d'une arc ayant une influence sur le d&eacute;placement (voir Stygmergie), l'id&eacute;e est qu'une fourmi ne souhaite pas qu'un arc li&eacute; &agrave; une fourmilli&egrave;re concurrente soit fr&eacute;quent&eacute;.</p> 			<p>A chaque cycle de la simulation, la quantit&eacute; de ph&eacute;romones sur chaque arc diminue (&eacute;vaporation) selon un coefficient <tt>ro</tt>. Pour un arc k, la nouvelle quantit&eacute; de ph&eacute;romone diminue :</p> 		</div> 		<div align="center"> 			<p><tt>Act(k) = (1 - ro) * Act(k)</tt></p> 		</div> 		<div align="left"> 			<p>L'activation d'un arc peut &ecirc;tre positive ou n&eacute;gative selon l'activit&eacute; des fourmis. Cependant, avec le temps et si aucune fourmi ne repasse sur l'arc, l'activation a naturellement tendance &agrave; converger vers 0.</p> 			<div align="left"> 				<p>Dans ce qui pr&eacute;c&egrave;de sur la description du processus de deplacement d'une fourmi, les activations des arcs ne joue pas de r&ocirc;le. L'ensemble du processus est donc analogue &agrave; un algorithme glouton. La terme de stygmergy correspond au ph&eacute;nom&egrave;ne de communication indirecte et de renforcement induit par les ph&eacute;romones d&eacute;pos&eacute;es par les fourmis. Les ph&eacute;romones sont ici simul&eacute;es par le niveau d'activation des arcs.</p> 				<p>On rappelle qu'&agrave; chaque passage sur un arc, une fourmi augmente l'activation de ce dernier d'une petite constante (delta = 0.1). La probabilit&eacute; de choisir l'arc <tt>k</tt> &agrave; partir de <tt>node</tt> (ayant les arcs 1 &#133; k &#133; n) est &eacute;gale :</p> 				<div align="center"> 					<p><tt>pb(k)=sigmo(Act(k))/somme[i=1;n](sigmo(Act(i)))</tt></p> 				</div> 				<p>Toutses choses &eacute;tant &eacute;gales par ailleurs, les fourmis ont tendance &agrave; pr&eacute;f&eacute;rer  les zones de fort passage.</p> 				<p>De fa&ccedil;on globale, une fourmi &eacute;value donc une destination (cad un arc k et le n&#156;ud destination k) :</p> 				<div align="center"> 					<p><tt>p(ant,k)= pa(k)* pb(k)/somme[i=1;n](pa(i)* pb(i))</tt></p> 				</div> 				<p>En toute generalit&eacute; (cf Dorigo), on peut affecter des pond&eacute;rations <tt>A</tt> et <tt>B</tt> aux termes <tt>pa</tt> et <tt>pb</tt>:</p> 				<div align="center"> 					<p><tt>p(ant,k)= pa(k)<sup>A</sup>* pb(k)<sup>B</sup>/somme[i=1;n](pa(i)<sup>A</sup>* pb(i)<sup>B</sup>)</tt></p> 				</div> 				<p>en pratique, on obtient de bons r&eacute;sultats en fixant <tt>A = B = 1.</tt></p> 			</div> 			<div align="left"> 				<h3>Fourmis : propagation de vecteurs et stygmergie rationnelle</h3> 				<p>Lors de son d&eacute;placement sur les n&#156;uds interne de l'arbre, une fourmi propage son vecteur conceptuel. Le vecteur port&eacute; par un n&#156;ued est modifi&eacute; lors du passage d'une fourmi :</p> 			</div> 		</div> 		<div align="center"> 			<p><tt>V(n) = V(n) + fs * alpha * V(ant)</tt></p> 		</div> 		<div align="left"> 			<p>alpha est une petite constante non nulle (alpha = 0.05, soit 5 %) et <tt>fs = 1</tt> par d&eacute;faut. Au debut de la simulation les n&#156;uds internes n'ont pas de vecteur. La facteur alph peut &ecirc;tre diminu&eacute; ou agment&eacute; selon la fonction syntaxique du n&#156;ud d'ou provient la fourmi. En particulier, si la n&#156;ud pr&eacute;cedent est un gouverneur (GOV) alors <tt>fs = 2</tt> . Les fourmilli&egrave;res sont les seuls n&#156;uds dont le vecteur ne peut pas &ecirc;tre modifi&eacute; par le passage d'autres fourmis (ce sont des points fixes).</p> 			<p>Le d&eacute;placement des fourmis implique une propagation des vecteurs et participe &agrave; l'effet stygmerg&eacute;tique (traces). Cependant, l'effet est ici rationnel pour les fourmis car elle ont tendance, selon leur type, &agrave; choisir selon leur destination selon les vecteurs port&eacute; par les n&#156;uds.</p> 			<p>Ce ph&eacute;nom&egrave;ne permet aux fourmis de revenir &agrave; leur fourmilli&egrave;re, ou &eacute;ventuellement &agrave; se tromper et &agrave; se diriger vers des fourmilli&egrave;re amies.</p> 		</div> 		<h2>Les fourmilli&egrave;res</h2> 		<p>Une fourmilli&egrave;re dispose :</p> 		<ol> 			<li>d'un niveau d'&eacute;nergie <tt>E(node)</tt> (variant de -infini a +infini) qui influe sur le taux de production de fourmis.Il est &eacute;ventuellement possible d'imposer des bornes <tt>min</tt> et <tt>max</tt> &agrave; ces niveaux d'&eacute;nergie.  		</ol> 		<h3>Fourmilli&egrave;res : production de foumis</h3> 		<p>La production d'une fourmi est pseudo-al&eacute;atoire et est gourvern&eacute;e par une fonction (dite Sigmo) de l'activation. La propabilit&eacute; de produire une fourmi pour un n&#156;ud k est :</p> 		<div align="center"> 			<p><tt>pf(k) = Sigmo(E(k))</tt></p> 		</div> 		<p>Par exemple, une fourmilli&egrave;re &agrave; activation 0, a une chance sur deux de produire une fourmi. Une fourmilli&egrave;re sera dite inhib&eacute; sur <tt>E &lt;&lt; 0</tt>, et activ&eacute; si <tt>E &gt;&gt; 0</tt> .</p> 		<div align="left"> 			Une fourmilli&egrave;re produit des  fourmis de type R portant une charge de nourriture &eacute;gale &agrave; 0 (on rappelle que le type de la fourmis chantgera au cours du temps). 			<p>Le co&ucirc;t d'une fourmi est constant (<tt>AntCost</tt>) et baisse l'&eacute;nergie du n&#156;ud node de AntCost : </p> 		</div> 		<div align="center"> 			<p><tt>E(node) = E(node) - AntCost</tt></p> 		</div> 		<div align="left"> 			<p>Le co&ucirc;t est empiriquement fix&eacute; (<tt>AntCost = 0.1</tt>) .</p> 		</div> 		<h2>Discussion</h2> 		<p>La discussion qui suit pr&eacute;sente la dynamique globale du syst&egrave;me, qui est induite par les r&eacute;gles de comportement pr&eacute;sent&eacute;es ci-dessus.</p> 		<h3>Discussion : effet de l'&eacute;nergie</h3> 		<p>L'&eacute;nergie est la facteur de contr&ocirc;le des population de fourmis. En effet, contrairement aux applications classques des algorithmes fourmis &agrave; certains probl&egrave;mes de combinatoire (TSP, etc) nous somme dans une situation ou plusieurs populations de fourmis se font concurrence ou coop&egrave;rent. D'une fa&ccedil;on g&eacute;n&eacute;rale, plus une fourimmil&egrave;re obtient de l'&eacute;nergie plus sa population de fourmis va s'accro&icirc;tre. Et en retour, son niveau d'&eacute;nergie pourra &ecirc;tre maintenu relativement &eacute;lev&eacute;. Cependant, le syst&egrave;me ne peut diverger, la quantit&eacute; globale d'&eacute;nergie disponible &eacute;tant finie et constante.</p> 		<p>D'ou provient l'&eacute;nergie que reccup&egrave;re une fourmilli&egrave;re ? Elle provient  (1) de ces propres fourmis, mais aussi (2) des fourmis altruistes des autres fourmilli&egrave;re non-concurrentes. Ne consid&eacute;rons que se qui se passe avec ses propres fourmis.</p> 		<h3>Discussion : effet de la satisfaction</h3> 		&agrave; faire 		<p></p> 		<p></p> 		<p></p> 		<h3>Discussion : effet des vecteurs et stygmergie rationelle</h3> 		<p>&agrave; faire</p> 		<p></p> 		<p></p> 		<p></p> 		<h3>Discussion : effet des ph&eacute;romone et stygmergie irrationnelle</h3> 		&agrave; faire 		<p></p> 		<p></p> 		<h3>Discussion : Approche dure et approche douce</h3> 		<p>L'approche pr&eacute;cedente (dites <i>dure</i>) aboutit &agrave; un syst&egrave;me dont le dynamique est violente pour les fourmis minoritaires. Certaines modifications relachent les contraintes pesant sur les fourmis et les fourmilli&egrave;res. Cette approche est qualifi&eacute;e de <i>douce</i>.</p> 		<ol> 			<li>Le co&ucirc;t d'une fourmi est &eacute;gale a <tt>Sigmo(E(node))</tt>. Une fourmi a un co&ucirc;t relatif &agrave; l'&eacute;nergie de la fourmilli&egrave;re. Elle co&ucirc;te peu pour une fourmilli&egrave;re peu activ&eacute; et beaucoup sinon. Par exemple, le co&ucirc;t pour E(node)=0 sera de 1/2. 			<li>Le cas (3) du transfert d'&eacute;nergie devient<br> 				<tt>E(node) = E(node) + sim(Nest, Ant)*E(ant)*(1 - Sigmo(E(node)))</tt>.<br> 				L'id&eacute;e est de ne donner de l'&eacute;nergie &agrave; une fourmilli&egrave;re que dans la mesure ou celle en a besoin. Il est inutile de donner de l'&eacute;nergie &agrave; une fourmilli&egrave;re d&eacute;ja tr&egrave;s activ&eacute;e. 			<li>Le cas (2) est similaire. On ne prend de l'&eacute;n&eacute;rgie &agrave; une fourmilli&egrave;re concurrent que dans la mesure ou celle-ci est activ&eacute;. 		</ol> 		<h2>Quelques exemples</h2> 		Les chemins activ&eacute; sont en vert, les chemins inhib&eacute;s sont en rouges. La valeur absolue de l'&eacute;nerge d'une fourmilli&egrave;re est repr&eacute;sent&eacute;e via sa grosseur. Elle est inhib&eacute;e en violet (E&lt;0) et active en bleu (E&gt;=0) 		<h3>Exemple 1</h3> 		<p>Pour la phrase <i>il est avocat &agrave; la cour</i></p> 		<div align="center"> 			<p><img src="avocat-cours.gif" alt="" width="682" height="634" border="0"></p> 		</div> 		<p>Les sens <i>avocat.1</i> correspond au sens <i>d&eacute;fenseur de justice</i> et <i>avocat .2</i> correspond au sens de <i>fruit</i>. L'acception <i>cour.1</i> correspond &agrave; <i>cour de b&acirc;timent</i>, et <i>cour.2</i> correspond &agrave; <i>cour de justice</i>.</p> 		<h3>Exemple 2</h3> 		<p>Pour la phrase <i>L'avocat est v&eacute;reux</i></p> 		<div align="center"> 			<p><img src="avocat-vereux.gif" alt="" width="565" height="536" border="0"></p> 		</div> 		<p>Les sens <i>avocat.1</i> correspond au sens <i>d&eacute;fenseur de justice</i> et <i>avocat .2</i> correspond au sens de <i>fruit</i>. L'acception <i>v&eacute;reux.1</i> correspond &agrave; corrumpu, et <i>v&eacute;reux.2</i> correspond &agrave; <i>plein de vers</i>.</p> 		<p>M&ecirc;me phrase (<i>l'avocat est v&eacute;reux</i>), avec une approche douce.</p> 		<div align="center"> 			<p><img src="avocat-vereux-soft.gif" alt="" width="685" height="601" border="0"></p> 			<p></p> 		</div> 		<div align="left"> 			<h3>Exemple 3</h3> 			<p><i>L'avocat est v&eacute;reux, le pr&eacute;nue a &eacute;t&eacute; condamn&eacute;.</i> Approche douce.</p> 		</div> 		<div align="center"> 			<p><img src="avocat-prevenu.gif" alt="" width="980" align="middle" livesrc="../Library/Mail/Mailboxes/Message%20sent.mbox/MailViewer-682-1.mimeattach/pastedGraphic.tiff" height="529"></p> 		</div> 		<h3>Exemple 4</h3> 		La phrase <i>Il condamne la porte. </i>Le sens correcte de comdan&eacute;e est s&eacute;lectionner via le sens de porte (monos&eacute;mique ici). 		<div align="center"> 			<h2><img src="condamner-porte.gif" alt="" border="0" livesrc="../Library/Mail/Mailboxes/Message%20sent.mbox/MailViewer-682-2.mimeattach/pastedGraphic.tiff" width="760" height="600"></h2> 		</div> 		<h2>Rattachement de groupes pr&eacute;positionels</h2> 		&agrave; faire 		<h2>R&eacute;f&eacute;rences</h2> 		 		Dorigo 		<p>Drogoul</p> 		<p>Ferber</p> 		<p></p> 		<p></p> 		<p></p> 	</body>  </html> 
