Поиск экстремума двумерной функции

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

Любой объект исследования можно представить в виде “черного ящика” с определенным количеством входов X = (x ₁, x ₂, …, x_n) и выходов Y = (y ₁, y ₂, …, y_m). Входную переменную x_i называют фактором, а выходную переменную y_j – окликом. Зависимость Y (X) называется функцией отклика. Для получения полной информации о свойствах функции отклика в принципе необходимо проведение опытов во всех точках области определения факторов. Такой эксперимент называют экспериментом с полным перебором всех входных состояний или полным факторным анализом. Ясно, что если фактор является непрерывной переменной, то число испытаний должно быть бесконечным. Уменьшение количества испытаний при условии получения достаточно полной информации о функции отклика является целью планирования эксперимента.

В LabVIEW предусмотрена возможность визуального представления двумерной функции отклика, когда отклик и факторы заданы массивами. Для этого используется графический индикатор 3D Surface Graph (рис. 6.1).

На его входы “x vector” и “y vector” подаются массивы переменных х и y, а на вход “z matrix” – трехмерный массив z (x,y).

При проектировании типичной является задача оптимизации, то есть определения такой комбинации значений факторов, при которых отклик принимает экстремальное значение. Эта задача может быть решена аналитически, если установлена функциональная связь отклика с факторами, или экспериментально, когда функция отклика Y (X) неизвестна, но имеется возможность измерить значения Y при различных комбинациях уровней факторов х ₁, х ₂, … х_п. В последней ситуации используются поисковые методы.

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

а) определение направления движения из данной точки по результатам специально организованного эксперимента;

б) организации движения в найденном направлении и

в) многократное повторение этих процедур до достижения точки экстремума.

В LabVIEW реализованы два метода поиска экстремума: симплекс-метод наискорейшего спуска (Downhill Simplex nD) и метод сопряженных градиентов (Conjugate Gradient nD). На рис. 6.2 показана процедура поиска экстремума симплекс-методом. Здесь тонкими линиями изображены линии постоянного уровня отклика.

Пусть начальное значение факторов отображается точкой 1. Для организации поиска минимума двумерного отклика задаются произвольно еще две точки, так чтобы треугольник 123 был равносторонним. Для каждой точки находится значение отклика, и та точка, для которой значение отклика максимально, зеркально отображается относительно линии, соединяющей две другие точки. На рисунке – это точка 2, и она отображается в положение 4. Теперь рассматривается треугольник 134: максимальным значение отклика будет для точки 3 и она отображается в положение 5. Процедура продолжается пока не достигается точка минимума. Это будет соответствовать круговому или возвратному движению точки.

На рис. 6.3 показана организация градиентного поиска. Градиентом функции y (x ₁, x ₂) называется вектор с координатами, равными частным производным функции по соответствующим факторам. Градиент направлен в сторону максимальной крутизны поверхности отклика. Движение по направлению к минимуму производится следующим образом. Для начальной точки 1 находится градиент и в направлении обратном градиенту осуществляется перемещение на один шаг. Для новой точки опять находится градиент и производится перемещение на один шаг. И т. д., пока не будет достигнут экстремум. Признак достижения экстремума – изменение аргумента градиента на 180 градусов.

Наиболее простым в реализации является метод покоординатного поиска (метод Гаусса – Зейделя). Поиск производится сначала по одной из координат до достижения местного экстремума, потом аналогично по другой координате и т.д., пока не будет достигнут экстремум функции (рис. 6.4). В процессе поиска постоянно сравнивается текущее значение отклика с предыдущим значением. Изменение знака этой разности говорит о достижении местного экстремума и о необходимости перехода к поиску по другой координате.

В лабораторной работе метод Гаусса-Зейделя используется для поиска максимума двумерной функции

Эта функция симметрична относительно плоскостей x = x ₀ и y = y ₀, поэтому поиск завершается за два этапа: поиск по координате х и поиск по координате у. Структурная схема программы виртуального прибора приведена на рис. 6.5.

Координаты начальной точки x _нач и y _нач и величина шага поиска Δ задаются с лицевой панели. Напомним, что шаг поиска это величина приращения координаты за одну итерацию. Шаг поиска берем одинаковым по обеим координатам: Δ х = Δ у = Δ.

Рассмотрим, как производится определение направления поиска. Считаем, что поиск начинается по координате х. Сначала рассчитываются значения отклика в начальной точке z = z (x _нач, y _нач) и отстоящих от нее по координате х на величину δ х в сторону увеличения и уменьшения координаты: z ₁ = z (x _нач + δ х, y _нач) и z ₂ = z (x _нач – δ х, y _нач). Величина δ х должна быть не больше шага поиска Δ х. В зависимости от соотношения между z, z ₁ и z ₂ принимается решение о направлении поиска. Если z ₂ < z < z ₁, то координата х в процессе поиска должна увеличиваться, шаг Δ х = Δ положителен. Если z ₂ > z > z ₁, то координата х должна уменьшаться, шаг Δ х = -Δ отрицателен. Эти ситуации показаны на рис. 6.6 а) и в) для начальной точки, находящейся вблизи максимума.

