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

На рисунке 85 приведен пример простого генетического алгоритма.

Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока поколения не перестанут существенно отличаться друг от друга, или не пройдет заданное количество поколений или заданное время. Для каждого поколения реализуются отбор, кроссовер (скрещивание) и мутация. Рассмотрим этот алгоритм.

Шаг 1: генерируется начальная популяция, состоящая из N особей со случайными наборами признаков.

Шаг 2 (борьба за существование): вычисляется абсолютная приспособленность каждой особи популяции к условиям среды f(i) и суммарная приспособленность особей популяции, характеризующая приспособленность всей популяции. Затем при пропорциональном отборе для каждой особи вычисляется ее относительный вклад в суммарную приспособленность популяции P_s(i), т.е. отношение ее абсолютной приспособленности f(i) к суммарной приспособленности всех особей популяции (3):

В выражении (3) сразу обращает на себя внимание возможность сравнения абсолютной приспособленности i-й особи f(i) не с суммарной приспособленностью всех особей популяции, а со средней абсолютной приспособленностью особи популяции (4):

Тогда получим (5):

Если взять логарифм по основанию 2 от выражения (5), то получим количество информации, содержащееся в признаках особи о том, что она выживет и даст потомство (6).

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

Поскольку количество потомства особи пропорционально ее приспособленности, то естественно считать, что если это количество информации:

- положительно, то данная особь выживает и дает потомство, численность которого пропорциональна этому количеству информации;

- равно нулю, то особь доживает до половозрелого возраста, но потомства не дает (его численность равна нулю);

- меньше нуля, то особь погибает до достижения половозрелого возраста.

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

Это накопление информации происходит на различных уровнях иерархии популяции, как системы, включающей:

- элементы системы: отдельные особи;

- взаимосвязи между элементами: отношения между особями в популяции, обеспечивающие передачу последующим поколениям максимального количества информации об их выживании и продолжении рода (путем скрещивания наиболее приспособленных особей и наследования рациональных приобретений);

- цель системы: сохранение и развитие популяции, реализуется через цели особей: индивидуальное выживание и продолжение рода.

Фенотип соответствует генотипу и представляет собой его внешнее проявление в признаках особи. Особь взаимодействует с окружающей средой и другими особями в соответствии со своим фенотипом. В случае, если это взаимодействие удачно, то особь передает генетическую информацию, определяющую фенотип, последующим поколениям.

Шаг 3: начало цикла смены поколений.

Шаг 4: начало цикла формирования нового поколения.

Шаг 5 (отбор): осуществляется пропорциональный отбор особей, которые могут участвовать в продолжении рода. Отбираются только те особи популяции, у которых количество информации в фенотипе и генотипе о выживании и продолжении рода положительно, причем вероятность выбора пропорциональна этому количеству информации.

Шаг 6 (кроссовер): отобранные для продолжения рода на предыдущем шаге особи с заданной вероятностью P_c подвергаются скрещиванию или кроссоверу (рекомбинации).

Если кроссовер происходит, то потомки получают по половине случайным образом определенных признаков от каждого из родителей. Численность потомства пропорциональна суммарной приспособленности родителей. В некоторых вариантах ГА потомки после своего появления заменяют собой родителей и переходят к мутации.

Если кроссовер не происходит, то исходные особи - несостоявшиеся родители, переходят на стадию мутации.

Шаг 7 (мутация): выполняются операторы мутации. При этом признаки потомков с вероятностью P_m случайным образом изменяются на другие. Отметим, что использование механизма случайных мутаций роднит генетические алгоритмы с таким широко известным методом имитационного моделирования, как метод Монте-Карло.

Шаг 8 (борьба за существование): оценивается приспособленность потомков (по тому же алгоритму, что и на шаге 2).

Шаг 9: проверяется, все ли отобранные особи дали потомство.

Если нет, то происходит переход на шаг 5 и продолжается формирование нового поколения, иначе - переход на следующий шаг 10.

Шаг 10: происходит смена поколений:

- потомки помещаются в новое поколение;

- наиболее приспособленные особи из старого поколения переносятся в новое, причем для каждой из них это возможно не более заданного количества раз;

- полученная новая популяция замещает собой старую.

Шаг 11: проверяется выполнение условия останова генетического алгоритма. Выход из генетического алгоритма происходит либо тогда, когда новые поколения перестают существенно отличаться от предыдущих, т.е., как говорят, "алгоритм сходится", либо когда пройдено заданное количество поколений или заданное время работы алгоритма (чтобы не было "зацикливания" и динамического зависания в случае, когда решение не может быть найдено в заданное время ).

Если ГА сошелся, то это означает, что решение найдено, т.е. получено поколение, идеально приспособленное к условиям данной фиксированной среды обитания.

Иначе - переход на шаг 4 - начало формирования нового поколения.

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

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

Поэтому под термином "генетические алгоритмы" по сути дела надо понимать не одну модель, а довольно широкий класс алгоритмов, подчас мало похожих друг на друга.

В настоящее время рассматривается много различных операторов отбора, кроссовера и мутации: турнирный отбор (Brindle, 1981; Goldberg и Deb, 1991), реализует n турниров, чтобы выбрать n особей, при этом каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них (наиболее распространен турнирный отбор с k=2); элитный отбор (De Jong, 1975) гарантируют, что при отборе обязательно будут выживать лучший или лучшие члены популяции совокупности (наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла как другие через процесс отбора, кроссовера и мутации); двухточечный кроссовер (Cavicchio, 1970; Goldberg, 1989c) и равномерный кроссовер (Syswerda, 1989) отличаются способами наследования потомками признаков родителей.

Не смотря на то, что модели биологической эволюции, реализуемые в ГА, обычно сильно упрощены по сравнению с природным оригиналом, тем ни менее ГА являются мощным средством, которое может с успехом применяться для решения широкого класса прикладных задач, включая те, которые трудно, а иногда и вовсе невозможно, решить другими методами.

3. Достоинства и недостатки генетических алгоритмов

Однако, ГА не гарантирует обнаружения глобального решения за приемлемое время. ГА не гарантируют и того, что найденное решение будет оптимальным решением. Тем ни менее они применимы для поиска "достаточно хорошего" решения задачи за "достаточно короткое время". ГА представляют собой разновидность алгоритмов поиска и имеют преимущества перед другими алгоритмами при очень больших размерностях задач и отсутствия упорядоченности в исходных данных, когда альтернативой им является метод полного перебора вариантов.

В случаях, когда задача может быть решена специально разработанным для нее методом, практически всегда такие методы будут эффективнее ГА как по быстродействию, так и по точности найденных решений.

Главным же достоинством ГА является то, что они могут применяться для решения сложных неформализованных задач, для которых не разработано специальных методов, т.е. ГА обеспечивают решение проблем. Но даже в тех случаях, для которых хорошо работают существующие методики, можно достигнуть интересных результатов сочетая их с ГА.

4. Примеры применения генетических алгоритмов