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

Выполнить ИП1 и отыскать т. х² для которой .

Шаг 2.

Если ИП1 удачен т.е. найдена  х², то перейти на шаг 3, иначе, но в то же время h<ε необходимо уменьшить шаг в β раз и вернуться на шаг 1. При h<ε остановиться х* = х¹.

Шаг 3.

Выполнить УП в пробную  точку 

Обозначить 

В окрестности х3 попытаться ИП2 найти т. х⁴ «лучшую» чем х¹.

Шаг 4.

Если ИП2 удачен, то положить и вернуться на шаг 1.

Иначе: уменьшить шаг  в β раз и вернуться на шаг 1.

 

Метод Ньютона

 

Если f(x) является дважды дифференцируемой в Rⁿ, то эффективность процесса поиска точки х* ее минимума можно повысить, используя информацию не только о градиенте этой функции, но и о ее матрице Гecce H(x). Алгоритмы такого поиска обычно относят к методу Ньютона. В простейшем варианте алгоритма на каждой k-й итерации целевая функция аппроксимируется в окрестности точки xk-1 (на первой итерации в окрестности начальной точки х0) квадратичной функцией и затем определяется точка xk минимума функции . На следующей, (k+1)-й итерации строится новая квадратичная аппроксимация уже в окрестности точки xk.

 

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

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

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

Шаг 1

(1) Строится Ньютоновское  направление: - градиент в заданной точке, H – матрица Гессе

(2) Найти  как результат решения системы уравнений

(3) 

(4)

Шаг 3

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

Метод Зангвилла

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

Выбрать константу остановки  и начальную точку . Положить , , и перейти к основному этапу.

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

Шаг 1. Взять в качестве оптимальное решение задачи минимизации при и положить . Если , то перейти к шагу 4; в противном случае перейти к шагу 2.

Шаг 2. Положить и взять в качестве оптимальное решение задачи минимизации при . Положить , и перейти к шагу 3.

Шаг 3. Если , то остановиться; -- оптимальное решение. В противном случае взять в качестве оптимальное решение задачи минимизации при . Положить . Если , то заменить на и повторить шаг 3. В противном случае положить , заменить на и перейти к шагу 1.

Шаг 4. Положить , , заменить на , положить и перейти к шагу 1.

Флетчера-Ривса

Метод сопряжённых направлений основан на свойствах векторов сопряженных относительно некоторой квадратной матрицы. Различие в способах построения системы сопряженных векторов, определяющих сопряжённые направления спуска, порождает несколько алгоритмов этого метода. В качестве матрицы сопряжений берётся матрица Гессе.  Особенность алгоритмов метода сопряженных направлений состоит в том, что систему сопряженных векторов строят последовательно в процессе выполнения итераций, причем найденный на очередной, k-й итерации вектор pk определяет на этой  итерации  направление спуска. Для не квадратичных функций получаемые направления, в конце концов, перестают быть взаимносопряженными поэтому, как и в ДФП через n шагов вектор направления делают равным антиградиенту.

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

Выбрать x¹, e, k=1.

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

Шаг 1.

Построить вектор pk:

Шаг 2.

Найти новую точку  как результат одномерного поиска полученного направления .

Шаг 3.

Проверить КОП: .

 

Расчетное соотношение Флетчера-Ривса

 

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

 

Метод достаточно прост  в реализации и обладает квадратичной сходимостью вблизи минимума. Стратегия метода базируется на свойстве квадратичных функций параллельного подпространства: если x¹ минимум квадратичной функции по вектору p, а x² минимум этой же функции по вектору параллельному предыдущему, то .

 

Первый вариант алгоритма метода Пауэлла

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

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

(2) Положить

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

Шаг 1.

(1) Выполнить n переходов  по векторам базиса  :

(2) Определить новое  направление и спуститься вдоль  него:

Шаг 2.

Проверить КОП: если ,или k = n (для квадратичных функций) то прекратить поиск, иначе Шаг 3

Шаг 3.

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

Таким образом изменение системы поиска выглядит так:

 

 

Второй вариант алгоритма метода Пауэлла

Отличается от первого  варианта тем, что изначально строится поисковая система где первый и последний вектор параллельны:

Изменение поисковой системы выглядит так:

 

 

 

 

Блок-схемы

     Метод Свенна

 

 

Метод ЗС-1

 

 

Метод ЗС-2

 

 

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

 

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

 

Метод Больцано

 

 

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

 

 

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

 

 

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

 

 
Спецификация  программы

 

Для написания программы  была использована библиотека MFC (Microsoft Foundation Classes) и соответствующий мастер диалогового окна MFC AppWizard. Итоговая программа получилась благодаря созданию новых классов и функций, а также созданию ресурса основного диалогового окна с дружественным интерфейсом.

 

Программа состоит из восьми классов:

1. CEnterFunction - парсер
2. CMatrix  - класс матриц
3. CMETODI  - методы оптимизации
4. CMalgin_kursApp - приложение
5. CMalgin_kursDlg - диалоговое окно

 

Рассмотрим подробнее  каждый из этих классов.

 

 

