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

Требуется найти такие значения n переменных X=x₁,x₂,...x_n, при которых значение функции F(X) будет наибольшим или наименьшим из возможных. Переменные x₁,x₂,...x_n называются искомыми или управляемыми переменными. Функция F(X) называется целевой функцией. Целевая функция может быть максимизируемой или минимизируемой (максимизация прибыли, минимизация затрат).

Задача максимизации функции соответствует минимизации целевой функции .

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

G(X) = g_i(x₁,x₂,...x_n) < , = , > 0; i = 1,...m,где m - число ограничений.

Таким образом, задача оптимизации формулируется так:

при ограничениях G(X) < , = , > 0.

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

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

Простейшая задача: оптимизация функции одного переменного без ограничений - . Необходимым условием наличия минимума в точке х* является равенство нулю первой производной F по х в этой точке: . Данное уравнение определяет необходимое условие минимума, но не является достаточным условием. Точках* является точкой минимума, если вторая производная .

Минимум определяется как решение, для которого значение целевой функции строго меньше, чем ее значения для любого решения из окрестности точки минимума. Такой минимум называется локальным.

Целевая функция может иметь несколько минимумов. Наименьшее значение функции достигается в точке глобального минимума. Глобальный минимум есть минимум из всех локальных минимумов. На рис. 3.1 локальные минимумы функции достигаются в точках А и В, причем в точке В достигается глобальный минимум.

Рис. 3.1. Многоэкстремальная целевая функция

Есть два особых и важных вида функций: выпуклые и вогнутые (рис. 3.2). У выпуклых функций вторая производная всегда неотрицательная и, если выпуклая функция имеет локальный минимум, он же является и глобальным. У вогнутых функций вторая производная всегда отрицательная и, если такая функция имеет локальный максимум, он же является и глобальным.

Рис. 3.2. Выпуклая и вогнутая функции

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

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

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

3.3. Оптимизация без ограничений

3.3.1. Прямой одномерный поиск

Если уравнение не решается аналитически, например, функция F неизвестна, для его решения используются численные (прямые) методы.

С помощью прямых методов минимум целевой функции ищется непосредственно на некотором интервале a<x<b, в котором, как предполагается, лежит минимум, вычисляя значения функции в выбранных точках данного интервала. Иногда это единственно возможная стратегия поиска.

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

Однако можно поставить эксперимент и провести процесс при различных Т, найти его стоимость для всех рассмотренных значений Т и надеяться определить такое значение Т, при котором стоимость процесса минимальна.

Задачей численных математических методов является достижение поставленной цели наиболее эффективным способом – при минимальном числе экспериментов.

Поиск методом Фибоначчи[3].Предположим, что минимум нужно определить как можно точнее, то есть с наименьшим возможным интервалом неопределенности,но при этом можно выполнить только n вычислений функции. Как следует выбрать n точек, в которых вычисляется функция? Надо попытаться сделать так, чтобы значения функции, полученные в предыдущих экспериментах, определяли положение последующих точек – накапливая информацию о значениях функции использовать ее в дальнейшем поиске [5].

Предположим, что имеется интервал неопределенности (х₁,х₃) и известно значение функции f(x₂) внутри этого интервала (рис. 3.3). Если можно вычислить функцию всего один раз в точке х₄, то где следует поместить точку х₄, для того чтобы получить наименьший возможный интервал неопределенности?

Положим х₂-х₁=L и х₃-х₂=R, причем L>R и эти значения будут фиксированы, если известны х₁,х₂ и х₃.

Если х* находится в интервале (х₁,х₂), то:

если f(x₄)<f(x₂), то новым интервалом неопределенности будет (х₁,х₂) длиной x₂-x₁=L;

если f(x₄)>f(x₂), то новым интервалом неопределенности будет (х₄,х₃) длиной x₃-x₄=D.

Рис. 3.3. Поиск методом Фибоначчи. Длины интервалов

Поскольку неизвестно, какая из этих ситуаций будет иметь место, выберем х₄ таким образом, чтобы минимизировать наибольшую из длин x₃-x₄и x₂-x₁. Достигнуть этого можно, сделав длины Lи Dравными, то есть, поместив х₄ внутри интервала (x₁,x₂)симметрично относительно точки х₂, лежащей внутри интервала (x₁,x₃).

Любое другое положение точки х₄, может привести к тому, что полученный интервал Dбудет больше L. Помещая х₄ симметрично относительно х₂, мы ничем не рискуем в любом случае.

