21.02.2018 14:43
red_b 0 1800 Источник
В ходе работы с глобальной оптимизацией, появилась потребность в конструировании многоэкстремальных тестовых функций. Зачастую большинство готовых функций, например из Википедии, не подходят для корректной оценки работы алгоритма. Часть функций являются одноэкстремальными, для таких примеров больше подходят алгоритмы локального поиска, другая – относится к овражным. Для глобальной же оптимизации необходимо использовать многоэкстремальные, где экстремумы ощутимо различаются по величине.

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

Метод Фельдбаума


Данный метод построен на основе простых степенных одноэкстремальных функций вида:

$$display$$I_i(x-c_i)=\sum_{j=1}^n a_{ij}|x_j-c_{ij}|^{p_{ij}}+b_i, p_{ij}>0$$display$$


Приведенная выше функция будет иметь минимум в точке $inline$c_i$inline$, а значение в этой точке будет равно $inline$b_i$inline$.
Если $inline$p_{ij}>0$inline$ (степень гладкости функции в районе экстремума), то в точке минимума функция будет гладкой, a если $inline$0< p_{ij} \le1$inline$, то в точке минимума функция будет угловой (не дифференцируемой).

Коэффициент $inline$a$inline$ отвечает за степень крутости функции в районе экстремума.
Чтобы построить многоэкстремальную функцию необходимо применить оператор минимума к набору одноэкстремальных функций. Общий вид будет следующий:

$$display$$I(x)=min\{ \sum_{j=1}^m a_{ij}|x_j-c_{ij}|^{p_{ij}}+b_i, i=\overline{1,N} \}$$display$$


Пример:

Аналитический вид функции

$$display$$I_1(x-c_1)=7|x_1|^2+7|x_2|^2,$$display$$


$$display$$I_2(x-c_2)=5|x_1+2|^{0.5}+5|x_2|^{0.5}+6,$$display$$


$$display$$I_3(x-c_3)=5|x_1|^{1.3}+5|x_2+2|^{1.3}+5,$$display$$


$$display$$I_4(x-c_4)=5|x_1|^{1}+5|x_2-4|^{1}+8,$$display$$


$$display$$I_5(x-c_5)=4|x_1-2|^{1.5}+4|x_2-2|^{1.5}+7,$$display$$


$$display$$I_6(x-c_6)=5|x_1-4|^{1.8}+5|x_2|^{1.8}+9,$$display$$


$$display$$I_7(x-c_7)=6|x_1-4|^{0.6}+6|x_2-4|^{0.6}+4,$$display$$


$$display$$I_8(x-c_8)=6|x_1+4|^{0.6}+6|x_2-4|^{1.6}+3,$$display$$


$$display$$I_9(x-c_9)=3|x_1+4|^{1.2}+3|x_2+4|^{0.5}+7.5,$$display$$


$$display$$I_{10}(x-c_{10})=2|x_1-3|^{0.9}+4|x_2+5|^{0.3}+8.5,$$display$$


$$display$$I(x)=min\{I_i(x-c_i), i=\overline{1,N} \}.$$display$$



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

image

Срез функции при $inline$x_1=x_2$inline$:

image

Срез функции при $inline$x_2=4$inline$:

image

Приведенная выше функция имеет минимумы в точках: (0, 0), (-2, 0), (0, -2), (0, 4), (2, 2), (4, 0), (4, 4), (-4, 4), (-4, -4), (3, -5). Глобальным является минимум в точке (0, 0).
Код для генерации тестовых функций:

def get_test_function_method_min(n: int, a: List[List[float]], c: List[List[float]], 
                                 p: List[List[float]], b: List[float]):
    """
    :param n: количество экстремумов
    :param a: список коэффициентов крутости экстремумов, чем выше значения, 
              тем быстрее функция убывает/возрастает и тем уже область экстремума
    :param c: список координат экстремумов
    :param p: список степеней гладкости в районе экстремума
    :param b: список значений функции
    :return: возвращает функцию, которой необходимо передавать одномерный список 
координат точки, возвращаемая функция вернет значение тестовой функции в данной точке
    """
    def func(x):
        l = []
        for i in range(n):
            res = 0
            for j in range(len(x)):
                res = res + a[i][j] * np.abs(x[j] - c[i][j]) ** p[i][j]
            res = res + b[i]
            l.append(res)
        res = np.array(l)
        return np.min(res)
    return func

Гиперболические потенциальные функции


Одноэкстремальная функция имеет вид:

$$display$$I_{Г,i}(x-c_i)=-\frac{1}{b_i*\sum_{j=1}^m a_{ij}|x_j-c{ij}|^{p_{ij}}+d_i}, b_i>0, d_i>0$$display$$


Эта функция также имеет минимум в точке $inline$c_i$inline$, его глубина определяется величиной $inline$d_i$inline$. Степень крутизны задается с помощью коэффициента $inline$b_i$inline$, чем он больше, тем уже область экстремума и круче функция.

