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

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

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

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

Ответ на эти вопросы возможен только в том случае, когда определен класс функций {Ф(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 Общая схема экспериментального тестирования алгоритмов поисковой оптимизации

Классы тестовых функций