Если окажется, что можно выполнить еще одно вычисление функции, то следует применить описанную процедуру к интервалу (х₁,х₂), в котором уже есть значение функции, вычисленное в точке х₄, или к интервалу (х₄,х₁), в котором уже есть значение функции, вычисленное в точке х₂.

Следовательно, стратегия поиска ясна с самого начала. Нужно поместить следующую точку внутри интервала неопределенности симметрично относительно уже находящейся там точки.

Для организации поиска обычно используется числовой ряд Фибоначчи: F₀=1, F₁=1 и F_k=F_k-1+F_k-2 для k=2,3…,m.

Если начальный интервал (а, b) имеет длину L₀=b-a и требуется получить результат с точностью e(интервал неопределенности 2e), необходимо выполнить n+1 шаг, причем n определяется из условия: и это наилучший результат (число шагов минимально).

Задача поиска может быть поставлена в двух вариантах:

- при заданном числе шагов найти оптимальное решение с максимальной точностью;

- при заданной точности найти оптимальное решение за минимальное число шагов.

Пример:

1) начальный интервал (а, b) имеет длину L₁=b-а, за четыре шага найти решение с максимальной точностью (рис. 3.4).

2) начальный интервал (0,10) м, найти минимальное число шагов для получения решения с точностью e=±0,01 м. F₁₃=377, F₁₄=610. Число шагов равно 15.

Рис. 3.4. Поиск методом Фибоначчи. L₄ - окончательный интервал неопределенности

Поиск методом «золотого сечения».Не всегда удается определить, сколько раз придется вычислять функцию. В методе Фибоначчи это нужно для реализации первого шага, то есть определения положения начальной точки поиска.

Метод «золотого сечения»[4] практически столь же эффективен как метод Фибоначчи, однако при этом не требуется знать n – количество вычислений функции, определяемое заранее. Он лучше поддается алгоритмизации.

Функция последовательно вычисляется в точках, делящих интервал неопределенности в соотношении, определяемом как «золотое сечение»:

(рис. 3.5).

Это число называют также «золотым числом».

Рис. 3.5. «Золотое сечение»

Вывод формулы «золотого сечения»:

На первом шаге значения функции определяются в точках x₁ и x₂, делящих начальный интервал так, чтобы отношение целого к большей части равнялось отношению большей части к меньшей, что возможно только при равенстве этого отношения «золотому сечению».

Затем в зависимости от соотношения значения функции f(x₁) и f(x₂) интервал (a,x₁) или интервал (x₂,b) отбрасывается. После этого на каждом шаге значение функции определяется только в одной точке (на втором шаге в точке х₃), при этом «золотое сечение» всегда сохраняется (рис. 3.6).

Рис. 3.6. Поиск минимума функции методом золотого сечения

Случайный поиск–метод Монте-Карло

При случайном поиске значения функции определяются последовательно для x равномерно распределенных (в простейшем случае) на начальном интервале (a,b).

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

При a = 0, b = 10 м, p = 0.999, точности e= ± 0.005 м: . Это меньше, чем при простом сканировании зоны поиска с .

Вероятность успеха поиска равная 0,999 соответствует практической достоверности результата для технических приложений.

Однако, для одноэкстремальной задачи с аналогичными характеристиками, при использовании метода Фибоначчи – N=17, а при использовании метода Монте-Карло – N=6905.

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

С этим недостатком приходится считаться, однако, если задача действительно многоэкстремальна, найти им альтернативу крайне трудно.

3.3.2. Прямой многомерный поиск

Рассмотрим функцию двух переменных. Линии постоянного уровня показаны на рис. 3.7 (линией уровня называется кривая, соединяющая точки с равными значениями функции), а минимум лежит в точке х₁*,х₂*.

Рис. 3.7. Покоординатный спуск

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

Поиск по образцу, метод Хука-Дживса [5]

Поиск состоит из последовательности шагов вокруг базисной точки, за которой в случае успеха следует поиск по образцу (рис. 3.8).

Рис. 3.8. Поиск по образцу

Описание процедуры поиска:

A. Выбрать начальную точку b₁ и шаг длиной h.

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

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

2. Каждая переменная по очереди изменяется прибавлением шага h. Таким образом, вычисляется значение функции , где – единичный вектор в направлении оси . Если это приводит к уменьшению значения функции, то заменяется на . В противном случае вычисляется значение функции , и если ее значение уменьшилось, то заменяется значением . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка остается неизменной и рассматриваются изменения в направлении оси х_j+1, то есть находится значение функции и т.д. Когда будут рассмотрены все n переменных, мы будим иметь новую базисную точку.

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

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

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

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

2. Затем исследование следует продолжить вокруг данной точки.

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

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