Факторы, создающие сложности для работы генетических алгоритмов.

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

Многоэкстремальность

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

Пример: функция Растригина.

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

Обманчивость

Обманчивость – свойство функции, построенной таким образом, что при работе ГА сходится к локальному экстремуму.

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

В подобных случаях ГА «скатывается» в локальный экстремум.

Пример:   Строка-хромосома состоит из 10-ти 4-х битовых подстрок (генов).

Функция пригодности задаётся как функция, зависящая от количества «1» в каждом из генов.

Функция q(ui) задаётся в табличном виде:

Анализируя табличную функцию q(ui), увидим, что максимум ФП получится, если все гены будут состоять из четырёх единиц (1111), вероятность чего крайне мала. В остальных случаях увеличение числа единиц приводит к уменьшению ФП. Поэтому решения с увеличением числа единиц будут с большей вероятностью «отбрасываться» алгоритмом, не позволяя алгоритму «дойти» до искомого оптимума с четырьмя единицами в гене.

ФП лок.оптимума = 3*10

ФП глоб. оптимума  = 4*10

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

Изолированность оптимума («поиск иголки в стоге сена»)

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