Параметрическая и структурная адаптация алгоритмов
Комплекс данных методов позволяет пользователю с достаточной надежностью получать оптимальные решения поставленных однокритериальных задач. Это обусловлено тем, что пользователь может оперативно адаптировать процесс решения задачи в зависимости от вида модели.
Задача адаптации процесса возникает тогда, когда процесс надо изменить в процессе его работы, чтобы поддержать его эффективность. Это происходит когда заранее невозможно предусмотреть ситуацию, в которую попадает алгоритм поиска решения. Такого рода неопределенность требует введения процедуры адаптации (предоставления пользователю возможности самому изменять параметры или структуру поиска). Различают адаптацию параметрическую и структурную.
Основными параметрами алгоритмов случайного поиска являются величина рабочего шага и параметра распределения вероятности случайного шага . Адаптация величины рабочего шага связана с необходимостью его уменьшения или увеличения в зависимости от результатов предыдущего шага. Наиболее часто применяется эвристика: при неудачном случайном шаге его величину уменьшают и увеличивают при удачном. Неудачный шаг свидетельствует о возможном приближении к экстремуму. Удачный показывает, что до цели еще далеко.
|
aN+1 = 1 · aN при YN<0, где 1>1. aN+1 = 2 · aN при YN0, где 2<1 |
(1)
(2) |
Возникает задача, как подобрать коэффициенты 1, 2 таким образом, чтобы быстрее найти точку экстремума.
Адаптация закона распределения вероятности случайного шага заключается в использовании информации о поведении целевой функции для деформации этого распределения. Основная характеристика распределения случайного шага есть его математическое ожидание M. Адаптация достигается за счет добавления вектора W к 0, где 0 – случайный вектор с нулевым математическим ожиданием
|
M0=0. |
(3) |
|
= 0+M. |
(4) |
Вектор W отражает предысторию работы алгоритма, выявляет перспективные направления поиска и определяет систематический дрейф случайного блуждания в направлении экстремума (рис. 3).
Используется эвристика: направление W формируется, как взвешенная сумма случайных шагов, когда удачные шаги берутся с положительными весами, неудачные с отрицательными, и предпочтение отдается более свежей информации.
Структурная адаптация предусматривает переход от одного алгоритма к другому при решении однокритериальной задачи. Пользователь может выбирать, каким способом будет осуществляться поиск оптимальной точки и методами глобального поиска, и методами локального поиска. Если пользователь имеет некоторую априорную информацию о поведении модели, то он может соответственно выбрать метод, который будет наиболее надежно и точно работать с данной моделью.
Порядок выполнения работы
Разработать программу поиска минимума функции методами случайного поиска с линейной и нелинейной тактикой с прежними исходными данными. Координаты начальной точки поиска должны быть заданы двумя способами: ввод координат пользователем и случайным образом. Шаг поиска также задается пользователем. Реализовать адаптацию величины рабочего шага.
Осуществить 3-4 запуска программы из различных точек с разным шагом. Окончание процесса поиска происходит в случае k неудачных шагов из одной точки.
Отобразить траекторию поиска из стартовой точки.
Осуществить 3-4 запуска программы из различных точек с разным шагом и параметрами условий окончания счета.
Реализовать возможность совместной работы алгоритмов случайного поиска и Хука-Дживса в режиме со структурной адаптацией (точка, найденная одним методом, является стартовой при запуске другого метода).