МЕТОДЫ ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА ОДНОМЕРНЫХ МНОГОЭКСТРЕМАЛЬНЫХ ФУНКЦИЙ
Оценка 4.8

МЕТОДЫ ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА ОДНОМЕРНЫХ МНОГОЭКСТРЕМАЛЬНЫХ ФУНКЦИЙ

Оценка 4.8
doc
08.05.2020
МЕТОДЫ ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА ОДНОМЕРНЫХ МНОГОЭКСТРЕМАЛЬНЫХ ФУНКЦИЙ
39. МЕТОДЫ ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА ОДНОМЕРНЫХ МНОГОЭКСТРЕМАЛЬНЫХ ФУНКЦИЙ.doc

4 МЕТОДЫ ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА ОДНОМЕРНЫХ МНОГОЭКСТРЕМАЛЬНЫХ ФУНКЦИЙ

Некоторые методы решения многомерных задач оптимизации (если размерность вектора варьируемых параметров X больше единицы, то детерминированная задача оптимизации называется многопараметрической задачей оптимизации) требуют решения одномерной задачи глобальной оптимизации (ставится задача отыскания глобального минимума критерия оптимальности f(x)).

4.1 Метод перебора. Одномерный метод Монте-Карло

Рассматривается следующая одномерная задача условной глобальной оптимизации (если задача оптимизации является задачей условной оптимизации и отыскивается глобальный минимум критерия оптимальности f(x), то эта задача оптимизации называется задачей глобальной условной оптимизации): найти минимум, вообще говоря, многоэкстремальной функции f(x), определенной в замкнутой области допустимых значений D = [a;b]:

                                                             (4.1)

 

 

Алгоритм метода перебора

 

 

 

 

 

 

 

 

 

 

 


Рис. 4.1. Иллюстрация метода перебора

 

Шаг 1. Покрываем интервал [a;b] некоторой сеткой с узлами .

Шаг 2. Производим испытание в точке , т.е. вычисляем значения  функции f(x) в этой точке.

Шаг 3. Полагаем r = 2.

Шаг 4. Производим испытание в точке xr и вычисляем значение fr = f(xr) функции f(x) в этой точке.

Шаг 5. Если , то выполняем присваивания .

Шаг 6. Если r < N, то выполняем присваивание r = r + 1 и переходим к шагу 4, иначе заканчиваем вычисления.

Шаг 7. Принимаем  в качестве приближенного значения точки глобального минимума функции f(x) на интервале [a;b] или каким-либо из рассмотренных одномерных методов локальной оптимизации организуем в окрестности точки  поиск локального минимума этой функции.

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

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

Алгоритм одномерного метода Монте-Карло

Шаг 1. Генерируем с помощью какого-либо программного генератора случайных чисел, равномерно распределенных в интервале [a;b], случайное число .

Шаг 2. Производим испытание в точке  и вычисляем значения  функции f(x) в этой точке.

Шаг 3. Полагаем r = 2.

Шаг 4. Аналогично шагу 1 генерируем случайное число .

Шаг 5. Производим испытание в точке  – вычисляем значение fr = f(xr) функции f(x) в этой точке.

Шаг 6. Если , то выполняем присваивания .

Шаг 7. Если r < N, то выполняем присваивание r = r + 1 и переходим к шагу 4, иначе заканчиваем вычисления. Здесь N – количество испытаний.

Шаг 8. Принимаем  в качестве приближенного значения точки глобального минимума функции f(x) на интервале [a;b] или каким-либо из рассмотренных одномерных методов локальной оптимизации организуем в окрестности точки  поиск локального минимума этой функции.

При достаточно большом N метода гарантирует нахождение глобального минимума с высокой вероятностью.

4.2 Метод выделения интервалов унимодальности

Рассмотрим одномерную задачу условной глобальной оптимизации: найти минимум одномерной многоэкстремальной функции f(x), определенной в замкнутой области допустимых значений D = [a;b] и имеющей в этой области конечное число минимумов (4.1).

Метод выделения интервалов унимодальности функции f(x) требует априорного знания оценки d > 0 минимального расстояния между локальными минимумами этой функции.

Алгоритм метода выделения интервалов унимодальности (рис. 4.2):

Шаг 1. Полагаем r = 1.

Шаг 2. Если функция f(x) в точке a возрастает, то полагаем  и переходим к шагу 4.

Шаг 3. Если функция f(x) в точке a убывает, то полагаем  и переходим к шагу 5.

 

 

 

 

 

 

 

 

 

 

 


Рис. 4.2. К алгоритму метода выделения интервалов унимодальности

 

Шаг 4. Последовательно увеличивая х на величину  по формуле , находим первую точку , в которой функция f(x) убывает. Здесь и далее  – величина в несколько раз меньшая величины d.

Шаг 5. Последовательно увеличивая х на величину  по формуле , находим первую точку , в которой функция f(x) возрастает.

Шаг 6. В качестве r-го интервала унимодальности принимаем интервал [].

Шаг 7. Если интервал [a;b] исчерпан, переходим шагу 8, иначе полагаем  и переходим к шагу 4.

