Marche aléatoire renforcée
Nous allons étudier un modèle aléatoire non-markovien le plus simple possible : la marche aléatoire renforcée à 2 états. Ce modèle est à la base d'un algorithme d'apprentissage par renforcement appelé algorithme du bandit1. Il a été également été proposé pour modéliser l'exploration d'un milieu par des insectes sociaux2.

La fourmi va emprunter le chemin A avec probabilité r(3)r(1)+r(3).
Soit r:N→(0,+∞) une fonction telle que r(x)≥x pour tout x, r est appelée la fonction de renforcement.
On considère la suite de variables aléatoires (Xk)k≥1 à valeurs dans {A,B} définie de la façon suivante. Pour k≥1, SAk désigne le nombre de passages en A :
SA0=0,SAk=k∑i=11Xi=A∈{0,1,…,k}.
L'évolution est alors définie par :
P(Xk+1=A|X1,…,Xk)=r(Sk)r(Sk)+r(k−Sk).
Plus la fonction r a de grandes variations, plus la marche est renforcée : la fourmi a une grande tendance à emprunter le chemin majoritaire jusque-là. On cherche à évaluer l'influence de la fonction r sur le renforcement. Nous allons tracer l'évolution de la proportion SAkk.
1. Renforcement linéaire
On trace K trajectoires de SAnn pour r de la forme r(x)=a+x.xxxxxxxxxx
import numpy as np
import matplotlib.pyplot as plt
K=20 # Nombre de trajectoires
N=2000 # Durée de chaque simulation
def renforcement(x):
return 1+x # renforcement linéaire
for k in range(K):
PassagesenA=[] # True = on passe en "A"
NbPassagesenA=0
for n in range(N):
biais = (renforcement(NbPassagesenA)+0.0)/(renforcement(NbPassagesenA)+renforcement(n-NbPassagesenA))
OnPasseEnA=np.random.rand()<biais # Passage en A aléatoire, suivant le biais
PassagesenA.append(OnPasseEnA)
NbPassagesenA=NbPassagesenA+OnPasseEnA
plt.plot((np.cumsum(PassagesenA)+0.0)/np.array(range(1,N+1)))
plt.title('Trajectoires de $(S_n/n)$ pour un renforcement lineaire')
plt.axis([0,N,0,1])
plt.show()
2. Renforcement géométrique
On trace K trajectoires de SAnn pour r de la forme r(x)=ρx, avec ρ>1.xxxxxxxxxx
import numpy as np
import matplotlib.pyplot as plt
K=20 # Nombre de trajectoires
N=2000 # Durée de chaque simulation
def renforcement(x):
return 1.04**x # renforcement géométrique
for k in range(K):
PassagesenA=[] # True = on passe en "A"
NbPassagesenA=0
for n in range(N):
biais = (renforcement(NbPassagesenA)+0.0)/(renforcement(NbPassagesenA)+renforcement(n-NbPassagesenA))
OnPasseEnA=np.random.rand()<biais # Passage en A aléatoire, suivant le biais
PassagesenA.append(OnPasseEnA)
NbPassagesenA=NbPassagesenA+OnPasseEnA
plt.plot((np.cumsum(PassagesenA)+0.0)/np.array(range(1,N+1)))
plt.title('Trajectoires de $(S_n/n)$ pour un renforcement geometrique')
plt.axis([0,N,0,1])
plt.show()
Références
1Lien : Algorithme du bandit
2Voir par exemple cet article : Deneubourg, J. L., Aron, S., Goss, S., & Pasteels, J. M.. The self-organizing exploratory pattern of the argentine ant. Journal of insect behavior vol.3 (1990), n.2,p.159-168..
2Voir par exemple cet article : Deneubourg, J. L., Aron, S., Goss, S., & Pasteels, J. M.. The self-organizing exploratory pattern of the argentine ant. Journal of insect behavior vol.3 (1990), n.2,p.159-168..
Liens
- Moodle : Cours MAP432
- Initiation à Python : Page web de l'initiation python du cours de tronc commun