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


Содержание

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

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

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

Впервые подобный алгоритм был предложен в 1975 году Дж. Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов.

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

В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.

Основные генетические операторы

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

  1. из популяции выбираются две особи, которые будут родителями;
  2. определяется (обычно случайным образом) точка разрыва;
  3. потомок определяется как конкатенация части первого и второго родителя.

Рассмотрим функционирование этого оператора:

Допустим, разрыв происходит после 3-го бита хромосомы, тогда

Хромосома_1: 0000000000 >> 000 1111111 Результирующая_хромосома_1

Хромосома_2: 1111111111 >> 111 0000000 Результирующая_хромосома_2

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

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

000 1111111 >> 1111111 000

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

Схема функционирования генетического алгоритма

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

  1. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B = 1,A2,…,Ak)
  2. Вычислить приспособленность (пригодность) каждой особи FAi = fit(Ai) , i=1…k и популяции в целом Ft = fit(Bt) (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
  3. Выбрать особь Ac из популяции. Ac = Get(Bt)
  4. С определенной вероятностью (вероятностью кроссовера Pc) выбрать вторую особь из популяции Аc1 = Get(Bt) и произвести оператор кроссовера Ac = Crossing(Ac,Ac1).
  5. С определенной вероятностью (вероятностью мутации Pm) выполнить оператор мутации. Ac = mutation(Ac).
  6. С определенной вероятностью (вероятностью инверсии Pi) выполнить оператор инверсии Ac = inversion(Ac).
  7. Поместить полученную хромосому в новую популяцию insert(Bt+1,Ac).
  8. Выполнить операции, начиная с пункта 3, k раз.
  9. Увеличить номер текущей эпохи t=t+1.
  10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Рассмотрим подробнее отдельные этапы алгоритма.

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

Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

Другой важный момент – определение критериев останова.

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

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

Пример

Найти максимум функции f(x)=x2 в диапазоне 0

Документация

Fuzzy Logic Toolbox™ обеспечивает функции MATLAB ® , приложения и блок Simulink ® для анализа, разработки и симуляции систем на основе нечеткой логики. Руководства по продукту вы через шаги разработки нечетких систем вывода. Функции обеспечиваются для многих общепринятых методик, включая нечеткую кластеризацию и адаптивное нейронечеткое изучение.

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

Начало работы

Изучите основы Fuzzy Logic Toolbox

Нечеткое системное моделирование вывода

Создайте нечеткие системы вывода и нечеткие деревья

Нечеткая системная настройка вывода

Настройте функции принадлежности и правила нечетких систем

Кластеризация данных

Найдите кластеры в данных о вводе/выводе с помощью нечетких c-средних-значений или отнимающей кластеризации

Моделируйте системы в Simulink

Развертывание

Сгенерируйте код для оценки нечетких систем

Документация Fuzzy Logic Toolbox
Поддержка

© 1994-2020 The MathWorks, Inc.

1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.

2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.

3. Сохраняйте структуру оригинального текста — например, не разбивайте одно предложение на два.

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

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

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

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

Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

Представление объектов

Из биологии мы знаем, что любой организм может быть представлен своим 36h->54d. Теперь посмотрим, какой интервал ему соответствует… После несложных подсчетов получаем интервал [0,20703125, 0,2109375]. Значит значение нашего параметра будет (0,20703125+0,2109375)/2=0,208984375.

Кодирование нечисловых данных

При кодировании нечисловых данных необходимо предварительно преобразовать их в числа. Более подробно это описано в статьях нашего сайта, посвященных использованию нейронных сетей.

Определение фенотипа объекта по его генотипу

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит

0010 1010 1001 0100 1101

теперь мы можем определить значения признаков

Основные генетические операторы

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

  1. из популяции выбираются две особи, которые будут родителями;
  2. определяется (обычно случайным образом) точка разрыва;
  3. потомок определяется как конкатенация части первого и второго родителя.

Рассмотрим функционирование этого оператора:

Признак Значение гена Двоичное значение признака Десятичное значение признака
Признак 1
Хромосома_1: 0000000000
Хромосома_2: 1111111111

Допустим разрыв происходит после 3-го бита хромосомы, тогда

Хромосома_1: 0000000000 >> 000 1111111 Результирующая_хромосома_1
Хромосома_2: 1111111111 >> 111 0000000 Результирующая_хромосома_2

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

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

000 1111111 >> 1111111 000

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

Схема функционирования генетического алгоритма

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

  1. Инициировать начальный момент времени $t=0$. Случайным образом сформировать начальную популяцию, состоящую из $k$ особей. $B_0 = \$
  2. Вычислить приспособленность каждой особи $F_ = fit(A_i)$ , $i=1…k$ и популяции в целом $F_t = fit(B_t)$ (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
  3. Выбрать особь $A_c$ из популяции $A_c = \mbox Get(B_t)$
  4. С определенной вероятностью (вероятностью кроссовера $P_c$) выбрать вторую особь из популяции $A_ = \mbox Get(B_t)$ и произвести оператор кроссовера $A_c = \mbox (A_c, A_)$.
  5. С определенной вероятностью (вероятностью мутации $P_m$) выполнить оператор мутации $A_c = \mbox (A_c)$.
  6. С определенной вероятностью (вероятностью инверсии $P_i$) выполнить оператор инверсии $A_c = \mbox (A_c)$.
  7. Поместить полученную хромосому в новую популяцию $\mbox (B_,A_c)$.
  8. Выполнить операции, начиная с пункта 3, $k$ раз.
  9. Увеличить номер текущей эпохи $t=t+1$.
  10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Теперь рассмотрим подробнее отдельные этапы алгоритма.

Наибольшую роль в успешном функционировании алгоритма играет этап отбора родительских хромосом на шагах 3 и 4. При этом возможны различные варианты. Наиболее часто используется метод отбора, называемый рулеткой. При использовании такого метода вероятность выбора хромосомы определяется ее приспособленностью, то есть $P_

Fit(A_i)/Fit(B_t)$. Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

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

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

Генетический алгоритм — это довольно новый инструмент в арсенале решения задач. Использовать метод стало возможным благодаря вычислительной технике. ЭВМ позволяет человеку невиданную ранее (ещё каких то 30 лет назад) роскошь — выполнять много бесполезных расчетов за короткое время. :)

По закону диалектики количество переходит в новое качество. Этим качеством является метод в решении задач оптимизации — генетические алгоритмы.

Причем тут генетика?

Стоит пояснить почему прилипло такое название, в чем смысл метафоры.

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

Миллиарды лет природа бросает игральные кости, генерирует варианты кода, самые эффективные из которых передаются в генах потомству.

Решает природа какие то уравнения? Нет. Есть ли какой то генеральный план? Нет. Восхищаемся ли мы тем, что в итоге получилось? — несомненно, да.

Осталось только повторить трюки природы (и запастись временем).

Давайте проводить параллели

В природе конкуренция идет между особями внутри популяции живых организмов. Кто лучше приспособлен — тот и выживает.

Инициализация: Вначале, нам нужно найти хоть какое то решение задачи. Одно или несколько решений сформируют начальный набор. Эти решения не оптимальны, они далеки от идеала, но обладают формальными признаками решения.

В терминах природы, каждое решение — это особь. Набор таких решений — популяция.

Пример: Для решения задачи о поиске кратчайшего пути из точки А к точке Б — нам нужно будет придумать вообще какие то пути из точки А к точке Б.

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

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

Пример: Для отбора кратчайшего пути необходимо посчитать длины маршрутов и сравнить их.

Кто больше приспособлен для этой жизни?

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

Отбор: Самые неудачные решения мы отбрасываем. Какую часть отбросить, а какую оставить — решать вам.

Пример: Мы можем отбрасывать какую то часть самых длинных маршрутов, а можем оставлять только один — самый лучший. Только практика покажет, какой подход верен в контексте вашей задачи.

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

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

Откуда берется новый набор генов в природе? Особенно таких, которых не было у родителей? Для этого у природы в рукаве спрятана эдакая игральная кость — мутация. Есть и другие механизмы.

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

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

Пример: Таким механизмом для алгоритма поиска оптимального пути может быть смещение уже существующих точек маршрута, добавление/удаление точек, через которые проходит маршрут и т.п.

Этапы генетического алгоритма

Изучая «тактику» природы, мы выделили несколько важных этапов —

  1. Инициализация,
  2. Отбор, используя критерий отбора,
  3. Формирование новых решений, используя механизмы изменения.

2й и 3й этапы мы будем повторять многократно. Мы не узнаем — являются ли новые решения идеальными. Когда оставить процесс — решать вам.

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

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

Я начал с того, что заявил о появлении генетических алгоритмов, как результате явного прогресса вычислительной техники. Казалось бы есть все шансы не гадать (а генетический алгоритм именно этим и занимается), а посчитать.

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

К примеру, классическая задача о Коммивояжере. При большом числе точек, перебор всех вариантов путей, чтобы найти тот единственный кратчайший, невозможен за адекватное время, используя современные ЭВМ.

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

И вот вы, не зная как получить точное решение, позволяете компьютеру бросать кости, чтобы он случайно нашел какое то решение.

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

Особенности генетического алгоритма

Вот что мы выяснили:

  • Генетический алгоритм не позволяет оценить насколько далеко вы от идеального решения;
  • Основной ресурс — время;
  • Задача решается приближено.

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

Данная запись опубликована в 09.12.2020 22:44 и размещена в Программирование. Вы можете перейти в конец страницы и оставить ваш комментарий.

Мало букафф? Читайте есчо !

Алкаши и наркоманы

На ленте прочитал с утра новость о запрете марша за легализацию марихуаны. На что надеются эти наркоманы? Что у нас как в США (в штатах Колорадо, Вашингтон .

По ту сторону от большого взрыва

О теории большого взрыва многие слыхали. Если вкратце, то сначала всех времен, где то 14 млрд. лет назад жил-был очень мощный фотон. Или квант какого то .

Генетические алгоритмы — это просто!

Введение

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

Классическим примером задач этого класса (класс NP) является “Задача коммивояжера” (является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.). Но ничто не мешает использовать их и для задач, поддающихся формализации.

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

Стоит отдельно упомянуть о том, что MetaQuotes Software Corp. использует ГА в своих программных продуктах MetaTrader 4/5. Все мы знаем о тестере стратегий и о том, сколько времени и усилий позволяет сэкономить встроенный оптимизатор стратегий, в котором на ряду с прямым перебором имеется возможность оптимизации с применением ГА. Кроме того, тестер MetaTrader 5 позволяет использовать пользовательские критерии оптимизации. Возможно, читателю будет интересно прочитать статьи на тему ГА и о преимуществах, которые дают ЭА по сравнению с прямым перебором.

1. Немного истории

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

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

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

Я не захотел связываться с двоичными преобразованиями, и решил работать с генами напрямую, т.е. представлять хромосому набором генов в виде вещественных чисел. Так появился на свет код моего генетического алгоритма с представлением хромосом вещественными числами. Позднее я узнал, что ничего нового не открыл, и подобные генетические алгоритмы (их называют real-coded GA) существуют уже более 15-и лет с момента первых публикаций о них.

Представленное на суд читателя моё видение подходов к реализации и принципах функционирования ГА основано на личном опыте использования их в практических задачах.

2. Описание ГА

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

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

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

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

Договоримся изображать хромосому в виде столбика. Тогда хромосома для функции f(x)=x^2 , будет выглядеть так:

Рисунок 1. Хромосома для функции f(x)=x^2

где 0-й индекс — значение функции f(x), называют приспособленностью особи (функцию будем называть фитнес функцией — FF, а значение функции — VFF). Хромосому удобно хранить в одномерном массиве. Для этого служит массив double Chromosome[].

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

Полная популяция особей при поиске минимума функции f(x)=x^2 может выглядеть, например, так:

Рисунок 2. Полная популяция особей

Популяция отсортирована по VFF. Здесь 0-й индекс хромосомы занимает особь с наименьшим VFF. Новые потомки полностью замещают только особей в колонии потомков, родительская колония остаётся неприкосновенной. Однако, колония родителей может не всегда быть полной, так как дубликаты особей уничтожаются, тогда новые потомки заполняют свободные места в колонии родителей, оставшиеся помещаются в колонию потомков.

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

Рисунок 3. Популяция до размножения

Рисунок 4. Популяция после размножения

Описанный механизм «половинного» заселения потомками популяции, а также уничтожение дубликатов и запрет на скрещивание особей самим с собой, имеют одну цель — избегать «эффекта бутылочного горлышка» (термин из биологии, означает сокращение генофонда популяции в результате критического уменьшения численности по различным причинам, что может привести к полному вымиранию вида, в ГА это грозит прекращением появления уникальных хромосом и “застреванием” в одном из локальных экстремумов.)

3. Описание функций UGAlib

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

3.1. Global variables. Глобальные переменные

Объявим на глобальном уровне следующие переменные:

3.2. UGA. Основная функция ГА

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

По завершении алгоритма в лог записывается следующая информация:

  • Сколько всего прошло эпох (поколений).
  • Сколько всего сбросов.
  • Количество уникальных хромосом.
  • Общее кол-во запусков FF.
  • Общее кол-во хромосом в истории.
  • Процентное отношение дубликатов к общему кол-ву хромосом в истории.
  • Лучший результат.

«Количество уникальных хромосом» и «Общее кол-во запусков FF» – одни и те же величины, но рассчитываются по-разному. Использовать для контроля.

3.3. ProtopopulationBuilding. Создание протопопуляции.

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

3.4. GetFitness. Получение приспособленности

Выполняет по очереди для всех хромосом оптимизируемую функцию.

3.5. CheckHistoryChromosomes. Проверка хромосомы по базе хромосом

Хромосома каждой особи проверяется по базе — рассчитывалась ли для неё FF, и если рассчитывалась, то готовое VFF берется из базы, если нет, то для неё вызывается FF. Таким образом, исключаются повторные ресурсоемкие вычисления FF.

3.6. CycleOfOperators. Цикл операторов UGA

Здесь, в прямом смысле, вершится судьба целой эпохи искусственной жизни — рождается и умирает целое поколение. Происходит это следующим образом: отбираются два родителя для скрещивания или один для совершения над ним акта мутации. Доля каждого оператора ГА определена соответствующим параметром. В результате появляется один потомок. Всё повторяется снова и снова, пока полностью не заполнится колония потомков. Потом колония потомков выпускается в среду обитания, что бы каждый проявил себя, как может, т.е. вычисляем VFF.

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

3.7. Replication. Репликация

Оператор наиболее близок к природному явлению, которое в биологии имеет название — Репликация ДНК, хотя и не является одним и тем же по сути. Но поскольку более близкого природного эквивалента я не нашел, решил остановиться на этом названии.

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

Рассмотрим принцип работы оператора Replication. Используется две родительские хромосомы. Новый ген потомка случайное число из интервала

где С1 и С2 родительские гены, ReplicationOffset — коэффициент смещения границ интервала [C1,C2].

К примеру, от отцовской особи (синий цвет) и материнской (розовый цвет) может получиться такой потомок (зеленый цвет):

Рисунок 5. Принцип работы оператора Replication

Графически вероятность гена потомка можно представить так:

Рисунок 6. Вероятность появления гена потомка на числовой прямой

Аналогично генерируются остальные гены потомка.

3.8. NaturalMutation. Естественная мутация

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

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

В операторе NaturalMutation мутация заключается в генерации случайного гена в интервале [RangeMinimum,RangeMaximum]. NMutationProbability=100% будет означать 100% мутацию всех генов в хромосоме, а NMutationProbability=0% — полное отсутствие мутаций. Последний вариант в практических задачах использовать не имеет смысла.

3.9. ArtificialMutation. Искусственная мутация

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

Так же, как и в Replication, используется две родительские хромосомы. Но задача оператора ArtificialMutation не передать потомку признаки родителей, а наоборот, сделать потомка непохожим на них. Потому, являясь полной противоположностью, используя тот же коэффициент смещения границ интервала, но гены генерируются вне интервала, который бы занял Replication. Новый ген потомка случайное число из интервалов [RangeMinimum, C1-(C2-C1)*ReplicationOffset] и [C2+(C2-C1)*ReplicationOffset, RangeMaximum]

Графически вероятность гена потомка при ReplicationOffset=0.25 можно представить так:

Рисунок 7. Вероятность появления гена потомка при ReplicationOffset=0.25 на числовой прямой интервале [RangeMinimum;RangeMaximum]

3.10 GenoMerging. Заимствование генов

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

Работает так: для первого гена потомка отбирается родитель и берется у него первый ген, далее, для второго гена отбирается второй родитель и берется второй ген и т.д. Целесообразно применять при количестве генов больше одного. Иначе стоит отключить, так как оператор будет генерировать дубликаты хромосом.

3.11. CrossingOver. Кроссинговер

Кроссинговер (другое название в биологии перекрёст) — явление обмена участками хромосом. Так же, как и GenoMerging, является комбинаторным механизмом поиска.

Отбираются две родительские хромосомы. Обе “разрезаются” в случайном месте. Хромосома потомка будет состоять из родительских частей хромосом.


Механизм проще всего проиллюстрировать рисунком:

Рисунок 8. Механизм обмена участками хромосом

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

3.12. SelectTwoParents. Отбор двух родителей

Для предотвращения обеднения генофонда введен запрет на скрещивание сам с собой. Делается 10 попыток найти разных родителей, если так и не удалось найти пару, дается добро на скрещивание особи сам с собой. По сути, появится копия этой особи.

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

Используется в операторах Replication, ArtificialMutation, CrossingOver.

3.13. SelectOneParent. Отбор одного родителя

Здесь всё просто — из всей популяции отбирается один родитель.

Используется в операторах NaturalMutation и GenoMerging.

3.14. NaturalSelection. Естественный отбор

Естественный отбор — процесс, приводящий к выживанию и преимущественному размножению более приспособленных к данным условиям среды особей, обладающих полезными наследственными признаками.

Оператор похож на традиционный оператор «Рулетка» (Roulette-wheel selection – отбор особей с помощью n «запусков» рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине приспособленности), но имеет существенные отличия. Он учитывает положение особей относительно самой приспособленной и наименее приспособленной. Причем, даже особь, имеющая самые плохие гены, имеет шанс оставить потомка. Справедливо, не правда ли? Хотя дело не в справедливости, а в том, что в природе все особи имеют возможность оставить потомка.

Для примера, возьмем 10 особей, имеющие такие VFF в задаче максимизации: 256, 128, 64, 32, 16, 8, 4, 2, 0,-1 — где наибольшее значение соответствует лучшей приспособленности. Такой пример взят для того, что бы было видно, что «расстояние» между соседними особями в 2 раза больше, чем между двумя предыдущими особями. Однако на круговой диаграмме вероятность того, что каждая особь оставит потомка выглядит так:

Рисунок 9. Диаграмма вероятности отбора родительский особей

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

Рисунок 10. Диаграмма вероятности отбора родительский особей

3.15. RemovalDuplicates. Удаление дубликатов

Функция удаляет дубликаты хромосом в популяции, а оставшиеся уникальные хромосомы (уникальные для популяции текущей эпохи) сортируются по VFF в порядке, определяемым типом оптимизации, т.е. по убыванию или по возрастанию.

3.16. PopulationRanking. Ранжирование популяции

Сортировка производится по VFF. Метод похож на «пузырьковый» (Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован.

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

3.17. RNDfromCustomInterval. Генератор случайных чисел из заданного интервала

Просто удобная функция. Пригодилась и в UGA.

3.18. SelectInDiscreteSpace. Выбор в дискретном пространстве

Служит для уменьшения пространства поиска. При параметре step=0.0 поиск осуществляется в непрерывном пространстве (ограничено лишь языковыми ограничениями, в MQL до 15-го значащего знака включительно). Для использования алгоритма ГА с большей точностью, понадобится писать дополнительную библиотеку для работы с длинными числами.

Работу функции при RoundMode=1 можно проиллюстрировать следующим рисунком:

Рисунок 11. Работа функции SelectInDiscreteSpace при RoundMode=1

3.19. FitnessFunction. Функция приспособленности

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

3.20. ServiceFunction. Сервисная функция

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

4. Примеры работы UGA

Все задачи оптимизации, решаемые с помощью ЭА, делятся на два типа:

  1. Генотип соответствует фенотипу. Значения генов хромосом напрямую назначаются аргументам оптимизируемой функции. Пример 1.
  2. Генотип не соответствует фенотипу. Требуется интерпретация значений генов хромосом для вычисления оптимизируемой функции. Пример 2.

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

Задача: Найти минимум и максимум функции «Skin»:

Ответ: fmin(3.07021,3.315935)= -4.3182, fmax(-3.315699;-3.072485)= 14.0606.

Рисунок 12. График функции «Skin» на участке [-5;5]

Для решения задачи напишем такой скрипт:

Вот и весь код скрипта для решения задачи. Запустив его, получим информацию, выданную функцией Comment() :

Рисунок 13. Результат решения задачи

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

Широко распространено мнение, что индикатор ZZ показывает идеальные входы переворотной торговой системы. Индикатор очень популярен среди “волновиков” и тех, кто пользуется им для определения размера “фигур”.

Задача: Выяснить, существуют ли иные точки входов для переворотной торговой системы на исторических данных, отличные от вершин ZZ, дающие в сумме больше пунктов теоретической прибыли?

Для экспериментов выберем пару GBPJPY на M1 100 баров. Примем спред равным 80 пунктам (пятизначные котировки). Для начала, нужно определить наилучшие параметры ZZ. Для этого простым перебором найдем лучшее значение параметра ExtDepth с помощью нехитрого скрипта:

Запустив скрипт, получили 4077 пунктов при ExtDepth=3. На 100 барах “уместилось” 19 вершин индикатора. С увеличением ExtDepth количество вершин ZZ уменьшается, уменьшается и прибыльность.

Теперь найдем вершины альтернативного ZZ с помощью UGA. У вершин ZZ может быть три положения на каждом баре: 1) High, 2) Low, 3) Отсутствие вершины. Признак наличия и положения вершины и будет нести каждый ген для каждого бара. Таким образом, размер хромосомы – 100 генов.

