Безградиентные методы детерминированного поиска

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

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

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

К безградиентным методам детерминированного поиска относятся: метод локализации экстремума функции, метод «золотого сечения», метод поиска с использованием чисел Фибоначчи, метод Гаусса-Зейделя, метод сканирования [1]. Рассмотрим один из этих методов – метод сканирования.

Метод сканирования

Метод сканирования заключается в последовательном просмотре значений критерия оптимальности в ряде точек, принадлежащих области изменения независимых переменных, и нахождении среди этих точек такой, в которой критерий оптимальности имеет минимальное (максимальное) значение. Точность метода определяется тем, насколько “густо” располагаются выбранные точки в допустимой области изменения независимых переменных.

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

Другое достоинство – независимость от вида оптимизируемой функции.

К недостаткам метода относится необходимость вычисления критерия для большого числа точек. Последнее обстоятельство существенно ограничивает возможности использования метода сканирования.

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

Для сокращения объема вычислений используется алгоритм с переменным шагом сканирования.