Анализ эффективности алгоритмов поиска оптимума.

Функционирование системы автоматизированного оптимального проектирования предполагает наличие предварительной информации об эффективности алгоритмов поиска и их предпочтительной стадии применения. Такая информация накапливается на основе статистики, полученной на математических моделях проектируемых изделий, либо с помощью тестов [4].

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

Обычно при оценке эффективности метода используют два типа характеристик: локальные и общие [6].

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

- модуль разности значений в точках и ; (7)

- норма разности двух векторов и (8)

- норма вектора градиента функции в точке . (9)

В дальнейшем значения компонент вектора х, полученные на k-ой итерации, будем обозначать , а при возведении в квадрат записывать .

Пример 2. Вычислить e_х и d_х на k-ой итерации поиска минимума функции , если получены значения .

По формуле (7) получаем значения

и по формуле (8)

Общие оценки эффективности алгоритмов поиска отражают такие важнейшие их свойства, как:

· Точность поиска, т.е. значение окрестности локального оптимума, в которую приводит алгоритм оптимизации после заданного числа итераций;

· Скорость сходимости, т.е. число итераций, необходимое для достижения заданной точности;

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

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

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

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

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

- тесты должны быть унифицированными и общепринятыми (или известными);

- тесты должны моделировать типовые особенности для данного класса методов;

- решение тестовой задачи должно быть известно;

- тестовая задача должна быть компактной.

Основными тестовыми функциями являются следующие [8]:

1. Квадратичная функция простой структуры

(10)

2. Функция Розенброка

(11)

3. «Асимметричная долина» (12)

Предлагаю ознакомиться с аналогичными статьями:

Оптимизация

• Безусловная минимизация функций численными методами второго порядка.
• Метод сопряженных градиентов Флетчера-Ривса.
• Метод наискорейшего спуска.
• Градиентные методы.
• Формулировка задачи многомерной оптимизации.
• Метод поиска минимума функции одной переменной с использованием кубичной аппроксимации

образование

• Мой тест по сетям
• Цифровая обработка сигналлов
• Интерфейсы. Общие положения.
• Активность
• Основная семиотическая конструкция: треугольник Фреге
• Семиотика и знания

Университет

• Моделирование процессов управления ЛА. Управление самолетом «Боинг - 747» при посадке.
• ТЕТРАДЬ ВЫРЕЗОК
• ПЕРЕПЛЕТ ЖУРНАЛОВ
• КАК ПРОДЛИТЬ КНИЖКЕ ЖИЗНЬ
• Мой тест по сетям
• Компьютерная философия