По моим расчетам (а при необходимости математики меня поправят) на 100 барах можно построить 3^100, или 5.15378e47 вариантов альтернативных “зигзагов”. Именно столько вариантов нужно рассмотреть, используя прямой перебор. При вычислениях со скоростью 100000000 вариантов в секунду, понадобится 1.6e32 года! Это больше, чем возраст Вселенной. Тут у меня возникли сомнения в возможности решения этой задачки.

Но все же, приступим, пожалуй.

Так как UGA использует представление хромосомы вещественными числами, нам нужно как-то закодировать положения вершин. Это как раз тот случай, когда генотип хромосомы не соответствует фенотипу. Зададим интервал поиска для генов[0;5]. Условимся считать интервал [0;1] соответствием вершине ZZ на High, интервал [4;5] соответствием вершине на Low, и интервал (1;4) соответствием отсутствия вершины.

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

Как говорят некоторые бывшие трейдеры: “Лучшая стратегия торговли – не торговать”. Такая особь будет вершиной искусственной эволюции. Что бы заставить эту “настольную” эволюцию рождать торгующих особей, т.е. заставить расставлять вершины альтернативного ZZ, назначим приспособленность особи с отсутствием вершин значение “-10000000.0”, заведомо поставить её на самую низшую ступеньку эволюции по сравнению с любыми другими особями.

