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

Реферат ...

Введение 3
Исследование поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка 6
Метод последовательного перебора 6
Поисковый метод минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка 9
Реализация поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка и метода последовательного перебора 14
Сравнительное исследование эффективности методов 26
Заключение 37
Список литературы 38
Приложение 40

Экстремальные задачи нередко возникают в различных отраслях современной науки, таких, как информатика, кибернетика, экономика, космонавтика, физика, вычислительная математика, технические науки и многие другие. В большинстве случаев экстремальные задачи не поддаются аналитическому исследованию и для их решения используются численные методы, ориентированные на применение компьютера. Численные методы минимизации функций многих переменных обычно сводят решение многомерной экстремальной задачи к итерационному процессу на каждом шаге которого решается задача одномерной минимизации (задача определения минимума функции одной переменной). Существующие методы одномерной минимизации, в свою очередь, принято подразделять на методы локальной и глобальной минимизации. Первые применяются в основном для определения минимума унимодальных функций [20]. Применение методов локальной минимизации к функциям, имеющим несколько локальных минимумов, приводит обычно к определению одного из локальных минимумов, не обязательно совпадающего с минимумом глобальным. К наиболее распространённым методам локальной минимизации относятся такие методы, как метод половинного деления, метод золотого сечения, метод парабол. Методы глобальной минимизации работают намного медленнее, зачастую требуют хранения больших наборов данных, но зато позволяют во многих случаях найти глобальный минимум функции, которая не является унимодальной. К наиболее известным методам глобальной минимизации относятся метод равномерного перебора и метод ломаных [2].
Работы, посвященные новым методам минимизации функций одной переменной, продолжают появляться на страницах математических книги журналов [2], [4], [16]. К настоящему времени не существует общепринятого универсального численного метода, который позволял бы получать оптимальное решение для любой задачи нелинейной оптимизации. При решении каждой задачи минимизации, может требоваться применение нескольких методов, поэтому эффективное решение задачи минимизации зависит от набора алгоритмов минимизации, которыми владеет исследователь.
Вряд ли можно создать численный метод, способный определять сколь угодно узкие локальные минимумы. Важно лишь, чтобы были параметры, способные увеличивать чувствительность метода к узким локальным минимумам. К сожалению, повышение чувствительности всегда достигается за счёт сгущения сетки точек и существенного увеличения объёмов вычислительной работы [20], поэтому задача минимизации функций, а также составление новых методов минимизации мультимодальной функции одной переменной в наше время является актуальной.
Целью данной работы является исследование и программная реализация нового поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка [20].
Для достижения цели решались задачи:
1. Создание обзора методов минимизации функций и функционалов.
2. Реализация метода последовательного перебора средствами Borland Delphi.
3. Реализация поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы интервалов первого порядка средствами Borland Delphi.
4. Постановка, проведение и анализ результатов сравнительного экспериментального исследования метода последовательного перебора, метода ломаных, монотонного алгоритма Стронгина, поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка, поискового метода минимизации мультимодальной функции одной переменной на основе трехзвенной схемы отбора интервалов первого порядка и поискового метода минимизации мультимодальной функции одной переменной на основе трехзвенной схемы отбора интервалов второго порядка.
В приложении приведен листинг программы, реализующей метод последовательного перебора и поисковый метод минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка.

