Лабораторная работа 8
Поиск образов
Терминология в поиске образов
Образ - набор векторов, которые использует алгоритм для определения точки поиска на каждой итерации. Например, если имеются 2 независимые переменные в задаче оптимизации, то образ состоит из следующих векторов:
v1 = [1 0]
v2 = [0 1]
v3 = [-1 0]
v4 = [0 -1].
Узлы
На каждом шаге алгоритм поиска образов отыскивает множество точек, называемых узлом, для точки, которая улучшает целевую функцию. Алгоритм образует узел путем:
1. Умножения векторов образа на скаляр, называемый размером узла.
2. Сложением результирующих векторов с текущей точкой (точкой с наилучшим значением целевой функции, найденной на предыдущем шаге).
Например, текущая точка определяется как [1.6 3.4].
Образ состоит из векторов:
v1 = [1 0]
v2 = [0 1]
v3 = [-1 0]
v4 = [0 -1]
Размер узла равен 4.
Алгоритм умножает вектора образа на 4 и прибавляет их к текущей точке для получения следующего узла:
[1.6 3.4] + 4*[1 0] = [5.6 3.4]
[1.6 3.4] + 4*[0 1] = [1.6 7.4]
[1.6 3.4] + 4*[-1 0] = [-2.4 3.4]
[1.6 3.4] + 4*[0 -1] = [1.6 -0.6]
Оценка
На каждом шаге алгоритм оценивает точки в текущем узле путем расчета значений целевой функции (ЦФ). Когда опция Complete poll выключена (Off), алгоритм останавливает оценивание узловых точек как только он найдет точку со значением ЦФ меньшим, чем ЦФ текущей точки. Если это происходит, оценка называется успешной, и найденная точка становится текущей в следующей итерации. В случае, если алгоритм находит точку, которая улучшает ЦФ, то оценка называется неуспешной, и текущая точка остается той же самой в следующей итерации.
В случае установки Complete poll в положение «включено» (On), то алгоритм вычисляет ЦФ во всех узловых точках. Далее алгоритм сравнивает узловую точку с наименьшим значением ЦФ с текущей точкой. Если узловая точка имеет меньшее значение, чем текущая точка, то оценка успешная.
1. Для выполнения поиска образов напечатать в командном окне
psearchtool. Это откроет следующую панель, как показано на рис.1.
Рис.1. Панель для поиска образов
Пример. Воспользуемся файлом данным ps_example, который включен в Genetic Algorithms and Direct Search Toolbox. График функции показан на рис.2
Рис.2. График функции
Для нахождения минимума функции сделаем следующие шаги:
1. В поле ЦФ введем @ps_example.
2. В поле начальной точки введем [2.1 1.7].
3. Поля ограничений можно оставить незаполненными, так как задача без ограничений.
Нажать Start для запуска алгоритма.
Состояние и результаты отображаются на соответствующих панелях. Минимальное значение функции приблизительно -2. Панель Final point указывает точку, в которой достигается минимум (Рис.3).
Рис.3. Итоговые результаты
2. Определение задачи
· Целевая функция - это функция, которую необходимо минимизировать. Здесь нужно ввести М-файл (см. ниже) той функции, которая вычисляет целевую функцию.
· Начальная точка - исходная точка для запуска алгоритма поиска образа.
Создание М-файла
Для работы вначале нужно записать М-файл, который вычисляет целевую функцию. Для ясности изложения рассмотрим пример такой функции:
которую необходимо минимизировать.
Для записи М-файла сделаем следующие шаги:
· Создадим М-файл таким образом: в исходной панели MATLAB выбрать File - New - M-File. Эта процедура откроет редактор М-файла.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
