Курсовая работа: Определение экстремума методом случайного поиска

Политехнический институт

Кафедра «Промышленная автоматика и робототехника»

КУРСОВАЯ РАБОТА

по дисциплине «Методы принятия оптимальных решений»

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

Выполнил: ст-т гр.621011и

Нгуен М.Т.

Проверил: к.т.н., доц. каф.ПАиР

Акименко Т.А.

ОГЛАВЛЕНИЕ

• ВВЕДЕНИЕ
• ЗАДАНИЕ
• ТЕОРИТИЧЕСКИЕ СВЕДЕНИЯ
• АЛГОРИТМ РАБОТЫ ПРОГРАММЫ
• ЛИСТИНГ ПРОГРАММЫ
• АНАЛИЗ РЕЗУЛЬТАТОВ РАБОТЫ ДЛЯ РАЗНЫХ ВХОДНЫХ ДАННЫХ
• ВЫВОД
• СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

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

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

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

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

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

В данной курсовой работе содержится 24 л., 5 ил., 3 табл.

ЗАДАНИЕ

Для данной функции вычислить экстремум методом случайного поиска.

Функция для варианта №7:

.

ТЕОРИТИЧЕСКИЕ СВЕДЕНИЯ

Случайный поиск является одним из методов определения экстремума функции качества. Он применяется тогда, когда имеется значительное количество параметров оптимизации и функция качества L(X) с высокой вычислительной сложностью, имеющая точки разрыва, для которой проблематично рассчитать градиент даже разностным методом.

Основным понятием метода случайного поиска является понятие реализации. Компоненты вектора X представляют собой случайные величины, которые для каждой реализации выбираются случайным образом из области допустимых значений: .

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

Функцией распределения случайной величины называют функцию

.

Функция распределения F(x) обладает следующими свойствами.

Область определения R функции F(x) совпадает с областью распределения случайной величины или, что то же самое, с областью изменения функции . В общем случае можно считать, что область определения функции F(x) R = ().

Для любого справедливо неравенство:

.

Функция F(x) является неубывающей и непрерывной, хотя и может иметь счетное число скачков (точек разрыва).

Если , и , то имеет место равенство

,

где - вероятность попадания случайной величины в соответствующую область.

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

.

Вследствие того, что функция F(x) является неубывающей, для нее справедливо свойство

.

Вследствие зависимости (1.19) справедливо также свойство

; ;

.

Если множество является конечным (счетным) и функция представляет собой дискретную случайную величину, принимающую значения из множества (х₁,..., х_п,..., х_N), то функцию F(x) можно представить в виде совокупности единичных ступенчатых функций

,

где - приращение функции распределения, имеющее физический смысл вероятности того, что х = х_п,

;

- единичная функция Хевисайда

Дифференцирование (1.25) дает

,

где - дельта-функция Дирака,

.

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

,

или в виде матрицы

.

Указанные представления называются дискретным распределением.

В соответствии с общим определением для дискретной случайной величины функция распределения определяется равенством

.

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

.

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

Начальным моментом s-го порядка непрерывной случайной величины х называется интеграл

.

Начальным моментом s-го порядка дискретной случайной величины х называется сумма вида

.

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

для непрерывной случайной величины

;

для дискретной случайной величины

.

Пусть имеется случайная величина х с математическим ожиданием Х. Тогда центрированной случайной величиной называется величина, смещенная на математическое ожидание, т.е.

х^о = х - Х.

Начальные моменты центрированной случайной величины носят название центральных моментов.

Центральным моментом r-го порядка непрерывной случайной величины х называется интеграл

.

Центральным моментом r-го порядка дискретной случайной величины х называется сумма вида

.

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

для непрерывных величин

;

для дискретных величин

.

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

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

.

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

Если задана величина х = (х₁,..., х_l,..., х_L) то может быть определена многомерная функция распределения

Функция распределения также является неубывающей по каждой из случайных величин.

Для каждой из случайных величин x_l

; .

Дискретным случайным вектором называется система случайных величин, принимающая конечное или счетной число значений. Совместное распределение случайных величин задается вероятностями

.

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

.

Для системы непрерывных случайных величин задается совместная плотность распределения . Функция совместного распределения определяется формулой

.)

Свойства совместной плотности распределения:

.

.

Случайные величины считаются независимыми (в совокупности), если

.

Если случайные величины имеют непрерывные распределения, то для независимых (в совокупности) случайных величин совместная плотность распределения определяется в виде

.

Смешанным моментом порядка k называют момент

,

(1.58)

где

.

Ковариацией двух случайных величин называют смешанный центральный момент второго порядка центрированных случайных величин:

. (1.59)

Для произвольно зависимых случайных величин

. (1.60)

Коэффициентом корреляции называют величину

. (1.61)

Свойства:

; . (1.62)

Если , то с вероятностью единица случайные величины х и у связаны линейной зависимостью

. (1.63)

Ковариационной матрицей случайных величин называют квадратную, симметричную относительно главной диагонали матрицу С с элементами .

Случайные величины называют попарно некоррелироваными, если для любых l, и .

Если случайные величины попарно независимы, то они попарно некоррелированы. Обратное в общем случае неверно.

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

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

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

Одним из основных элементов любого алгоритма случайного поиска экстремума является генератор случайных чисел. К указанному генератору предъявляются следующие требования:

1. Большое количестве реализаций без повторения последовательности.

2. Равномерность распределение.

Как правило, генератор случайных чисел входит в компилятор языков высокого уровня с именем RAND. В частности, имеется такой генератор в средах программирования MATHCAD, MATHLAB. Генераторы вырабатывают случайную величину у, распределенную равновероятно в интервале . Если параметр x_i выбирается распределенным равномерно, то пересчет величины y в параметр x_i производится следующим образом:

.

Если параметр считается распределенным по закону, отличному от равновероятного, то для определения x_i решается уравнение:

.

Общий алгоритм определения экстремума методом случайного поиска является следующим.

1. В ячейку L⁰ заносится начальное значение.

2. Обнуляется счетчик количества реализаций m = 0.

3. Обнуляется счетчик количества переменных i = 0.

4. Запускается генератор случайных чисел и формируется число у, равномерно распределенное в интервале от 0 до 1.

5. Определяется переменная x_i:= {x_i|}.

6. Пп. 4, 5 повторяются для .

7. Определяется функция качества L(X).

8. Выполняется основная процедура оптимизации.

9. Пп. 3 - 8 выполняются для 0 < m < M.

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

.

Количество попаданий в область допустимых решений определяется биномиальным распределением

где m, M - целые числа; - число сочетаний из M элементов по m.

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

Р = 1 - (1 - р)^М.

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

.

Соответственно, вычислительная сложность алгоритма

,

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

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

АЛГОРИТМ РАБОТЫ ПРОГРАММЫ

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

Рисунок 1 Блок схема алгоритма

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

ЛИСТИНГ ПРОГРАММЫ

uses graphABC;

var

del, n, m, ww, wh, x0, y0, keox, keoy: integer;

a, b: real;

function F(x: real): real; // Функция из условия, для которой ищем экстремум

begin

F:= exp(-x-1)+x*x+2*x-1;

end;

procedure interval(aint:real); // Процедура, выделяющая края интервала поиска на графике

var

yf:real;

begin