Разработка компьютерной системы для решения задач многомерной оптимизации методом прямого поиска с дискретным шагом
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Оглавление
1. Теоретическая основа метода оптимизации
.1 Постановка задачи
.2 Математические основы метода
.3 Пример расчета экстремума функции методом прямого поиска с дискретным шагом
.4 Анализ результатов расчетов
. Программная реализация задачи на ЭВМ
.1 Описание структуры программы
.2 Результаты отладки программы на контрольных примерах
.3 Составление инструкции по использованию программы
. Исследование эффективности работы метода оптимизации на тестовых задачах
.1 Выбор и описание тестовых задач
.2 Исследование влияния начального приближения
.3 Исследование работоспособности метода путем решения задач различной размерности и сложности
.4 Обработка результатов исследований визуальными и формальными средствами Excel
1. Теоретическая основа метода оптимизации
1.1 Постановка задачи
Целью данной работы является разработка компьютерной системы для решения задач многомерной оптимизации методом прямого поиска с дискретным шагом.
Для реализации поставленной цели необходимо решить следующие задачи:
Проанализировать теоретические основы метода оптимизации;
Программно реализовать данный метод оптимизации;
Исследовать эффективность работы метода оптимизации на контрольных примерах;
1.2 Математические основы метода
Хук и Дживс предложили логически простую стратегию поиска, использующую априорные сведения и в то же время отвергающую устаревшую информацию относительно характера топологии целевой функции. Метод включает два этапа: исследующий поиск вокруг базисной точки и поиск по образцу в направлении, выбранном для минимизации. На рис. 1 представлена упрощенная траектория этого метода.
Рисунок 1 - Траектория метода прямого поиска с дискретным шагом
Рассматриваемый метод состоит из следующих операций. Исследующий поиск. Задается начальное приближение X(1) и приращения по координатам DX. Рассчитывается значение f(X(1)) в базисной точке. Затем в циклическом порядке совершаются пробные шаги. Если приращение улучшает целевую функцию, то шаг считается удачным. По этой переменной значение изменяется на величину шага и дается приращение по другой переменной (см. рисунок 1). Иначе - неудачным и делается шаг в противоположном направлении. И если он тоже оказался неудачным, то значение этой переменной оставляют без изменения и дается приращение по другой переменой и т.д. пока не будут изменены все независимые переменные. На этом завершается первый исследующий поиск, найдена точка X(2).
Поиск по образцу осуществляется вдоль направления, соединяющего X(2) и X(1). Совершается один или несколько шагов до тех пор пока шаги являются удачными.
1.3 Пример расчета экстремума функции методом прямого поиска с дискретным шагом
В качестве контрольного примера возьмем функцию от двух переменных f(x)=(x1-2)4+(x1- 2x2)2.
Постановка задачи: Найти минимум функции f(x)=(x1-2)4+( x1- 2x2)2 с точностью ?=0,05.
Выбираем начальные приближение X = [2,5; 2,5] и приращения по координатам DX=0,05. Результаты расчетов с применением ECXEL по алгоритму методом прямого поиска с дискретным шагом, который рассмотрен выше, представлены в таблице 1.
Таблица 1 - Результаты расчетов с применением ECXEL
№x1x2f(x)Критерий Исследующий поиск12,52,56,313022,552,56,094032,552,556,594042,552,455,6140 Поиск по образцу12,552,455,614022,62,44,970032,652,354,381042,72,33,850052,752,253,379062,82,22,970072,852,152,625082,92,12,346092,952,052,137010322,0000113,051,951,9380123,11,91,9540 Исследующий поиск 13,051,951,938023,11,952,1040331,951,81004322,0000531,91,6400 Поиск по образцу 131,91,640022,951,851,377032,91,81,146042,851,750,945052,81,70,770062,751,650,619072,71,60,490082,651,550,381092,61,50,2900102,551,450,2140112,51,40,1520122,451,350,1040132,41,30,0660142,351,250,0381
Таким образом, оптимальное решение имеем в точке X= [2,35, 1,25] и (x)= 0,038.
Рисунок 2 - Траектория движения алгоритма
1.4 Анализ результатов расчета
По результатам, полученным в контрольном примере, можно сделать вывод, что решением данной задачи является следующая точка оптимума и значение функций в ней соответственно:
,
Для решения данной задачи потребовалось произвести 35 итераций.
2. Программная реализация задачи на ЭВМ
2.1 Описание структуры программы
1. Кнопка Выполнить. После заполнения всех начальных параметров и выбора исследуемой функции вызывает процедуру поиска минимума.
. Кнопки передачи результатов расчета в Excel.
. Кнопки показывающие графики линий уровня и приближение к оптимальному решению.
. Кнопки передачи результатов расчета в Excel.
Интерфейс программы представлено на Рисунке 3.
Рисунок 3 - Интерфейс программы
Для отображения текущего состояния программы и управления её поведением были использованы следующие компоненты:
Компоненты класса TButton. Используются для управления ходом работы метода. Данные компоненты являются наиболее простыми и часто используемыми для выполнения действий подобного рода.
Компонент класса TEdit используется для ввода исходных данных метода.
Компонент класса TImage используется для отображения графика.
Компонент класса TComboBox используется для выбора функции для оптимизации.
Компонент TSrtingGrid используется для отображения данных в табличном виде, позволяя производить действия с каждой ячейкой таблицы, является средством просмотра результата вычислений, данные которой могут быть при желании пользователя представлены в виде таблицы Excel.
Компонент класс TLabel используется для подписи данны