Метод перебора

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

Пускай задана функция
И задача оптимизации выглядит так:
Пускай также задано число наблюдений n.

Тогда отрезок разбивают на равных частей точками деления:

Вычислив значения в точках найдем путем сравнения точку где это число от 1 до n такую, что
для всех i от 1 до n.
Тогда интервал неопределённости составляет величину а погрешность определения точки минимума функции соответственно составляет :

Модификация
Если заданное количество измерений чётно (n = 2k), то разбиение можно проводить другим, более изощрённым способом:

где δ — некая константа из интервала
Тогда в худшем случае интервал неопределённости имеет длину

Поиск экстремума функции
Для численного решения задач поиска локального максимума и минимума в Mathcad имеются встроенные функции Minerr, Minimize И Maximize. Принцип их действия очень близок к принципу расчетов, заложенных во встроенной функции Find, предназначенной для решения алгебраических уравнений (см. главу 5).

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

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

Powered by Drupal - Design by artinet