Modèle NK

Le modèle NK est un modèle mathématique formulé par Stuart Kauffman et permettant de décrire un paysage adaptatif "rugueux adaptable". Cette "rugosité" suppose que, à la fois la taille globale du paysage et le nombre de "pics" et "vallées" locales peuvent être ajustés via des changements dans ses deux paramètres $N$ et $K$ définis plus bas. Le modèle NK a des applications dans une grande variété de domaines, dont l'étude théorique de la biologie évolutive, l'immunologie, l'optimisation combinatoire, l'évolution technologique et les systèmes complexes. Le modèle a été également adopté en théorie des organisations, où on l'utilise pour décrire la façon dont un agent (entité individuelle ou collective comme un organisme ou un groupe) peut faire des recherches dans un paysage en manipulant plusieurs de ses caractéristiques. Par exemple, un agent peut être une organisation, les pics et les vallées représentent le profit (ou les changements de celui-ci), et le mouvement au sein du paysage nécessite des décisions organisationnelles (comme le fait d'ajouter des lignes de produit ou de modifier la structure organisationnelle), qui tendent à interagir entre elles et affecter le profit d'une manière complexe.

Une première version du modèle a été présentée par Kauffman et Levin et 1987, qui considérait seulement les paysages les plus lisses ($K=0$) et les plus rugueux ($K=N$). Le modèle sous sa forme actuelle est apparu la première fois dans la publication de Kauffman et Weinberger de 1989.

L'une des raisons pour lesquelles le modèle a attiré l'attention de la part de la communauté scientifique en optimisation est qu'il s'agit d'un exemple particulièrement simple d'un problème dit NP-complet.

Détails mathématiques

Visualisation en 2D d'un paysage adaptatif NK. Les flèches représentent divers chemins mutationnels que la population est capable de suivre lors de son évolution dans le paysage adaptatif.

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 $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 $S$ donnée correspond à la somme des contributions de chaque locus $S_i$ dans la chaîne :

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

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

$f(S_i)=f(S_i,S_1^i,\dots ,S_K^i),$

où les $S_j^i$ correspondent aux autres loci dont dépend la fitness des $S_i$.

Ainsi, la fonction de fitness $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, Weinberger a publié une analyse détaillée du cas où $1<<k\le 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

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

et une variance approximative de

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

Exemple

Illustration d'une topologie ajustable dans le modèle NK. Les nœuds correspondent à des chaînes individuelles binaires, et les arêtes les connectent par une distance de Hamming de valeur exacte 1. Gauche : N = 5, K = 0 ; Centre : N = 5, K = 1 ; Droite : N = 5, K = 2. La couleur d'un nœud indique sa fitness, avec des valeurs plus vers le rouge ayant une fitness plus forte. Le plongement de l'hypercube est choisi de telle sorte que la valeur maximale de fitness est au centre. Noter que le paysage où K = 0 apparaît plus lisse que les cas où K est plus élevé.

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 $f(S_i)=f(S_i,S_{i+1})$, de façon que chaque locus est affecté par son voisin, ainsi que $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 :

$F(00101)=f(0,0)+f(0,1)+f(1,0)+f(0,1)+f(1,0)=0+1+2+1+2=6$

$F(11100)=f(1,1)+f(1,1)+f(1,0)+f(0,0)+f(0,1)=0+0+2+0+1=3$

Topologie ajustable

La valeur de K contrôle le degré d'épistasie dans le modèle NK, ou bien à quel point les autres loci affectent la contribution à la fitness d'un locus donné. Avec K = 0, la fitness d'une chaîne donnée est une somme simple des contributions individuelles des loci : pour des fonctions de fitness non triviales, on a la présence d'un optimum global facile à localiser (le génome de tous les 0 si f(0) > f(1), ou de tous les 1 si f(1) > f(0)). Pour K non nul, la fitness d'une chaîne est la somme des fitness des sous-chaînes, qui peuvent interagir pour frustrer le système (voir la façon dont on obtient la fitness optimale dans l'exemple ci-dessus). Augmenter la valeur de K augmente ainsi la rugosité du paysage adaptatif.

Variations dans les espaces neutres

Le modèle NK de base ne supporte pas le phénomène d'espace neutre, c'est-à-dire les groupes de génomes connectés par des mutations simples ayant la même valeur de fitness. Deux adaptations ont été proposées pour inclure cette structure biologiquement importante :

• le modèle NKP introduit un paramètre $P$ : une proportion $P$ des $2^K$ contributions à la fitness est mis à zéro, de sorte que les contributions de plusieurs motifs génétiques dégénèrent ;
• le modèle NKQ introduit un paramètre $Q$ et renforce une discrétisation sur les valeurs possibles de contribution à la fitness de sorte que chaque contribution prend l'une des valeurs possibles de $Q$, introduisant de nouveau une dégénérescence dans les contributions à partir de certains motifs génétiques.

Le modèle NK de base correspond aux cas où $P=0$ et $Q=\mathrm{\infty }$ dans ces conditions de paramétrisation.

Extension Multi-objective du modèle NK

Le modèle MNK est une extension du modèle NK pour l'optimisation multiobjectif. Le paramètre $M$ configure le nombre d'objectifs. Le paysage d'une fonction MNK est définie comme un vecteur de fonction $F(S)=(F_1(S),f_2(S),...,f_M(S))$, tel que chaque $F_i(S)$ est une instance du modèle NK avec la même valeur d'épistasie $K$ (homogénéité de la rugosité des objectifs).

Le modèle $\rho$MNKest une adaptation du modèle MNK dont :

• les structures épistasiques sont identiques pour tous les objectifs.
• le paramètre $\rho$ contrôle la corrélation entre les objectifs.

Applications

Le modèle NK a trouvé son utilité dans de nombreux domaines, dont l'étude des verres de spin, l'épistasie et la pléiotropie en biologie évolutive, ainsi que l'optimisation combinatoire.

Voir aussi

Articles connexes

• Paysage adaptatif
• Optimisation combinatoire
• Problème NP-complet