Генетический алгоритм

Материал из MachineLearning.

Версия 11:56, 2 ноября 2008

ДНК

Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. «Отцом-основателем» генетических алгоритмов считается Джон Холланд (англ. John Holland), книга которого «Адаптация в естественных и искусственных системах» (англ. Adaptation in Natural and Artificial Systems) является основополагающим трудом в этой области исследований.

Описание алгоритма

Задача кодируется таким образом, чтобы её решение могло быть представлено в виде вектора («хромосома»). Случайным образом создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются вектора (селекция), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» - crossover и «мутация» - mutation), создавая таким образом следующее «поколение». Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторы и т. д. Так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:

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

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

Таким образом, можно выделить следующие этапы генетического алгоритма:

1. Создание начальной популяции
2. Вычисление функций приспособленности для особей популяции (оценивание)
3. (Начало цикла)
   1. Выбор индивидов из текущей популяции (селекция)
   2. Скрещивание и\или мутация
   3. Вычисление функций приспособленности для всех особей
   4. Формирование нового поколения
   5. Если выполняются условия остановки, то (конец цикла), иначе (начало цикла).

Кодирование генома

На первом этапе создания ГА требуется решить, какие признаки и как(Вектор типов) будут закодированы в хромосому. В природе каждый элемент гена может иметь только 4 возможных варианта (4 азотистых основания ДНК: Тимин, Гуанин, Аденин, Цитозин). В ГА часто используют следующие типы кодирования:

• Бинарный, если признак сам по себе является бинарным;
• Численный в двоичной системе. Расширенный вариант бинарного, где используется фиксированное число бит. Самый простой в реализации, но имеет существенный недостаток (см. ниже);
• Код Грея[1]. Избавляет от проблем предыдущего варианта, но добавляет накладные расходы на кодирование/декодирование;
• Без побитовых операторов скрещивания и мутаций:
  • Числа с плавающей запятой. Используются в том случае, когда масштаб изменения признака заранее не известен;
  • Номинальные типы и более абстрактные сущности;
• Типы с автоподстройкой. Основа мета-ГА.

Целевая функция

Целевая функция или функция приспособленности (Fitness) имеет ключевой значение для ГА. Она вместе с вектором типов признаков задаёт саму задачу оптимизации. Вычисление функции приспособленности практически всегда полагается самым трудоёмким процессом, так что вся реализация ГА сведена к уменьшению обращений к этой внешней функции. Например, в природе вычисление целевой функции особи - суть вся жизнь особи от рождения, онтогенеза, рождения и ухода за собственными потомками. В то время как суть ГА - деление и слияние нескольких клеток в репродуктивной системе. В практических задачах вычисление целевой функции - вычисление какой-то сложно устроенной функции или обращение к базе данных.

Создание начальной популяции

Перед первым шагом нужно случайным образом создать некую начальную популяцию; даже если она окажется совершенно неконкурентоспособной (сравнивать-то пока не с чем!), генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности. Итогом первого шага является популяция H, состоящая из N особей.

Отбор

На этапе отбора нужно из всей популяции выбрать определённую её долю, которая останется "в живых" на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.

Размножение

Размножение в генетических алгоритмах обычно половое - чтобы произвести потомка, нужны несколько родителей; обычно, конечно, нужны ровно два (Варианты с несколькими родителями пока либо не исследовались, либо ни к чему не привелиШаблон:Нет источников). Размножение в разных алгоритмах определяется по-разному - оно, конечно, зависит от представления данных. Главное требование к размножению - чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, "смешав" их каким-либо достаточно разумным способом. В простейшем случае, для того чтобы провести операцию размножения, нужно выбрать (1-s)p/2 пар гипотез из H и провести с ними размножение, получив по два потомка от каждой пары (если размножение определено так, чтобы давать одного потомка, нужно выбрать (1 - s)p пар), и добавить этих потомков в H'. В результате H' будет состоять из N особей. Более сложные алгоритмы могут работать сразу с несколькими поколениями или не иметь чёткого понятия "поколение" (см., например, Кагортный ГА).

Основные цели скрещивания:

