ГЛОБАЛЬНАЯ ОПТИМИЗАЦИЯ:… > Разработанное ПО > Генераторы тестовых задач

Генераторы тестовых задач

Функции Гришагина

Двумерные многоэкстремальные функции Гришагина определяются соотношениями:

$\begin{align*} \varphi(y_1, y_2) = - \left\{\left(\sum_{i=1}^7\sum_{j=1}^7[A_{ij}a_{ij}(y_1, y_2) + B_{ij}b_{ij}(y_1, y_2)]\right)^2 + \right.\\ + \left.\left(\sum_{i=1}^7\sum_{j=1}^7[C_{ij}a_{ij}(y_1, y_2) - D_{ij}b_{ij}(y_1, y_2)]\right)^2\right\}^{\frac 1 2} \end{align*}$

где

$a_{ij}(y_1, y_2) = \sin(\pi i y_1)\sin(\pi j y_2),\;\; b_{ij}(y_1, y_2) = \cos(\pi i y_1)\cos(\pi j y_2)$

определены в области $0 \leq y_1, y_2 \leq 1$ , а параметры $-1 \leq A_{ij}, B_{ij}, C_{ij}, D_{ij} \leq 1$ являются независимыми случайными равномерно распределенными величинами.

Генератор GCGen (Global Constrained optimization problem Generator)

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

В генераторе GCGen предполагается, что задача условной оптимизации поставлена в виде

min{φ(y): y ∈ D, g_i(y) ≤ 0, 1 ≤ i ≤ m}
D = {y ∈ R^N: a_j ≤ y_j ≤ b_j, 1 ≤ j ≤ N}.

где функционал φ(y) (обозначаемый в дальнейшем также g_(m+1)(y)) – N-мерная целевая функция, а g_i(y), 1 ≤ i ≤ m, – функциональные ограничения.
При этом будем предполагать, что функционалы g_i(y), 1 ≤ i ≤ m, удовлетворяют условию Липшица с априори неизвестными константами L_i, т.е.

|g_i(y₁) — g_i(y₂)| ≤ L_i‖y₁ — y₂‖, 1 ≤ i ≤ m + 1.

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

возможность задавать объем допустимой области по отношению ко всей области изменения параметров (т.е. долю допустимой области в гиперпараллелепипеде D);
возможность изменить целевую функцию так, чтобы глобальный минимум находился вне допустимой области;
возможность сдвинуть точку условного глобального минимума на границу допустимой области;
возможность задать число активных ограничений в точке условного глобального минимума.

Структура классов

GCGen base classes image

IGeneralOptProblem – базовый класс для создания задачи глобальной оптимизации. Чтобы поставить задачу глобальной оптимизации, необходимо задать следующее:
1. Вектор функций, среди которых есть как целевые, так и функции ограничений. Максимальное количество параметров, которые могут быть известны для некоторой функции (размерность задачи), точка минимума и минимальное значение, точка максимума и максимальное значение, константа Липшица.
2. Границы допустимой области, заданной в виде гиперинтервала
3. Точка глобального минимума и минимальное значение
4. Индекс задачи в семействе (если задача принадлежит некоторому семейству задач)
IOptProblem – класс для создания задачи глобальной оптимизации без ограничений.
IConstrainedOptProblem – класс для создания задачи глобальной оптимизации с ограничениями.

Генератор допускает следующие модификации задачи оптимизации:

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

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

GCGen family classes image

IGeneralOptProblemFamily – базовый класс для задания семейства задач глобальной оптимизации.
IOptProblemFamily — класс для задания семейства задач глобальной оптимизации без ограничений.
IConstrainedOptProblemFamily — класс для задания семейства задач глобальной оптимизации с ограничениями.

Примеры создания многомерной задачи на основе функции Гришагина

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

Пример 1. Задачи без ограничений, различные значения параметров.