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

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

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

Зачем использовать GA? Ответ прост: генетический алгоритм оперирует совокупностью особей (популяция), которые представляют собой строки, кодирующие одно из решений задачи. В отличие от GA, другие алгоритмы оптимизации работают лишь с одним решением. [1]

Генетические алгоритмы применяются для:

• •     Оптимизации запросов в базах данных.

• •    Решения задач на графах.

• •    Настройки и обучение нейронной сети.

• •    Решения задач компоновки.

• •     Составления расписаний.

• •    Разработки игровых стратегий.

• •    Реализации искусственной жизни и т.д.

Преимущества GA:

• •    Быстрее и эффективнее по сравнению с классическими методами решения оптимизационных задач.

• •    Имеет хорошие возможности для параллельного решения нескольких задач.

• •    Оптимизирует как непрерывные, так и дискретные функции.

• •    Предоставляет список решений, а не одно решение.

• •    Эффективен, когда пространство поиска очень велико.

Недостатки GA:

• •    Ограничение на круг решаемых задач.

• •    Из-за того, что GA выполняет многократные вычисления, для некоторых проблем (задач) это может оказаться дорогостоящим процессом.

• •    Генетический алгоритм является стохастическим (случайным), а это значит, что нет никаких гарантий, получить оптимальное или качественное решение. [2]

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

Алгоритм делится на четыре этапа:

• •    Создания нового поколения

• •    Размножение

• •    Мутации

• •    Отбор

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

Рассмотрим каждый шаг более подробно:

Создание популяции. На первом шаге создается основная популяция. Неэффективная, как правило. Самое главное, чтобы она подходила по всем параметрам и «могла размножаться».

Размножение. На втором шаге происходит все как у человеческих особей. Для получения потомства необходимо наличие двух родителей. Потомок должен обладать чертами обоих родителей.

Мутации. На третьем шаге происходит изменение значения гена потомка на противоположное.

Отбор. На заключительном этапе производится отбор на основании некоторого критерия качества. Не прошедшие отбор особи исключаются из рассмотрения. [3]

Существует различные виды генетических алгоритмов:

• •    Канонический GA

• •    Генитор (Genitor)

• •    Гибридный алгоритм (Hybrid algorithms)

• •    CHC (Cross-population selection, Heterogeneous recombination and Cataclysmic mutation)

• •    GA с нефиксированным размером популяции (Genetic Algorithm with Varying Population Size - GAVaPS)

• •    Параллельный GA (Parallel implementations)

• • Миграция (Migration)

Чтобы доказать насколько мощен генетический алгоритм, рассмотрим пример. Необходимо получить фрагмента песни «крылатые качели» из случайно сгенерированного списка букв. Общее количество символов – 14, каждый из может быть любой из 32 русского алфавита. Следовательно, вероятность получения нужно строки случайным способом равна,

(132)14 = 8.6 х10-22

т. е. практически ноль.

Чтобы произвести кодировку фразы воспользуемся таблицей ASCII.

Тогда фраза «крылатые качели» преобразуется в следующую матрицу:

[234, 240, 251, 235, 224, 242, 251, 229, 234, 224, 247, 229, 235, 232]

Далее генерируется исходная популяция из 10 случайных фраз:

[238, 241, 234, 244, 252, 242, 221, 255, 234, 180, 247, 229, 232,242]

[226, 251, 239, 229, 224, 246, 247, 234, 234, 224, 225, 229, 232,237]

[247, 232, 235, 234, 244, 229, 251, 242, 253, 233, 247, 229, 243,240]

…………………………………………………………………………….. [232, 247, 224, 229, 224, 242, 251, 229, 234, 251, 240, 235, 235, 234]

После этого происходит преобразование матрицы в строки символов и получается 10 случайных фраз:

оскфьтэякrчеит выпефцчккабеин чилифеытэйчеур ичаеатыеырллк.

Функция соответствия вычисляет число правильно отгаданных букв. Например, для строки «оскфьтэякrчеит» это 7. На заключительном этапе будут отобраны наилучшие потомки. [4]

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