Для получения многоэкстремальной функции необходимо применить оператор суммирования:

$$display$$I(x)=\sum_{i=1}^N I_{Г,i}(x-c_i)$$display$$


Пример:

Аналитический вид функции

$$display$$I_1(x-c_1)=-\frac{1}{|x_1+4|^1+|x_2|^1+0.25},$$display$$


$$display$$I_2(x-c_2)=-\frac{1}{2|x_1|^1+2|x_2|^1+0.2},$$display$$


$$display$$I_3(x-c_3)=-\frac{1}{0.5|x_1+3|^{0.6}+0.5|x_2-3|^{0.6}+0.1},$$display$$


$$display$$I_4(x-c_4)=-\frac{1}{1.5|x_1-2|^1+1.5|x_2-2|^1+0.3},$$display$$


$$display$$I_5(x-c_5)=-\frac{1}{0.8|x_1+3|^1+0.8|x_2+4|^1+0.35},$$display$$


$$display$$I(x_1, x_2)=\sum_{i=1}^5 I_{Г,i}(x-c_i)$$display$$



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

image

Срез функции при $inline$x_1=x_2$inline$:

image

Срез функции при $inline$x_2=x_1+3$inline$:

image

Приведенная выше функция имеет минимумы в точках: (-4, 0), (0, 0), (-3, 3), (2, 2), (-3, -4). Глобальным является минимум в точке (-3, 3).

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

Код
def get_tf_hyperbolic_potential_abs(n: int, a: List[float], c: List[List[float]], 
                                    p: List[List[float]], b: List[float]):
    """
    :param n: количество экстремумов
    :param a: коэффициенты, определяющие крутость функции в районе экстремума
    :param c: список координат экстремумов
    :param p: степени гладкости функции в районе экстремума
    :param b: список коэффициентов, определяющих значения функции в точках экстремумов
    """
    def func(x):
        value = 0
        for i in range(n):
            res = 0
            for j in range(len(x)):
                res = res + np.abs(x[j] - c[i][j]) ** p[i][j]
            res = a[i] * res + b[i]
            res = -(1 / res)
            value = value + res
        return value
    return func


Экспоненциальные потенциальные функции


Одноэкстремальная функция имеет вид:

$$display$$I_{Э,i}(x-c_i)=-d_i*exp\{ -b_i*\sum_{j=1}^m a_{ij}|x_j-c_{ij}|^{p_{ij}} \}, b_i>0, d_i>0$$display$$


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

$$display$$I(x)=\sum_{i=1}^N I_{Э,i}(x-c_i)$$display$$


Пример:

Аналитический вид функции

$$display$$I_{Э,1}(x-c_1)=-6*exp\{-1*[|x_1+4|^{0.3}+|x_2|^1]\},$$display$$


$$display$$I_{Э,2}(x-c_2)=-5*exp\{-2*[|x_1|^{1}+|x_2|^1]\},$$display$$


$$display$$I_{Э,3}(x-c_3)=-7*exp\{-0.5*[|x_1+3|^{0.6}+|x_2-3|^{1.1}]\},$$display$$


$$display$$I_{Э,4}(x-c_4)=-4*exp\{-1.5*[|x_1-2|^{1.3}+|x_2-2|^{0.8}]\},$$display$$


$$display$$I_{Э,5}(x-c_5)=-4.5*exp\{-0.8*[|x_1+3|^{1.5}+|x_2+4|^2]\},$$display$$


$$display$$I(x_1, x_2)=\sum_{i=1}^5 I_{Э,i}(x-c_i)$$display$$



График линий равных уровней представлен ниже:

image

Срез функции при $inline$x_1=x_2$inline$:

image

Срез функции при $inline$x_2=-x_1$inline$:

image

Приведенная выше функция имеет минимумы в точках: (-4, 0), (0, 0), (-3, 3), (2, 2), (-3, -4). Глобальным является минимум в точке (-3, 3).

Код для генерации экспоненциальной потенциальной функции
def get_tf_exponential_potential(n: int, a: List[float], c: List[List[float]], 
                                 p: List[List[float]], b: List[float]):
    """
    :param n: количество экстремумов
    :param a: коэффициенты, определяющих крутость функции в районе экстремума
    :param c: координаты экстремумов
    :param p: степени гладкости функции в районе экстремума
    :param b: значения функции в точках экстремумов
    """
    def func(x):
        value = 0
        for i in range(n):
            res = 0
            for j in range(len(x)):
                res = res + np.abs(x[j] - c[i][j]) ** p[i][j]
            res = (-b[i]) * np.exp((-a[i]) * res)
            value = value + res
        return value
    return func


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

Список литературы


Рубан А. И. Конструирование многоэкстремальных функций
Википедия. Тестовые функции для оптимизации

Комментарии (0)