Модель НК

Модель NK — это математическая модель , описанная ее основным изобретателем Стюартом Кауфманом как «настраиваемая жесткая» фитнес-среда . «Настраиваемая жесткость» отражает интуитивное понимание того, что как общий размер ландшафта, так и количество его местных «холмов и долин» можно регулировать путем изменения двух его параметров : уровень пересечённости ландшафта. ${\displaystyle N}$ ${\displaystyle K}$ ${\displaystyle N}$ ${\displaystyle K}$

Модель NK нашла применение в самых разных областях, включая теоретическое исследование эволюционной биологии , иммунологии , оптимизации , технологической эволюции , командной науки ^[1] и сложных систем . Модель также была принята в теории организаций , где она используется для описания того, как агент может исследовать ландшафт, манипулируя различными своими характеристиками. Например, агентом может быть организация , холмы и долины представляют собой прибыль (или ее изменения), а движение по ландшафту требует организационных решений (таких как добавление линий продуктов или изменение организационной структуры), которые имеют тенденцию взаимодействовать друг с другом. и влияют на прибыль сложным образом. ^[2]

Ранняя версия модели, которая учитывала только самые гладкие ( ) и самые пересеченные ( ) ландшафты, была представлена ​​Кауфманом и Левином (1987). ^[3] Модель в том виде, в котором она известна в настоящее время, впервые появилась в работе Кауфмана и Вайнбергера (1989). ^[4] ${\displaystyle K=0}$ ${\displaystyle K=N-1}$

Одна из причин, почему модель привлекла широкое внимание в оптимизации, заключается в том, что она представляет собой особенно простой пример так называемой NP-полной задачи ^[5] , что означает, что трудно найти глобальные оптимумы. Недавно было показано, что модель NK для K > 1 также является PLS-полной ^[6], а это означает, что в целом трудно найти даже локальные оптимумы приспособленности. Это имеет последствия для изучения открытой эволюции.

Прототипический пример: приспособленность плазмид.

Плазмида — это небольшой круг ДНК внутри определенных клеток, который может реплицироваться независимо от клеток-хозяев . Предположим, мы хотим изучить приспособленность плазмид.

Для простоты мы моделируем плазмиду как кольцо из N возможных генов, всегда в одном и том же порядке, и каждый из них может иметь два возможных состояния (активное или неактивное, тип X или тип Y и т. д.). Тогда плазмида моделируется двоичной строкой длины N , и поэтому функция приспособленности равна . ${\displaystyle F:\{0,1\}^{N}\to \mathbb {R} }$

В самой простой модели гены не взаимодействуют друг с другом, и поэтому мы получаем, где каждый обозначает вклад в приспособленность гена в местоположении . $${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1})+f_{2}(S_{2})+\cdots +f_{N}(S_{N})}$$ ${\displaystyle f_{i}(S_{i})}$ ${\displaystyle S_{i}}$ ${\displaystyle i}$

Чтобы смоделировать эпистаз , мы вводим еще один фактор K — количество других генов, с которыми взаимодействует ген. Разумно предположить, что в плазмиде два гена взаимодействуют, если они расположены рядом, что дает, например, когда K = 1 и N = 5 , $${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1},S_{2})+f_{2}(S_{2},S_{3})+\cdots +f_{N-1}(S_{N-1},S_{N})+f_{N}(S_{N},S_{1})}$$

${\displaystyle F(00101)=f_{1}(0,0)+f_{2}(0,1)+f_{3}(1,0)+f_{4}(0,1)+f_{5}(1,0)}$

Модель NK обобщает это, допуская произвольные конечные K, N, а также допуская произвольное определение смежности генов (гены не обязательно лежат на окружности или отрезке прямой).

Математическое определение

Модель NK определяет комбинаторное фазовое пространство , состоящее из каждой строки (выбранной из заданного алфавита) длины . Для каждой строки в этом пространстве поиска определяется скалярное значение (называемое пригодностью ). Если между строками определена метрика расстояния , результирующая структура представляет собой ландшафт . ${\displaystyle N}$

