где

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

Пусть

где

y - переменная, зависящая от независимой переменной x;

Установим уравнение регрессии для отражения роста в высоту насаждений с относительно быстрым ростом в молодом возрасте для II бонитета бонитетной шкалы К.Е.Никитина с использованием широко известной в лесном деле для описания процессов роста функции Бакмана

В табл. 3.1 приведены результаты измерения высоты в зависимости от возраста насаждения.

Таблица 3.1

Результаты измерений

где

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

• Методы прямого поиска, основанные на вычислении только значений целевой функции;
• Градиентные методы, в которых используются точные значения первых производных W(x);
• Методы второго порядка, в которых наряду с первыми производными используются также вторые производные функции W(x).

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

Рассматриваемые далее методы применимы также и к задачам максимизации, в которых целевую функцию следует умножить на -1.

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

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

1. "Накрытие" точки минимума. Если вершина, которой соответствует наибольшее значение целевой функции, построена на предыдущей итерации, то вместо нее берется вершина, которой соответствует следующее по величине значение целевой функции.
1. Циклическое движение. Если некоторая вершина симплекса не исключается на протяжении более чем М итераций, то необходимо с помощью коэффициента редукции уменьшить размеры симплекса. Новый симплекс следует строить выбрав в качестве базовой точку, которой соответствует минимальное значение целевой функции. В качестве расчетной формулы для расчета числа итераций (с округлением до целого) использовать следующую эмпирическую зависимость: M = 1,65N + 0,05N², где N - размерность задачи.
2. Критерий окончания поиска. Поиск завершается, когда или размеры симплекса, или разности между значениями функций в вершинах становятся достаточно малыми в контексте конкретной прикладной задачи. В этой связи необходимо задать величину параметра окончания поиска.

Реализация рассматриваемого алгоритма основана на вычислениях двух типов:

где

• расчете координат отраженной точки.

Пусть x^j - точка, подлежащая отражению. Центр тяжести остальных N точек расположен в точке

Все точки прямой, проходящей через x^j и x_c, задаются формулой

x^j_новая = 2x_c - x^j_{предыдущая}.

Итерации продолжаются до тех пор, пока не потребуется применение правил 1, 2, 3.

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

• возникает проблема масштабирования, поскольку все координаты вершин симплекса зависят от одного масштабного множителя. Чтобы избежать такого рода проблем в практических задачах, следует промасштабировать все переменные с тем, чтобы их значения были сравнимы по величине;
• алгоритм работает достаточно медленно, т.к. полученная на предыдущих итерациях информация не используется для ускорения поиска;
• не существует простого способа расширения симплекса. Требуется перерасчет значений целевой функции во всех точках образца.

Процедура поиска Хука-Дживса представляет собой комбинацию "исследующего поиска" и "ускоряющего поиска по образцу".

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

Поиск по образцу заключается в реализации единственного шага из полученной базовой точки x^k вдоль прямой, соединяющей эту точку с предыдущей базовой точкой x^k-1. Новая точка образца x^k+1 определяется в соответствии с формулой

x^k+1 = x^k + (x^k - x^k-1). (3.12)

Как только движение по образцу не приводит к уменьшению целевой функции, точка x^k+1 фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск. Если в результате получается точка с меньшим значением целевой функции, чем в точке x^k, то она рассматривается как новая базовая точка x^k+1.

С другой стороны, если исследующий поиск неудачен, то необходимо вернуться в точку x^k и провести исследующий поиск с целью выявления нового направления минимизации. В конечном счете возникает ситуация, когда такой поиск не приводит к успеху. В этом случае требуется уменьшить величину шага путем введения некоторого множителя и продолжить исследующий поиск. Поиск завершается, когда величина шага становится достаточно малой.

Рис. 3.7. Поиск по методу Хука-Дживса

Шаг 2. Провести исследующий поиск.

Шаг 3. Был ли исследующий поиск удачным: да - к шагу 5; нет - продолжить.

Шаг 5. Провести поиск по образцу: x_p^k+1 = x^k + (x^k - x^k-1).

Шаг 6. Провести исследующий поиск, используя x_p^k+1 в качестве базовой точки. Пусть x^k+1 - полученная в результате точка.

Шаг 7. W(x^k+1)< W(x^k)?

• Если "да" - положить x^k-1= x^k, x^k= x^k+1 и перейти к шагу 5.
• Если "нет" - перейти к шагу 4.

Преимущества метода:

• несложная стратегия поиска;
• невысокий уровень требований к ЭВМ;
• широкое применение в инженерных приложениях.

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

Основная идея метода заключается в том, что если построена система сопряженных направлений, то точку оптимума квадратичной функции W(x) можно найти в результате реализации в точности N² (N - размерность задачи) одномерных поисков. Система сопряженных направлений можно определить на основе следующего элементарного свойства квадратичных функций.

Рис.3.8. Двухмерный поиск по методу сопряженных направлений Пауэлла

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

Сначала поиск осуществляется вдоль трех координатных направлений e¹, e² и e³. Затем эти направления заменяются вновь построенными сопряженными направлениями. Серия одномерных поисков из x^o проводится в направлении e³, затем e¹, e² и снова e³. В результате построены сопряженные направления e³ и x⁴-x¹. Направление e¹ заменяется новым направлением поиска 4. Следующая серия поисков проводится в направлении 4, затем e², e³ и снова 4. Согласно свойству параллельного подпространства новое направление x⁸-x⁵, 5, сопряжено не только с 4, но и с e³. Следовательно, e³, x⁴-x⁵ и x⁸-x⁵ образуют систему взаимно сопряженных направлений. Поэтому, если провести дополнительный поиск из точки x⁸ в направлении x⁸-x⁵, то будет найдена точка x⁹, в которой должен достигаться оптимум квадратичной функции трех переменных W(x), поскольку поиск последовательно осуществлялся в трех взаимно сопряженных направлениях.

Рис. 3.9. Трехмерный поиск по методу сопряженных направлений Пауэлла

Шаг 1. Задать начальную точку x^o и систему N линейно независимых направлений sⁱ ; целесообразно принять sⁱ = eⁱ, i=1,2,...,N.

Шаг 2. Минимизировать W(x) при последовательном движении по N+1 направлениям; при этом полученная ранее точка минимума берется в качестве исходной, а направление s^N используется как при первом, так и при последнем поиске.

Шаг 3. Определить новое сопряженное направление с помощью обобщенного свойства параллельного подпространства.

Шаг 4. Заменить s¹ на s² и так далее. Заменить s^N сопряженным направлением. Перейти к шагу 2.

Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Если целевая функция квадратична и обладает минимумом, то точка минимума находится в результате реализации N циклов, включающих шаги 2-4. Здесь N - число переменных. Если же функция W(x) не является квадратичной, то требуется более чем N циклов.

Все методы основаны на итерационной процедуре, реализуемой в соответствии с формулой

где

x^k - текущее приближение к решению x^*;

s(x^k) - направление поиска в N - мерном пространстве управляемых переменных x_i, i = 1, 2,..., N.

В основе метода лежит следующая итерационная модификация формулы (3.13):

где

Недостатки:

Данный метод иногда называют методом Коши.

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

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

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

где

На рис. 3.8 изображена система подачи газа по трубам, в которой компрессорные станции расположены на расстоянии L километров друг от друга. Суммарные затраты на эксплуатацию газопровода в течении года определяются функцией:

где

Предположим, что расход газа в единицу времени можно описать функцией:

где - коэффициент трения.