Если же z > z ₁ и z > z ₂ (рис. 6.6 б), то поиск проводить не нужно, так как точки, более близкой к экстремуму, при выбранном шаге поиска нет. Анализируя записанные соотношения между z, z ₁ и z ₂, замечаем, что шаг Δ x должен быть положительным, если z <z ₁, и отрицательным, если z <z ₂. В противном случае достигнут максимум и поиск не производится.

Блок-схема программы определения направления поиска приведена на рис. 6.7 а). Текст программы записывается в структуре Formula Node (пример текста представлен на рис. 6.7 б).

После определения направления поиска производится изменение координаты х в сторону достижения максимума добавлением к х значения Δ х в структуре While (рис. 6.8), пока вычисленное текущее значение z не станет меньше предыдущего. За максимальное значение z принимается предыдущее значение.

Условием выхода из цикла While является равенство нулю шага поиска dx или отрицательная разность текущего и предыдущего значений z. Выводятся массивы переменных х, у и z для формирования траектории поиска и последние значения переменных х и у, которые являются начальными координатами для поиска по координате у.

Оценим ошибку определения экстремума. Ее значение можно определить, исследуя процесс поиска вблизи максимума. Рассмотрим подробнее эту ситуацию (рис. 6.9).Так как z (x) < z ₁, то принимается решение об изменении координаты х в сторону увеличения на величину шага Δ x. Тогда вычисленное значение z (х + Δ х) окажется меньше предыдущего z (х) и за максимальное значение будет принято z (х).

Ошибка – это разность между истинной x_m _ист и рассчитанной x_m координатами максимума. Чему равно максимальное значение ошибки? Если уменьшать х, то z (x) будет уменьшаться, а z (х + Δ х) увеличиваться. Когда они сравняются, ошибка будет равна Δ х /2. При дальнейшем уменьшении х значение z (х + Δ х) становится больше значения z (х) и за максимальное значение принимается z (х + Δ х). Ошибка становится равной -Δ х /2. Таким образом, ошибка может принимать значения от -Δ х /2 до Δ х /2. Если координаты начальной точки поиска равномерно распределены в области определения функции z (x, y), то и ошибка равномерно распределена в интервале (-Δ х /2, Δ х /2).

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

Аналогично осуществляется поиск по координате у. Выходные переменные х, у и z структуры While, осуществляющей изменение координаты у, выводятся в виде массивов (как на рис 6.8) для формирования траектории поиска. А для индикации координат точки максимума выводятся последние значения переменных х, у и z.

Объединение массивов координат х, у и z, сформированных структурами While, производится функцией Build Array, поставленной в режим формирования одномерного массива (щелкнуть ПКМ на Build Array и в раскрывшемся меню активизировать Concatenate Inputs).

Для индикации траектории поиска используется графический индикатор 3D Curve Graph (рис. 6.10). Схема подсоединения к входам “x vector”, “y vector” и “z vector”, а также схема формирования массивов показана на рис. 6.11. На входы функций подаются одномерные массивы.

1. Дайте определения фактора, отклика и функции отклика.

3. Какими последовательными процедурами достигается экстремальное значение отклика в поисковых методах?

4. Поясните процедуру поиска экстремума симплекс-методом.

5. Поясните процедуру градиентного поиска экстремума.

6. Поясните процедуру поиска экстремума методом покоординатного поиска (методом Гаусса – Зейделя).

7. Составьте структурную схему программы поиска экстремума по одной координате методом Гаусса-Зейделя.

8. Поясните, как производится определение направления поиска.

9. Составьте блок-схему программы определения направления поиска.

10. Как определяется ошибка достижения экстремума и какие предельные значения она может принимать?

11. Для чего используется графический индикатор 3D Surface Graph?

12. В какой структуре записывается текст программы определения направления поиска?

13. В какой структуре производится изменение координаты до достижения максимума функции?

14. Что является условием выхода из цикла While, осуществляющего изменение переменной х?

15. Как выводятся из структуры While координаты точки максимума?

16. Как формируются массивы координат х, у и z для задания траектории поиска?

17. Для чего используется графический индикатор 3D Curve Graph?

Внимание!!! Блок-схема программы ВП, разрабатываемого в данной лабораторной работе, занимает много места, поэтому расположите ее, как показано на рис. 6.12 и старайтесь компактно располагать узлы.

2. Вычисление и индикация двумерной функции z (x, y).

2.1.На лицевую панель вывести цифровые элементы управления: максимальные значения х и у (они берутся одинаковыми поэтому достаточно одного органа управления – “х макс”), количество рассчитываемых точек по каждой координате – “ N ”. Поместить на лицевую панель графический индикатор 3D Surface Graph.