Значения приспособленности определяются в соответствии с конкретным воплощением модели, но ключевой особенностью модели NK является то, что приспособленность данной строки представляет собой сумму вкладов каждого локуса в строке: ${\displaystyle S}$ ${\displaystyle f_{i}(S)}$

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

а вклад каждого локуса в целом зависит от его состояния и состояния других локусов: ${\displaystyle K}$

${\displaystyle {\tilde {f}}_{i}(S)=f_{i}(S_{i},S_{k_{i1}},\dots ,S_{k_{iK}}),}$

где – номер соседа локуса . ${\displaystyle k_{ij}}$ ${\displaystyle j}$ ${\displaystyle i}$

Следовательно, функция приспособленности представляет собой отображение между строками длины K  + 1 и скалярами, которые в более поздней работе Вайнбергера называются «вкладами приспособленности». Такие вклады приспособленности часто выбираются случайным образом из некоторого заданного распределения вероятностей. ${\displaystyle f_{i}}$

Визуализация двух измерений фитнес-ландшафта НК. Стрелки обозначают различные мутационные пути, по которым может следовать популяция, развиваясь в сфере фитнеса.

Пример: модели спинового стекла.

Одномерную модель спинового стекла Изинга обычно записывают так: где – гамильтониан, который можно рассматривать как энергию. $${\displaystyle H=-\sum _{i=1}^{N}J_{i,i+1}S_{i}S_{i+1}-\mu \sum _{i=1}^{N}h_{i}S_{i}}$$ ${\displaystyle H}$

Мы можем переформулировать это как частный случай модели НК с K=1 : определив В общем, m-мерная модель Изинга на квадратной сетке является моделью НК с . $${\displaystyle H=F(S)=\sum _{i,j}f_{i,j}(S_{i},S_{j})}$$ $${\displaystyle f_{i}(S_{i},S_{i+1})=-J_{i,i+1}S_{i}S_{i+1}-\mu h_{i}S_{i}}$$ ${\displaystyle \{1,2,...,n\}^{m}}$ ${\displaystyle N=n^{m},K=m}$

Поскольку K грубо измеряет «устойчивость» ландшафта приспособленности (см. ниже), мы видим, что по мере увеличения размерности модели Изинга ее устойчивость также увеличивается.

При , это модель Эдвардса-Андерсона, которая точно разрешима. ${\displaystyle \mu =0}$

Модель Шеррингтона-Киркпатрика обобщает модель Изинга, позволяя взаимодействовать всем возможным парам спинов (вместо сеточного графа используйте полный граф ), таким образом, это также модель NK с . ${\displaystyle K=N-1}$

Позволяя взаимодействовать всем возможным подпоследовательностям спинов, а не просто парам, мы получаем модель бесконечного диапазона, которая также является моделью NK с . ${\displaystyle K=N-1}$

Настраиваемая топология

Иллюстрация настраиваемой топологии в модели NK. Узлы — это отдельные двоичные строки, ребра соединяют строки с расстоянием Хэмминга , равным ровно единице. (слева) N = 5, K = 0. (в центре) N = 5, K = 1. (справа) N = 5, K = 2. Цвет узла обозначает его пригодность, причем более красные значения имеют более высокую пригодность. Вложение гиперкуба выбрано так, чтобы максимум приспособленности находился в центре . Обратите внимание, что ландшафт K = 0 выглядит более гладким, чем случаи с более высоким K.

Значение K контролирует степень эпистаза в модели NK или то, насколько другие локусы влияют на вклад приспособленности данного локуса. При K = 0 пригодность данной строки представляет собой простую сумму отдельных вкладов локусов: для нетривиальных функций приспособленности присутствует глобальный оптимум , который легко найти (геном всех нулей, если f (0) > f (1 ), или все единицы, если f (1) > f (0)). При ненулевом K пригодность строки представляет собой сумму приспособленностей подстрок, которые могут взаимодействовать, разрушая систему (подумайте, как достичь оптимальной приспособленности в приведенном выше примере). Таким образом, увеличение K увеличивает устойчивость фитнес-ландшафта.

