Тесты и результаты

В работе сравнивались пять методов: три на основе гаплоидного представления решения, в том числе алгоритм с использованием внешней памяти, один на основе диплоидного представления (триаллельная схема) [Smith et al., 1992] и на основе структурного представления [Dasgupta, 1993].

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

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

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

Перечисленные выше алгоритмы сравнивались по скорости отклика на изменение состояния среды, коллективной приспособленности [Morrison, 2003]. Под скоростью отклика понимается количество замеров, произведенных алгоритмом после изменения среды, для прихода к оптимальному решению (в таблице приведено среднее количество поколений). Коллективная приспособленность для алгоритма, является значением лучшей в популяции особи, усредненным по количеству поколений в одном запуске и общему количеству запуска алгоритма.

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

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

Табл. 1.