2.2. В окно BD поместить структуру Formula Node внутри двух структур For Loop (рис. 6.13).Внутри структуры Formula Node записать выражение (6.1) функции z (x, y), приняв х = i*d и y = j*d. Значения параметров взять из таблицы по номеру варианта.

2.3. Задать число итераций равным N, сформировать d = “x max”/N и подсоединить d к соответствующему терминалу. Одномерный массив х подсоединить к входам “x vector” и “у vector” графического индикатора 3D Surface Graph. Двумерный массив z подсоединить к входу “z matrix” графического индикатора 3D Surface Graph.

2.4. Убедитесь в отсутствии ошибок. Перейти на FP. Задать N =100, “х макс” = 4 Запустить выполнение программы. Полученное графическое изображение поверхности можно поворачивать инструментом “выделение” (стрелка) при нажатой ЛКМ. При желании можете поэкспериментировать с цветом, характером изображения и т.д., щелкнув ПКМ на индикаторе и выбрав в раскрывшемся меню CWGraph3D → Свойства.

3. Составление блок-схемы программы поиска максимума функции.

3.1. На лицевой панели добавить элементы управления и индикации: цифровые элементы управления для задания координат начальной точки “x нач” и “y нач”, а также шага поиска “d”. Вывести на лицевую панель три цифровых элемента индикации: “х m”, “у m” и “z m” для индикации координат точки максимума и графический индикатор 3D Curve Graph для индикации траектории поиска. Разместить выведенные элементы на лицевой панели, исходя из удобства работы.

3.2. Перейти в окно BD. Вывести структуру Formula Node. Поместить внутрь нее программу определения направления поиска по координате х, ориентируясь на рис. 6.7 б). Образовать терминалы для всех входных и выходных переменных. Подсоединить к входным терминалам выходы элементов управления, задающие координаты начальной точки поиска и величину шага поиска.

3.3. Вывести структуру While Loop. Внутри нее разместить программу изменения координаты х, ориентируясь на рис. 6.8. Выход элемента управления “х нач” подсоединить к терминалу начального условия регистра сдвига переменной х. Выход “у нач” соединить с терминалом “у” структуры Formula Node. К терминалу dx подсоединить выход dx блока определения направления поиска. Выход z этого блока соединить с терминалом начальных условий регистра сдвига z.

3.4. Скопировать блок определения направления поиска по координате х (структуру Formula Node) и вставить ее за блоком изменения координаты х. Внести изменения в программу, записанную в структуре Formula Node, учитывая, что производится определение направления поиска по координате у. На входы “х” и “у” подать последние значения переменных х и у с блока изменения координаты х. Вход d соединить с выходом элемента управления “d”.

3.5. Скопировать блок изменения координаты х (структуру While Loop) и разместить ее за блоком определения направления поиска по координате у. Внести изменения в программу, реализованную в структуре While Loop, учитывая, что производится изменение координаты у. К терминалу начальных условий регистра сдвига переменной у подсоединить выход последнего значения у блока изменения координаты х. Входной терминал переменной х соединить с выходом последнего значения переменной х блока изменения координаты х. Входной терминал dy соединить с выходом dy блока определения направления поиска по координате у. Выход “z” этого блока соединить с терминалом начальных условий регистра сдвига переменной z.

3.6. Поместить в окно BD графический индикатор 3D Curve Graph и три элемента Build Array.. Разместить их в правом верхнем углу блок-схемы программы и соединить в соответствии с рис. 6.11. Входы элементов Build Array соединить с соответствующими выходами массивов блоков изменения координат х и у. Build Array поставить в режим формирования одномерного массива.

3.7. Выходы последних значений координат х, у и z подсоединить к входам цифровых индикаторов “х m”, “у m” и “z m”.

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

4.1.Задать величину шага поиска d = 0.1 и значения координат начальной точки поиска произвольно в пределах от 0 до 4 Запустить выполнение программы. Чтобы лучше была видна траектория поиска, измените цвет экрана (Щелчок ПКМ на экране; в раскрывшемся меню выбрать CWGraph3D → Свойства: в закладке Graph → General → Plot area color выбрать подходящий цвет) или цвет траектории. Изменяя значения координат начальной точки поиска, посмотрите изменение траектории.

4.2. Снять зависимость ошибки определения экстремума δ х = x ₀ – x_m от координаты х начальной точки поиска, изменяя ее от выбранного значения х_нач до значения х_нач + d через 0,01. Составить таблицу, нарисовать график, объяснить. Почему при изменении координаты х начальной точки поиска значение y_m не меняется?

4.3. Снять зависимость ошибки определения экстремума δ х = x ₀ – x от величины шага поиска d при постоянной координате начальной точки поиска, изменяя шаг от 0,1 до 0,25 через 0,01. Составить таблицу, изобразить зависимость в виде точечного графика. Объяснить тенденцию изменения ошибки.

5. Сохранить в своей папке материалы, необходимые для отчета.

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: