Генетические алгоритмы. 
Искусственные нейронные сети

Генетический алгоритм — это простая модель эволюции в природе. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде.

Вот как моделируется генетическое наследование:

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

Жизненный цикл популяции — это несколько случайных скрещиваний (посредством рекомбинации) и мутаций, в результате которых к популяции добавляется какое-то количество новых индивидуумов. Отбор в генетическом алгоритме — это процесс формирования новой популяции из старой, после чего старая популяция погибает. После отбора к новой популяции опять применяются операции рекомбинации и мутации, затем опять происходит отбор, и так далее.

Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе следующим образом:

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

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

кодирование прикладной задачи, множество операторов мутации, критерий селекции.

Сущность их очень проста. Обычно генетический алгоритм стартует с некоторой популяцией индивидов. Каждый из них оценивается по некоторому критерию селекции. На основе значения этого критерия для отдельного индивида выносится решение о величине вероятности наследования его свойств в следующем поколении. Обычно при таком наследовании свойств применяются так называемые операторы мутации и/или рекомбинации (crossing-over). Следующее поколение индивидов также оценивается и описанный процесс стартует снова. Структура алгоритма представлена на рис. 1.

Рис. 1. Структура генетического алгоритма.

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

Генетические алгоритмы оказались очень эффективными при решении задач многомерной оптимизации. В этих случаях под индивидом понимается ничто иное как значение оптимизируемой функции в некоторой точке области определения. Этот индивид представляется (кодируется) бинарными кодами:

I_i = (x, y), где x, y [0,1]^k

Операторы.

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

точечная мутация и рекомбинация (crossing-over).

При бинарном кодировании данных об индивиде точечная мутация сводится к инвертированию содержимого одного случайно выбранного бита (разряда).

Пример:

100 011 101 011 100 111 101 011.

Здесь инвертированный разряд выделен большим размером.

При рекомбинации (crossing-over) в текущей популяции выбираются две двоичные последовательности и в них производится обмен двух соответствующих частей. Из двух возникающих при этом индивидов выбирается один индивид для следующего поколения (рис. 2).

Рис. 2. Операторы рекомбинации (первый вариант).

На рис. 3 представлен набор наиболее популярных операторов скрещивания для рекомбинации (crossing-over).

Рис. 3. Операторы рекомбинации (второй вариант).

Критерии селекции Выбор индивида осуществляется на основе подходящего критерия селекции, измеряющего степень эффективности (Fitness, Performanz) некоторого индивида по сравнению со своими «конкурентами». В нашем примере оптимизации функций в качестве критерия селекции используется непосредственно значение функции f (x). Степень эффективности (Fitness) некоторого индивида x выражается значением функции f в этой точке x. На рис. 4 а-г представлен принцип функционирования генетического алгоритма.

Рис. 4. Принцип функционирования генетического алгоритма

Преимущества генетических алгоритмов в сравнении с другими методами оптимизации (например, градиентными методами):

Глобальная оптимизация. Вследствие случайной составляющей генетический алгоритм может исследовать все функциональное пространство. В результате этого в частности становится возможным выход из локальных минимумов. Следует однако отметить, что во многих случаях обычные методы оптимизации (hill-climbing-Methoden) используются в окрестности предполагаемого глобального оптимума, ибо последние обычно быстрее и надежнее отыскивают абсолютный оптимум.

Минимальное знание и функции цели. Генетические алгоритмы ограничиваются измерением степени эффективности (Fitness) индивида. Они используют лишь значение функции f в точке x. При этом информация о первой или второй производной для расчета градиента не используется.

Параллельность генетических алгоритмов. Генетические алгоритмы тривиально могут быть реализованы на нескольких процессорах.