Условия (6) - (8) позволяют выявить все окрестности внутренних точек локального минимума функции на отрезке , ширина которых не меньше , а также окрестности граничных точек локального минимума функции , ширина которых не меньше . С ростом значения и уменьшением , условия (6) - (8) будут выявлять окрестности всё более и более узких локальных минимумов и при достаточно большом значении (маленьком значении ) будут выявлены окрестности всех точек локального минимума функции , на которых функция является унимодальной. А далее методом золотого сечения получатся приближенные значения точек локального минимума и локальных минимумов с погрешностями и , соответственно. Параллельно вычисляются количество обнаруженных локальных минимумов , приближенные значения глобального минимума и точка глобального минимума (). Точка совпадает с одной из приближенных точек локального минимума , а совпадает с одним из приближенных локальных минимумов . Поэтому, если , то погрешности и также не будут превышать и , соответственно. В заключение заметим, что хранить значения и нет смысла [20].Для завершения описания метода решения экстремальной задачи осталось сформулировать условия окончания итераций и условия выбора начального значения величины . Процесс сгущения сеток будем заканчивать, когда значение глобального минимума перестаёт уменьшаться при сгущении сетки (с учётом заданной точности его определения методом золотого сечения ). Чтобы сформулировать условия выбора начального значения заметим, что если ,(9)то заданное условие в методе золотого сечения будет выполнено. Если при этом второе условие выполняется, то это значит, что функция имеет узкие минимумы, ширина которых меньше . В этом случае нужно уменьшить . Решая неравенство (2.9) относительно получим следующее условие,(10)при выполнении которого следует выдать сообщение о необходимости уменьшения значения . Здесь - целая часть вещественного числа. Начальное значение будем выбирать меньшим, чем и таким, чтобы после третьего сгущения сетки значение ещё не достигало , а после четвёртого сгущения значение становилось больше :.(11)При таком выборе начального значения величина границы погрешности становится параметром, влияющим на чувствительность метода к узким локальным минимумам. Для повышения чувствительности метода следует уменьшать [20].Реализация поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка и метода последовательного перебораОписанные методы были реализованы в системе Delphi 7. Текст программы приведен в приложении.Delphi— это интегрированная среда разработки, в которой используется язык программирования Object Pascal. Delphi является средой RAD (rapid application development — быстрая разработка приложений). Начиная со среды разработки Delphi 7.0, в официальных документах Borland стала использовать название Delphi для обозначения языка Object Pascal. Начиная с 2007 года уже язык Delphi (производный от Object Pascal) начал жить своей самостоятельной жизнью и претерпевал различные изменения связанные с современными тенденциями (например, с развитием платформы .net) развития языков программирования: появились class helpers, перегрузки операторов и д.р.Программа тестировалась на модельных задачах. Для хранения значений параметров приближенного решения использовались одномерные массивы. Исходными данными для программы являются концы отрезка, на котором ищется минимум функции и , значения погрешности точки минимума и погрешности значения функции в точке минимума, а также значения и для четвертой модельной задачи. Результатами работы программы являются приближенное значение точки , в которой находится минимум функции, а также приближенное значение минимума функции в точке . Руководство пользователяОткрываем файл Project2 в среде разработки Borland Delphi 7.0. В коде программы пишется новая функция, аналогичная функции TForm1.f4(x:real):real. Затем находится функция TForm1.VyborFunction(z1:real):real, в которой осуществляется условие перевода данных в введенную функцию. Ввод функции производится с клавиатуры, поддерживаются цифры 0-9, арифметические операции, ^ - (степень числа), тригонометрические функции (sin, cos, tan, asin, acos, atan, sh, ch, th, cth), также функции (abs, exp, lg, ln, sqrt).После этого программа по нажатию F9 запускается на выполнение. При запуске программы появляется окно, в котором необходимо ввести начальные данные.При запуске программы появляется окно, в котором необходимо ввести начальные данные.На рис. 2 изображено окно программы. Рис. 2. Главное окно программыПри нажатии на кнопку "Выберите уравнение" программа открывает окно (см. рис. 3) с набором функций, которые может выбрать пользователь.Рис. 3. Окно выбора модельной задачиПосле выбора функции пользователь определяет, с каким методом он будет работать, выбрав между поисковым методом и методом последовательного перебора (см. рис. 4(a)).Рис. 4.(а) Окно программы для выбора метода минимизацииПосле выбора функции при нажатии на кнопку "Задать параметры" программа открывает окно (см. рис. 2.4.(b)), в котором пользователь может задать начало и конец отрезка минимизации функции, а также погрешность вычисления точки глобального минимума и погрешность вычисления функции в точке глобального минимума . Рис. 4.(b) Окно для задания параметров функцииПри нажатии на кнопку "Посчитать значения" программа ищет точку глобального минимума функции и ее значение в этой точке с заданными погрешностями и выводит полученные результаты в новом окне (см. рис. 2.5).Рис. 2.5 Окно результатов работы программыПри нажатии на кнопку "График" программа открывает новое окно, в котором пользователь может выбрать погрешность с которой программа построит график выбранной ранее функции и выведет его в области слева при нажатии на кнопку "Построить".Рис. 2.6. Окно программы, отображающей график выбранной модельной задачиПри нажатии на кнопку "Очистить параметры", появляющуюся после заполнения параметров функции, все ранее заданные параметры удаляются (кроме значения, определяющего функцию, выбранную пользователем). При нажатии на кнопку "Крестик" программа производит полную очистку всех выбранных ранее параметров и заданных значений.Руководство программистаТрансляцию функции, выбираемой пользователем, выполняет функция TForm1.VyborFunction(). Основные вычисления производятся в процедуре TForm1.Button4Click(Sender: TObject),где Sender - передаваемые в процедуру TForm1.Button4Click параметры функции. Результат работы выводится на форму с полем Form4.Memo1.Ввод данных (промежуток поиска минимума , точность), производится процедурой ParametersForMemo(), которая передает данные в процедуру TForm1.Button4Click(), а значения в процедуру processgrid2(ap,bp:real). EpsX - погрешность точки минимума, EpsY - погрешность функции в точке минимума. Ввод константы Липшица производится с помощью процедуры TForm3.Button1Click().kkl - константа Липшица.Поиск минимума: выбор функции, с которой будет работать пользователь осуществляется функцией TForm1.VyborFunction(z1:real). Она возвращает номер выбранной функции. Выбор метода, с которым придется работать в дальнейшем осуществляется с помощью переключателей sRadioButton1, sRadioButton2. Начальный шаг разбиения определяется как Shag(Fa,Fb,EpsX), куда передаются значения начала и конца отрезка, а также значение погрешности точки минимума. Процедура processgrid2() выполняет проверку отрезка на унимодальность и дальнейшее его разбиение на малые отрезки для поиска минимума методом золотого сечения в процедуре localMinimum(). Параметры xa,ag,xb,bg,xd,dg,xe,eg являются результатом работы процедуры processgrid2() и исходными данными для процедуры localMinimum(). Результат работы (найденные локальные минимумы) процедуры localMinimum() записывается в поле Form4.Memo1. Программа завершает работу после того, как перестанут выполняться условия: (Abs(ygpr-ygsl)>2*EpsY) and (Mmax-M>0.5) - для поискового метода, u[i-1]<(b-(h/2)) - для метода последовательного перебора. Рисование графика функции производит процедура TForm5.Button1Click(). Результат работы программа выводит на форму.Используемые в программе глобальные переменные:yb - одномерный массив вещественных чисел, используемый для выбора пользователем погрешности значения точки глобального минимума функции;yy (вещественное число) - погрешность значения функции в точке глобального минимума;numf (целое число) - номер функции, выбранной пользователем;k1, k2, k3, k4, k5, k6 (целые числа) - счетчики в циклах;tmstart (вещественное число) - переменная, хранящая время начала работы программы для поиска точки минимума и минимума функции;tmfinish (вещественное число) - переменная, хранящая время окончания работы программы для поиска точки минимума и минимума функции;tmout (вещественное число) - переменная, хранящая время работы программы для поиска точки минимума и минимума функции;timeRR - двумерный массив, хранящий сведения о времени работы программы в таблице;XL, YL - одномерные массивы вещественных чисел, хранящие промежуточные значения точки локального минимума и значения функции в этой точке;alpha (вещественное число) - переменная хранящая значение константы, используемой в методе золотого сечения;u0, u1, u2, u3, u5 (вещественные числа) - переменные, хранящие значения точек при поиске точки минимума методом золотого сечения;KP (целое число) - переменная, хранящая общее число локальных минимумов, найденных программой;st (целое число) - переменная, необходимая для возведения в степень для выбранной функции;izm (переменная типа boolean) - переменная, показывающая, когда на форме были произведены изменения;xgpr, ygpr, xgsl, ygsl (вещественные переменные) - переменные, хранящие промежуточные значения при поиске точки глобального минимума и значения функции в этой точке;XG (вещественное число) - точка глобального минимума;YG (вещественное число) - глобальный минимум функции;rnr, r1r, r2r, res (вещественные числа) - переменные, необходимые для задания функций;hp (вещественное число) - длина отрезка, на котором исследуется функция;ffpr, ffsl, x0p, x1p, x2p, x1pp, x2pp, x3p, f0p, f1p, f2p, f1pp, f2pp, f3p (вещественные числа) - переменные для ранения промежуточных значений при поиске точки глобального минимума и точки глобального минимума методом золотого сечения;Fa (вещественное число) - начало отрезка, на котором исследуется функция;Fb (вещественное число) - конец отрезка, на котором исследуется функция;w, g (вещественные числа) - числа в показателях степеней для четверной функции;ad, bd, cd (вещественные числа) - промежуточные значения, для определения точек в методе золотого сечения;hg (вещественное число) - шаг сетки;n (вещественное число) - число отрезков разбиения на сетке;fgm (вещественное число) - промежуточный глобальный минимум;xgm (вещественное число) - промежуточное значение точки глобального минимума;EpsX (вещественное число) - погрешность точки минимума;EpsY (вещественное число) - погрешность функции;xx(вещественное число) - переменная, необходимая для возведения в степень;m(вещественное число) - параметр, через который вычисляется число отрезков разбиения на сетке;Dt, Tm, mas (строковые переменные) - переменные, необходимые для вывода таймера.Используемые в программе процедуры и функции:procedure TForm1.Button1Click(Sender: TObject)Процедура выбора уравнения с которым в дальнейшем будет работать программа.procedure TForm1.BitBtn1Click(Sender: TObject)Процедура очистки выбранных ранее параметров. Процедура TForm1.BitBtn1Click начинает работать после нажатия на кнопку "Очистить параметры".procedure TForm1.FormCreate(Sender: TObject)Процедура слежения за текущим временем и датой, которые отображаются внизу окна программы.procedure ParametersForMemo()Процедура для задания параметров при нажатии на кнопку "Задать параметры".procedure TForm1.Timer1Timer(Sender: TObject)Процедура таймера. Форма обновляется с интервалом в 1 мс.function TimeMmSs(timeMS:real):stringФункция возвращает строку времени в минутах, секундах и миллисекундах.function stepen(x:real;step:integer):realФункция stepen позволяет возводить в степень число step раз.function TForm1.Shag(a,b,y:real):realФункция считает число отрезков разбиения на сетке.function TForm1.f1(x:real):realФункция для описания первого модельного примера.function TForm1.f2(x:real):realФункция для описания второго модельного примера.function TForm1.f3(x:real):realФункция для описания третьего модельного примера.function TForm1.f4(x:real):realФункция для описания четверного модельного примера.procedure TForm1.Button3Click(Sender: TObject)Процедура очищает поля с ранее заданными параметрами при нажатии на кнопку "Очистить параметры".function TForm1.VyborFunction(z1:real):realФункция непосредственного выбора функции с которой будет работать пользователь и дальнейшее подстановка заданных параметров в выбранную функцию.function Unimodal(zn1,zn2:real;zn3:real=0):booleanФункция проверки выбранного отрезка на унимодальность. Начальные данные определяются процедурой processgrid2. Результат представляет собой логическую переменную.procedure localMinimum(xa,ag,xb,bg,xd,dg,xe,eg:real)Процедура поиска локального минимума. Начальные данные определяются процедурой processgrid2. Результаты заносятся в два одномерных массива, хранящие полученные значения точки локального минимума и сам минимум.procedure processgrid2(ap,bp:real)Процедура проверки отрезка на унимодальность и дальнейшее разбиение этого отрезка по методу золотого сечения. Начальные данные хранятся в переменных ap, bp - начало и конец отрезка. Результат передается в процедуру localMinimum.procedure TForm1.Button4Click(Sender: TObject)Основная процедура программы. Содержит в себе модифицированный метод золотого сечения, позволяющий найти локальный минимум на выбранном отрезке сетки с заданной погрешностью. Результаты записываются в таблицу, открывающуюся по нажатию на кнопку "Посчитать значения".Тестирование программы, реализующей метод последовательного перебораДля проведения тестирования выберем задачу минимизации функции на отрезке ,для которой можно легко найти единственный глобальный и локальный минимум. Он достигается в точке и равен .Результат работы программы зафиксируем в таблице. Для этого введем следующие обозначения: - точное значение точки глобального минимума функции; - приближенное значение точки глобального минимума функции, полученное с помощью программы; - точное значение глобального минимума функции в точке ; - приближенное значение глобального минимума функции в точке , полученное с помощью программы. Введем следующие величины, для более точного сравнения полученных результатов: , . Зафиксируем погрешность вычисления значения функции .Таблица 2--Смысл тестирования заключается в том, что заданная точность должна достигаться, т. е. при любых допустимых значениях должно выполняться . Если слишком мало, то погрешности вычисления значения функций будет больше чем и такая точность принципиально не достижима.Из таблицы результатов работы программы, реализующей метод последовательного перебора, можно сделать вывод, что заданная точность была достигнута для всех заданных значений .Тестирование программы, реализующей поисковый метод на основе двухзвенной схемы отбора интервалов первого порядкаДля проведения тестирования выберем задачу минимизации функции на отрезке , для которой можно легко найти единственный глобальный и локальный минимум. Он достигается в точке и равен .Результат работы программы, реализующей поисковый метод на основе двухзвенной схемы отбора интервалов первого порядка зафиксируем в таблице. Для этого введем следующие обозначения: - точное значение точки глобального минимума функции; - приближенное значение точки глобального минимума функции, полученное с помощью программы; - точное значение глобального минимума функции в точке ; - приближенное значение глобального минимума функции в точке , полученное с помощью программы. Введем следующие величины, для более точного сравнения полученных результатов: , . Зафиксируем погрешность вычисления значения функции .Таблица 3--Из таблицы результатов работы программы, реализующей поисковый метод на основе двухзвенной схемы отбора интервалов первого порядка, можно сделать вывод, что заданная точность была достигнута для всех заданных значений .Сравнительное исследование эффективности методовВ этом параграфе проводится сравнительное исследование поисковых методов минимизации мультимодальной функции одной переменной на основе схем отбора интервалов, метода последовательного перебора, монотонного алгоритма глобального поиска Стронгина и метода ломаных. В качестве параметра эффективности метода выберем количество вычисления значений функций для достижения заданной точности.Подобный метод определения эффективности численных методов используется многими другими авторами, например Стронгиным [17]. В таблицах 4-9 представлены результаты вычисления этого параметра эффективности для перечисленных методов. Результаты для метода ломаных и поискового метода на основе трехзвенной схемы отбора интервалов первого порядка были взяты из работы [9]. Результаты для монотонного алгоритма глобального поиска Стронгина и поискового метода на основе трёхзвенной схемы отбора интервалов второго порядка были взяты из работы [14]. Под точностью будем понимать абсолютную погрешность значения точки глобального минимума , где - точное значение точки глобального минимума, - приближенное значение точки глобального минимума, вычисленное с помощью программы. Для достижения нужной точности используется параметр, который есть в каждом методе и при устремлении его к нулю, заданная точность должна быть достигнута. Для всех поисковых методов, метода последовательного перебора, метода ломаных и монотонного алгоритма глобального поиска Стронгина таким параметром является - оценка погрешности приближенного значения точки глобального минимума. Этот параметр используется и вводится непосредственно в программе. Т.о. при его последовательном уменьшении абсолютная погрешность точки глобального минимума также будет уменьшаться.В первой колонке задается значение , такое что и приблизительно равное . Фиксируем значение и уменьшаем значение параметра соответствующего метода до тех пор, пока значение погрешности не станет меньше или равным и в то же время близким к . Для последнего случая фиксируем количество вычислений значения функции и помещаем его в таблицу.Для некоторых задач точное значение глобального минимума аналитически найти невозможно. В этих случаях это значение находится с помощью численного метода. Для получения значения параметра воспользуемся поисковым методом на основе двухзвенной схемы отбора интервалов первого порядка. С его помощью найдем значение точки глобального минимума с высокой точностью, т.е. при . Полученное значение используем как точное значение точки глобального минимума исследуемой функции при вычислении погрешности. Характерной особенностью всех методов, кроме поисковых, является использование в качестве исходного данного константы Липшица для функции на .В простейших случаях константа Липшица вычисляется аналитически. Аналитический метод вычисления константы Липшица заключается в том, что находится производная функции и вычисляется ее максимум на том отрезке, для которого ищется минимум функции. Таким образом, на отрезке вычисляется производная исследуемой функции равное .