Оптимизация в САПР

(2) заменить k на k+1 и вернуться  на шаг 1.

Метод квадратичной интерполяции – экстраполяции

 

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

Начальный этап

1. Выбрать произвольную точку x¹ÎRⁿ
2. Задаться величиной шага h=0.001
3. Определить погрешность
4. Положить счётчик числа итераций равным 1, а также b=x¹

Основной этап

Шаг 1. Вычислить f_i в 3-х точках: a, b и с – центральной (b) и двух соседних: a=b-h, c=b+h. Затем, по формуле

  (1)

или

     (2)

найти аппроксимирующий минимум d

Шаг 2. Проверить критерий близости 2-х точек b и d

 и

Если оба условия  выполняются – фиксируем аппроксимирующий минимум

и останавливаемся. Если оба критерия не выполняются, полагаем b=d и возвращаемся на шаг 1.

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

Метод Пауэлла является одним из самых популярных методов. Эффективен как и рассмотренный ранее алгоритм квадратичной интерполяции – экстраполяции, если начальная точка x¹Îd(x*).

Начальный этап

1. Выбрать ε₁, ε₂, h.
2. Взять 3 точки a, b, c на равных на равных интервалах. Предполагается, что сработал метод Свенна и получен интервал [a, b].

a=a;

c=b;

b=(a+c)/2;

Основной этап

1. Найти аппроксимирующий минимум на 1-й итерации по формуле:

на последующих итерациях  по формуле:

2. Проверить критерии близости двух точек:

;

Если он выполняется, принять  и остановиться.

Если не выполняется, то из 2-х точек b и d выбрать «лучшую» - в которой наименьшее значение функции, обозначить её как b, а 2 соседние с ней – a и c. Далее рассмотреть 4 ситуации аналогично ЗС-2.

3. Положить k=k+1 и вернуться на шаг 1.

 

Метод Давидона

Начальный этап

1. Выбрать ε, x⁰, p, α₁
2. Предполагается, что сработал метод Свенна и получен интервал [a, b].

Основной этап

1. Найти аппроксимирующий минимум, т.е. точку d по формулам:

