Пояснительная записка к курсовому проекту на тему «Оптимизация функции двух переменных методом покоординатного спуска»

Вид материала

Пояснительная записка

Содержание Батаев И.Ф. Пиявский С.А. Текст изучаемого раздела 2. Конспект лекции для автора курсового проекта как для преподавателя 3. Презентация для лекции 4. Сценарий имитационного или мультимедиа-компонента учебного 5. Тест для контроля усвоения учебного материала

Подобный материал:

• «Реализация метода оптимизация функции нескольких переменных (метод покоординатного, 58.58kb.
• Пояснительная записка к курсовому проекту на тему «Кодирование информации методом Шеннона-Фано», 253.27kb.
• Пояснительная записка к курсовому проекту на тему «Ранг матрицы» по дисциплине, 251.76kb.
• Пояснительная записка к курсовому проекту на тему «Машина Тьюринга» по дисциплине, 256.01kb.
• Пояснительная записка к курсовому проекту на тему №13: «Цех по ремонту строительных, 141.43kb.
• Пояснительная записка к курсовому проекту по дисциплине: «Объектно-ориентированное, 43.57kb.
• Пояснительная записка к курсовому проекту по курсу: «Процессы и аппараты химической, 41.88kb.
• Календарно-тематический план учебная дисциплина: «Математика», 35.73kb.
• Отчет по дисциплине «методы оптимизации и принятия решения» на тему «лабораторная работа, 23.84kb.
• Государственная Академия Управления имени С. Орджоникидзе Институт национальной и мировой, 399.35kb.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОУВПО «Самарский государственный архитектурно-строительный университет»

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

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


Пояснительная записка

к КУРСОВОМУ ПРОЕКТУ на тему

«Оптимизация функции двух переменных методом покоординатного спуска»

СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ

В ОБРАЗОВАНИИ


СТУДЕНТА ГИП-105Б БАТАЕВ И.Ф.

			Подпись, дата	Расшифровка подписи
		ВЫПОЛНИЛ:		Батаев И.Ф.
		студент		/ /
		Модуль сдан в библиотеку кафедры ПМ и ВТ
		Модуль размещен на портале ФИСТ
		ПРОВЕРИЛ:		Пиявский С.А.
		ОЦЕНКА		/ /

Оглавление

	Введение
	1	Текст изучаемого раздела
	2	Конспект лекции для автора курсового проекта как для преподавателя
	3	Презентация для лекции
	4	Сценарий имитационного или мультимедиа-компонента учебного назначения
	5	Тест для контроля усвоения учебного материала
	Заключение
	Этапы выполнения курсового проекта
Библиографический список

Введение.


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

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

 оживляет материал и позволяет студенту «общаться» с ним;

 даёт больше интерактивности и стимулирует активное обучение;

 наглядно демонстрирует некоторые идеи, которые трудно объяснить на лекциях или просто в тексте;

 позволяет заглянуть внутрь изучаемых процессов посредством различных симуляций;

 развивает навыки самостоятельного обучения и самоконтроля;

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

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

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

1. текст изучаемого раздела для включения в методическое пособие для студентов;
   

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

2. конспект лекции для автора курсового проекта как для преподавателя;
   

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

3. презентацию для лекции;
   

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

4. сценарий имитационного или мультимедиа-компонента учебного назначения для использования на лекции, или в лабораторной работе, или при самостоятельном изучении материала студентом;
   

5. имитационный или мультимедиа-компонент учебного назначения с применением математического моделирования, графики, мультимедиа и т.п.;
   

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

6. тест для контроля усвоения учебного материала;
   

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

1. Текст изучаемого раздела
   

Метод покоординатного спуска.

Пусть нужно найти наименьшее значение целевой функции u=f(M)=f(x_, x_, . . . ,x_n). Здесь через М обозначена точка n-мерного пространства с координатами x_, x_, . . . ,x_n: M=(x_, x_, . . . ,x_n). Выберем какую-нибудь начальную точку М_=(x_^, x_^, . . . ,x_n⁰) и рассмотрим функцию f при фиксированных значениях всех переменных, кроме первой: f(x_, x_^,x_^, . . . ,x_n⁰ ). Тогда она превратится в функцию одной переменной  x_ . Изменяя эту переменную, будем двигаться от начальной точки x_=x_^_ в сторону убывания функции, пока не дойдем до ее минимума при x_=x_^, после которого она начинает возрастать. Точку с координатами ( x_^, x_^,x_^, . . . ,x_n⁰) обозначим через М_, при этом f(M₀)  f(M_).

Фиксируем теперь переменные: x_=x_^, x_= x_^, . . . ,x_n=x_n⁰ и рассмотрим функцию f как функцию одной переменной  x_: f(x_^, x_^, x_^ . . . ,x_n⁰). Изменяя  x_ , будем опять двигаться от начального значения x₂=x₂⁰   в сторону убывания функции, пока не дойдем до минимума при x₂=x₂¹ .Точку с координатами {x_^, x_^, x_^ . . . x_n⁰} обозначим через М_, при этом   f(M₁) f(M_).


Проведем такую же минимизацию целевой функции по переменным   x_, x_,  . . . ,x_n. Дойдя до переменной x_n, снова вернемся к x_ и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М_,М_,М_, . . . , которой соответствует монотонная последовательность значений функции f(M₀) f (M_)f(M_) Обрывая ее на некотором шаге k можно приближенно принять  значение функции f(M_k) за ее наименьшее значение в рассматриваемой области. Рис. 2. Поиск наименьшего значе- 
ния функции методом покоординат- 
ного спуска. Отметим, что данный метод сводит задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Если целевая функция   f(x_, x_, ... ,x_n)  задана явной формулой и является дифференцируемой, то мы можем вычисллить ее частные производные и использовать их для определения направления убывания функции по каждой переменной и поиска соответствующих одномерных минимумов. В противном случае, когда явной формулы для целевой функции нет, одномерные задачи следует решать с помощью одномерных методов.


На рисунке изображены линии уровня некоторой функции двух переменных             u= f (х, у). Вдоль этих линий функция сохраняет постоянные значения, равные 1, 3, 5, 7, 9. Показана траектория поиска ее наименьшего значения, которое достигается в точке О, с помощью метода покоординатного спуска. При этом нужно ясно понимать, что рисунок служит только для иллюстрации метода. Когда мы приступаем к решению реальной задачи оптимизации, такого рисунка, содержащего в себе готовый ответ, у нас, конечно, нет.

 Пусть требуется решить задачу:

f(x) -->min,  х Rⁿ.                                     

В двумерном пространтсве R². Решение задачи методом покоординатного спуска, иначе называемого методом Гаусса - Зейделя, производят по следующей общей схеме.
Выбирают произвольно начальную точку х⁽⁰⁾   из   области определения функции f(х). Приближения х^(k) определяются соотношениями:
x^(k+1)=x^(k)+t^(k)S^(k)      (k=0,1,2, ...),
где вектор направления спуска s^(k)- это единичный вектор, совпадающий с каким-либо координатным направлением (например, если  S^(k) параллелен х₁, то S^(k)= {1,0,0,...,0}, если он параллелен  x₂, то S^(k)={0, 1, 0, . . . ,0} и т.д.) ; величина t^(k)   является решением задачи одномерной минимизации:
f(x^(k)+ts^(k)) -->  min,   t R¹,    (k=0,1,2, ...),
и может определяться, в частности, методом сканирования.
Детальная реализация общей схемы в двумерном случае R² дает траекторий приближения к точке х* методом покоординатного спуска, состоящую из звеньев ломаной, соединяющих точки х^(k), х^(k), x^(k+1)   (k=0, 1,  2,)       (рис.2).    При k=0, исходя  из начальной точки х⁽⁰⁾=(x₁⁽⁰⁾,x₂⁽⁰⁾), находят точку х⁽⁰⁾= (x₁⁽⁰⁾,x₂⁽⁰⁾), минимума функции одной переменной f(x₁,x₂⁽⁰⁾); при этом f(x⁽⁰⁾)f(x⁽⁰⁾).Затем находят точку минимума x⁽¹⁾  функции f (x₁⁽⁰⁾,x₂) по второй  координате. Далее делают следующий шаг вычислений при k=1. Полагают, что исходной точкой расчета является  х⁽¹⁾.   Фиксируя вторую  координату   точки  х⁽¹⁾,   находят   точку   минимума х⁽¹⁾= (x₁⁽¹⁾,x₂⁽¹⁾), функции  f(x₁,x₂⁽¹⁾) одной переменной x⁽¹⁾; при  этом f(x⁽¹⁾)f(x⁽¹⁾)f(x⁽⁰⁾). Точку х⁽²⁾   получают, минимизируя целевую функцию f(x₁⁽¹⁾,x₂), вновь по коорданате х₂, фиксируя координату x₁⁽¹⁾ ,точки x⁽¹⁾ , и т.д.
Условием прекращения вычислительной процедуры при достижении заданной точности  может служить неравенство
x^(k+1) - x^(k) <

2. Конспект лекции для автора курсового проекта как для преподавателя


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

Будем рассматривать эти методы как методы поиска min f (x₁,x₂,...,x_n). Рассмотрим градиентный метод, а именно метод покоординатного спуска.


Метод покоординатного спуска.


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

Большинство методов предназначено для оптимизации непрерывной дифференцируемой выпуклой функции. Напомним, что функция называется выпуклой вниз (вогнутой), если



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

,

т.е. обращаются в нуль все n частные производные критерия. Значит, чтобы найти эту точку, достаточно решить эту систему уравнений с n неизвестными - компонентами вектора .

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

Условием прекращения вычислительной процедуры может служить заданная точность .


Рассмотрим пример:


sin(x)*tan(y)*cos(y)min


-5 ≤ x ≤ 5

-5 ≤ y ≤ 5


Указываем точку х = 1, y = 1. Значение функции в ней будет равно Z=0,078.


Программа строит путь до точки х = 4,667 y= - 4,667 z=-0,098


Указываем другую точку, например х =-2,333, y = 333. Значение функции в ней будет равно Z=0,138.


Программа строит путь до точки х = -4,667 y= 4,667 z=-0,098

3. Презентация для лекции




















4. Сценарий имитационного или мультимедиа-компонента учебного

назначения.


Шаг 1: студент вводит функцию, которую необходимо оптимизировать.

Шаг 2: студент вводит диапазон значений x и y.

Шаг 3: При нажатии кнопки «Построить» все данные интерпритиуются..

Шаг 4: Студент шелкает на точке (или пересечении прямых, если установлен флаг «каркас»). Программа указывает результ упрошенного покоординатного спуска.


5. Тест для контроля усвоения учебного материала

1. Какой методы основаны на вычислении и анализе частных производных функции f (х₁,...,х_n):
   
   1. градиентные
      
   2. безградиентные
      

2. После фиксирования одной из переменных функция становится оптимизацией функции:
   
   1. нескольких переменных
      
   2. одной переменной
      

3. Что является основной задачей оптимизации?
   
   1. Нахождение минимума или максимума действительной функции в некоторой области.
      
   2. Нахождение экстремального значения некоторой заданной функции
      
   3. Поиск оптимального значения параметров заданной функции на заданном промежутке при заданных условиях
      
4. После однократной оптимизации каждой переменной оптимизация прекращается:
   
   1. Да
      
   2. Нет
      

5. Возможно ли графически изобразить функцию двух переменных:
   
   1. Нет
      
   2. Да, линиями уровня.
      

Заключение


Разработка электронного обучающего модуля является очень трудоемкой, но в то же время очень важной и востребованной деятельностью.

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

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

Этапы выполнения курсового проекта

1. Получение темы курсового проекта.
   
2. Поиск материала по данной тематике.
   
3. Разработка программного модуля.
   
4. Подготовка текста изучаемого раздела.
   
5. Подготовка лекции для преподавателя.
   
6. Подготовка презентации для лекции.
   
7. Подготовка теста для контроля усвоения материала.
   
8. Оформление пояснительной записки к курсовому проекту.
   

Библиографический список

1. Пиявский С.А. Методы оптимизации и принятия решений, Самара, СГАСУ, 2004
   
2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ, Пиявский С.А.
   
3. ссылка скрыта Покоординатный спуск
   
4. ссылка скрыта – 3d визуализация
   
5. Информационные системы и технологии в образовании: Методические указания к курсовому проектированию «Разработка электронного обучающего модуля» / составитель С.А. Пиявский; Самарск. гос. арх.-строит. ун-т. - Самара, 2007. - 19 с.