Вариации с нейтральными пространствами

Голая NK-модель не поддерживает феномен нейтрального пространства — то есть наборов геномов, связанных одиночными мутациями, которые имеют одинаковую ценность приспособленности. Были предложены две адаптации для включения этой биологически важной структуры . Модель NKP ^вводит параметр : доля вкладов приспособленности устанавливается равной нулю, так что вклады нескольких генетических ^{мотивов вырождаются} . Модель NKQ вводит параметр и обеспечивает дискретизацию возможных значений вклада приспособленности, так что каждый вклад принимает одно из ^{возможных значений} , снова внося вырождение во вклады от некоторых генетических ^{мотивов} . Голая модель NK соответствует случаям и при этих параметризациях. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle 2^{K}}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle P=0}$ ${\displaystyle Q=\infty }$

Известные результаты

В 1991 г. Вайнбергер опубликовал подробный анализ ^[7] случая, когда вклады приспособленности выбираются случайным образом. Его аналитическая ^оценка числа локальных оптимумов позже ^{оказалась} ошибочной ^. Однако численные эксперименты, включенные в анализ Вайнбергера, подтверждают его аналитический результат о том, что ожидаемая пригодность струны обычно распределяется со средним значением примерно ${\displaystyle 1<<k\leq N}$

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

и дисперсия примерно

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

Приложения

Модель NK нашла применение во многих областях, в том числе при изучении спиновых стекол , коллективном решении задач, ^[8] эпистазе и плейотропии в эволюционной биологии , а также комбинаторной оптимизации .

Рекомендации

1. Бороманд, Амин; Смальдино, Пол Э. (2023). «Предвзятость превосходства и коммуникационный шум могут улучшить коллективное решение проблем». Журнал искусственных обществ и социального моделирования . 26 (3). дои : 10.18564/jasss.5154 .
2. Левинталь, Д.А. (1997). «Адаптация к суровым ландшафтам». Наука управления . 43 (7): 934–950. дои : 10.1287/mnsc.43.7.934.
3. Кауфман, С.; Левин, С. (1987). «К общей теории адаптивных прогулок по пересеченной местности». Журнал теоретической биологии . 128 (1): 11–45. Бибкод : 1987JThBi.128...11K. дои : 10.1016/s0022-5193(87)80029-2. ПМИД  3431131.
4. Кауфман, С.; Вайнбергер, Э. (1989). «Модель NK суровых фитнес-ландшафтов и ее применение к созреванию иммунного ответа». Журнал теоретической биологии . 141 (2): 211–245. Бибкод : 1989JThBi.141..211K. дои : 10.1016/s0022-5193(89)80019-0. ПМИД  2632988.
5. Вайнбергер, Э. (1996), «NP-полнота модели Кауфмана Nk, настраиваемо прочный фитнес-ландшафт», Рабочий документ Института Санта-Фе, 96-02-003.
6. Казначеев, Артем (2019). «Вычислительная сложность как окончательное ограничение эволюции». Генетика . 212 (1): 245–265. doi :10.1534/genetics.119.302000. ПМК 6499524 . ПМИД  30833289. 
7. Вайнбергер, Эдвард (15 ноября 1991 г.). «Локальные свойства модели Кауфмана Нк: настраиваемый суровый энергетический ландшафт». Физический обзор А. 10. 44 (10): 6399–6413. Бибкод : 1991PhRvA..44.6399W. дои : 10.1103/physreva.44.6399. ПМИД  9905770.
8. Бороманд, А. и Смальдино, П.Е., 2021. Тяжелая работа, принятие риска и разнообразие в модели коллективного решения проблем. Журнал искусственных обществ и социального моделирования, 24 (4).