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

Описанные методы были реализованы в системе 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 изображено окно программы.

Главное окно программы При нажатии на кнопку «Выберите уравнение» программа открывает окно (см. рис. 3) с набором функций, которые может выбрать пользователь.

Окно выбора модельной задачи После выбора функции пользователь определяет, с каким методом он будет работать, выбрав между поисковым методом и методом последовательного перебора (см. рис. 4 (a)).

Окно программы для выбора метода минимизации После выбора функции при нажатии на кнопку «Задать параметры» программа открывает окно (см. рис. 2.4. (b)), в котором пользователь может задать начало и конец отрезка минимизации функции, а также погрешность вычисления точки глобального минимума и погрешность вычисления функции в точке глобального минимума .

Окно для задания параметров функции При нажатии на кнопку «Посчитать значения» программа ищет точку глобального минимума функции и ее значение в этой точке с заданными погрешностями и выводит полученные результаты в новом окне (см. рис. 2.5).

Окно результатов работы программы При нажатии на кнопку «График» программа открывает новое окно, в котором пользователь может выбрать погрешность с которой программа построит график выбранной ранее функции и выведет его в области слева при нажатии на кнопку «Построить».

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

Руководство программиста Трансляцию функции, выбираемой пользователем, выполняет функция 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 (). Результат работы программа выводит на форму.

Используемые в программе глобальные переменные:

• 1. yb — одномерный массив вещественных чисел, используемый для выбора пользователем погрешности значения точки глобального минимума функции;
• 2. yy (вещественное число) — погрешность значения функции в точке глобального минимума;
• 3. numf (целое число) — номер функции, выбранной пользователем;
• 4. k1, k2, k3, k4, k5, k6 (целые числа) — счетчики в циклах;
• 5. tmstart (вещественное число) — переменная, хранящая время начала работы программы для поиска точки минимума и минимума функции;
• 6. tmfinish (вещественное число) — переменная, хранящая время окончания работы программы для поиска точки минимума и минимума функции;
• 7. tmout (вещественное число) — переменная, хранящая время работы программы для поиска точки минимума и минимума функции;
• 8. timeRR — двумерный массив, хранящий сведения о времени работы программы в таблице;
• 9. XL, YL — одномерные массивы вещественных чисел, хранящие промежуточные значения точки локального минимума и значения функции в этой точке;
• 10. alpha (вещественное число) — переменная хранящая значение константы, используемой в методе золотого сечения;
• 11. u0, u1, u2, u3, u5 (вещественные числа) — переменные, хранящие значения точек при поиске точки минимума методом золотого сечения;
• 12. KP (целое число) — переменная, хранящая общее число локальных минимумов, найденных программой;
• 13. st (целое число) — переменная, необходимая для возведения в степень для выбранной функции;
• 14. izm (переменная типа boolean) — переменная, показывающая, когда на форме были произведены изменения;
• 15. xgpr, ygpr, xgsl, ygsl (вещественные переменные) — переменные, хранящие промежуточные значения при поиске точки глобального минимума и значения функции в этой точке;
• 16. XG (вещественное число) — точка глобального минимума;
• 17. YG (вещественное число) — глобальный минимум функции;
• 18. rnr, r1r, r2r, res (вещественные числа) — переменные, необходимые для задания функций;
• 19. hp (вещественное число) — длина отрезка, на котором исследуется функция;
• 20. ffpr, ffsl, x0p, x1p, x2p, x1pp, x2pp, x3p, f0p, f1p, f2p, f1pp, f2pp, f3p (вещественные числа) — переменные для ранения промежуточных значений при поиске точки глобального минимума и точки глобального минимума методом золотого сечения;
• 21. Fa (вещественное число) — начало отрезка, на котором исследуется функция;
• 22. Fb (вещественное число) — конец отрезка, на котором исследуется функция;
• 23. w, g (вещественные числа) — числа в показателях степеней для четверной функции;
• 24. ad, bd, cd (вещественные числа) — промежуточные значения, для определения точек в методе золотого сечения;
• 25. hg (вещественное число) — шаг сетки;
• 26. n (вещественное число) — число отрезков разбиения на сетке;
• 27. fgm (вещественное число) — промежуточный глобальный минимум;
• 28. xgm (вещественное число) — промежуточное значение точки глобального минимума;
• 29. EpsX (вещественное число) — погрешность точки минимума;
• 30. EpsY (вещественное число) — погрешность функции;
• 31. xx (вещественное число) — переменная, необходимая для возведения в степень;
• 32. m (вещественное число) — параметр, через который вычисляется число отрезков разбиения на сетке;
• 33. Dt, Tm, mas (строковые переменные) — переменные, необходимые для вывода таймера.

