Генетические алгоритмы и их практическое применение (стр. 2 из 5)
Переформулируем задачу оптимизации как задачу нахождения максимума некоторой функции f(x1, x2, …, xn), называемой функцией приспособленности (fitness function). Она должна принимать неотрицательные значения на ограниченной области определения (для того, чтобы мы могли для каждой особи считать её приспособленность, которая не может быть отрицательной), при этом совершенно не требуются непрерывность и дифференцируемость.
Каждый параметр функции приспособленности кодируется строкой битов.
Особью будет называться строка, являющаяся конкатенацией строк упорядоченного набора параметров (рис1):
1010 10110 101 … 10101
| x1 | x2 | x3 | … | xn |
Рис 1. Ионкатенационная строка упорядоченного набора параметров
Универсальность ГА заключается в том, что от конкретной задачи зависят только такие параметры, как функция приспособленности и кодирование решений. Остальные шаги для всех задач производятся одинаково.[9]
Генетические алгоритмы оперируют совокупностью особей (популяцией), которые представляют собой строки, кодирующие одно из решений задачи. Этим ГА отличается от большинства других алгоритмов оптимизации, которые оперируют лишь с одним решением, улучшая его.[10]
С помощью функции приспособленности среди всех особей популяции выделяют:
· наиболее приспособленные (более подходящие решения), которые получают возможность скрещиваться и давать потомство
· наихудшие (плохие решения), которые удаляются из популяции и не дают потомства
Таким образом, приспособленность нового поколения в среднем выше предыдущего.[11]
В классическом ГА:
· начальная популяция формируется случайным образом
· размер популяции (количество особей N) фиксируется и не изменяется в течение работы всего алгоритма
· каждая особь генерируется как случайная L-битная строка, где L — длина кодировки особи
· длина кодировки для всех особей одинакова[12]
1.3 Алгоритм работы
На рисунке 2 изображена схема работы любого генетического алгоритма:
Рис 2. Схема работы любого генетического алгоритма.
Шаг алгоритма состоит из трех стадий:
1. генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения
2. скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения
3. мутация нового поколения [13]
Промежуточная популяция — это набор особей, получивших право размножаться. Наиболее приспособленные особи могут быть записаны туда несколько раз, наименее приспособленные с большой вероятностью туда вообще не попадут.[14]
В классическом ГА вероятность каждой особи попасть в промежуточную популяцию пропорциональна ее приспособленности, т.е. работает пропорциональный отбор (proportional selection).
Существует несколько способов реализации данного отбора:
- stochastic sampling. Пусть особи располагаются на колесе рулетки так, что размер сектора каждой особи пропорционален ее приспособленности. N раз запуская рулетку, выбираем требуемое количество особей для записи в промежуточную популяцию.
- remainderstochasticsampling. Для каждой особи вычисляется отношение ее приспособленности к средней приспособленности популяции. Целая часть этого отношения указывает, сколько раз нужно записать особь в промежуточную популяцию, а дробная показывает её вероятность попасть туда ещё раз. Реализовать такой способ отбора удобно следующим образом: расположим особи на рулетке так же, как было описано. Теперь пусть у рулетки не одна стрелка, а N, причем они отсекают одинаковые сектора. Тогда один запуск рулетки выберет сразу все N особей, которые нужно записать в промежуточную популяцию.[15] Такой способ иллюстрируется рисунком 3:
Рис 3. Способ remainderstochasticsampling в реализации отбора
Особи промежуточной популяции случайным образом разбиваются на пары, потом с некоторой вероятностью скрещиваются, в результате чего получаются два потомка, которые записываются в новое поколение, или не скрещиваются, тогда в новое поколение записывается сама пара.
В классическом ГА применяется одноточечный оператор кроссовера (1-point crossover): для родительских строк случайным образом выбирается точка раздела, потомки получаются путём обмена отсечёнными частями [16] (рис.4).
Рис 4. Одноточечный оператор кроссовера 1.6 Мутация
К полученному в результате отбора и скрещивания новому поколению применяется оператор мутации, необходимый для "выбивания" популяции из локального экстремума и способствующий защите от преждевременной сходимости.
Каждый бит каждой особи популяции с некоторой вероятностью инвертируется. Эта вероятность обычно очень мала, менее 1% (рис 5).
1011001100101101 -> 1011001101101101Рис 5. МутацияМожно выбирать некоторое количество точек в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать сразу некоторую группу подряд идущих точек.[17]
Такой процесс эволюции, вообще говоря, может продолжаться до бесконечности, пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:
1. нахождение глобального, либо субоптимального решения;
2. исчерпание числа поколений, отпущенных на эволюцию;
3. исчерпание времени, отпущенного на эволюцию. Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска.[18]
2. Преимущества и недостатки ГА
2.1 Преимущества
Эксперименты, описанные в литературе, показывают, что генетические алгоритмы очень эффективны в поиске глобальных минимумов адаптивных рельефов, так как в них исследуются большие области допустимых значений параметров нейронных сетей. (Градиентные алгоритмы дают возможность находить только локальные минимумы.) Другая причина того, что генетические алгоритмы не застревают в локальных минимумах — случайные мутации, которые аналогичны температурным флуктуациям метода имитации отжига.
В литературе есть указания на достаточно высокую скорость обучения при использовании генетических алгоритмов. Хотя скорость сходимости градиентных алгоритмов в среднем выше, чем генетических алгоритмов.
Генетические алгоритмы дают возможность оперировать дискретными значениями параметров нейронных сетей. Это упрощает разработку цифровых аппаратных реализаций нейронных сетей. При обучении на компьютере нейронных сетей, не ориентированных на аппаратную реализацию, возможность использования дискретных значений параметров в некоторых случаях может приводить к сокращению общего времени обучения.[19]
2.2 Недостатки
Генетические алгоритмы обучения сложны для понимания и программной реализации. Есть такие случаи, где не только не желательно, но и проблематично использовать ГА: в случае когда необходимо найти точный глобальный оптимум; время исполнения функции оценки велико; необходимо найти все решения задачи, а не одно из них; конфигурация является не простой (кодирование решения); поверхность ответа имеет слабоизменяющийся рельеф.[20]
3. Некоторые модели генетических алгоритмов
3.1 CanonicalGA (J. Holland)
Данная модель алгоритма является классической. Она была предложена Джоном Холландом в его знаменитой работе "Адаптация в природных и исусственных средах" (1975). Часто можно встретить описание простого ГА (Simple GA, D. Goldberg), он отличается от канонического тем, что использует либо рулеточный, либо турнирный отбор. Модель канонического ГА имеет следующие характеристики:
- Фиксированный размер популяции.
- Фиксированная разрядность генов.
- Пропорциональный отбор.
- Особи для скрещивания выбираются случайным образом.
- Одноточечный кроссовер и одноточечная мутация.
- Следующее поколение формируется из потомков текущего поколения без "элитизма". Потомки занимают места своих родителей. [21]
3.2Genitor (D. Whitley)
В данной модели используется специфичная стратегия отбора. Вначале, как и полагается, популяция инициализируется, и её особи оцениваются. Затем выбираются случайным образом две особи, скрещиваются, причем получается только один потомок, который оценивается и занимает место наименее приспособленной особи. После этого снова случайным образом выбираются 2 особи, и их потомок занимает место особи с самой низкой приспособленностью. Таким образом, на каждом шаге в популяции обновляется только одна особь. Подводя итоги можно выделить следующие характерные особенности:
- Фиксированный размер популяции.
- Фиксированная разрядность генов.
- Особи для скрещивания выбираются случайным образом.
- Ограничений на тип кроссовера и мутации нет.
- В результате скрещивания особей получается один потомок, который занимает место наименее приспособленной особи.[22]