Оптимизация

Введение:

 

Оптимизация — модификация  системы для улучшения её эффективности. Система может быть одиночной  компьютерной программой, набором компьютеров  или даже целой сетью, такой как  Интернет.

Хотя целью оптимизации  является получение оптимальной  системы, истинно оптимальная система в процессе оптимизации достигается далеко не всегда. Оптимизированная система обычно является оптимальной только для одной задачи или группы пользователей: где-то может быть важнее уменьшение времени, требуемого программе для выполнения работы, даже ценой потребления большего объёма памяти; в приложениях, где важнее память, могут выбираться более медленные алгоритмы с меньшими запросами к памяти.

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

 

 

 

 

 

 

 

Однопараметрическая оптимизация

 

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

 

Все численные методы одномерной безусловной оптимизации  условно можно сгруппировать  следующим образом:

 

1. Методы исключения  интервалов (линейный поиск):

- Метод половинного деления;

- Метод «золотого сечения»;

-  Метод Фибоначчи;

 

2. Метод полиномиальной аппроксимации: 

-  Метод Пауэлла;

 

3. Методы с использованием производных: 

-  Метод секущих;

-  Метод качательных.

 

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

 

Методы исключения интервалов накладывают  единственное требование на исследуемую  функцию: она должна быть унимодальной. Следовательно, указанные методы можно  использовать для анализа как  непрерывных, так и разрывных функций, а также в случаях, когда переменные принимают значения из дискретного множества. Логическая структура поиска с помощью методов исключения интервалов основана на простом сравнении значений функции в двух пробных точках. Кроме того, при таком сравнении в расчет принимается только отношение порядка на множестве значений функции и не учитывается величина разности между значениями функции.Большим достоинством этих методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы методов нулевого порядка, это возможность определения значений f(x) в заданных точках, а также, что исследуемая целевая функция в допустимой облас-ти, по крайней мере, обладает свойством унимодальности.

 

 

 

1. Метод дихотомии (Метод половинного деления)

 

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

Дана функция F(x). Необходимо найти , доставляющий минимум (или максимум) функции F(x) на интервале [a,b] с заданной точностью , т.е. найти

Запишем словесный алгоритм метода.

1) На каждом шаге  процесса поиска делим отрезок [a,b] пополам, x=(a+b)/2 - координата середины отрезка [a,b].

2) Вычисляем значение  функции F(x) в окрестности вычисленной точки x, т.е.

3) Сравниваем F1 и F2 и отбрасываем одну из половинок отрезка [a,b] (рис.1).

При поиске минимума:

Если F1<F2, то отбрасываем отрезок [x,b], тогда b=x. (рис.1.а)

Иначе отбрасываем отрезок [a,x], тогда a=x. (рис.1.б)

При поиске максимума:

Если F1<F2, то отбрасываем отрезок [a,x], тогда a=x.

Иначе отбрасываем отрезок [x,b], тогда b=x.

4) Деление отрезка [a,b] продолжается, пока его длина не станет меньше заданной точности , т.е.

 
Рис.1.  Поиск экстремума функции F(x) методом дихотомии

 

 

Схема алгоритма метода дихотомии представлена на рис.2.

На рис.2: c - константа,

При выводе x – координата точки, в которой функция F(x) имеет минимум (или максимум), FM – значение функции F(x) в этой точке.

 

 
Рис. 2.  Схема алгоритма метода дихотомии

 

 

 

 

 

 

 

 

 

 

 

 

 

Многометрическая (многомерная) оптимизация

 

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

Математическая постановка таких задач аналогична их постановке в одномерном случае: ищется наименьшее (наибольшее) значение целевой функции, заданной на некотором множестве G возможных значений ее аргументов.

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

 

1. Метод Хука – Дживса

 

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

Описание этой процедуры  представлено ниже:

А. Выбрать начальную базисную точку b₁ и шаг длиной h_j для каждой переменной x_j, j = 1, 2, ..., n. В приведенной ниже программе для каждой переменной используется шаг h, однако указанная выше модификация тоже может оказаться полезной.

Б. Вычислить f(x) в базисной точке b₁ с целью получения сведений о локальном поведении функции f(x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(x) в базисной точке b₁ находится следующим образом:

1. Вычисляется значение  функции f(b₁) в базисной точке b₁.

2. Каждая переменная  по очереди изменяется прибавлением  длины шага.

Таким образом, мы вычисляем  значение функции f(b₁ + h₁e₁), где e₁ - единичный вектор в направлении оси х₁. Если это приводит к уменьшению значения функции, то b₁ заменяется на b₁ + h₁e₁. В противном случае вычисляется значение функции f(b₁ – h₁e₁), и если ее значение уменьшилось, то b₁ заменяем на b₁-h₁e₁. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b₁ остается неизменной и рассматриваются изменения в направлении оси х₂, т.е. находится значение функции f(b₁ + h₂e₂) и т.д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b₂.

3. Если b₂ = b₁, т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b₁, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если  , то производится поиск по образцу.

В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

1. Разумно двигаться  из базисной точки b₂ в направлении b₂ - b₁, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца

(1.1)

В общем случае

(1.2)

2. Затем исследование  следует продолжать вокруг точки P₁ ( P_j ).

3. Если наименьшее значение на шаге В,2 меньше значения в базисной точке b₂ (в общем случае b_j+1 ), то получают новую базисную точку b₃ (b_j+2), после чего следует повторить шаг В,1. В противном случае не производить поиск по образцу из точки b₂ (b_j+1) а продолжить исследования в точке b₂ (b_j+1).

Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.

Ниже приведена блок-схема  данного метода.

 
Рис. 3.

 
Рис. 4.

 

2. Метод полного перебора (метод сеток)

 

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

 
Рис. 5.

Как мы уже говорили выше, данный метод используется для решения  одномерных задач. Иногда он применяется  также для решения двумерных, реже трехмерных задач. Однако для задач большей размерности он практически непригоден из-за слишком большого времени, необходимого для проведения расчетов. Действительно, предположим, что целевая функция зависит от пяти переменных, а область определения G является пятимерным кубом, каждую сторону которого при построении сетки мы делим на 40 частей. Тогда общее число узлов сетки будет равно . Пусть вычисление значения функции в одной точке требует 1000 арифметических операций. В таком случае общее число операций составит 10¹¹. Если в нашем распоряжении имеется ЭВМ с быстродействием 1 млн. операций в секунду, то для решения задачи с помощью данного метода потребуется 10₅ секунд, что превышает сутки непрерывной работы. Добавление еще одной независимой переменной увеличит это время в 40 раз. Проведенная оценка показывает, что для больших задач оптимизации метод сплошного перебора непригоден. Иногда сплошной перебор заменяют случайным поиском. В этом случае точки сетки просматриваются не подряд, а в случайном порядке. В результате поиск наименьшего значения целевой функции существенно ускоряется, но теряет свою надежность.

Список литературы:

1. Измаилов А.Ф., Солодов М.В. - Численные методы оптимизации
2. Ю.В. Губарь - Введение в математическое программирование