Modèle NK

Le modèle NK définit un espace des phases combinatoire, dans lequel chaque chaîne de caractères (choisie à partir d'un alphabet donné) de longueur ${\displaystyle N}$. Pour chaque chaîne dans cet espace de recherche, une valeur scalaire (appelée fonction de fitness) est définie. Si une distance métrique est définie entre les chaînes, la structure résultante constitue un paysage.

Les valeurs de fitness sont définies selon une incarnation spécifique du modèle, mais la caractéristique-clé du modèle NK est que la fitness d'une chaîne ${\displaystyle S}$ donnée correspond à la somme des contributions de chaque locus ${\displaystyle S_{i}}$ dans la chaîne :

${\displaystyle F(S)=\sum _{i}f(S_{i}),}$

et la contribution de chaque locus en général dépend de la valeur des ${\displaystyle K}$ autre loci :

${\displaystyle f(S_{i})=f(S_{i},S_{1}^{i},\dots ,S_{K}^{i}),}$

où les ${\displaystyle S_{j}^{i}}$ correspondent aux autres loci dont dépend la fitness des ${\displaystyle S_{i}}$.

Ainsi, la fonction de fitness ${\displaystyle f(S_{i},S_{1}^{i},\dots ,S_{K}^{i})}$ est une cartographie entre des chaînes de longueur K+1 et des scalaires, ce que Weinberger a appelé plus tard les contributions à la fitness. De telles contributions à la fitness sont souvent choisies de façon aléatoire à partir d'une certaine distribution de probabilité spécifique.

En 1991^[5], Weinberger a publié une analyse détaillée du cas où ${\displaystyle 1<<k\leq N}$ et les contributions à la fitness sont choisies aléatoirement. Son estimation analytique du nombre d'optima locaux s'est par la suite révélée imparfaite. Cependant, des expériences numériques incluses dans l'analyse de Weinberger sont en faveur de son résultat analytique selon lequel la fitness attendue d'une chaîne suit une distribution normale avec une moyenne approximative de

${\displaystyle \mu +\sigma {\sqrt {{2\ln(k+1)} \over {k+1}}}}$

et une variance approximative de

${\displaystyle {{(k+1)\sigma ^{2}} \over {N[k+1+2(k+2)\ln(k+1)]}}}$.

Summarize Timeline Fact Check

Par souci de simplicité et de compréhension, on va travailler dans cet exemple avec des chaînes binaires. On considère un modèle NK avec N = 5 et K = 1. Ici, la fitness d'une chaîne est donnée par la somme des contributions à la fitness individuelles de chacun des 5 loci. Chaque contribution à la fitness dépend de la valeur du locus local ainsi que d'une autre. On va utiliser la convention selon laquelle ${\displaystyle f(S_{i})=f(S_{i},S_{i+1})}$, de façon que chaque locus est affecté par son voisin, ainsi que ${\displaystyle f(S_{5})=f(S_{5},S_{1})}$ pour la cyclicité. Si l'on choisit par exemple les fonctions de fitness f(0, 0) = 0, f(0,1) = 1, f(1, 0) = 2 et f(1, 1) = 0, les valeurs de fitness des deux exemples de chaînes se calculent comme suit :

${\displaystyle F(00101)=f(0,0)+f(0,1)+f(1,0)+f(0,1)+f(1,0)=0+1+2+1+2=6}$

${\displaystyle F(11100)=f(1,1)+f(1,1)+f(1,0)+f(0,0)+f(0,1)=0+0+2+0+1=3}$