Лекция. Генетические алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• поколение;

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

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

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

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

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

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

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

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

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

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

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

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

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

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