Построение классификации методов глобальной оптимизации

Размещено на http://www.allbest.ru/

Санкт-Петербургского Государственного Горного Университета

Построение классификации методов глобальной оптимизации

Певнева А.Г.

Задача классифицирования методов глобальной оптимизации на основе различных критериев представляется весьма интересной. Как отмечается в [1], современная теория глобальной оптимизации исключительно богата идеями, проработанными гораздо меньше, чем теория локальных методов поиска экстремума. Следовательно, общая структура теории не завершена. Кроме этого, при выборе метода для прикладной задачи зачастую используются неформальные соображения, далекие от строгого обоснования рациональности применения в данном случае. Поэтому использование классификации по различным критериям полезно как при изучении теоретических аспектов, так и в практике применения глобальных методов поиска.

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

В общем виде задача глобальной оптимизации формулируется следующим образом:

Пусть F - множество в некотором линейном пространстве над R. В - метрическое пространство с метрикой ,

Требуется найти и такой элемент х Х, что

(1)

Алгоритмом глобальной оптимизации называется способ построения последовательности точек из Х, всюду плотной в Х , сходящейся к некоторой точке х*, в которой выполнено условие (1). Типы сходимости могут быть разными, от сходимости по значениям f(x), до сходимости по вероятности.

Процесс нахождения глобального минимума является итерационным. Правило остановки этого процесса формулируется в виде логического оператора. В результате каждой итерации вычисляется приближение к глобальному оптимуму х*=arg min f. Все операции, производимые в ходе одной итерации можно разделить на две группы: множество алгоритмических операций А и множество информационных вычислений In. Алгоритмические операции - это совокупность действий, направленных на сбор информации о целевой функции, множестве оптимизации и преобразования этих объектов. Информационные вычисления - это построение оценок значений функционалов, определяющих приближение к глобальному оптимуму. Итак, множество алгоритмических операций

,

где - отображение ,

- множество значений j- й алгоритмической операции на i-м шаге,

Х(i) Х - подмножество множества оптимизации, построенное на каждом шаге по данному правилу , - множество всех подмножеств,

Z- множество значений информационных вычислений.

Так что множество алгоритмических операций на i-м шаге

А(i) =А,

где А - множество функционалов над F, - множество преобразований множества оптимизации Х.

Множество информационных вычислений

К алгоритму предъявляются требования:

1) операции должны быть однозначно определены как операторы, функционалы в соответствующих пространствах.

2) правило остановки, заданное оператором L(Z,I) должно быть однозначным и предусматривать возможность ”аварийной” остановки

Таким образом, различные способы задания указанных отображений, операторов, функционалов, структура их множеств определения задают методологию конструирования алгоритма. Определение функционального класса F эквивалентно определению области сходимости; структура множества Х определяет правила построения операторов, функционалов и отображений из множеств А и In. Изменяя вид этих зависимостей, сужая класс F по различным принципам, можно построить различные классификации методов. Основным же принципом современной классификации методов служит методологическое различие построения алгоритма - рассматривается ли принадлежность как необходимая информация для построения множеств А и In, или элементы этих множеств конструируются с приоритетным использованием эмпирических наблюдений и интуитивным подбором параметров. В русскоязычной литературе для обозначения этих различий используются термины рациональный и эвристический.

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

.

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

где В - множество параметров, найденных опытным путем.

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

Основным стержнем структурной классификации алгоритмов является деление их на множества пассивных и последовательных. На необходимость построения такой классификации указано в [1, 3].

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

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

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

В дальнейшем рациональные методы классифицируются по типу модели целевой функции, то есть, по функциональному классу F. Но принципы сужения этих классов формулируются на основании двух концепций оптимальности - минимаксный подход, и теория средней оптимальности [2]. В рамках минимаксного подхода рассматриваются детерминированные модели, в терминах средней оптимальности строятся стохастические модели.

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

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

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

Рисунок 1. Классификация рациональных методов

Рисунок 2. Классификация эвристических методов

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

Способы введения в алгоритм стохастических определений также можно считать методологическим отличием алгоритмов, так как, рандомизация алгоритма может проводиться по разным схемам. Можно выделить два подхода: введение вероятностной меры на классе F или построение различных распределений на множестве Х. Стохастический алгоритм характеризуется распределением некоторой меры на - алгебре подмножеств F. Тогда множества А и In содержат случайные функции и их характеристики.

Рандомизированным алгоритмом назовем алгоритм, в котором вероятностное пространство вводится на множестве Х:

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

Рандомизированные алгоритмы - рациональные методы поиска на случайной сетке, эвристические методы случайного поиска

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

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

Список использованных источников

1. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального оптимума - М.: Наука, 1991 247с.

2. Жилинскас А.Г. Глобальная оптимизация. Аксиоматика статистических моделей, алгоритмы, применение. - Вильнюс: Москлас 1986. - 166 с.

3. Жилинскас А.Г., Шалтянис В.Р. Поиск оптимума. Компьютер расширяет возможности. М.: Наука, 1989. 87 с.

4. Стронгин Р.Г. Поиск глобального минимума, М.: “Знание”, серия ”Математика Кибернетика” 1990, № 2. - С. 23-34.

Аннотация

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

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

Размещено на Allbest.ru