Сравнительный анализ эволюционных алгоритмов

Высокий потенциал, которым обладают различные формы ЭА для решения трудных оптимизационных задач, известен давно. Диверсификация ЭА привела к значительному разнообразию их форм. Актуальной становится проблема сравнительного анализа, систематизация их особенностей и выработка рекомендаций для решения оптимизационных задач (табл. 5.1), [89]. Джон Фон Нейман опубликовал теорию самовоспроизводящихся автоматов [90].

Критерий сравнения Таблица 5.1.

Вид ЭА	Критерий сравнения
Представление решения	целевая функция	Селекция	Мутация	Рекомбинация	Самоадаптивность
ГА	Двоичное вещественное	Скаляр	Стохастическая, недискриминационная	Вспомогательный оператор	Основной оператор поиска	Малоисследована
ГП	Программное	-	То же	Применяется неоднозначно	То же	-
ЭС	Вещественное	вектор	Детерминированная, дискриминационная	Основной оператор поиска	Важна для самоадаптивности	Среднеквадратичное отклонение
ЭП	-	-	То же	Единственный оператор поиска	Не применяется	-

Различные формы ЭА имитируют эволюционный процесс на различном уровне

абстракции. ГА (генетический алгоритм) и ГП (генетическое программирование) делает акцент на генетический механизм наследственности на уровне хромосом. ЭС, напротив, рассматривают ход эволюции на уровне фенотипа. Алгоритмы ЭП анализируют эволюцию на уровне популяции в целом. Один стринг (хромосома) в ГА кодирует одно решение, т.е. пропорция между генотипом и фенотипом равна 1:1, что соответствует в биологическом смысле одному гаплоиду, т.е. особь с одинарным набором непарных хромосом.

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

В ГА вероятность мутации отдельных генов и хромосом (называется инверсией) близка к природной. В алгоритмах ЭП мутация вообще является единственным оператором поиска, а оператор дискретной рекомбинации в ЭС соответствует природному механизму доминирования родительских хромосом в отличие от так называемой промежуточной рекомбинации, которая аналогична природной передаче некоторых признаков по наследству, что соответствует некоторому компромиссу между родительскими хромосомами. Наконец, оператор кроссинговера, который не применяется в алгоритмах ЭП, т.е. является основным алгоритмом для ГА и ГП. Эти и многие другие методологические различия между разными формами ЭА позволяют говорить о базовых постулатах, таких, как универсальность и фундаментальность, присущих эволюции независимо от формы и уровня абстракции модели. Указанная общность может быть выражена в следующей схеме абстрактного ЭА [89-92]:

1) установка параметров эволюции;

2) инициализация начальной популяции P(0);

3) ;

4) оценка решений, входящих в популяцию;

5) ;

6) селекция (отбор);

7) репликация (повторение, копирование, аутосинтез)

8) вариация (видоизменение);

9) оценка решений – потомков;

10) образование новой популяции ;

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

12) вывод результатов и останов.

Контроверзу Ч. Дарвина (1859 г.) о том, что в ходе естественного отбора побеждает сильнейший, необходимо дополнить: материал для эволюции дают побеждённые.

Между тем в ЭА чаще всего применяются статические fitness – функции, что не позволяет учесть механизм коэволюции в живой природе. Популяция в природе, как объясняет правило, состоит из отдельных, более или менее изолированных локальных подпопуляций, допускающих миграцию отдельных индивидуумов. Большинством ЭА это обстоятельство игнорируется, алгоритмы работают с одной большой, неструктурированной популяцией. Тем не менее решающим обстоятельством для оценки практической пригодности ЭА является прежде всего то, насколько успешно с помощью ЭА может быть решена та или иная оптимизационная задача с точки зрения качества решения и вычислительной сложности. Результаты сравнительного анализа ГА, ГП, ЭС и ЭП представлены выше в таблице 5.1 [81].

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

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

Английские учёные Вольперти Макрид сформулировали и доказали следующую теорему NFL (No-Free-Lunch).

Теорема NFL: для любой пары эвристических алгоритмов поисковой оптимизации справедливо следующее соотношение:

= . (5.1)

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

Несмотря на очевидную ограниченность NFL- теоремы (не учитывается время решения оптимизационной задачи конкурирующими алгоритмами), она позволяет подходить к оценке алгоритмов оптимизации с единых методологических позиций и имеет практически важные следствия:

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

