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

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

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

Основные определения и свойства

Являясь разновидностью методов поиска с элементами случайности, генетические алгоритмы имеют целью нахождение лучшего по сравнению с имеющимся, а не оптимальным решением задачи. Это связано с тем, что для сложной системы часто требуется найти хоть какое-нибудь удовлетво­рительное решение, а проблема достижения оптимума отходит на второй план. При этом другие методы, ориентированные на поиск именно опти­мального решения, вследствие чрезвычайной сложности задачи становят­ся вообще неприменимыми. В этом кроется причина появления, развития и роста популярности генетических алгоритмов. Хотя, как и всякий дру­гой метод поиска, этот подход не является оптимальным методом решения любых задач. Дополнительным свойством этих алгоритмов является не­вмешательство человека в развивающийся процесс поиска. Человек может влиять на него лишь опосредованно, задавая определенные параметры.

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

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

· Для поиска генетический алгоритм использует несколько то­чек поискового пространства одновременно, а не переходит от точки к точке, как это делается в традиционных методах. Это позволяет преодо­леть один из их недостатков - опасность попадания в локальный экстре­мум целевой функции, если она не является унимодальной, то есть имеет несколько таких экстремумов. Использование нескольких точек одновре­менно значительно снижает такую возможность.

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

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

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

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

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

В процессе работы алгоритма генерация новых особей происходит на основе моделирования процесса размножения. При этом, естественно, по­рождающие особи называются родителями, а порожденные - потомками. Родительская пара, как правило, порождает пару потомков. Непосредствен­ная генерация новых кодовых строк из двух выбранных происходит за счет работы оператора скрещивания, который также называют кроссинговером (от англ, crossover). При порождении новой популяции оператор скрещи­вания может применяться не ко всем парам родителей. Часть этих пар мо­жет переходить в популяцию следующего поколения непосредственно. Насколько часто будет возникать такая ситуация, зависит от значения ве­роятности применения оператора скрещивания, которая является одним из параметров генетического алгоритма.

Моделирование процесса мутации новых особей осуществляется за счет работы оператора мутации. Основным параметром oпepaтоpa мутации также является вероятность мутации.

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

Таким образом, можно перечислить основные понятия и термины, ис­пользуемые в области генетических алгоритмов:

· генотип и фенотип;

· особь и качество особи;

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

· поколение;

· родители и потомки.

К характеристикам генетического алгоритма относятся:

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

· оператор скрещивания и вероятность его использования;

· оператор мутации и вероятность мутации;

· оператор отбора;

· оператор редукции;

· критерий останова.

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

Критерием останова работы генетического алгоритма может быть одно из трех событий:

· Сформировано заданное пользователем число поколений.

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

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

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

Последовательность работы генетического алгоритма

Рассмотрим теперь непосредственно работу генетического алгоритма. Общий алгоритм его работы выглядит следующим образом:

1. Создание исходной популяции

2. Выбор родителей для процесса размножения (работает оператор отбора)

3. Создание потомков выбранных пар родителей (работает оператор скрещивания)

4. Мутация новых особей (работает оператор мутации)

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

6. Сокращение расширенной популяции до исходного размера (работает оператор редукции)

7. Критерий останова работы алгоритма выполнен ?

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

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

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

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

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

Рассмотрим простейший оператор скрещивания. Он выполняется в два этапа. Пусть особь представляет собой строку из m элементов. На первом этапе равновероятно выбирается натуральное число k от 1 до m-1. Это число называется точкой разбиения. В соответствии с ним обе исходные строки разбиваются на две подстроки. На втором этапе строки обменива­ются своими подстроками, лежащими после точки разбиения, то есть эле­ментами с k+1-го по m-й. Так получаются две новые строки, которые на­следовали частично свойства обоих родителей.

Вероятность применения оператора скрещивания обычно выбирается достаточно большой, в пределах от 0,9 до 1, чтобы обеспечить постоянное появление новых особей, расширяющих пространство поиска. При значе­нии вероятности меньше 1 часто используют элитизм. Это особая страте­гия, которая предполагает переход в популяцию следующего поколения элиты, то есть лучших особей текущей популяции, без каких-либо измене­ний. Применение элитизма способствует сохранению общего качества по­пуляции на высоком уровне. При этом элитные особи участвуют еще и в процессе отбора родителей для последующего скрещивания.

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

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

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

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

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

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

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

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

Устойчивость поиска оценивается степенью устойчивости алгоритма к попаданию в точки локальных экстремумов и способностью постоянно увеличивать качество популяции от поколения к поколению.

Два этих фактора - скорость и устойчивость - и определяют эффектив­ность генетического алгоритма для решения каждой конкретной задачи.

Скорость работы генетических алгоритмов

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

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

В первом же случае применяется структурирование популяции реше­ний на основе одного из двух подходов:

· Популяция разделяется на несколько различных подпопуляций (де­мосов), которые впоследствии развиваются параллельно и незави­симо. То есть скрещивание происходит только между членами од­ного демоса. На каком-то этапе работы происходит обмен частью особей между подпопуляциями на основе случайной выборки. И так может продолжаться до завершения работы алгоритма. Дан­ный подход получил название концепции островов.

· Для каждой особи устанавливается ее пространственное положе­ние в популяции. Скрещивание в процессе работы происходит между ближайшими особями. Такой подход получил название концепции скрещивания в локальной области.

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

Еще одним средством повышения скорости работы является кластери­зация. Суть ее состоит, как правило, в двухэтапной работе генетического алгоритма. На первом этапе генетический алгоритм работает традицион­ным образом с целью получения популяции более "хороших" решений. После завершения работы алгоритма из итоговой популяции выбираются группы наиболее близких решений. Эти группы в качестве единого целого образуют исходную популяцию для работы генетического алгоритма на втором этапе/Размер такой популяции будет, естественно, значительно меньше, и, соответственно, алгоритм будет далее осуществлять поиск значительно быстрее. Сужения пространства поиска в данном случае не про­исходит, поскольку применяется исключение из рассмотрения только ряда очень похожих особей, существенно не влияющих на получение новых ви­дов решений.

Устойчивость работы генетических алгоритмов

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

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

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

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

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

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

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

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

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

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

· случайный равновероятный отбор;

· рангово-пропорциональный отбор;

· отбор пропорционально значению целевой функции.

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

· случайное равновероятное удаление; удаление К наихудших;

· удаление, обратно пропорциональное значению целевой функции.

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

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

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