• Стягивание плотности популяции генотени к тем областям, где она итак велика в том предположении, что "нас много там, где хорошо".
• Перемешивание имеющихся хороших генов по популяции.

Мутации

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

В природе мутация происходят постоянно и преимущественно причиной её является ошибки репликации ДНК при делении клеток. Есть мнение^{[источник?]}, что организмы не стали отказываться от механизмов мутаций, хоть и могли.

Основные цели мутаций:

• Принос новой информации в популяцию;
• Вытягивание из локальных экстремумов;
• Поиск решения вдали от основной генотени популяции.

Применение генетических алгоритмов

Генетические алгоритмы применяются для решения следующих задач:

1. Оптимизация функций
2. Оптимизация запросов в базах данных
3. Разнообразные задачи на графах (задача коммивояжёра, раскраска, нахождение паросочетаний)
4. Настройка и обучение искусственной нейронной сети
5. Задачи компоновки
6. Составление расписаний
7. Игровые стратегии
8. Теория приближений
9. Искусственная жизнь
10. Биоинформатика (свёртывание белков)

Эффективность генетических алгоритмов

Холланд недвусмысленно пишет^{[источник?]}, что при прочих равных условиях ГА будет работать хуже, чем специальный алгоритм, рассчитанный на конкретную задачу (тип признаков, целевую функцию). Например, полный перебор конечного небольшого пространства или любой эффективных алгоритм спуска будет всегда эффективнее чем ГА. Тем не менее, в ситуации, когда о задаче ничего a priori не известно, можно полагаться на результат работы простейшего генетического алгоритма как некого приближения.

Существуют некоторый класс функций (Building Blocks), с которым за приемлемое время (пока?) справляются только генетические алгоритмы.

Мнения

Конвергенция с генетикой и синтетической теории эволюции

Прообраз генетического алгоритма пришёл из биологии и, несомненно, продолжает "подсматривать" оттуда ответы на многие вопросы, возникающие при проектированию эффективных реализаций генетических алгоритмов. Более того, идеи по оптимизации ГА находят свою поддержку подтверждение и у биологов. Например, такие явления как га- ди- и квадру- плоидные наборы хромосом, инцест, удвоение гена, управление скоростью мутаций, триггеры и т.п. Тем не менее, математика и кибернетика позволяет выйти за пределы химической реальности клетки и представить n-плоидный набор хромосом, объектные сущности вместо генов и т.п.

Нейронные сети и эволюционное моделирование

ИНС и ГА часто пытаются применять к тандеме, т.к. и те и другие имеют корни из биологии. Тем не менее (см. выше об эффективности ), во-первых алгоритм обратного распространения ошибки настройки ИНС работает значительно (на порядок) быстрее в простых случаях. А во-вторых, настройка нейронной сети в биологии происходит методом, который, скорее всего, значительно разнится с генетическим подходом.

Аналогия с другими алгоритмами

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

Преимущества ГА

• Большое число свободных параметров, позволяющим эффективно встраивать эвристики (см. Мета-ГА);
• Эффективное распараллеливание;
• Работает заведомо не хуже абсолютно случайного поиска;
• Связь с биологией, дающая некоторую надежду на исключительную эффективность ГА в природе.

Недостатки ГА

• Большое количество свободных параметров, которое превращает "работу с ГА" в "игру с ГА";
• Недоказанность сходимости;
• В просты целевых функциях (гладкие, один экстремум и т.п.) генетика всегда проигрывает по скорости простым алгоритмам поиска.

Некоторые конкретные реализации

• Простой ГА (sGA)
• Кагортный ГА (cGA)
• Мета-ГА (mGA) - некая абстрактная реализация самообучающегося ГА

Читайте также

• Теорема схемы
• Операторы ГА - пример в непрерывном пространстве
• Building Blocks
• n-плоидный набор хромосом -- Га- ди- и т.д набор. Здесь же особенности инцеста.

...

Ссылки

Генетические алгоритмы и не только
Генетические алгоритмы на basegroup.ru
GAUL: Genetic Algorithm Utility Library — нетривиальная обобщенная свободная реализация GA