Разработка специализированного программного модуля

Размещено на http://www.allbest.ru/

Разработка специализированного программного модуля

Введение

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

Одним из представителей данного класса алгоритмов можно считать алгоритм стохастического градиентного спуска. В основе метода лежит алгоритм градиентного спуска. Цель - минимизировать заданную нами функцию.

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

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

В пункте 2 - приведено описание алгоритма.

В пункте 3 - проведены блок-схема алгоритма, описание программы, результаты выполнения и экспериментальное исследование трудоемкости алгоритма, а так же приведен код программы.

1. Постановка задачи

Дана функция Розенброка, которая имеет вид:

минимум программа функция отрезок

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

Необходимо провести экспериментальное исследование средней трудоемкости алгоритма

2. Алгоритм градиентного стохастического спуска

2.1 Описание алгоритма градиентного стохастического спуска

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

.

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

Таким образом, чтобы определить, как правильно исправлять координаты точек, мы должны вычислить градиент и отнять вектор какой-нибудь наперёд заданной длины (в нашем случае этой длинной выступает заданный шаг а) от имеющегося вектора точек:

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

Пример 1 - алгоритм градиентного спуска для одной точки.

GradientDescent()

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

2. Повторить Number_of_Steps раз:

а) Для всех i от 1 до n

б) Для всех j от 1 до m:

(i) Для всех i от 1 до n

в)

3. выдать значения .

.

Это значит, что нам нужно подправлять координаты точек после каждого тестового примера так:

Новый, изменённый алгоритм показан в примере 1. Правда, нужно внести и другие изменения. Во-первых, мы больше не можем рассчитывать на то, что в какой-то момент достигнем идеальной гармонии с исходными данными, и нам нужно научиться останавливаться в какой-то момент. В качестве условия для остановки здесь принято то, что алгоритм выполняется пока разности значений функции меньше ранее заданной точности. Другое изменение - в том, что если оставлять а постоянным, то на каком-то этапе точка перестанет приближаться к искомому минимуму, а начнёт его «перепрыгивать» на каждой итерации, то в одну сторону, то в другую. Поэтому a нужно уменьшать со временем. В данной программе мы уменьшаем шаг на два.

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

2.2 Теоретическая оценка трудоемкости алгоритма оптимизации

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

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

1) операцию присваивания ab;

2) операцию индексации массива a[i];

3) арифметические операции *,/,-,+;

4) операции сравнения a < b;

5) логические операции or, and, not.

Отметим, что неявно в операцию сравнения входит машинная команда перехода в конструкции if then else:

F _{«ветвление»} = f_then * p + f_else * (1-p).

Цикл не является элементарной операцией, т.к. может быть представлен в виде;

for i1 to N

тело

next i;

Таким образом, конструкция цикла требует 2*N элементарных операций:

F _«цикл» = 2*N+N*f_{«тело цикла».}

Для цикла while выберем худший случай. Худший случай (F_a(N)) - наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N.

Таким образом, для нашей программы получим:

N - количество точек;

F(N)=2+N*4+3+F_a1(F_а1(1+8*N+3+F_f)+1+F_a1(1+6*N+(2*4+2*N+4+F_f+F_pr))+4*N)+3+3*50+4+4*N+4*(N+1)+2

где, F_f трудоемкость функции F;

F_f =2;

F_a1 - наибольшее количество операций совершаемый циклом while;

F_pr - трудоемкость функции pr;

F_pr - 4*N+45.

В результате получим следующую функцию трудоемкости:

F(N)= 11+ F_a1^(F_a1 *29+1+ F_a1 *84+4))+179;

Возьмем в качестве начального значения следующие значения: N=2.

Исходя из начального значения, максимальное количество операций совершаемых циклом while в функции main F_a1 =732.

В результате теоретического вычисления трудоемкость данной программы составила F(N)=60 551 384 элементарных операций.

3. Разработка схемы программного модуля и его описание

3.1 Разработка схемы программного модуля

Рисунок 1 - блок-схема главной функции программы

Рисунок 2 - блок-схема функции F (x())



Рисунок 3 - блок-схема функции pr (n, i, x())

3.2 Описание программы

Начинает выполняться главная функция программы, изображенная на рисунке 1. Программа начинает работать с заданным количеством переменный n исходной функции (в данном случае две). Исходя из n формируются два массива: массив переменных-x() и массив новых посчитанных переменных-x1 (). Далее задается двумерный массив минимумов функций и их координат соответственно. Далее задается точность e=0.0000001, которая послужит условием выхода из цикла While при разности значений функции меньше e, шаг (a) с которым будет спускаться функция к своему минимуму и счетчик d количества попыток выбора новых случайных значений переменных. Если выбор новых значений не будет произведен за 2000 итераций, то за минимум принимается исходная точка. Потом происходит выбор случайным образом двух точек из промежутка, из которых и будет производиться спуск.

Если все условия выполнились корректно (т.е. полученные точки не являются минимумами) начинается поиск минимума. Происходит расчет новых значений переменных с шагом a при движении против градиента pr (функция градиента изображена на рисунке 3). Функция pr является функцией подсчета градиента. Далее происходит проверка правильности спуска для новых переменных. Если разность полученного и предыдущего значений функции (функция Розенброка изображена на рисунке 2) меньше точности e, то шаг уменьшается на два, иначе, происходит замена текущих значений переменных на новые.

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

3.3 Экспериментальное исследование трудоемкости алгоритма

