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

Министерство образования  Российской Федерации

Санкт-Петербургский  Государственный  Электротехнический Университет “ЛЭТИ”  имени В.И. Ульянова (Ленина)

197376, Санкт-Петербург,  ул. Проф. Попова, 5

 

Факультет компьютерных технологий и информатики

Кафедра вычислительной техники

                                                                «ЗАЧТЕНО»

                                                                  _________Г.Д. Дмитревич

                                                                  “__”___________2005 г.

ПОяснительная записка  к курсовому проекту

По  курсу: “Оптимизация в САПР”

Студент группы 2311          _________ С.А. Мальгин

Санкт-Петербург 2005

 

 

Оглавление

 

 

Задание на проектирование

 

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

1. Программа должна позволять:

• проводить оптимизации целевых функций с числом переменных n≤5.

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

2. Программа должна быть дружественной пользователю:

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

3. Программа должна быть хорошо структурирована:

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

 

Введение

 

Одним из важнейших направлений  оптимизации является задача поиска оптимального решения различных функций многих переменных. Поэтому целью курсового проекта является углубленное изучение методов оптимизации в САПР. Наибольший акцент делается на методы безусловной оптимизации. Курсовой проект предполагает разработку программы автоматизированного поиска оптимального решения с использованием процедур, написанных и отлаженных самостоятельно, а также процедур, разработанных ранее при выполнении цикла лабораторных работ в курсах «Методы оптимизации» и «Теория принятия решений». Эти курсы включают в себя следующие основные направления:

1. Методы одномерного поиска минимума унимодальных функций.
2. Методы полиномиальной интерполяции для поиска минимума целевых функций.
3. Линейный поиск по направлению.
4. Градиентные методы.
5. Методы безусловной оптимизации первого порядка.
6. Методы безусловной оптимизации нулевого порядка.

Для реализации курсового  проекта наиболее подходящим и рекомендуемым является алгоритмический язык Microsoft Visual С++ 6.0, т.к. он обладает полным набором средств для создания и управления различными прикладными задачами, в том числе, и задачей поиска минимума функции. При разработке рекомендуется использовались технологии объектно-ориентированного программирования. 

МетодЫ решения оптимизационной  задачи

 

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

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

 

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

Метод Свенна

 

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

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

1. задать произвольную начальную точку x₀ÎRⁿ
2. выбрать начальный шаг h=Dx=0,01

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

Шаг 1. Установить направление  убывания функции. Для этого взять x₂=x₁+h.  Если f(x₁) <f(x₂), то поменять направление движения: h₁=-h₁ и взять x₂=x₁+h₁.

Шаг 2. Вычислить f_k в точках x_k+1=x_k+h_k, где k=2,3,4,…,m-1; h_k=2h_k-1 – движение с удвоением шага, до тех пор, пока не придём в точку x_m такую, что f(x_m)<f(x_m-1).

Шаг 3. Установить начальный  интервал локализации минимума

a₁=x_m-2

b₁=x_m

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

 

Метод золотого сечения – это процедура одномерного поиска минимума на интервале [a₁,b₁] или [0,1]. На каждом шаге пробная точка l_k или m_k внутри текущего интервала локализации [a_k,b_k] делит его в отношении, постоянном для всех интервалов - золотое сечение. Можно показать, что , откуда , следовательно , значит . Одним из корней этого уравнения является t₁=0,618 – первое золотое число. Отметим, что t₁²=0,618²=0,382 – второе золотое число. Следует отметить, что в методе золотого сечения имеет место правило симметрии (эквидистантности) точек относительно концов интервала, а также правило одного вычисления, т.е. на каждой итерации требуется одно и только одно новое вычисление (кроме первой итерации), т.к. точки на соседних итерациях совпадают.

 

Алгоритм ЗС-1

 

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

1. Выбрать погрешность расчёта e=10^-3¸10^-7. Получить начальный интервал методом Свенна.
2. Вычислить стартовые точки l₁=a₁+0,382L₁, m₁=a₁+0,618L₁ (следует отметить, что золотые числа следует вычислять точно)
3. Принять k=1 – счётчик числа итераций

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

Шаг 1.Сократить ТИЛ рассмотрением 2-х ситуаций:

1. Если f(l)<f(m),то

a_k+1=a_k

b_k+1=m_k

m_k+1=l_k

l_k=a_k+1+0,382L_k+1

      иначе

a_k+1=l_k

b_k+1=b_k

l_k+1=m_k

m_k=a_k+1+0,618L_k+1

2. Положить k=k+1, L_k+1=|b_k+1-a_k+1|

Шаг 2. Проверить критерий окончания поиска: если |a_k+1-b_k+1|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как . Иначе вернуться на шаг 1.

 

Алгоритм ЗС-2

 

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

