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

Использование двухэтапного алгоритма весовой фильтрации предполагает на первом этапе применение процедуры, обеспечивающей поиск точки (области) глобального экстремума - . Математическая формулировка этого факта имеет следующую форму [8]:

 

 при всех .

 

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

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

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

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

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

Алгоритмы глобальной оптимизации в настоящее время принято разделять на два класса [11,13,17]: использующие модель глобального поведения функции (рациональные) и не использующие таковой (эвристические).

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

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

Основные идеи построения рациональных и эвристических алгоритмов определяют следующую классификацию [11,17]:

1. Методы поиска глобального экстремума, основанные на использовании алгоритмов локальной оптимизации.

2. Алгоритмы минимизации функций с ограниченной скоростью изменения.

3. Методы, основанные на использовании статистических моделей целевых функций.

4. Глобальный случайный поиск.

5. Методы декомпозиции.

Анализ большого количества работ [8,11,17], посвященных методам глобальной оптимизации показывает, что с точки зрения объема вычислительных затрат, точности нахождения глобального экстремума и возможности программной реализации наиболее предпочтительными являются алгоритмы глобального случайного поиска и методы декомпозиции.