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

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

3 Зачем нужны ГА? Генетические алгоритмы применяются для решения следующих задач: Оптимизация функций Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний) Настройка и обучение искусственной нейронной сети Составление расписаний Игровые стратегии Аппроксимация функций Искусственная жизнь Биоинформатика

4 Ключевые работы Родителем современной теории генетических алгоритмов считается Д.Х. Холланд (J. Holland). Однако сначала его интересовала, прежде всего, способность природных систем к адаптации, а его мечтой было создание такой системы, которая могла бы приспосабливаться к любым условиям окружающей среды. В 1975 году Холланд публикует свою самую знаменитую работу «Adaptation in Natural and Artificial Systems».В ней он впервые ввёл термин «генетический алгоритм» и предложил схему классического генетического алгоритма (canonical GA). В дальнейшем понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА. Ученики Холланда - Кеннет Де Йонг (Kenneth De Jong) и Дэвид Голдберг (David E. Goldberg) - внесли огромный вклад в развитие ГА. Наиболее известная работа Голдберга - «Genetic algorithms in search optimization and machine learning» (1989).

5 Принцип работы ГА Популяция – совокупностью всех «особей», представляющих собой строки, кодирующие одно из решений задачи. С помощью функции приспособленности: наиболее приспособленные (более подходящие решения) получают возможность скрещиваться и давать потомство наихудшие (плохие решения) удаляются из популяции и не дают потомства Таким образом, приспособленность нового поколения в среднем выше предыдущего. В классическом ГА: начальная популяция формируется случайным образом размер популяции (количество особей N) фиксируется и не изменяется в течение работы всего алгоритма каждая особь генерируется как случайная L- битная строка, где L длина кодировки особи длина кодировки для всех особей одинакова

6 Схема работы любого ГА Шаг алгоритма состоит из трех стадий: 1. генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения 2. скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения 3. мутация нового поколения

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

Скрещивание Особи промежуточной популяции случайным образом разбиваются на пары, потом с некоторой вероятностью скрещиваются, в результате чего получаются два потомка, которые записываются в новое поколение, или не скрещиваются, тогда в новое поколение записывается сама пара. В классическом ГА применяется одноточечный оператор кроссовера (1-point crossover): для родительских строк случайным образом выбирается точка раздела, потомки получаются путём обмена отсечёнными частями >

Мутация К полученному в результате отбора и скрещивания новому поколению применяется оператор мутации, необходимый для "выбивания" популяции из локального экстремума и способствующий защите от преждевременной сходимости. Каждый бит каждой особи популяции с некоторой вероятностью инвертируется. Эта вероятность обычно очень мала, менее 1% > Можно выбирать некоторое количество точек в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать сразу некоторую группу подряд идущих точек. Среди рекомендаций по выбору вероятности мутации нередко можно встретить варианты 1/L или 1/N.

Настройка ГА Генетический алгоритм производит поиск решений с помощью: - отбора гиперплоскостей (hyperplane sampling), осуществляемого кроссовером, поскольку последний комбинирует и совмещает шаблоны родителей в их детях. - метода hill-climbing, обеспечивающегося мутацией: особь случайным образом изменяется – неудачные варианты вымирают, полезные изменения сохраняются популяцией. Исследования показали, что на простых задачах с малым размером популяции ГА с мутацией (и без кроссовера) находят решение быстрее. На сложных многоэкстремальных функциях лучше использовать ГА с кроссовером, поскольку этот метод более надежен, хотя и требует большего размера популяции. Для эффективной работы генетического алгоритма необходимо поддерживать тонкое равновесие между исследованием и использованием. Необходимость сбалансированной сходимости ГА: быстрая сходимость может привести к схождению к неоптимальному решению медленная сходимость часто приводит к потере найденной наилучшей особи.

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

Оператор кроссинговера Оператор кроссинговера (crossover operator), также называемый кроссовером, является основным генетическим оператором, за счет которого производится обмен генетическим материалом между особями. Моделирует процесс скрещивания особей. Пусть имеются две родительские особи с хромосомами Х={xi, i=1,L} и Y={yi, i=1,L}. Случайным образом определяется точка внутри хромосомы, в которой обе хромосомы делятся на две части и обмениваются ими. Назовем эту точку точкой разрыва. Вообще говоря, в англоязычной литературе она называется точкой кроссинговера (crossover point), просто точка разрыва более образное название и к тому же позволяет в некоторых случаях избежать тавтологии.

Данный тип кроссинговера называется одноточечным, т.к. при нем родительские хромосомы разрезаются только в одной случайной точке. Также существует 2-х и n-точечный операторы кроссинговера. В 2-х точечном кроссинговере точек разрыва 2, а n-точечный кроссинговер является своеобразным обобщением 1- и 2- точечного кроссинговеров для n > 2. Вероятность кроссинговера самая высокая среди генетических операторов и равна обычно 60% и больше.

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

Так же как и кроссинговер, мутация проводится не только по одной случайной точке. Можно выбирать некоторое количество точек в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать сразу некоторую группу подряд идущих точек. Вероятность мутации значительно меньше вероятности кроссинговера и редко превышает 1%. Среди рекомендаций по выбору вероятности мутации нередко можно встретить варианты 1/L или 1/N, где L - длина хромосомы, N - размер популяции. Необходимо также отметить, что есть мнение, что оператор мутации является основным поисковым оператором и известны алгоритмы, не использующих других операторов (кроссинговер, инверсия и т.д.) кроме мутации

Факторы, создающие сложность для ГА Свойства функций приспособленности, создающие сложность для ГА. Многоэкстремальность: создается множество ложных аттракторов. Пример функция Растригина: На картинке изображен график функции Растригина с одним аргументом.

Обманчивость (deception): функция построена так, что шаблоны малого порядка уводят популяцию к локальному экстремуму. Пример: пусть строка состоит из 10-ти четырехбитных подстрок. Пусть равно количеству единиц в i-той подстроке. Зададим функцию g(u) следующей таблицей: и пусть функция приспособленности равна сумме g( ) по всем i = 1..10: u01234 g(u)32104

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

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