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

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

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

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

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

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

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

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

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

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

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

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

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

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

§ генотип и фенотип,

§ особь и качество особи,

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

§ поколение,

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

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

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

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

§ оператор мутации и вероятность мутации,

§ оператор отбора,

§ оператор редукции,

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

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

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

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

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

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

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

Рассмотрим теперь непосредственно работу генетического алгоритма.

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

Генетические алгоритмы представляют собой алгоритмы поиска, построенные на принципах, сходных с принципами естественного отбора и генетики. Если говорить обобщенно, они объединяют в себе принцип выживания наиболее перспективных особей – решений и структуризированный обмен информацией, в котором присутствует элемент случайности, который моделирует природные процессы наследования и мутации[1,2]. Дополнительным свойством этих алгоритмов является невмешательство человека в развивающийся процесс поиска.

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

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

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

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

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

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

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

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

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

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

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

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

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

· генотип и фенотип, особь и качество особи;

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

· поколение;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим теперь непосредственно работу генетического алгоритма.

1. Создание исходной популяции (задается случайным образом).

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

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

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

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

порожденных особей.

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

7. Останов работы генетического алгоритма по заданному критерию.

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

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

где n – размер популяции; i – номер особи; Pi – вероятность участия особи в процессе размножения; Fi – значение целевой функции для i-й особи. Очевидно, что одна особь может быть задействована в нескольких родительских парах.

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

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

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

Стока 1 X1X2...XkXk+1...Xn X1X2...XkYk+1...Yn

Строка 2 Y1Y2...YkYk+1...Yk Y1Y2...YkXk+1...Xn

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

K=(1-P)ÍN,

где К- количество элитных особей; Р – вероятность применения оператора скрещивания; N- размер популяции.

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

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

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

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

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