Вот код скрипта, использующего UGA для нахождения вершин альтернативного ZZ:

Запустив скрипт, получаем вершины, с суммарным профитом в 4939 пунктов. Причем, понадобилось всего лишь 17929 раз посчитать пункты против 3^100 прямого перебора, на моем компьютере 21,7 секунды против 1.6e32 года!

Рисунок 14. Результат решения задачи. Отрезки черного цвета – альтернативный ZZ, небесного цвета – индикатор ZZ

Итак, ответ на вопрос задачи будет звучать следующим образом: “Существуют”.

5. Рекомендации по работе с UGA

  1. Старайтесь корректно задавать оценочные условия в FF, чтобы ожидать адекватный результат работы алгоритма. Вспомните про Пример2. Это, пожалуй, главный совет.
  2. Не используйте слишком малое значение параметра Precision. Хотя алгоритм и способен работать с шагом 0, всё же, следует требовать разумную точность решения задачи. Именно для снижения размерности задач и задуман этот параметр.
  3. Варьируйте размер популяции и пороговое значение количества эпох. Хорошим решением будет назначать параметр Epoch в два раза большим, чем показал MaxOfCurrentEpoch. Не стоит выбирать слишком большие значения, это не ускорит решение задачи.
  4. Экспериментируйте с параметрами генетических операторов. Универсальных параметров нет, и нужно задавать их исходя из условий поставленной задачи.