1. CEnterFunction – этот класс представляет собой интерпретатор формул. В качестве аргумента он получает строку с формулой и две переменных, в которые при ошибке возвращается номер ошибочной позиции и текст ошибки. После вычислений, при условии отсутствия ошибок в формуле, возвращается значение типа double. Для непосредственной работы с классом существует только один открытый метод – Calculation, посредством которого и осуществляются все вычисления. Остальные методы являются закрытыми и не представляют особого интереса при программировании.

 

2. CMatrix – один из основных классов программы. Посредством него появляется возможность работы с векторами и матрицами. Класс обладает широким набором различных методов и переопределённых операторов, что позволяет максимально удобно использовать его в прикладных задачах.

 

3. CMETODI – самый главный класс. Содержит различные методы поиска, представленные в виде отдельных членов класса. Кроме того, в него включены вспомогательные методы, такие, как, например, численное дифференцирование, получение значения функции, получение матрицы Гессе, получение обратной матрицы методом Гаусса-Жордана и т.д. При создании класса ему передаётся строка с формулой (не содержащая ошибок, т.е. заранее проверенная) и дальше можно пользоваться различными методами. Рассмотрим подробнее члены класса.

 

4. CMalgin_kursApp – стандартный класс приложения,  который создаётся мастером. Особо интересной информации для нас не содержит, разве что вызов главного диалогового окна.

 

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

 

 

 

Описание  логики работы программы.

 

Логика работы программы не представляет собою ничего сложного. Она основывается на простой последовательности действий и в ближайшем рассмотрении выглядит следующим образом: ввод данных – проверка корректности введённых данных – поиск минимума – вывод результатов поиска.

Более детальное представление  о логике работы программы может  дать следующая блок-схема:

 

 

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

 

 Результаты тестирования программы

Результат тестирования методов для одномерной функции

Результат тестирования методов для двухмерной функции

 

 

 

 

Результат тестирования методов для трёхмерной функции

 

Результат тестирования методов для четырёхмерной функции

 

Результат тестирования метода комплексов Бокса

1.

2.

Результат тестирования парсера

 

Инструкция для пользователя

Ввод функции производится двумя способами: выбором из списка имеющейся функции либо ввод функции в ручную. При вводе в ручную можно использовать любые математические функции типа sin,cos,exp,ctg…

 

 

Исходные данные

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

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

 

 

 

 

 

 

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

 

Заключение

 

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

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

 

Приложение  – листинг программы

 

// Метод Свенна

 

int CMETODI::Swann(CMatrix &x,CMatrix &p)

{

double h = 0.1; // шаг

double la = 0;  // значение функции

int k = 0;   // счётчик числа итераций

 

if(dfp(x,p)>0)  // если необходимо,

h=-h;    // меням направление поиска

 

while(dfp(x+la*p,p)*dfp(x+(la+h)*p,p)>0) // сокращаем ТИЛ до начала            

{              // возрастания функции         

la += h;   // изменяем значения функции

h = 2*h;   // удваиваем шаг

k++;    // увеличиваем счётчик числа итераций

}

 

if(h<0)    // проверяем направление поиска

{      // и в соответствии с ним

b = la;   // присваиваем новые значения

a = la+h;  // локализированного минимума

}

else

{

a = la;

b = la+h;

}

return k;   // возвращаем число итераций

}

 

 

// Метод Больцано

 

int CMETODI::Bolcano(

CMatrix &x,   // начальная точка

CMatrix &p,   // направление поиска

double &e,   // погрешность поиска

int &max_step)  // максимальное количество итераций

{

int k=0;    // устанавливаем счётчик числа итераций

 

// сокращаем ТИЛ до  соответствующего условия

while((fabs(dfp(x+((a+b)/2)*p,p)))>e && fabs(b-a)>e && k<max_step)

{

k++;    // увеличиваем счётчик итераций

 

if(dfp(x+((a+b)/2)*p,p)>0)  // локализуем минимум

b=(a+b)/2;      // в соответствии с

else         // методом

a=(a+b)/2;

}

alpha = (a+b)/2; // изменяем значение коэффициента удлинения вектора

return k;   // возвращаем количесво итераций

}

 

 

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

 

int CMETODI::ZS_1(

CMatrix &x,   // начальная точка

CMatrix &p,   // направление поиска

double &e,   // погрешность поиска

int &max_step)  // максимальное количество итераций

{

int k=0;    // задаём счётчик числа итераций

 

double l = a+0.382*fabs(b-a);  // выбираем первую точку

double m = a+0.618*fabs(b-a);  // выбираем вторую точку

 

// сокращаем ТИЛ до  соответствующего условия

while((fabs(dfp(x+((a+b)/2)*p,p)))>e && fabs(a-b)>e && k<max_step)

{

if(f(x+l*p)<f(x+m*p))

{

b = m;

m = l;

l = a+0.382*fabs(b-a);

}

else

{

a = l;

l = m;

m = a+0.618*fabs(b-a);

}

k++;    // увеличиваем счётчик итераций

}

alpha = (a+b)/2; // изменяем значение коэффициента удлинения вектора

return k;   // возвращаем количество итераций

}

 

 

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

 

int CMETODI::ZS_2(

CMatrix &x,   // начальная точка

CMatrix &p,   // направление поиска

double &e,   // погрешность поиска

int &max_step)  // максимальное количество итераций

{

int k=0;    // задаём счётчик числа итераций

 

double x1 = a + 0.618*fabs(b-a); //выбираем первую точку