Экспериментальное исследование средней трудоемкости алгоритма будет производиться путем подсчета каждой элементарной операции. Для этого в программе введем дополнительно счетчик, который будет увеличиваться на единицу после выполнения каждой элементарной операции. В результате выполнения программы для двух переменных экспериментальная трудоемкость программы составила F_экспер(N)= 61 912 349 (F_теорит(N)= 60 551 384). Результат отображен на рисунке.

Результат экспериментального исследования средней трудоемкости алгоритма

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

3.4 Результат выполнения программы

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

Результат выполнения программы

3.5 Листинг программы, разработанный на языке VBA

Public Sub grad()

Dim x() As Double 'Массив перемменых

Dim x1 () As Double 'массив в новых посчитанных переменных

Dim min (5000, 5) As Double 'массив минимумов функции и их координат

Dim a As Double 'шаг изменения переменной

Dim df As Double 'разность между значениями функции для текущих и предыдущих переменных

Dim flag As Boolean 'условия выхода из цикламен

n = 2 'количество переменных

ReDim x(n) As Double

ReDim x1 (n) As Double

Dim trud As Long

trud = 1

For i = 1 To n 'объявление начальных значений переменных

x1 (n) = -10

trud = trud + 4

Next i

j = 0 'счетчик количества попыток поиска минимума

flag = True

e = 0.0000001 'точность

trud = trud + 3

Do

a = 0.1

d = 0 'счетчик количества попыток выбора новых случайных значений переменных

trud = trud + 2

Do

For i = 1 To n

x(i) = Int((-10 + 20 * Rnd) * 100) / 100 'задание новых случайных значений переменных

trud = trud + 8

Next i

d = d + 1

trud = trud + 3

If (d > 2000) Then

flag = False

trud = trud + 1

End If

trud = trud + 6

Loop While (F (x()) >= F (x1 ()) And flag = True)

trud = trud + 1

If (flag = True) Then

j = j + 1

trud = trud + 2

End If

trud = trud + 1

If (flag = True) Then

Do 'начало поиска минимума

For i = 1 To n

x1 (i) = x(i) - a * pr (n, i, x()) 'расчет новых значений переменных с шагом а при движении против градиента pr

trud = trud + 6

Next i

trud = trud + 3

If (F (x1 ()) < F (x())) Then 'проверка правильности спуска для новых переменных

df = F (x()) - F (x1 ()) 'разность нового и предыдущего значения функции

trud = trud + 4

For i = 1 To n

x(i) = x1 (i) 'замена текущи значений переменных на новые

trud = trud + 4

Next i

Else

df = 1

a = a / 2 'деление шага на 2

trud = trud + 4

If (a = 0) Then

MsgBox «все!!»

df = 1

trud = trud + 1

End If

End If

trud = trud + 1

Loop While (df > e) 'выход из цикла при разности функций меньше точности

End If

trud = trud + 1

If (flag = True) Then

min (j, 1) = F (x()) 'запись найденного минимума в массив

trud = trud + 3

For i = 1 To n

min (j, i + 1) = x(i) 'запись значений переменных для найденного минимума

trud = trud + 4

Next i

End If

trud = trud + 1

Loop While (flag = True)

'поиск наименьшего из найденных минимумов и вывод его на лист

trud = trud + 1

If (j > 1) Then

minimum = min (1, 1)

numin = 1

trud = trud + 3

For i = 2 To 50

trud = trud + 2

If (min (i, 1) < minimum) Then

minimum = min (i, 1)

numin = i

trud = trud + 3

End If

Next i

Else

min (1, 1) = F (x1 ())

numin = 1

trud = trud + 4

For i = 1 To n

min (1, i + 1) = x1 (i)

trud = trud + 4

Next i

End If

For i = 1 To n + 1

Cells (1, i) = min (numin, i)

trud = trud + 4

Next i

Cells (2, 1) = trud

Cells (2, 2) = j + 1

trud = trud + 3

End Sub

'функция

Private Function F (x() As Double)

F = 100 * (x(2) - x(1) ^ 2) ^ 2 + (1 - x(1)) ^ 2 ' - функци Розенброка, около 4000 итераций, (1,1)

trud = trud + 10

'F = 0

'For a = 0.1 To 1 Step 0.1

' F = F + ((Exp (-a * x(1)) - Exp (-a * x(2))) - (Exp(-a) - Exp (-10 * a))) ^ 2 '-экспоненциальная функция около 700 итераций, (1,10)

'Next a

End Function

'функция подсчета градиента

Private Function pr (n, i, x() As Double)

Dim tmp(4) As Double

Dim xtmp() As Double

ReDim xtmp(n) As Double

For k = 1 To n

xtmp(k) = x(k)

trud = trud + 4

Next k

tmp(1) = xtmp(i) + 0.02

tmp(2) = xtmp(i) + 0.01

tmp(3) = xtmp(i) - 0.01

tmp(4) = xtmp(i) - 0.02

pr = 0

xtmp(i) = tmp(1)

pr = pr - F (xtmp())

xtmp(i) = tmp(2)

pr = pr + 8 * F (xtmp())

xtmp(i) = tmp(3)

pr = pr - 8 * F (xtmp())

xtmp(i) = tmp(4)

pr = pr + F (xtmp())

pr = pr / 0.12

trud = trud + 45

End Function

Заключение

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

По приведенным результатам можно сравнить эффективность работы алгоритма. Было проведено экспериментальное исследование средней трудоёмкости алгоритма. При проверке полученных даны можно установить что был найден действительный минимум функции.

Список источников

1. Ульянов М.В., Шептунов М.В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. - М.: МГАПИ, 2003. - 80 с.

2. Конспект лекций по дисциплине «Математическая логика и теория алгоритмов».

Размещено на Allbest.ru