Метод наилучшей пробы
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Приднестровский государственный университет им. Т.Г. Шевченко
Инженерно-технический институт
Кафедра информационных технологий и автоматизированного
управления производственными процессами
КУРСОВАЯ РАБОТА
по дисциплине Математическое программирование
тема: МЕТОД НАИЛУЧШЕЙ ПРОБЫ
Работу выполнил:
студент группы ИТ09Др62ИВ1
А.Е. Гусев
Руководитель:
Доцент, к.т.н.
Т.Д. Бордя
Тирасполь, 2012
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
. МЕТОДЫ СЛУЧАЙНОГО ПОИСКА
.1 Методы наилучшей пробы
.2 Адаптивный метод случайного поиска
. ОПИСАНИЕ АЛГОРИТМА
.1 Входные данные
.2 Блок-схема алгоритма метода Наилучшей пробы
. ОПИСАНИЕ ПРОГРАММНОЙ ЧАСТИ
.1 Выбор среды программирования
.2 Входные и выходные данные
.3 Описание программы
. КОНТРОЛЬНЫЙ ПРИМЕР
.1 Результаты работы программы
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А - Руководство пользователя
ПРИЛОЖЕНИЕ Б - Листинг программы
ВВЕДЕНИЕ
Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходиться заниматься в повседневной жизни. Термином оптимизация в литературе обозначает процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или оптимального решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.
Необходимость принятия наилучших решений так же стара, как само человечество. Испокон веку люди, приступая к осуществлению своих мероприятий, раздумывали над их возможными последствиями и принимали решения, выбирая тем или другим образом зависящие от них параметры - способы организации мероприятий. Но до поры, до времени решения могли приниматься без специального математического анализа, просто на основе опыта и здравого смысла.
Цель данной курсовой работы:
проанализировать и обработать теоретические и экспериментальные данные по теме Метод наилучшей пробы;
анализ собранной информации;
сравнительный анализ с другими методами;
разработка программы, реализующая данный метод.
1. МЕТОДЫ СЛУЧАЙНОГО ПОИСКА
Метод случайного поиска является прямым развитием метода проб и ошибок, когда решение ищется случайно, и при удаче принимается, а при неудаче отвергается с тем, чтобы немедленно снова обратиться к случайности как к источнику возможностей. Такое случайное поведение разумно поведение разумно опирается на уверенность, что случайность содержит в себе все возможности, в том числе и искомое решение во всех его вариантах.
Метод случайного поиска, называемый так же методом Монте-Карло, основан на том, что при одном и том же числе испытаний вероятность получения решения, близкого к оптимальному, при случайном поиске больше, чем при последовательном переборе через равные интервалы изменения отдельных параметров.
Идея метода случайного поиска состоит в следующем. Пусть задача минимизации решается для некоторой ограниченной области параметров. Если это возможно, то эта область соответствующим преобразованием координат переводится в единичный гиперкуб. Если такое преобразование неосуществимо, то производится замена координат таким образом, чтобы область поиска лежала внутри единичного гиперкуба. В этом случае эффективность поиска будет сильно зависеть от соотношения объемов единичного гиперкуба и области поиска в нем.
Существуют несколько методов случайного поиска, отличия друг от друга заключаются несколькими шагами или условиями.
1.1 Метод наилучшей пробы
Задается начальная точка х. Каждая последующая точка находится по формуле:
xk+l = хк + tk ? к (1.1)
где tk > 0 - величина шага; ?к - случайный вектор единичной длины, определяющий направление поиска; k - номер итерации. На текущей итерации при помощи генерирования случайных векторов ?* получается M точек ух,...,ум, лежащих на гиперсфере радиуса tk с центром в точке хк в соответствии с рисунком 1.1 Среди полученных точек выбирается точка ут, в которой значение функции наименьшее. Если в выбранной точке значение функции меньше, чем в центре, то дальнейший поиск продолжается из этой точки. Иначе поиск продолжается из старого центра, но с меньшим шагом до тех пор, пока он не станет меньше заранее заданной величины R.
Рисунок 1.1 - Гиперсфера полученная в результате применения данного метода
1.2 Адаптивный метод случайного поиска
Вначале задается начальная точка х. Каждая последующая точка находится по формуле:
xk+l = хк + tk ? к (1.2)
где tk > 0 - величина шага; ?к - случайный вектор единичной длины, определяющий направление поиска; k - номер итерации. На текущей итерации при помощи генерирования случайных векторов ?к получаются точки, лежащие на гиперсфере радиуса tk с центром в точке хк в соответствии с рисунком 1.2.
Рисунок 1.2 - Гиперсфера полученная в результате применения данного метода
Если значение функции в полученной точке не меньше, чем в центре, шаг считается неудачным, пр