2) Чтобы найти хорошее решение для заданного класса задач оптимизации, необходимо, в начале, идентифицировать характеристические особенности классов задач и затем на их основе искать подходящий алгоритм (самый простой алгоритм – задача линейного программирования и симплекс-метод).

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

Достоинства ЭА:

а) широкая область применения [92];

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

в) пригодность для поиска в сложном пространстве решений большой размерности;

г) отсутствие ограничений на вид целевой функции;

д) ясность схемы и базовых принципов ЭА;

е) интегрируемость ЭА с другими классическими парадигмами ИИ, такими как, искусственные нейросети и нечеткая логика.

Недостатки ЭА:

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

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

в) невысокая эффективность ЭА на исключительных фазах моделирования эволюции (в особенности для ГА), объясняется тем, что операторы поиска в ЭА не ориентированы на быстрое попадание в локальный оптимум;

г) нерешенными остаются вопросы самоадаптации ЭА.

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

Параллелизм ЭА.

Различают следующие типы параллелизма ЭА [81, 89]:

1. глобальный;

2. миграционная модель;

3. диффузионная модель.

В первом случае выполняется параллельное вычисление целевой функции и параллельное выполнение операторов ЭА. Целевая функция отдельного индивидуума в популяции, как правило, не зависит от других индивидуумов, поэтому вычисление целевых функций допускает распараллеливание. При этом популяция хранится в общей памяти, а отдельный процессор считывает хромосому из памяти и возвращает результат после вычислений целевой функции в виде fitness-значения. Процедура синхронизации здесь проводится лишь при формировании новой популяции. В случае, если вычислительная система имеет распределенную память, то популяция и fitness-значения отдельных индивидуумов хранятся в «мастер-процессоре», а расчеты производятся на вспомогательных процессорах. Некоторую трудность для распараллеливания представляет процедура селекции. Здесь преимущество в смысле распараллеливания получают те форы селекции, которые не используют глобальную статистику о популяции, например, «соревновательные» способы селекции. Легко распараллеливаемыми являются операторы мутации и кроссинговера, так как они выполняются независимо друг от друга и в основном случайным образом.

Другой тип параллелизма – миграционная модель - наиболее эффективно реализуется в вычислительных системах с MIMD – архитектурой путем разделения общей популяции на отдельные подпопуляции, имитационное моделирование которых осуществляются на отдельных процессорах. Если между отдельными подпопуляциями установить правила миграции отдельных индивидуумов, то получится миграционная модель. Для этого требуется задать количество и размеры подпопуляций, топологию связей между ними, частоту и интервал миграции, а также стратегию эмиграции и иммиграции. Размеры и число подпопуляций определяются числом и быстродействием используемых процессов или транспьютеров, а так же сложностью решаемой оптимизационной проблемы. Что касается топологии связей в миграционной модели, то здесь различаются два варианта: «островная» модель, предусматривающая миграцию между любыми подпопуляциями, и миграционная модель, предусматривающая обмен между соседними подпопуляциями. Применение того или иного варианта миграционной модели зависит от архитектуры параллельного вычислителя (сетевая или кольцевая). Частота миграции определяется размерами подпопуляций. При высокой частоте подпопуляция может быстро потерять гетерогенность. Наоборот, при слабой интенсивности миграции и большом числе подпопуляций возрастает вероятность получения нескольких хороших решений, однако сходимость ЭА замедляется [92].

Третья разновидность параллелизм ЭА – диффузионная модель – наиболее эффективно реализуется в вычислительных системах с SIMD-архитектурой. В этом случает общая популяция разделяется на большое количество немногочисленных подпопуляций, а операторы кроссинговера и селекции применяются лишь в ограниченной области, определяемой отношением соседства. Это приводит к тому, что хорошие решения очень медленно распространяются в популяции (диффузия) и проблема попадания в «локальную яму» становится менее острой.

Выводы. Эволюционные алгоритмы наименее подходят для решения оптимизационных проблем, если:

· требуется найти глобальный оптимум;

· имеется эффективный не эволюционный алгоритм оптимизации;

· переменные, от которых зависит решение, можно оптимизировать независимо;

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

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

Принципиально подходящими для решения с помощью ЭА являются следующие оптимизационные проблемы:

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

· стохастические задачи;

· динамические задачи с блуждающим оптимумом;

· задачи комбинаторной оптимизации;

· задачи прогнозирования и распознавания образов.