Выводы

Наряду с очень мощным штатным тестером стратегий терминала, язык MQL5 позволяет создавать не менее мощные инструменты для работы трейдера, позволяющие решать поистине грандиозные поставленные задачи. Получен очень гибкий и масштабируемый алгоритм оптимизации. И я, без стеснения, горжусь своим “велосипедом”, открытым заново.

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

Желаю читателю успехов в поиске оптимальных решений. Надеюсь я, хоть немного, помог ему в этом. Удачи!

В статье использовался индикатор ZigZag. Все исходные коды UGA прилагаются.

Лицензии: Исходные коды, прилагаемые к статье (код UGA), распространяются на условиях BSD.

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

Генети́ческий алгори́тм (англ. genetic algorithm ) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Содержание

История

Первые работы по симуляции эволюции были проведены в 1954 году Нильсом Баричелли на компьютере, установленном в Институте перспективных исследований Принстонского университета. [1] [2] Его работа, опубликованная в том же году, привлекла широкое внимание общественности. С 1957 года, [3] австралийский генетик Алекс Фразер опубликовал серию работ по симуляции искусственного отбора среди организмов с множественным контролем измеримых характеристик. Положенное начало позволило компьютерной симуляции эволюционных процессов и методам, описанным в книгах Фразера и Барнелла(1970) [4] и Кросби (1973) [5] , с 1960-х годов стать более распространенным видом деятельности среди биологов. Симуляции Фразера включали все важнейшие элементы современных генетических алгоритмов. Вдобавок к этому, Ганс-Иоахим Бремерманн в 1960-х опубликовал серию работ, которые также принимали подход использования популяции решений, подвергаемой рекомбинации, мутации и отбору, в проблемах оптимизации. Исследования Бремерманна также включали элементы современных генетических алгоритмов. [6] Среди прочих пионеров следует отметить Ричарда Фридберга, Джорджа Фридмана и Майкла Конрада. Множество ранних работ были переизданы Давидом Б. Фогелем (1998). [7]

