Метод равномерного перебора

Пусть задана целевая функция y = f (x) для которой необходимо отыскать глобальный минимум на отрезке [ a, b ] (рис. 3.6).

 

 

Рис. 3.6. Пример поиска экстремума функции
методом равномерного перебора

 

В соответствии с данным методом алгоритм поиска х _опт заключается в следующем. Фиксируют величину шага h > 0. Вычисляют значения целевой функции f (x ₁) и f (x ₂) соответственно в точках х ₁ = а и х ₂ = х ₁ + h. Полученные значения сравнивают. Запоминают меньшее из этих двух значений. Далее выбирается точка х ₃ = х ₂ + h и в ней вычисляется значения целевой функции f (x ₃). Сравнивается оставшееся на предыдущем шаге значение и значение f (x ₃). Наименьшее из них опять запоминают. Так поступают до тех пор, пока очередное значение х не превысит b. Последнее оставшееся значение является приближенным значением глобального минимума.

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

Метод золотого сечения

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

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

В соответствии с данным методом в каждый текущий момент времени рассматривается всегда две точки, например, в начальный момент точки х ₁ и х ₂ так, чтобы а < х ₁ < х ₂ < b. При этом возможен один из двух случаев (рис. 3.7). Согласно свойству унимодальной функции в первом случае искомая точка х _min не может находиться на отрезке [ x ₂, b ], во втором случае на отрезке [ a, x ₁] (показаны штриховкой). Значит, область поиска сужается, и следующую точку х ₃ необходимо брать на одном из укороченных отрезков: [ a, x ₂] – случай 1 или [ x ₁, b ] – случай 2.

Далее следует определиться, где на исходном отрезке [ a, b ] необходимо выбирать точки х ₁ и х ₂. Первоначально о положении точки х _min ничего не известно, поэтому любой из приведенных выше случаев возможен с одинаковой вероятностью. Это означает, что лишним может оказаться любой из отрезков: [ x ₂, b ] или [ a, x ₁]. Отсюда следует, что точки х ₁ и х ₂ необходимо выбирать симметрично относительно середины отрезка [ a, b ].

Рис. 3.7. Варианты выбора области поиска минимума целевой функции

 

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

Таким образом, с одной стороны, точки следует брать рядом с серединой отрезка, а, с другой стороны, слишком близко друг от друга их брать нельзя. То есть необходимо найти некую «золотую середину».

Рассмотрим для простоты вместо отрезка [ a, b ] отрезок единичной длины [0, 1] (рис. 3.8).

 

Рис. 3.8.

 

На рис. 3.8 ÷ АВ ê=÷ CD ê= х, ÷ А C ê=÷ В D ê= 1 – х, ÷ ВС ê= 1 – 2 х.

Для того, чтобы точка B была «выгодной» как на данном, так и на следующем этапе (шаге), она должна делить отрезок AD в таком же отношении, как и AC: AB / AD = BC / AC. При этом в силу симметрии аналогичным свойством будет обладать и точка C: CD / AD = BC / BD. В обозначениях координаты x эти пропорции принимают вид: x /1 = (1 – 2 x)/(1 – x). Решим эту пропорцию:

х (1 – х) = 1 – 2 х Þ х – х ² = 1 – 2 х Þ х – х ² – 1 + 2 х = 0 Þ – х ² + 3 х – 1 = 0 Þ х ² – 3 х + 1 = 0; Д = b ² – 4 ac = 9 – 4 = 5.

Корни этого уравнения равны:

.

Корень x ₂ > 1 не приемлем, т. е. уравнение имеет один корень.

О точке, которая расположена на расстоянии  длины от одного из концов отрезка, говорят, что она осуществляет «золотое сечение» данного отрезка. Очевидно, что каждый отрезок имеет две такие точки, расположенные симметрично относительно его середины.

Таким образом, алгоритм метода «золотого сечения» заключается в следующем (рис. 3.9). На исходном отрезке [ a, b ] выбираются две точки x ₁ и x _2, так, чтобы выполнялось приведенное выше соотношение «золотого сечения» этого отрезка. Вычисляются значения целевой функции в этих точках f (x ₁) и f (x ₂). Они сравниваются, и из дальнейшего рассмотрения исключается отрезок, прилегающий к точке, дающей большее значение целевой   функции  (здесь  отрезок  [ x ₂, b ]).   Т. е.  исходный  отрезок  [ a, b ] «стягивается» до отрезка [ a, b ₁].

 

Рис. 3.9. Иллюстрация алгоритма метода «золотого сечения»

 

Для этого нового отрезка находится его середина, и по отношению к ней симметрично оставшейся точке x ₁ ставится точка x ₃. Для нее рассчитывается значение целевой функции f (x ₃) и сравнивается с f (x ₁). Из дальнейшего рассмотрения опять исключается отрезок, прилегающий к точке с большим значением целевой функции, здесь это отрезок [ a, x ₃]. Текущий отрезок «стягивается» до нового отрезка, здесь это [ a ₁, b ₁] и т. д.

Метод «золотого сечения» прост, эффективен и широко применяется в практической оптимизации.

Метод линеаризации

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

Пример № 1. Рассмотрим суть данного метода на примере № 2 многопараметрической однокритериальной задачи оптимизации, который решался ранее. Напомним формулировку задачи: найти х _1опт и х _2опт. Целевая функция у = х ₂ / х ₁ ® max, ограничения:

1 £ х ₁ £ 8,      2 £ х ₂ £ 12,      х ₁ × х ₂ ³ 10.

В первую очередь приводим данную задачу к задаче линейного программирования. Для этого проводим логарифмирование ограничений и целевой функции:

lg 1 £ lg х ₁ £ lg 8;    lg 2 £ lg х ₂ £ lg 12;  lg х ₁ + lg х ₂ ³ lg 10.

После вычислений получим:

0 £ lg х ₁ £ 0,903;     0,301 £ lg х ₂ £ 1,079;        lg х ₁ + lg х ₂ ³ 1.                                           

После логарифмирования целевой функции:

lg y = lg х ₂ – lg х ® max.

Далее задача решается с применением симплекс-метода или графо-аналитически.

Пример № 2. Необходимо определить область рациональных режимов резания (например, токарной обработки) исходя из условия максимума производительности.

Целевой функцией в данном случае является величина Q производительности обработки:

Q = B × n × S ® max,

где B – постоянный множитель; n – число оборотов шпинделя; S – подача.

При решении задачи оптимизации абсолютное значение целевой функции не играет никакой роли. Таким образом, от исходной формулировки целевой функции можно перейти к формулировке упрощённой:

Q = n × S ® max.

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

ln Q = ln n + ln S. Тогда Z = ln Q;

x ₁ = ln n; x ₂ = ln S; Z = x ₁ + x ₂ ® max.

Ограничения, накладываемые на область допустимых решений задачи S _min, S _max, n _min, n _max, определяются паспортом станка, заданными параметрами шероховатости обработанной поверхности, стойкостью инструмента и др. Пример графо-аналитического решения задачи приведен на рис. 3.10.

 

 

Рис. 3.10. Область допустимых значений режимов резания