2. Проверить КОП: если y`<sub>r</sub>≤ ε, то остановиться, х=a+α<sub>r</sub>p. Иначе: сократить ТИЛ: если y`_r <0, то [r,b], если y`_r >0, то [a,r].

Положить k=k+1 и вернуться на шаг 1. 

Методы многомерной  минимизации

 

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

x – вектор от которого  зависит функция

x0 – стартовая точка 

p – направление 

L – смещение по  направлению

 

Метод Коши

 

Метод Коши относится  к группе  методов градиентного спуска.  Градиентные методы – это методы, где на каждом шаге выбирается антиградиентное направление спуска.

Начальный этап

Выбрать x1, e, k.

Основной этап

Шаг 1

Шаг 2

(1) Найти L как результат  минимизации функции по направлению  p.

(2)

Шаг 3

(1) Вычислить новое значение градиента

(2) Проверить КОП: если  , то , иначе на Шаг 1.

 

Метод Циклического покоординатного  спуска

 

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

Начальный этап

Выбрать x1, e, k=1, l=1.

Основной этап

Шаг 1

(1) В качестве направления  p выбрать   , где ненулевая позиция имеет индекс l.

(2) Найти L как результат  минимизации функции по направлению  p.

(3)

(4) Если l<n то Шаг 2, иначе повторить Шаг 1 с l = l+1.

Шаг 2

(1) Вычислить 

(2) Проверить КОП: если  , то , иначе , l=1 и на Шаг 1.

Метод параллельных касательных

 

Начальный этап:

Выбрать х1, ε = 10^-4 – 10^-8   установить k = 1;

Основной этап:

Шаг 1.

Из точки x¹ выполнить антиградиентный в точку x²= x¹+α₁р¹, где p¹=-Ñу¹.

Шаг 2.

Последовательно выполнить  две операции:

1. Антиградиентный спуск в точку x³.
2. Вычислить ускоряющее направление d=x³-x¹ и, не останавливаясь совершить ускоряющий шаг в точку x⁴=x³+α₃d.

Шаг 3.

Проверить КОП: - остановиться x*=x⁴.

Иначе:

1. Обозначить x² как новую начальную x¹=x², а точку x⁴ как новую точку ускорения x²=x⁴.

Перейти к шагу 2.

 

Метод Гаусса-Зейделя

 

Начальный этап

Выбрать х1, ε = 10^-4 – 10^-8   установить k = 1;

Основной этап:

Шаг 1.

Выполнить серию одномерных поисков вдоль координатных орт

 

Шаг 2.

Вычислить ускоряющее направление  и проверить КОП: , если выполняется, минимум найден: x*=xⁿ⁺¹.

Иначе:

1. Выполнить ускоряющий шаг в новую точку хⁿ⁺²
2. Обозначить последнюю точку как начальную и вернуться на  шаг 1.

Метод комплексов Бокса

 

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

При использовании метода принимаются  следующие предположения:

1. Задача поиска экстремума функционала (1) решается при наличии ограничений 1-го и 2-го рода.
2. Значения целевой функции и функций ограничений могут быть вычислены в любой точке допустимой области изменения независимых переменных.
3. Допустимая область выпукла.
4. Значения целевой функции и функций ограничений вычисляются без ошибок.

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

В отличие от симплексного метода, в комплексе-методе используется случайный набор N точек – Комплекс, а число точек Комплекса определяется по правилу:

   

где n – число независимых переменных.

Вычислительная последовательность (алгоритм) комплекс-метода включает в  себя следующие этапы.

1) Формируется исходный комплекс. Координаты вершин исходного Комплекса х_ij вычисляются последовательно с помощью равномерно распределенных на интервале (0;1) псевдослучайных чисел r_ij:

x_ij=g_i+r_ij(h_i - g_i),   i=1, 2,…,n,   j=1, 2,   ,N.

В каждой вершине с  номером j проверяется выполнение ограничений 2-го рода (ограничения 1-го рода выполняются автоматически).

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

Пусть число точек, удовлетворяющих  ограничениям 2-го рода Р (Р≥1), тогда (N–P) – число точек, в которых ограничения нарушены.

Далее для каждой из еще незафиксированных  вершин выполняется операция по ее смещению к центру Р вершин Комплекса, при этом новые координаты точки х*_ij вычисляются по формуле

  ,    i=1, 2,…, n,    j=P+1, P+2,…,N.

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

2) Для всех N вершин Комплекса вычисляются значения целевой функции F_i:

F_j=F(x_j),  

,   j=1, 2,…,N.

3) Выбираются наилучшее R и наихудшее S (с точки зрения экстремума) значения из массива F_i:

R=F_G;  S=F_D.

где G – номер самой «хорошей»; а D – самой «плохой» вершины.

4) Определяются координаты C_i центра Комплекса с отброшенной «наихудшей» вершиной:

,    i=1, 2,…,n.

5) Проверяется условие окончания поиска. Для этого вычисляется величина В:

.

Если В<ε (ε – заданная точность вычисления), т.е. среднее расстояние от центра Комплекса до худшей (D) и лучшей (G) вершин меньше ε, то поиск заканчивают, считая экстремум найденным.

В противном случае вычисления продолжаются:

6) взамен наихудшей вычисляются  координаты новой точки Комплекса:

x_i0=2,3C_i – 1,3x_iD,   i=1, 2,…,n.

В этой новой точке  проверяется выполнение ограничений 1-го рода. В случае, если ограничения нарушаются, x_i0 принимает значения g_i+ε или h_i–ε в зависимости от того, в какую сторону i-е ограничение нарушено;

7) для новой точки проверяется  выполнение ограничение 2-го рода. Если хотя бы одно из ограничений нарушено, то новую точку смещают к центру Комплекса на половину расстояния:

.

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

8) В новой точке  вычисляют значения целевой функции F₀:

     .

9) Если F₀ оказывается хуже S (значение целевой функции в наихудшей точке D предыдущего комплекса), т.е. новая точка находится дальше от экстремума, чем вершина с номером D, то новая вершина находится смещением x_i0 на половину расстояния к лучшей из вершин комплекса G:

.

Затем вновь вычисляют  значение целевой функции F₀ и сравнивают его с S. Смещением к лучшей вершине по формуле (15) продолжают до тех пор, пока F₀ не станет лучше S.

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

10) Если вычисленное  в новой точке х₀ значение F₀ лучше S, то в Комплексе на месте наихудшей точки х_D фиксируется точка х₀ и значение S заменяется на F₀.

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

Метод Хука-Дживса (конфигураций)

 

Эффективность прямого  поиска точки минимума можно повысить, если на каждом k-м шаге поиска соответствующим образом выбирать направление спуска. Для этого на каждом k-м шаге выделяют предварительный этап исследующего поиска. Целью этого этапа является выбор направления спуска путем исследования поведения целевой функции f(x) в окрестности точки xk-1, найденной на предыдущем шаге. В результате выполнения этапа исследующего поиска находится точка xk, для которой f(x^k) < f(x^k-1). Направление спуска, завершающего k-w. шаг поиска, определяется вектором x^k - x^k-1. Такая стратегия поиска, получила название метода Хука - Дживса.

 

Исследующий поиск 1

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

 

Ускоряющий поиск

Выполняем единичный  шаг вдоль направления  , . Затем производим исследующий поиск в окрестности x³, в надежде найти точку лучшую чем x².

 

Начальный этап

β = 10, ε = 10-4 – 10-8 , k = 1, х¹, h₁= … =h_n=0.1;

Основной этап

Шаг 1.