4. Выбрать погрешность расчёта e=10^-3¸10^-7. Получить начальный интервал методом Свенна.
5. Вычислить стартовые точки l₁=a₁+0,382L₁, m₁=a₁+0,618L₁ (следует отметить, что золотые числа следует вычислять точно)
6. Принять k=1 – счётчик числа итераций

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

Шаг 1. Взять очередную  пробную точку x₂=a_k+b_k-x₁, симметричную исходной и сократить ТИЛ рассмотрением 4-х возможных ситуаций:

1. Если (x₁<x₂) и (f(x₁)<f(x₂)) то b=x₂;
2. Если (x₁<x₂) и (f(x₁)>=f(x₂)) то a=x₁;
3. Если (x₁>x₂) и (f(x₁)<f(x₂)) a=x₂;
4. Если (x₁>x₂) и (f(x₁)>=f(x₂)) b=x₁;

Увеличить счётчик числа  итераций k=k+1

Шаг 2. Проверить критерий окончания поиска: если |a_k+1-b_k+1|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как . Иначе вернуться на шаг 1.

 

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

 

Метод Фибоначчи является процедурой линейного поиска минимума унимодальной функции f(x) на замкнутом  интервале [a, b], отличающейся от процедуры  золотого сечения тем, что очередная  пробная точка делит интервал локализации в отношении двух последовательных чисел Фибоначчи. Последовательность чисел Фибоначчи задаётся условиями F₀ = F₁ = 1, F_k+1 = F_k + F_k-1, k = 1,2,... Начальными членами последовательности будут 1, 1, 2, 3, 5, 8, 13,... Стратегия поиска Фибоначчи требует заранее указать n - число вычислений минимизируемой функции и e - константу различимости двух значений f(x). Рассмотрим один из возможных вариантов метода.

 

Алгоритм Фибоначчи-1

 

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

(1) Задать константу e, начальный интервал [a₁, b₁], длину конечного интервала L_n и определить число n так, чтобы выполнялось условие F_n > (b₁ - a₁)/L_n.

(2) Взять две пробные точки l₁ = a₁ + (F_n-2/F_n)(b₁ - a₁) и m₁ = a₁ + (F_n-1/F_n)(b₁-a₁). Положить k = 1.

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

Шаг 1. Сократить текущий интервал локализации:

(1) Если f(l_k) < f(m_k), то положить a_k+1 = a_k, b_k+1 = m_k,m_k+1 =l_k и вычислить новую точку l_k+1 = a_k+1 + (F_n-k-2/F_n-k)L_k+1, где L_k+1 = b_k+1 - a_k+1; перейти на шаг 2.

(2) Если f(l_k)>> f(m_k),то положить a_k+1 =l_k, b_k+1 = b_k, l_k+1 = m_k и вычислить m_k+1 = a_k+1 + (F_n-k-1/F_n-k) L_k+1.

Шаг 2. Проверить критерий окончания поиска:

(1) Заменить k на k+1. (2) Если k = n - 1, перейти на шаг 3, иначе  - на шаг 1.

Шаг 3. Найти аппроксимирующий минимум х^(*):

(1) Положить m_k = l_k + e.

(2) Если f(l_k) > f(m_k), то x^(*) = (l_k + b_k)/2. В противном случае - x^(*) = (a_k + m_k)/2.

 

Алгоритм Фибоначчи-2

 

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

(1) Задать константу e, начальный интервал [a₁, b₁], длину конечного интервала L_n и определить число n так, чтобы выполнялось условие F_n > (b₁ - a₁)/L_n.

(2) Выбрать одну пробную  точку . Положить

k = 1.

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

Шаг 1. Проверить критерий окончания поиска: если k=n, то остановиться и положить x*=x₂.

Шаг 2. Сократить текущий  интервал локализации рассмотрением 4-х ситуаций, аналогично методу золотого сечения-2.

 

Метод средней точки (метод  Больцано)

 

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

Начальный этап. Для запуска метода необходимо:

(1) задать [a₁,b₁]- начальный интервал локализации минимума, на границах которого знаки производных различны, т.е. f'¢(a₁)f'¢(b₁)<0; e - малое положительное число;

(2) положить к=1 и перейти  к основному этапу.

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

Шаг 1. Взять пробную  точку х_k в центре текущего интервала и проверить критерий окончания поиска: (1) x_k = (a_k + b_k)/2; (2) если ½f'¢(x_k)½ ≤ e и L_k= ½b_k - a_k½≤ e, то остановиться (х_k = х* -аппроксимирующий минимум).

Шаг 2. Сократить текущий  интервал:

(1) Если f ¢(x_k) > 0, то положить a_k+1 = a_k и b_k+1 =x_k, в противном случае - a_k+1 =x_k, b_k+1 =b_k;

(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.