Модели эволюции. Генетические алгоритмы

Вид материала

Реферат

Содержание 2.2. Модель случайно взаимодействующих элементов.

Подобный материал:

• Доклад «Моделирование эволюции. Генетические алгоритмы», 75.42kb.
• Доклад «Моделирование эволюции. Генетические алгоритмы», 108.9kb.
• Доклад на тему: "Модели эволюций и генетические алгоритмы", 155.74kb.
• Информатика, вычислительная техника и инженерное образование 2011, №1(3) эволюционное, 635.81kb.
• Л. И. Параллелизмы в молекулярной организации генома и проблемы эволюции. В кн.: Молекулярные, 251.18kb.
• Программа дисциплины «Нечеткая логика, генетические алгоритмы и экспертные системы, 228.23kb.
• Дисциплина: Инженерия знаний Доклад Генетические алгоритмы, 371.21kb.
• Курс, 1-й семестр лекции (51 час), экзамен практикум на ЭВМ (68 часов), зачет (с оценкой), 24.4kb.
• Фрагментные генетические алгоритмы, 140.16kb.
• Курсовая работа По дисциплине: «Моделирование систем» По теме: «Генетические алгоритмы, 324.78kb.

2.2. Модель случайно взаимодействующих элементов.

Была рассмотрена Дарвиновская эволюция информационных последовательностей – модель квазивидов. Был рассмотрен простейший случай Хемминговой меры близости между последовательностями. А именно, анализировалась эволюция популяции последовательностей S₁ , S₂ , ... , S_n в предположении, что имеется одна наилучшая особь S_m , а приспособленность f(S) произвольной особи S определяется расстоянием по Хеммингу  (S, S_m) между S и S_m (числом несовпадающих компонент в этих векторах), причем  f(S) экспоненциально уменьшается с ростом (S, S_m):

  f(S_k) = exp[-  (S_k, S_m)],                                                              (1)

где - параметр, характеризующий интенсивность отбора.

Рассматривался поэтапный эволюционный процесс, в котором на каждом этапе происходит отбор особей в популяцию следующего поколения с вероятностями, пропорциональными их приспособленностям, а также мутации особей - равновероятные замены компонент векторов S . При достаточно малой интенсивности мутаций после большого числа этапов эволюции в популяции формируется стационарное распределение последовательностей   - квазивид, в который входят оптимальная особь S_m и ее ближайшие мутанты.

Существенный недостаток модели с Хемминговой мерой близости – предположение о существовании единственного максимума приспособленности f(S). В настоящей лекции мы устраним этот недостаток и построим модель для многоэкстремальной функции приспособленности f(S) , используя хорошо известную модель спиновых стекол Шеррингтона-Киркпатрика (1975г.), и покажем, что основные особенности "спин-стекольной" модели эволюции во многом аналогичны таковым в модели с Хемминговой мерой близости. Основное отличие состоит в том, что квазивид формируется в окрестности не глобального минимума приспособленности, а в окрестности одного из локальных максимумов приспособленности.

Рассмотрим эволюцию популяции, в которой "геномы" S модельных особей представляют собой информационные последовательности N символов S = S₁ , S₂ ,..., S_N . Символы принимают значения 1 или  -1: S_i = 1, -1 .   Популяция есть набор {S_k}, состоящий из n  последовательностей, k = 1,..., n. Приспособленности модельных "организмов" S_k определяем как:

f(S_k) = exp[- E(S_k)] ,                                                                             (9)

где E(S_k)   – энергия спинового стекла, задаваемая формулами (2), (3),  – параметр интенсивности отбора.

Определение (9) подразумевает, что модельный "геном"  S_k состоит из последовательности элементов S_ki,  i = 1 , ..., N ,  которые случайно попарно взаимодействуют в  соответствии с матрицей взаимодействия J_ij . Максимальной приспособленностью (соответственно, минимальной энергией  E(S)) будут обладать те "организмы",  имеющие такую комбинацию элементов S_i , которая обеспечивает максимальную  кооперативность взаимодействий между спинами S_i  для данной матрицы J_ij .

Как и для Хемминговой меры близости предполагаем, что эволюционный процесс состоит из последовательности поколений. Новое поколение  {S_k (t+1)}получается из старого S_k(t) путем отбора и мутаций последовательностей S_k (t).

Формально эволюционный процесс может быть описан следующим псевдокодом:

	Шаг 0. Формирование начальной популяции {Sk (0)}. Для каждого k = 1, ..., n, и для каждого  i = 1 , ..., N , выбираем случайно символ Ski, полагая его равным 1 или -1.
	Шаг 1. Отбор

	Подшаг 1.1.   Расчет приспособленностей. Для каждого k = 1, ..., n, вычисляем величину f(Sk) в соответствии с формулами (2), (3), (9).
	Подшаг 1.2. Формирование популяции следующего поколения{Sk (t+1)}. Отбор   n особей в новую популяцию{Sk (t+1)} с вероятностями, пропорциональными f(Sk).

	Шаг 2. Мутации. Для каждого k = 1, ..., n, для каждого   i = 1, ..., N, с вероятностью Pm переворачиваем спин Ski(t+1): Ski --> - Ski. Параметр Pm характеризует интенсивность мутаций.
	Шаг 3. Организация последовательности поколений. Повторяем шаги 1, 2 для t = 0, 1, 2, ...

Отметим, что здесь параметр P_m отличается от параметра P (вероятность выбора символа для мутационной  замены), введенного в предыдущей лекции: P_m = 0,5P.

Описанная модель "спин-стекольной" эволюции анализировалась путем компьютерного моделирования и приближенных оценок [6]. Особенности эволюционного процесса иллюстрируются Рис. 1. Здесь n(E) – число таких последовательностей S , что  E(S) = E  в рассматриваемой популяции,  t   – номер поколения.



Рис. 1. Распределение последовательностей по энергиям  n(E) для разных поколений t ; t₃ > t₂ > t₁ ;  E₀ и E_L – глобальный и локальный минимумы энергии, соответственно; глобальный минимум энергии E₀ приближенно составляет: E₀ = - 0,8 N. Схематично, согласно компьютерному моделированию  [6].

Эволюция в спин-стекольной модели аналогична таковой для Хемминговой меры близости. Но в отличие от модели с Хемминговой мерой близости эволюция сходится к одному из локальных минимумов энергии E_L  , который может быть различен для различных реализаций эволюционного процесса.

Наряду с эволюционным процессом мы можем рассматривать последовательный поиск минимумов энергии спинового стекла. А именно, задаем систему из  N спинов, случайно выбираем спин S_i , переворачиваем его (S_i --> - S_i) и смотрим: уменьшилась энергия или увеличилась, при уменьшении энергии принимаем новое значение спина, при увеличении – возвращаемся к старому. Такой последовательный процесс также сходится к какому-либо локальному минимуму E_L . Моделирование показывает, что в среднем эволюционный процесс сходится к более глубокому локальному минимуму энергии E_L, чем последовательный поиск. Это обусловлено тем, что при эволюционном поиске одновременно просматриваются несколько "долин" в энергетическом ландшафте E(S) и увеличиваются шансы попасть в более глубокую долину и соответственно достичь более глубокого минимума энергии. 

Итак, на основе понятия спиновых стекол можно построить модель эволюции для "организмов", геномы которых состоят из множества случайно взаимодействующих между собой элементов. Эволюция может рассматриваться как процесс поиска такой комбинации элементов, которая обеспечивает наиболее эффективную кооперацию элементов генома.