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

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

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

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

Для работы оптимизационных алгоритмов в среде мультиверсионного исполнения необходимо доработать модуль согласования результатов. Этот модуль, опираясь на выходы мультиверсий, генерирует оптимальный выход всей системы. Используя процесс оптимизации, целесообразно не сравнивать результаты версий алгоритмов оптимизации между собой, а выбирать оптимальнуюточку среди всех выходов. В этом случае будем считать корректными все те результаты, которые находятся в определенной окрестности этого значения, а остальные - ошибочными. Иными словами, результат алгоритмаjсчитается корректным, если ,i,j[1,N], гдеN– количество мультиверсий. Назовем такой способголосованием по значению оптимизируемой функции.

4. Методология выбора наилучшего алгоритма оптимизации

Конкретную детерминированную задачу оптимизации можно решить различными алгоритмами. Отсюда возникают вопросы:

• какой алгоритм выбрать?

• какой алгоритм является «наилучшим»?

Ответ на эти вопросы возможен только в том случае, когда определен класс функций {Ф(X)}, которому принадлежит критерий оптимальности Ф(X). Без определения этого класса ответить на поставленные вопросы невозможно – нет алгоритма, наилучшего для всех возможных функций Ф(X).

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

Для формальной постановки задачи определения наилучшего алгоритма из множества {A} на классе функций {Ф(X)} необходимо еще ввестикритерий качества алгоритма оптимизации. Обозначим этот критерийW(Ф,A), где Ф{Ф(X)},A{A}. Положим, что оптимальным является наименьшее значение этого критерия.

Для построения критерия качества алгоритма на всем классе функций {Ф(X)} можно воспользоваться

• принципом гарантированного результата: ;

• некоторым средним значением критерия качества алгоритма на классе функций {Ф(X)}.

Если критерий качества алгоритма на классе функций {Ф(X)} тем или иным образом определен, то задача отысканиянаилучшего алгоритма оптимизациина этом классе функций формально может быть записана в следующем виде: .

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

В качестве критерия качества алгоритма оптимизации W(Ф,A) обычно рассматривают затраты времени на поиск. Эти затраты складываются

• из затрат на испытания

• из затрат на нахождение точек X^rпо информации о предыдущих испытаниях (можно сказать – из затрат на вычисления значений функции).

Обычно, на практике, последние затраты много меньше первых, поэтому в качестве критерия качества алгоритма оптимизации A можно использовать количество испытаний , необходимых для нахождения минимума функции Ф(X) с заданной точностью ε при начальном приближенииX⁰.

Для корректного сравнения эффективности различных алгоритмов, экспериментальное тестирование алгоритмов оптимизациинеобходимо выполнять при одинаковых значениях заданной точности решения ε. Поэтому будем в качестве критерия качества алгоритма оптимизацииAна классе функций {Ф(X)} использовать критерий.

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

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

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

Сделаем следующие предположения:

• множество тестируемых алгоритмов {A} состоит изn_AалгоритмовA_i, ;

• при тестировании алгоритма A_i, используется совокупностьn_Фтестовых функций;

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

В сделанных предположениях общую схему экспериментального тестирования алгоритмов оптимизации можно представить в следующем виде (см. рисунок 3 .12).

Рисунок 3.12 Общая схема экспериментального тестирования алгоритмов поисковой оптимизации