Шаг 8. Положим, что общее количество найденных интервалов унимодальности функции f(x) равно N 1. Каким-либо одномерным методом локальной оптимизации находим локальный минимум функции f(x) в каждом из N 1 интервалов унимодальности. Обозначим точки этих минимумов . Соответствующие значения функции f(x) обозначим . Добавим к точкам  точки  и вычислим соответствующие значения функции f(x).

Шаг 9. Найдем минимальную из величин  и соответствующее значение аргумента: .

Шаг 10. В качестве решения задачи глобальной оптимизации (4.1) примем точку .

На рис. 4.2 интервалами унимодальности являются интервалы .

Для определения того, возрастает или убывает в данной точке функция f(x), может использоваться ее первая разность в этой точке , где х – некоторая малая величина. А именно, если   fx > 0, то функция возрастает в точке х; иначе – убывает. Заметим, что при этом в каждой точке требуется выполнить дополнительное испытание функции f(x).

Если функция f(x) непрерывно дифференцируема в интервале [a;b], то для определения того, возрастает или убывает в данной точке эта функция, можно, очевидно, использовать значения первой производной функции f(x) в этой точке. А именно, если , то в точке x функция f(x) возрастает; в противном случае – убывает.

Замечание

Если априорная оценка d минимального расстояния между локальными минимумами функции f(x) отсутствует, то никаких оснований полагать, что в интервалах, выделенных с помощью рассмотренного алгоритма, функция f(x) является унимодальной функцией. Пусть, например, функция f(x) на интервале [c;d] постоянна (рис. 4.3). Если к такой функции применить алгоритм выделения интервалов унимодальности с любым > 0, то в качестве интервала унимодальности будет выделен интервал , на котором функция f(x) имеет бесконечное количество минимумов, т.е. не является унимодальной функцией.

 

 

 

 

 

 

 

 

 


Рис. 4.3. Иллюстрация к замечанию

 

4.3 Метод аппроксимирующих моделей

Рассмотрим одномерную задачу условной глобальной оптимизации: найти минимум одномерной мультимодальной функции f(x), определенной в замкнутой области допустимых значений D = [a;b] (4.1).

Алгоритм метода аппроксимирующих моделей:

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 4.4. Алгоритм метода аппроксимирующих моделей. N = 5

Шаг 1. Покрываем интервал [a;b] некоторой сеткой с узлами  и производим испытания в точках , т.е. вычисляем значения функции f(x) в этих точках .

Шаг 2. Строим аппроксимирующую функцию , проходящую через точки . Эту функцию принято называть математической моделью минимизируемой функции f(x) или модельной функцией.

Шаг 3. Оцениваем адекватность построенной модели . Для этого:

производим дополнительные испытания функции f(x) в некоторых точках;

вычисляем значения модельной функции  и функции f(x) в этих точках ;

вычисляем погрешность аппроксимации, например, .

Шаг 4. Если погрешность аппроксимации превышает заданную, то по результатам всех предшествующих испытаний строим новую модельную функцию  и переходим к шагу 3.

Шаг 5. Определяем положение глобального минимума модельной функции , который или принимается в качестве глобального минимума функции f(x), или уточняется с помощью какого-либо метода локальной оптимизации.

            На рис. 4.4  – точки локального минимума модельной функции ; точка  – приближенное значение точки глобального минимума функции f(x) на интервале [a;b].

В качестве модельных функций  чаще всего используют полиномы и сплайны.

Рассмотрим использование в качестве модельной функции полиномов.

Аппроксимирующий полином Лагранжа

Будем искать аппроксимирующий полином в виде

   (4.2)

где  – неизвестные полиномы от х, независящие от аппроксимируемой функции .

Из того условия, что модельная функция  должна совпадать с аппроксимируемой функцией f(x) в узлах сетки , имеем систему из  N + 1 равенств:

(4.3)

Для выполнения равенств (4.3) полиномы , очевидно, должны удовлетворять условиям

                                                  (4.4)

или, другими словами, полином , должен иметь в качестве корней все числа , кроме числа xj, а при x = xj должен иметь значение, равное единице.

Условию (4.4) удовлетворяют только полиномы вида , где A – неизвестная константа. Найдем эту константу из условия :

Таким образом,

    (4.5)

и искомый аппроксимирующий полином определяют выражением

                                     (4.6)

Полином (4.6) называется аппроксимирующим полиномом Лагранжа.

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

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


МЕТОДЫ ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА

МЕТОДЫ ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА

Шаг 3. Полагаем r = 2. Шаг 4

Шаг 3. Полагаем r = 2. Шаг 4

Метод выделения интервалов унимодальности

Метод выделения интервалов унимодальности

Шаг 7. Если интервал [ a ; b ] исчерпан, переходим шагу 8, иначе полагаем и переходим к шагу 4

Шаг 7. Если интервал [ a ; b ] исчерпан, переходим шагу 8, иначе полагаем и переходим к шагу 4

Рис. 4.3. Иллюстрация к замечанию 4

Рис. 4.3. Иллюстрация к замечанию 4

Шаг 3. Оцениваем адекватность построенной модели

Шаг 3. Оцениваем адекватность построенной модели

Условию (4.4) удовлетворяют только полиномы вида , где

Условию (4.4) удовлетворяют только полиномы вида , где
Скачать файл