Хотя Баричелли в своей работе 1963 года симулировал способности машины играть в простую игру, [8] искусственная эволюция стала общепризнанным методом оптимизации после работы Инго Рехенберга и Ханса-Пауля Швефеля в 1960-х и начале 1970-х годов двадцатого века — группа Рехенсберга смогла решить сложные инженерные проблемы согласно стратегиям эволюции. [9] [10] [11] [12] Другим подходом была техника эволюционного программирования Лоренса Дж. Фогеля, которая была предложена для создания искусственного интеллекта. Эволюционное программирование первоначально использовавшее конечные автоматы для предсказывания обстоятельств, и использовавшее разнообразие и отбор для оптимизации логики предсказания. Генетические алгоритмы стали особенно популярны благодаря работе Джона Холланда в начале 70-х годов и его книге «Адаптация в естественных и искусственных системах» (1975) [13] . Его исследование основывалось на экспериментах с клеточными автоматами, проводившимися Холландом и на его трудах написанных в университете Мичигана. Холланд ввел формализованный подход для предсказывания качества следующего поколения, известный как Теорема схем. Исследования в области генетических алгоритмов оставались в основном теоретическими до середины 80-х годов, когда была, наконец, проведена Первая международная конференция по генетическим алгоритмам в Питтсбурге, Пенсильвания (США).

С ростом исследовательского интереса существенно выросла и вычислительная мощь настольных компьютеров, это позволило использовать новую вычислительную технику на практике. В конце 80-х, компания General Electric начала продажу первого в мире продукта, работавшего с использованием генетического алгоритма. Им стал набор промышленных вычислительных средств. В 1989, другая компания Axcelis, Inc. выпустила Evolver — первый в мире коммерческий продукт на генетическом алгоритме для настольных компьютеров. Журналист The New York Times в технологической сфере Джон Маркофф писал [14] об Evolver в 1990 году.

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

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

Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип, им описываемый, решает поставленную задачу.

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

Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.

Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:

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

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

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

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

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

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

Отбор (селекция)

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

Выбор родителей

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

Можно выделить несколько операторов выбора родителей:

  1. Панмиксия — оба родителя выбираются случайно, каждая особь популяции имеет равные шансы быть выбранной
  2. Инбридинг — первый родитель выбирается случайно, а вторым выбирается такой, который наиболее похож на первого родителя
  3. Аутбридинг — первый родитель выбирается случайно, а вторым выбирается такой, который наиболее не похож на первого родителя

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

Размножение (Скрещивание)

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

Почему особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H’ (хотя последний вариант тоже имеет право на существование)? Дело в том, что главный недостаток многих генетических алгоритмов — отсутствие разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них — выбор для размножения не самых приспособленных, но вообще всех особей. Однако такой подход вынуждает хранить всех существовавших ранее особей, что увеличивает вычислительную сложность задачи. Поэтому часто применяют методы отбора особей для скрещивания таким образом, чтобы «размножались» не только самые приспособленные, но и другие особи, обладающие плохой приспособленностью. При таком подходе для разнообразия генотипа возрастает роль мутаций.

Мутации

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

Критика

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

  • Повторная оценка функции приспособленности (фитнесс-функции) для сложных проблем, часто является фактором, ограничивающим использование алгоритмов искусственной эволюции. Поиск оптимального решения для сложной задачи высокой размерности зачастую требует очень затратной оценки функции приспособленности. В реальных задачах, таких как задачи структурной оптимизации, единственный запуск функциональной оценки требует от нескольких часов до нескольких дней для произведения необходимых вычислений. Стандартные методы оптимизации не могут справиться с проблемами такого рода. В таком случае, может быть необходимо пренебречь точной оценкой и использовать аппроксимацию пригодности, которая способна быть вычислена эффективно. Очевидно, что применение аппроксимации пригодности может стать одним из наиболее многообещающих подходов, позволяющих обоснованно решать сложные задачи реальной жизни с помощью генетических алгоритмов.
  • Генетические алгоритмы плохо масштабируемы под сложность решаемой проблемы. Это значит, что число элементов, подверженных мутации очень велико, если велик размер области поиска решений. Это делает использование данной вычислительной техники чрезвычайно сложным при решении таких проблем, как, например, проектирование двигателя, дома или самолёта. Для того чтобы сделать так, чтобы такие проблемы поддавались эволюционным алгоритмам, они должны быть разделены на простейшие представления данных проблем. Таким образом, эволюционные вычисления используются, например, при разработке формы лопастей, вместо всего двигателя, формы здания, вместо подробного строительного проекта и формы фюзеляжа, вместо разработки вида всего самолёта. Вторая проблема, связанная со сложностью, кроется в том, как защитить части, которые эволюционировали с высокопригодными решениями от дальнейшей разрушительной мутации, в частности тогда, когда от них требуется хорошая совместимость с другими частями в процессе оценки пригодности. Некоторыми разработчиками было предложено, что подход, предполагающий развитие пригодности эволюционирующих решений, смог бы преодолеть ряд проблем с защитой, но данный вопрос всё ещё остаётся открытым для исследования.
  • Решение является более пригодным лишь по сравнению с другими решениями. В результате условие остановки алгоритма неясно для каждой проблемы.
  • Во многих задачах генетические алгоритмы имеют тенденцию сходиться к локальному оптимуму или даже к произвольной точке, а не к глобальному оптимуму для данной задачи. Это значит, что они «не знают», каким образом пожертвовать кратковременной высокой пригодностью для достижения долгосрочной пригодности. Вероятность этого зависит от формы ландшафта пригодности: отдельные проблемы могут иметь выраженное направление к глобальному минимуму, в то время как остальные могут указывать направление для фитнесс-функции на локальный оптимум. Эту проблему можно решить использованием иной фитнесс-функции, увеличением вероятности мутаций, или использованием методов отбора, которые поддерживают разнообразие решений в популяции, хотя Теорема об отсутствии бесплатного обеда при поиске и оптимизации[16] доказывает, что не существует общего решения данной проблемы. Общепринятым методом поддержания популяционного разнообразия является установка уровневого ограничения на численность элементов с высоким сродством, которое снизит число представителей сходных решений в последующих поколениях, позволяя другим, менее сходным элементам оставаться в популяции. Данный приём, тем не менее, может не увенчаться успехом в зависимости от ландшафта конкретной проблемы. Другим возможным методом может служить простое замещение части популяции случайно сгенерированными элементами, в момент, когда элементы популяции становятся слишком сходны между собой. Разнообразие важно для генетических алгоритмов (и генетического программирования) потому, что перекрёст генов в гомогенной популяции не несёт новых решений. В эволюционных стратегиях и эволюционном программировании, разнообразие не является необходимостью, так как большая роль в них отведена мутации.

