Коэволюционный алгоритм решения нестационарных задач оптимизации

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

Исследования с помощью математических моделей зачастую являются единственно возможным способом изучения сложных систем и решения важнейших практических задач управления. Эти задачи очень трудно или невозможно решить с помощью обычных оптимизационных методов, что приводит к необходимости разрабатывать и применять специализированные методы решения сложных оптимизационных задач [1]. К таким методам, в частности, относятся эволюционные (ЭА) и генетические алгоритмы (ГА), которые уже доказали свою конкурентоспособность при решении многих задач поиска и оптимизации, особенно в практических приложениях, где математические модели имеют сложную структуру и использование стандартных методов крайне затруднено [2; 3]. Тем не менее применение ЭА на практике является непростой проблемой. Это делает актуальными исследования по выявлению специальных свойств известных ЭА, делающих их более привлекательными для решения некоторых классов задач, и разработке подходов, автоматизирующих выбор эффективного эволюционного алгоритма в ходе решения практических задач.

В этом отношении одним из наиболее перспективных подходов является коэволюционный алгоритм (КА) [1], который моделирует эволюцию нескольких популяций, каждая из которых оптимизирует заданную функцию и обладает своей стратегией оптимизации. Таким образом, популяции «борются» за ресурс, который в течение работы алгоритма перераспределяется в пользу более эффективной из них. Изменение размеров ресурсов происходит путем сокращения каждой проигравшей популяции, не достигшей минимального гарантированного размера, который не может быть уменьшен («социальная карточка»), на некоторый определенный заранее процент и увеличения победившей популяции на число, равное сумме потерь проигравших. Таким образом, общее число индивидов остается неизменным. Затем алгоритмы продолжают свою работу с популяциями уже измененных размеров, в которые входят только лучшие индивиды из предыдущих популяций. Процесс продолжается до тех пор, пока либо не выполнится критерий останова, либо не кончится ресурс, выделенный на решение задачи [4].

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

Для решения этой задачи исследователи применяют различные подходы. Согласно широко распространенной классификации, применяемые решения данной проблемы можно отнести к следующим классам: механизмы памяти (явной и неявной) и механизмы поддержания разнообразия. Таким образом, путем комбинирования различных типов селекции и схем формирования нового поколения может быть получено большое количество индивидуальных алгоритмов решения нестационарных задач оптимизации. В табл. 1 приведены 9 из возможных алгоритмов.

Таблица 1

Классификация алгоритмов, оснащенных механизмами учета нестационарности целевой функции

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

• -    наиболее часто используемая тестовая задача - семейство динамических функций Осмера. Функция задается в следующем виде: q 1 ( x , t ) = 1 - e ²⁰"^{x l x -} c ^{( t ))} , где c ( t ) - 0,04([ t1 20]), при x О [1,000; 2,000];

• -    функция Трояновского-Михалевича: G ( x ) = f k ( x ) , если x e D k . Данная функция - полимодальная с настраиваемым числом локальных минимумов. Основная идея при генерации целевой функции такова: в пространстве поиска задан гиперкуб, который определен как разре- n шенная область поискового пространства: D = П [0;1) , i = 1

где и - размерность пространства. По каждой из координат разрешенная область делится на w равных интервалов таким образом, что вся разрешенная область разбивается на w" гиперкубиков, в каждом из которых определена уни n модальная функция f, (x) = а.. П (Г — x)(x — q,), где q. и i=1

г . - соответственно нижняя и верхняя границы текущего гиперкубика по i -й компоненте поискового пространства; a v - коэффициент высоты экстремума в центре текущего гиперкубика. Функция Трояновского-Михалевича рассмотрена при следующей размерности поискового пространства: 2,6 и 18.

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

Результаты исследования эффективности индивидуальных алгоритмов показали, что, как и в случае исследования индивидуальных алгоритмов для стационарной оптимизации, нельзя однозначно говорить о превосходстве определенного алгоритма. Но по большинству лучших результатов в каждой группе алгоритмов можно выявить наиболее эффективный алгоритм (в табл. 1 это алгоритмы 1, 5 и 7) и проранжировать остальные алгоритмы в порядке убывания показателя надежности. При этом установлено, что просто перезапуск стандартного генетического алгоритма сильно уступает алгоритмам для нестационарной оптимизации не только по надежности нахождения решения (лучший результат перезапуска - 40 %, результаты специализированных алгоритмов - 75^100 %), но и практически в два раза по времени выхода на оптимум.

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

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

Итак, проведенные исследования эффективности коэволюционного алгоритма для решения нестационарных задач оптимизации показали, что механизм адаптации стратегии поиска, встроенный в коэволюционный алго-

Таблица 2

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

Примечание. В табл. 2 приняты следующие обозначения: КА № 1 - комбинация, где в состав коэволюционного алгоритма включались два алгоритма, оснащенные неявной памятью и обладающие глобальным и локальным характерами поиска, два алгоритма, оснащенные явной памятью и обладающие глобальным и неизвестным характерами поиска, и один алгоритм, оснащенный гипермутационной схемой с локальным характером поиска; КА № 2 - комбинация, где в состав коэволюционного алгоритма включались один лучший алгоритм, оснащенный неявной памятью, один лучший алгоритм, оснащенный явной памятью, и один лучший алгоритм, оснащенный гипермутационной схемой (без учета характера поиска); КА № 3 - комбинация, где выбор алгоритмов в состав коэволюционного алгоритма производился случайно (независимо от характера поиска и механизма учета нестационарности); ГА - стандартный генетический алгоритм для решения нестационарных задач оптимизации, являющийся лучшим среди индивидуальных алгоритмов, которые предложены для включения в состав коэволюционного алгоритма.

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