АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ: МЕТОД ПОКООРДИНАТНОГО СПУСКА

Читайте также:
  1. A) Метод опроса
  2. I. Метод стандартизации
  3. I. Методы выбора инновационной политики
  4. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  5. I. Основные характеристики и проблемы философской методологии.
  6. I.ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ
  7. II. ВИРУСОЛОГИЧЕСКИЙ МЕТОД
  8. II. Вывод и анализ кинетических уравнений 0-, 1-, 2-ого порядков. Методы определения порядка реакции
  9. II. Методологічні засади, підходи, принципи, критерії формування позитивної мотивації на здоровий спосіб життя у дітей та молоді
  10. II. Методы прогнозирования и поиска идей
  11. II. Формальная логика как первая система методов философии.
  12. II. Цитогенетический метод

Теория

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

а) формулу целевой функции f(х12,..., хn),

б) Е - точность нахождения значений независимых переменных, при которых функция достигает минимума,

в) начальные приближения х1020..., хn0.

Зафиксируем все значения х-ов в виде начальных приближений, кроме первого. Тогда f(х1, х20..., хn0) - функция одной переменной х1. Решая задачу одномерной оптимизации, найдем минимум этой функции по координате х1 при фиксированных остальных координатах – хi1. В этом состоит первый шаг процесса оптимизации, заключающийся в спуске по координате x1.

Зафиксируем теперь все координаты, кроме x2. Снова решая одномерную задачу оптимизации, находим минимум функции по координате x2. Далее процедура повторяется до xn. На этом заканчивается первая итерация.

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

После каждой итерации вычисляется

D = çx1i+1 - x1iç + çx2i+1 - x2iç +.... +çxni+1 - xniç

и если D<=E, то вычисления прекращаются и последний набор x-ов считается решением. В противном случае проводится следующая

 

 

1.2.Алгоритм метода покоординатного спуска:

 

Решим эту задачу на EXCEL на новом рабочем листе.

Выделим столбец А под значения х1, столбец В - под значения х2, в столбец С будем заносить значения целевой функции и, наконец, в столбец D - значения погрешности D.

Занесем в ячейки А3 и В3 значения начальных приближений, равных 0,5 и в ячейку С3 формулу =(В3-А3^2)^2+(1-A3)^2. Скопируем эту формулу в блок ячеек С4:С17. На этом заканчивается подготовительный этап.

1 итерация.

1 шаг. Скопируем содержимое ячейки В3 в ячейку В4. Сделаем текущей ячейку С4. Процесс одномерной оптимизации для нахождения X1 выполним с помощью подпрограммы EXCEL Поиск решения.

В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С4, а в поле Изменяя ячейки - адрес А4. Щелкнем по кнопке Выполнить и по кнопке ОК. В результате в ячейке А4 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С4 по координате х1.

2 шаг. Скопируем содержимое ячейки А4 в ячейку А5.

Текущая ячейка С5, меню Сервис- Поиск решения. В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С5, а в поле Изменяя ячейки - адрес В5, Выполнить.

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

3 шаг. Занесем в ячейку D5 формулу =ABS(A3-A5)+ABS(B3-B5) для вычисления погрешности решения на первом шаге. На этом заканчивается первая итерация.

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

Можно построить диаграмму изменения на каждой итерации, выделив блок А2:В17 с помощью Мастера Диаграмм, выбрав тип диаграммы XY-точечная и формат 2. На диаграмме хорошо видны перпендикулярные ломаные линии движения от точки к точке параллельно одной из осей координат.

2. Ход решения:

 

Дана функция =2*х3-0,6*х2+0,06*х-0,002

1) Открываем чистый лист в MS Exel. Для выполнения 1 шага строим таблицу, состоящую из 4 столбцов и 13 строк.

Вносим следующие элементы:

1 ст. – Х1

2 ст. – Х2

3ст. - F

4 ст. – E (const)

 

2) Скопируем содержимое ячейки В3 в ячейку В4. Сделаем текущей ячейку С4. Процесс одномерной оптимизации для нахождения X1 выполним с помощью подпрограммы EXCEL Поиск решения.

В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С4, а в поле Изменяя ячейки - адрес А4. Щелкнем по кнопке Выполнить и по кнопке ОК. В результате в ячейке А4 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С4 по координате х1.

 

Метод покоординатного спуска  
X1 X2 F E
0,5 0,5    
0,199999999 0,5 0,1  

 

.

 

 

3)

 

 

 

4)

 

 

 

Вывод:

 

При выполнении лабораторной работы №3 мы познакомились с многомерными методами оптимизациями: методом координатного спуска, методом1и1методом1наискорейшего1спуска.
При выполнении практической части лабораторных работ, я применила полученные теоретические знания и научилась использовать метод покоординатного спуска для решения задач с помощью табличного процессора MS Excel.


Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)