Имеется много скептиков относительно целесообразности применения генетических алгоритмов. Например, Стивен С. Скиена, профессор кафедры вычислительной техники университета Стоуни—Брук, известный исследователь алгоритмов, лауреат премии института IEEE, пишет [17] :

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

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

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

Пример простой реализации на C++

Поиск в одномерном пространстве, без скрещивания.

Что такое генетические алгоритмы

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

Естественный отбор

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

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

5 шагов генетического алгоритма

Процесс обучения генетического алгоритма делится на 5 этапов:

  1. Начальная популяция
  2. Функция силы особи
  3. Отбор наиболее сильных решений
  4. Обмен характеристиками между двумя особями
  5. Мутация
  6. Новая итерация с созданием начальной популяции

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

В генетическом алгоритме набор генов особи представлен в виде бинарной строки. Закодированная комбинация генов называется хромосомой.

Популяция, хромосомы и гены

Функция силы

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

Отбор

Идея отбора заключается в том, чтобы отобрать наиболее сильных особей и передать их гены следующему поколению особей. N пар особей (родители) отбирается на основании их силы.

Скрещивание

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

Точка скрещивания

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

После обмена генами между родителями потомство добавляется в новую популяцию.

Мутация

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

Пример мутации особи

Завершение алгоритма

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

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

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

В глубоком обучении с помощью генетических алгоритмов оптимизируются параметры нейросети. В качестве особей популяции выступают сами параметры. Введение в state-of-the-art использование генетических алгоритмов для задач глубокого обучения находится по ссылке .

Генетический алгоритм (стр. 1 из 2)

Министерство транспорта и связи Украины

Одесская национальная академия связи им.О.С. Попова

Кафедра информатизации и управления

Ст. группы ПС-3.12

зав.кафедры Адреев А.И.

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

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

4Пример тривиальной реализации на C++

Генети́ческий алгори́тм (англ.genetic algorithm ) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическуюэволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

«Отцом-основателем» генетических алгоритмов считается Джон Холланд (en:John Henry Holland), книга которого «Адаптация в естественных и искусственных системах» (1975) [1] является основополагающим трудом в этой области исследований. Ему же принадлежит Генетические алгоритмы.

Идея генетических алгоритмов заимствована у живой природы и состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. Разработчик генетических алгоритмов выступает в данном случае как «создатель», который должен правильно установить законы эволюции, чтобы достичь желаемой цели как можно быстрее. Впервые эти нестандартные идеи были применены к решению оптимизационных задач в середине 70-х годов . Примерно через десять лет появились первые теоретические обоснования этого подхода . На сегодняшний день генетические алгоритмы доказали свою конкурентноспособность при решении многих NP-трудных задач и особенно в практических приложениях, где математические модели имеют сложную структуру и применение стандартных методов типа ветвей и границ, динамического или линейного программирования крайне затруднено.

Ежегодно в мире проводится несколько конференций по этой тематике, информацию о которых можно найти в Интернет по адресам:

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

