поведение не обеспечивает семейство генетических алгоритмов с двоичным
кодированием, т.к. эти алгоритмы оперируют битовой строкой целиком, и на
первых же эпохах младшие разряды чисел "застывают", принимая случайное
значение. В классических генетических алгоритмах разработаны специальные
приемы по выходу из этой ситуации. Например, последовательный запуск
ансамбля генетических алгоритмов с постепенным сужением пространства
поиска.
Есть и другая проблема: при увеличении длины битовой строки необходимо
увеличивать и численность популяции.
Математический аппарат непрерывных генетических алгоритмов
Как уже отмечалось, при работе с оптимизационными задачами в непрерывных
пространствах вполне естественно представлять гены напрямую вещественными
числами. В этом случае хромосома есть вектор вещественных чисел. Их
точность будет определяться исключительно разрядной сеткой той ЭВМ, на
которой реализуется real-coded алгоритм. Длина хромосомы будет совпадать с
длиной вектора-решения оптимизационной задачи, иначе говоря, каждый ген
будет отвечать за одну переменную. Генотип объекта становится идентичным
его фенотипу.
Вышесказанное определяет список основных преимуществ алгоритмов с
непрерывными генами:
1. Использование непрерывных генов делает возможным поиск в больших
пространствах (даже в неизвестных), что трудно делать в случае
двоичных генов, когда увеличение пространства поиска сокращает
точность решения при неизменной длине хромосомы.
2. Одной из важных черт непрерывных генетических алгоритмов является их
способность к локальной настройке решений.
3. Использование непрерывных генетических алгоритмов для представления
решений удобно, поскольку близко к постановке большинства прикладных
задач. Кроме того, отсутствие операций кодирования/декодирования,
которые необходимы в генетических алгоритмах с двоичным кодированием,
повышает скорость работы алгоритма.
Как известно, появление новых особей в популяции канонического
генетического алгоритма обеспечивают несколько биологических операторов:
отбор, скрещивание и мутация. В качестве операторов отбора особей в
родительскую пару здесь подходят любые известные из двоичных генетических
алгоритмов: рулетка, турнирный, случайный. Однако операторы скрещивания и
мутации не годятся: в классических реализациях они работают с битовыми
строками. Нужны собственные реализации, учитывающие специфику real-coded
алгоритмов.
Оператор скрещивания непрерывного генетического алгоритма, или кроссовер,
порождает одного или нескольких потомков от двух хромосом. Собственно
говоря, требуется из двух векторов вещественных чисел получить новые
векторы по каким-либо законам. Большинство real-coded алгоритмов
генерируют новые векторы в окрестности родительских пар. Для начала
рассмотрим простые и популярные кроссоверы.
Пусть 0x01 graphic
и 0x01 graphic
- две хромосомы, выбранные оператором селекции для скрещивания. После
формулы для некоторых кроссоверов приводится рисунок - геометрическая
интерпретация его работы. Предполагается, что 0x01 graphic
и 0x01 graphic
.
* Плоский кроссовер (flat crossover): создается потомок 0x01 graphic
- случайное число из интервала 0x01 graphic
.
* Простейший кроссовер (simple crossover): случайным образом выбирается
число k из интервала 0x01 graphic
и генерируются два потомка 0x01 graphic
и 0x01 graphic
.
* Арифметический кроссовер (arithmetical crossover): создаются два
потомка 0x01 graphic
, 0x01 graphic
, где 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, w либо константа (равномерный арифметический кроссовер) из интервала
0x01 graphic
, либо изменяется с увеличением эпох (неравномерный арифметический
кроссовер).
0x01 graphic
* Геометрический кроссовер (geometrical crossover): создаются два
потомка 0x01 graphic
, 0x01 graphic
, где 0x01 graphic
, 0x01 graphic
, w - случайное число из интервала 0x01 graphic
.
0x01 graphic
* Смешанный кроссовер (blend, BLX-alpha crossover): генерируется один
потомок 0x01 graphic
, где 0x01 graphic
- случайное число из интервала 0x01 graphic
, 0x01 graphic
, 0x01 graphic
, 0x01 graphic
. BLX-0.0 кроссовер превращается в плоский.
0x01 graphic
* Линейный кроссовер (linear crossover): создаются три потомка 0x01
graphic
, 0x01 graphic
, где 0x01 graphic
, 0x01 graphic
, 0x01 graphic
. На этапе селекции в этом кроссовере отбираются два наиболее сильных
потомка.
0x01 graphic
* Дискретный кроссовер (discrete crossover): каждый ген 0x01 graphic
выбирается случайно по равномерному закону из конечного множества 0x01
graphic
.
0x01 graphic
* Расширенный линейчатый кроссовер (extended line crossover): ген 0x01
graphic
, w - случайное число из интервала 0x01 graphic
.
0x01 graphic
* Эвристический кроссовер (Wright's heuristic crossover). Пусть 0x01
graphic
- один из двух родителей с лучшей приспособленностью. Тогда 0x01
graphic
, w - случайное число из интервала 0x01 graphic
.
0x01 graphic
Нечеткий кроссовер (fuzzy recombination, FR-d crossover): создаются два
потомка 0x01 graphic
, 0x01 graphic
. Вероятность того, что в i-том гене появится число 0x01 graphic
, задается распределением 0x01 graphic
, где 0x01 graphic
- распределения вероятностей треугольной формы (треугольные нечеткие
функции принадлежности) со следующими свойствами 0x01 graphic
( 0x01 graphic
и 0x01 graphic
):
+----------------------------------------------+
| Распределение |Минимум | Центр |Максимум|
| вероятностей | | | |
|-------------------+--------+--------+--------|
|0x01 graphic |0x01 |0x01 |0x01 |
| |graphic |graphic |graphic |
|-------------------+--------+--------+--------|
|0x01 graphic |0x01 |0x01 |0x01 |
| |graphic |graphic |graphic |
+----------------------------------------------+
Параметр d определяет степень перекрытия треугольных функций
принадлежности, по умолчанию 0x01 graphic
.
0x01 graphic
В качестве оператора мутации наибольшее распространение получили:
случайная и неравномерная мутация (random and non-uniform mutation).
При случайной мутации ген, подлежащий изменению, принимает случайное
значение из интервала своего изменения. В неравномерной мутации значение
гена после оператора мутации рассчитывается по формуле:
0x01 graphic
Сложно сказать, что более эффективно в каждом конкретном случае, но
многочисленные исследования доказывают, что непрерывные генетические
алгоритмы не менее эффективно, а часто гораздо эффективнее справляются с
задачами оптимизации в многомерных пространствах, при этом более просты в
реализации из-за отсутствия процедур кодирования и декодирования хромосом.
Рассмотренные кроссоверы исторически были предложены первыми, однако во
многих задачах их эффективность оказывается невысокой. Исключение
составляет BLX-кроссовер с параметром 0x01 graphic
- он превосходит по эффективности большинство простых кроссоверов. Позднее
были разработаны улучшенные операторы скрещивания, аналитическая формула
которых и эффективность обоснованы теоретически. Рассмотрим подробнее один
из таких кроссоверов - SBX.
SBX (англ.: Simulated Binary Crossover) - кроссовер, имитирующий двоичный.
Был разработан в 1995 году исследовательской группой под руководством K.
Deb'а. Как следует из его названия, этот кроссовер моделирует принципы
работы двоичного оператора скрещивания.
SBX кроссовер был получен следующим способом. У двоичного кроссовера было
обнаружено важное свойство - среднее значение функции приспособленности
оставалось неизменным у родителей и их потомков, полученных путем
скрещивания. Затем автором было введено понятие силы поиска кроссовера
(search power). Это количественная величина, характеризующая распределение
вероятностей появления любого потомка от двух произвольных родителей.
Первоначально была рассчитана сила поиска для одноточечного двоичного
кроссовера, а затем был разработан вещественный SBX кроссовер с такой же
силой поиска. В нем сила поиска характеризуется распределением
вероятностей случайной величины 0x01 graphic
:
0x01 graphic
Для генерации потомков используется следующий алгоритм, использующий
выражение для 0x01 graphic
. Создаются два потомка 0x01 graphic
, 0x01 graphic
, где 0x01 graphic
, 0x01 graphic
- число, полученное по формуле:
0x01 graphic
В формуле 0x01 graphic
- случайное число, распределенное по равномерному закону, 0x01 graphic
- параметр кроссовера.
На рисунке приведена геометрическая интерпретация работы SBX кроссовера
при скрещивании двух хромосом, соответствующих вещественным числам 2 и 5.
Видно, как параметр n влияет на конечный результат: увеличение n влечет за
собой увеличение вероятности появления потомка в окрестности родителя и
наоборот.
0x01 graphic
Эксперименты автора SBX кроссовера показали, что он во многих случаях
эффективнее BLX, хотя, очевидно, что не существует ни одного кроссовера,
эффективного во всех случаях. Исследования показывают, что использование
нескольких различных операторов кроссовера позволяет уменьшить вероятность
преждевременной сходимости, т.е. улучшить эффективность алгоритма
оптимизации в целом. Для этого могут использоваться специальные стратегии,
изменяющие вероятность применения отдельного эволюционного оператора в
зависимости от его «успешности», или использование гибридных кроссоверов,
которых в настоящее время насчитывается несколько десятков. В любом
случае, если перед Вами стоит задача оптимизации в непрерывных
пространствах, и Вы планируете применить эволюционные техники, то следует
сделать выбор в пользу непрерывного генетического алгоритма.
4. Заключение
За последние годы объёмы экономической информации возросли в несколько
раз, и это является дополнительным стимулом для многих учёных, работающих
в области анализа данных, теории информации и теории алгоритмов,
заниматься генетическими алгоритмами.
Очевидно, этим объясняется появление статей по данной теме и на русском
языке (на других языках уже опубликовано 9000 работ). Правда, стоит
отметить, что пока многие публикации частично (в большей или меньшей
степени) повторяют друг друга и может создаться ложное представление о
том, что теория генетических алгоритмов и, в частности, такая её часть,
как непрерывные генетические алгоритмы, - тема узкая и исчерпываемая
двадцатью страницами данной работы. На самом же деле есть не только
теория, но и практика генетических алгоритмов. В настоящее время известно
о существовании более пятисот программных продуктов, в том или ином виде
использующих генетические алгоритмы для решения оптимизационных и
прогностических задача.
Также стоит отметить, что талантливые программисты создали популярную
игру, базирующуюся на наработках теории генетических алгоритмов, которая
называется «Амёбы: Борьба видов» (http://amebas.ru). Суть игры заключается
в том, что каждый игрок «выращивает» на своём компьютере колонию амёб.
Каждая амёба имеет свой генотип и ведёт борьбу за выживание. В каждом
поколении в ходе сражений часть из них остаётся в проигрыше и не получает
возможности размножаться. По ходу развития (с каждым следующим поколением)
амёбы накапливают в себе всё больше и больше генетической информации. Раз
в некоторое время проводятся Интернет-турниры, на которые каждый игрок
выставляет свою лучшую амёбу. В игре учитываются разные возможности
скрещивания, возможность направить отбор в том или ином направлении,
регулировка количества и силы мутаций и прочие настройки.
В заключение можно сказать, что мои прогнозы развития генетических
алгоритмов являются очень оптимистичными по двум причинам:
1. С повышением вычислительной мощности ЭВМ (не исключено, что после
перехода на квантовые или молекулярные компьютеры) станет возможным
моделировать при помощи генетических алгоритмов всё более и более
сложные ситуации.
2. Не исключено, что учёные, работающие в области классической теории
алгоритмов, найдут решение одной из NP-полных задач, и тогда окажутся
решаемыми все алгоритмы, относящиеся к сложности NP.
5. Список использованной литературы.
1. «АНАЛИТИЧЕСКИЕ ТЕХНОЛОГИИ для прогнозирования и анализа данных», 2005.
«НейроПроект»
2. http://www.gotai.ru
3. http://basegroup.ru
4. http://ru.wikipedia.org
Гамильтоновым циклом в графе называют простой цикл, содержащий все вершины
графа ровно по одному разу. По материалам Википедии - свободной
энциклопедии.
NP-полные задачи — это класс задач, лежащих в классе NP, то есть для
которых пока не найдено быстрых алгоритмов решения, но проверка того,
является ли данное решение правильным, проходит быстро. По материалам
Википедии - свободной энциклопедии.
3