Используемые в программе процедуры и функции:

1. procedure TForm1. Button1Click (Sender: TObject)

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

2. procedure TForm1. BitBtn1Click (Sender: TObject)

Процедура очистки выбранных ранее параметров. Процедура TForm1. BitBtn1Click начинает работать после нажатия на кнопку «Очистить параметры».

3. procedure TForm1. FormCreate (Sender: TObject)

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

4. procedure ParametersForMemo ()

Процедура для задания параметров при нажатии на кнопку «Задать параметры».

5. procedure TForm1. Timer1Timer (Sender: TObject)

Процедура таймера. Форма обновляется с интервалом в 1 мс.

6. function TimeMmSs (timeMS:real):string

Функция возвращает строку времени в минутах, секундах и миллисекундах.

7. function stepen (x:real; step: integer):real

Функция stepen позволяет возводить в степень число step раз.

8. function TForm1. Shag (a, b, y: real):real

Функция считает число отрезков разбиения на сетке.

9. function TForm1. f1 (x:real):real

Функция для описания первого модельного примера.

10. function TForm1. f2 (x:real):real

Функция для описания второго модельного примера.

11. function TForm1. f3 (x:real):real

Функция для описания третьего модельного примера.

12. function TForm1. f4 (x:real):real

Функция для описания четверного модельного примера.

13. procedure TForm1. Button3Click (Sender: TObject)

Процедура очищает поля с ранее заданными параметрами при нажатии на кнопку «Очистить параметры».

14. function TForm1. VyborFunction (z1:real):real

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

15. function Unimodal (zn1, zn2: real; zn3: real=0):boolean

Функция проверки выбранного отрезка на унимодальность. Начальные данные определяются процедурой processgrid2. Результат представляет собой логическую переменную.

16. procedure localMinimum (xa, ag, xb, bg, xd, dg, xe, eg: real)

Процедура поиска локального минимума. Начальные данные определяются процедурой processgrid2. Результаты заносятся в два одномерных массива, хранящие полученные значения точки локального минимума и сам минимум.

17. procedure processgrid2 (ap, bp: real)

Процедура проверки отрезка на унимодальность и дальнейшее разбиение этого отрезка по методу золотого сечения. Начальные данные хранятся в переменных ap, bp — начало и конец отрезка. Результат передается в процедуру localMinimum.

18. procedure TForm1. Button4Click (Sender: TObject)

Основная процедура программы. Содержит в себе модифицированный метод золотого сечения, позволяющий найти локальный минимум на выбранном отрезке сетки с заданной погрешностью. Результаты записываются в таблицу, открывающуюся по нажатию на кнопку «Посчитать значения».

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

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

Результат работы программы зафиксируем в таблице. Для этого введем следующие обозначения:

— точное значение точки глобального минимума функции;

— приближенное значение точки глобального минимума функции, полученное с помощью программы;

— точное значение глобального минимума функции в точке ;

— приближенное значение глобального минимума функции в точке, полученное с помощью программы.

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

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

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

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

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

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

— точное значение точки глобального минимума функции;

— приближенное значение точки глобального минимума функции, полученное с помощью программы;

— точное значение глобального минимума функции в точке ;

— приближенное значение глобального минимума функции в точке, полученное с помощью программы.

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

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