Примерами служат задачи размещения, стандартизации, выполнимости и другие. Стандартный генетический алгоритм начинает свою работу с формирования начальной популяции I = <i 1 , i 2 , …, is > — конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью вероятностных жадных алгоритмов . Как мы увидим ниже, выбор начальной популяции не имеет значения для сходимости процесса в асимптотике, однако формирование «хорошей» начальной популяции (например из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума.

На каждом шаге эволюции с помощью вероятностного оператора селекции выбираются два решения, родители i 1 , i 2 . Оператор скрещивания по решениям i 1 , i 2 строит новое решение i’ , которое затем подвергается небольшим случайным модификациям, которые принято называть мутациями . Затем решение добавляется в популяцию, а решение с наименьшим значением целевой функции удаляется из популяции.

Доказательство теоремы схем.

1. Выбрать начальную популяцию I иположить

2. Пока не выполнен критерий остановки делать следующее.

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

Первые работы по симуляции эволюции были проведены в 1954 году Нильсом Баричелли на компьютере установленном в Институте Продвинутых Исследований Принстонского университета. [1] [2] Его работа, опубликованная в том же году, привлекла широкое внимание общественности. С 1957 года, [3] австралийский генетик Алекс Фразер опубликовал серию работ по симуляции искусственного отбора среди организмов с множественным контролем измеримых характеристик. Положенное начало позволило компьютерной симуляции эволюционных процессов и методам, описанным в книгах Фразера и Барнелла(1970) [4] и Кросби (1973). [5] , с 1960-х годов стать более распространенным видом деятельности среди биологов. Симуляции Фразера включали все важнейшие элементы современных генетических алгоритмов. Вдобавок к этому, Ганс-Иоахим Бремерманн в 1960-х опубликовал серию работ, которые также принимали подход использования популяции решений, подвергаемой рекомбинации, мутации и отбору, в проблемах оптимизации. Исследования Бремерманна также включали элементы современных генетических алгоритмов. [6] Среди прочих пионеров следует отметить Ричарда Фридберга, Джорджа Фридмана и Майкла Конрада. Множество ранних работ были переизданы Давидом Б. Фогелем (1998). [7]

Хотя Баричелли в своей работе 1963 года симулировал способности машины играть в простую игру, [8] искусственная эволюция стала общепризнанным методом оптимизации после работы Инго Рехенберга и Ханса-Пауля Швефеля в 1960-х и начале 1970-х годов двадцатого века – группа Рехенсберга смогла решить сложные инженерные проблемы согласно стратегиям эволюции. [9] [10] [11] [12] Другим подходом была техника эволюционного программирования Лоренса Дж. Фогеля, которая была предложена для создания искусственного интеллекта. Эволюционное программирование первоначально использовавшее конечные автоматы для предсказывания обстоятельств, и использовавшее разнообразие и отбор для оптимизации логики предсказания. Генетические алгоритмы стали особенно популярны благодаря работе Джона Холланда в начале 70-х годов и его книге «Адаптация в естественных и искусственных системах» (1975) [13] . Его исследование основывалось на экспериментах с клеточными автоматами, проводившимися Холландом и на его трудах написанных в университете Мичигана. Холланд ввел формализованный подход для предсказывания качества следующего поколения, известный как Теорема схем. Исследования в области генетических алгоритмов оставались в основном теоретическими до середины 80-х годов, когда была наконец проведена Первая международная конференция по генетическим алгоритмам в Питтсбурге, Пенсильвания (США).

С ростом исследовательского интереса существенно выросла и вычислительная мощь настольных компьютеров, это позволило использовать новую вычислительную технику на практике. В конце 80-х, компания General Electric начала продажу первого в мире продукта, работавшего с использованием генетического алгоритма. Им стал набор промышленных вычислительных средств. В 1989, другая компания Axcelis, Inc. выпустила Evolver – первый в мире коммерческий продукт на генетическом алгоритме для настольных компьютеров. Журналист The New York Times в технологической сфере Джон Маркофф писал [14] об Evolver в 1990 году.

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

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

Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип, им описываемый, решает поставленную задачу.

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

Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.

Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:

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

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

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

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

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

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

Размножение (Скрещивание)

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

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

Почему особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H (хотя последний вариант тоже имеет право на существование)? Дело в том, что главный бич многих генетических алгоритмов — недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них — выбор для размножения не самых приспособленных, но вообще всех особей.

Мутации

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

Отбор

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

Критика

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

  • Повторная оценка функции приспособленности (фитнесс-функции) для сложных проблем, часто является фактором, ограничивающим использование алгоритмов искусственной эволюции. Поиск оптимального решения для сложной задачи высокой размерности зачастую требует очень затратной оценки функции приспособленности. В реальных задачах, таких как задачи структурной оптимизации, единственный запуск функциональной оценки требует от нескольких часов до нескольких дней для произведения необходимых вычислений. Стандартные методы оптимизации не могут справиться с проблемами такого рода. В таком случае, может быть необходимо пренебречь точной оценкой и использовать аппроксимацию пригодности, которая способна быть вычислена эффективно. Очевидно, что применение аппроксимации пригодности может стать одним из наиболее многообещающих подходов, позволяющих обоснованно решать сложные задачи реальной жизни с помощью генетических алгоритмов.
  • Генетические алгоритмы плохо масштабируемы под сложность решаемой проблемы. Это значит, что число элементов, подверженных мутации очень велико, если велик размер области поиска решений. Это делает использование данной вычислительной техники чрезвычайно сложным при решении таких проблем, как, например, проектирование двигателя, дома или самолёта. Для того чтобы сделать так, чтобы такие проблемы поддавались эволюционным алгоритмам, они должны быть разделены на простейшие представления данных проблем. Таким образом, эволюционные вычисления используются, например, при разработке формы лопастей, вместо всего двигателя, формы здания, вместо подробного строительного проекта и формы фюзеляжа, вместо разработки вида всего самолёта. Вторая проблема, связанная со сложностью, кроется в том, как защитить части, которые эволюционировали с высокопригодными решениями от дальнейшей разрушительной мутации, в частности тогда, когда от них требуется хорошая совместимость с другими частями в процессе оценки пригодности. Некоторыми разработчиками было предложено, что подход предполагающий развитие пригодности эволюционирующих решений смог бы преодолеть ряд проблем с защитой, но данный вопрос всё ещё остаётся открытым для исследования.
  • Решение является более пригодным лишь по сравнению с другими решениями. В результате условие остановки алгоритма неясно для каждой проблемы.
  • Во многих задачах генетические алгоритмы имеют тенденцию сходиться к локальному оптимуму или даже к спорным точкам, вместо глобального оптимума для данной задачи. Это значит, что они «не знают», каким образом пожертвовать кратковременной высокой пригодностью для достижения долгосрочной пригодности. Вероятность этого зависит от формы ландшафта пригодности: отдельные проблемы могут иметь выраженное направление к глобальному минимуму, в то время как остальные могут указывать направление для фитнесс-функции на локальный оптимум. Эту проблему можно решить использованием иной фитнесс-функции, увеличением вероятности мутаций, или использованием методов отбора, которые поддерживают разнообразие решений в популяции, хотя Теорема об отсутствии бесплатного обеда при поиске и оптимизации [15] доказывает, что не существует общего решения данной проблемы. Общепринятым методом поддержания популяционного разнообразия является установка уровневого ограничения на численность элементов с высоким сродством, которое снизит число представителей сходных решений в последующих поколениях, позволяя другим, менее сходным элементам оставаться в популяции. Данный приём, тем не менее, может не увенчаться успехом в зависимости от ландшафта конкретной проблемы. Другим возможным методом может служить простое замещение части популяции случайно сгенерированными элементами, в момент, когда элементы популяции становятся слишком сходны между собой. Разнообразие важно для генетических алгоритмов (и генетического программирования) потому, что перекрёст генов в гомогенной популяции не несёт новых решений. В эволюционных стратегиях и эволюционном программировании, разнообразие не является необходимостью, так как большая роль в них отведена мутации.

Имеется много скептиков относительно целесообразности применения генетических алгоритмов. Например, Стивен С. Скиена, профессор кафедры вычислительной техники университета Стоуни—Брук, известный исследователь алгоритмов, лауреат премии института IEEE пишет [16] :

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

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

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

Пример тривиальной реализации на C++

Поиск в одномерном пространстве, без скрещивания.

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

Дискретные задачи размещения Оптимизационные алгоритмы

Идея генетических алгоритмов заимствована у живой природы и состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. Разработчик генетических алгоритмов выступает в данном случае как «создатель», который должен правильно установить законы эволюции, чтобы достичь желаемой цели как можно быстрее. Впервые эти нестандартные идеи были применены к решению оптимизационных задач в середине 70-х годов [7, 12]. Примерно через десять лет появились первые теоретические обоснования этого подхода [16, 21, 22]. На сегодняшний день генетические алгоритмы доказали свою конкурентноспособность при решении многих NP-трудных задач [6, 15] и особенно в практических приложениях, где математические модели имеют сложную структуру и применение стандартных методов типа ветвей и границ, динамического или линейного программирования крайне затруднено.

Ежегодно в мире проводится несколько конференций по этой тематике, информацию о которых можно найти в Интернет по адресам:
http://www.natural-selection.com/eps/
http://mat.gsia.cmu.edu/Conferences/ .

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

Примерами служат задачи размещения, стандартизации, выполнимости и другие [2, 5, 19]. Стандартный генетический алгоритм начинает свою работу с формирования начальной популяции I = <i1, i2, …, is> — конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью вероятностных жадных алгоритмов [1, 3, 4]. Как мы увидим ниже, выбор начальной популяции не имеет значения для сходимости процесса в асимптотике, однако формирование «хорошей» начальной популяции (например из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума.

На каждом шаге эволюции с помощью вероятностного оператора селекции выбираются два решения, родители i1, i2. Оператор скрещивания по решениям i1, i2 строит новое решение i’ , которое затем подвергается небольшим случайным модификациям, которые принято называть мутациями. Затем решение добавляется в популяцию, а решение с наименьшим значением целевой функции удаляется из популяции. Общая схема такого алгоритма может быть записана следующим образом.

2. Пока не выполнен критерий остановки делать следующее.

в предположении, что f (i) > 0 для всех i Î I. При турнирной селекции формируется случайное подмножество из элементов популяции и среди них выбирается один элемент с наибольшим значением целевой функции. Турнирная селекция имеет определенные преимущества перед пропорциональной, так как не теряет своей избирательности, когда в ходе эволюции все элементы популяции становятся примерно равными по значению целевой функции. Операторы селекции строятся таким образом, чтобы с ненулевой вероятностью любой элемент популяции мог бы быть выбран в качестве одного из родителей. Более того, допускается ситуация, когда оба родителя представлены одним и тем же элементом популяции.

Как только два решения выбраны, к ним применяется вероятностный оператор скрещивания (crossover). Существует много различных версий этого оператора [15], среди которых простейшим, по видимому, является однородный оператор. По решениям i1, i2 он строит решение i’ присваивая каждой координате этого вектора с вероятностью 0,5 соответствующее значение одного из родителей. Если вектора i1, i2 совпадали скажем по первой координате, то вектор i’ «унаследует» это значение. Геометрически, оператор скрещивания случайным образом выбирает в гиперкубе вершину i’ , которая принадлежит минимальной грани, содержащей вершины i1, i2. Можно сказать, что оператор скрещивания старается выбрать новое решение i’ где-то между i1, i2 полагаясь на удачу. Более аккуратная процедура могла бы выглядеть таким образом. Новым решением i’ является оптимальное решение исходной задачи на соответствующей грани гиперкуба. Конечно, если расстояние Хемминга между i1, i2 равно n, то задача оптимального скрещивания совпадает с исходной. Тем не менее даже приближенное решение этой задачи вместо случайного выбора заметно улучшает работу генетического алгоритма [8, 9, 10, 14]. По аналогии с однородным оператором скрещивания легко предложить и другие операторы, использующие не только два, но и произвольное число решений из популяции. Например, в [20] использовалось восемь родителей. Другие примеры можно найти в [13]. С адаптацией этой идеи к задаче коммивояжера можно познакомиться в [17].

Оператор мутации, применяемый к решению i’ в п. 2.3. генетического алгоритма, с заданной вероятностью pm Î (0, 1) меняет значение каждой координаты на противоположное. Например, вероятность того, что i’ = (0, 0, 0, 0, 0) в ходе мутации перейдет в j’ = (1, 1, 1, 0, 0) , равна pm ´ pm ´ pm ´ (1 – pm) ´ (1 – pm) > 0. Таким образом, с ненулевой вероятностью решение i’ может перейти в любое другое решение. Отметим, что модификация решения i’ может состоять не только в случайной мутации, но и в частичной перестройке решения алгоритмами локального поиска. Применение локального спуска позволяет генетическому алгоритму сосредоточиться только на локальных оптимумах. Множество локальных оптимумов может оказаться экспоненциально большим и на первый взгляд кажется, что такой вариант алгоритма не будет иметь больших преимуществ. Однако экспериментальные исследования распределения локальных оптимумов свидетельствуют о высокой концентрации их в непосредственной близости от глобального оптимума [11, 18]. Это наблюдение известно как гипотеза о существовании «большой долины» для задач на минимум или «центрального горного массива» для задач на максимум.

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

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

Александров Д. А. Алгоритм муравьиной колонии для задачи о минимальном покрытии. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т3 (1998), Иркутск, с. 17–20.

Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.

Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер. 2. т6 (1999), № 1, с. 12–32.

Горбачевская Л. Е., Кочетов Ю. А. Вероятностная эвристика для двухуровневой задачи размещения. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т1 (1998), Иркутск, с. 249–252.

Гэри В., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд.физ.-мат.наук. Омск, 2000.

Растригин Л. А. Случайный поиск — специфика, этапы истории и предрассудки. Вопросы кибернетики. Вып. 33 (1978), с. 3–16.

Aggarwal C. C., Orlin J. B., Tai R. P. Optimized crossover for maximum independent set. Oper. Res. v45 (1997), pp 225–234.

Balas E., Niehaus W. Finding large cliques in arbitrary graphs by bipartite matching. Cliques, coloring, and satisfiability. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. v26 (1996), pp 29–49.

Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems. J. Heuristics. v4 (1998), N4, pp 107–122.

Boese K. D., Kahng A. B., Muddu S. A new adaptive multi–start technique for combinatorial global optimizations. Oper. Res. Lett. v16 (1994), N2, pp 101-114.

Bremermann H. J., Roghson J., Salaff S. Global properties of evolution processes. Natural automata and useful simulations. London: Macmillan. 1966. pp 3-42.

Eiben A. E., Raue P. E., Ruttkay Zs. Genetic Algorithms with multiparent recombination. Parallel Problem Solving from Nature III. Berlin: Springer Verlag, (LNCS), v866 (1994), pp 78-87.

Eremeev A. V. A genetic algorithm with a non-binary representation for the set covering problem. Operations Research Proceedings 1998. Berlin: Springer Verlag. 1999. pp 175-181.

Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. 1989.

Holland J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press. 1975.

Johnson D. S., McGeoch L. A. The traveling salesman problem: a case study. Local search in combinatorial optimization. Chichester: Wiley, pp 215-310.

Kirkpatrick S., Toulouse G. Configuration space analysis of traveling salesman problems. J. de Phys. v46 (1985) , pp 1277-1292.

Mirchandani P. B., Francis R. L. Discrete Location Theory. New York: John Wiley and Sons, 1990.

Muhlenbein H. Parallel genetic algorithm, population dynamics and combinatorial optimization. Proc. Third Inter. Conf. Genetic Alg. San Mateo: Morgan Kaufman, 1989. pp 416-421.

Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der Biologischen Information, Freiburg: Fromman, 1973.

Schwefel H. P. Numerical optimization of computer models. Chichester: Wiley, 1981.

Илон Маск рекомендует:  Что такое код readline_completion_function
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL