Общие советы

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

Под кодированием понимается способ представления данных в генетическом виде. Здесь важно, чтобы была возможность получить решение в хромосоме, а также, чтобы в генотипе мог быть записан любой корректный вариант, более или менее претендующий на то, чтобы оказаться ответом на поставленную задачу. В большинстве случаев проблем по этому поводу не возникает, однако для одной и той же задачи может существовать несколько способов генетического представления параметров, которые могут существенно влиять на скорость генетического поиска и качество решения. См., например, D. Whitley "Fundamental principles of deception in genetic search", а также публикации по решению задач на графах и настройке ИНС.

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

Основная цель воспроизводства -- получение новых вариантов решений-кандидатов из уже существующих. Здесь очень желательно, чтобы при скрещивании родительских особей получались корректные в рамках поставленной задачи потомки. В ряде случаев это условие требует использования "нестандартных" генетических операторов и/или специфичного кодирования. К примеру при решении задачи коммивояжера в маршруте не должна 2 раза и чаще встречаться одна и та же вершина, что часто получается в результате применения традиционно используемых операторов 1- и 2-точечного и однородного кроссинговера. Поэтому для данной проблемы разработаны специальные операторы скрещивания и мутации.

[30 декабря 2006г.]

Размер популяции

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

Диапазоны для слишком малых и больших популяций даны приблизительно и зависят как от задачи, так и от используемой модели алгоритма. Например, при сравнении эффективности (читай количества ВЦФ) разных моделей ГА, выбранные алгоритмы существенно модифицировать нельзя. При этом может получиться так, что часть из них способны решать задачу только в случае использования большой популяции. Как правило они малоэффективны, по крайней мере для поставленной проблемы. Также есть алгоритмы, которые используют малый разиер популяции. Характерными представителями таковых являются эволюционные стратегии, микро ГА (micro GA), и hill-climber'ы, переводится как методы локального спуска (спасибо Е.С.Семенкину).

По личному опыту и анализу литературы, целесообразно использовать популяции размером 20-500 особей. Альтернативы, конечно же, возможны.

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

[30 декабря 2006г.]

Способ кодирования

На сегодняшний наиболее распространены следующие способы кодирования:

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

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

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

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

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

[30 декабря 2006г.]

Рекомендации по улучшению работы ГА

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

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

Итак, с критериями более-менее определились. А теперь о главном. Замечено, что:

• использование более агрессивных вариантов отбора вкупе с достаточно большой вероятностью мутации во многих случаях позволяет добиться более хороших результатов, по сравнению с каноническим ГА. Агрессивными стратегиями отбора можно считать отбор усечением с достаточно большим порогом (т.е. когда к воспроизводству допускается меньшее количество особей), а также турнирный отбор с размером турнира 4 и больше;
• популяция большего размера работает стабильнее и зачастую лучше. Если же необходимо уложиться в некоторое количество вычислений целевой функции, то лучше поискать оптимальный размер, при котором и решение может быть найдено (пусть и не всегда, алгоритм все-таки вероятностный), и вычислительные затраты вполне приемлемые. При этом, возможно, придется повозиться с настройкой других параметров;
• двухточечный и однородный операторы кроссинговера, как правило, работают лучше, чем одноточечный;
• планомерное выслеживание и ликвидация диверсионных элементов в лице дубликатов в популяции (атака клонов) повышают качество результатов и полезно против преждевременной сходимости;
• элитизм - хорошая штука (как ни крути);
• большая вероятность мутации в некоторых случаях способна улучшить работу алгоритма (особенно для малых популяций), но нежелательна, в силу внесения большой хаотичности в эволюционный процесс, что может отрицательно сказаться на стабильности работы алгоритма;
• если вы все сделали правильно, а генетический алгоритм работает либо совсем никак, либо нестабильно (то хорошо, то из рук вон плохо), то, скорее всего, в исходный код программы закралась ошибка (см. дисклаймер в начале параграфа);
• и, напоследок, самое главное. Эти советы не обязательно будут работать в 100% случаев. Они приведены, в первую очередь, чтобы дать пищу для размышлений и, вполне возможно, решение вашей проблемы лежит за пределами данного списка. Но ГА интересны не в последнюю очередь именно из-за своей многоплановостью и возможностями для исследования.

[30 декабря 2006г.]

Когда стоит применять генетические алгоритмы

Несколько советов по поводу целесообразности использования ГА. Не мудрствуя лукаво, привожу цитату К. Де Йонга, одного из студентов Д.Холланда, а ныне профессора Университета Дж. Мейсона, экс-главного редактора журнала "Evolutionary Computations", издательства MIT Press при Массачусетском институте технологий, и просто уважаемого в Evolutionary Computation сообществе человека:

The key point in deciding whether or not to use genetic algorithms for a particular problem centers around the question: what is the space to be searched? If that space is well understood and contains structure that can be exploited by special-purpose search techniques, the use of genetic algorithms is generally computationally less efficient. If the space to be searched is not well understood and relatively unstructured, and if an effective GA representation of that space can be developed, then GAs provide a surprisingly powerfull search heuristic for large, complex spaces.

De Jong, K.A. Introduction to the second special issue on
genetic algorithms. Machine Learning, 5(4), 351-353.

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

Де Йонг К. А. Введение ко второму специальному выпуску по
генетическим алгоритмам. Машинное обучение, №5(4), с. 351-353.)

Также отмечу, что не стоит расценивать генетические алгоритмы как своеобразную панацею для задач оптимизации. Существует No Free Lunch теорема (в моем вольном переводе "Об отсутствии бесплатных обедов", можно "О бесплатном сыре"), согласно которой на полном множестве задач нельзя выделить самый лучший метод оптимизации. Поэтому с большой вероятностью генетические алгоритмы покажут как минимум не лучшие результаты по сравнению со специально разработанными методами.

Большой (или даже так, ОГРОМНЫЙ) плюс эволюционных вычислений лично мне видится в предоставляемом ими унифицированном подходе к решению самых различных проблем. И еще, для сложных переборных задач (большинство из которых NP-полные, т.е. не решаются полным перебором за полиномиальное время), таких, например, как задача коммивояжера и поиск булевых термов, генетические алгоритмы показывают блестящие результаты, о чем и говорит д-р Де Йонг.

[30 декабря 2006г.]