red_b February 21, 2018 at 17:43

Test Method Design Methods

From the sandbox

In the course of working with global optimization, a need arose for constructing multi-extreme test functions. Often, most of the ready-made functions, for example from Wikipedia , are not suitable for the correct evaluation of the algorithm. Some functions are single extreme; for such examples, local search algorithms are more suitable, while the other relates to ravine ones. For global optimization, it is necessary to use multiextremals, where the extrema significantly differ in magnitude.

Let us consider some methods that make it easy to construct test multiextremal functions, while allowing us to set specific properties: the Feldbaum method, functions based on hyperbolic potentials, and functions based on exponential potentials. In addition to these methods, there are harmonic multi-extreme functions and their various combinations.

Feldbaum Method

This method is based on simple power one-extremal functions of the form:

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

The above function will have a minimum at a point

$ inline $ c_i $ inline $

, and the value at this point will be equal

$ inline $ b_i $ inline $

.
If

$ inline $ p_ {ij}> 0 $ inline $

(the degree of smoothness of the function in the region of the extremum), then at the minimum point the function will be smooth, and if

$ inline $ 0 <p_ {ij} \ le1 $ inline $

, then at the minimum point the function will be angular (not differentiable).

Coefficient

$ inline $ a $ inline $

responsible for the degree of coolness of the function in the extremum region.
To construct a multiextremal function, it is necessary to apply the minimum operator to the set of one-extremal functions. The general view will be as follows:

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

Example:

Analytical view of the function

$$$ 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 $$$

The graph of lines of equal levels of the given function will look as follows:

Slice function at

$ inline $ x_1 = x_2 $ inline $

Slice function at

$ inline $ x_2 = 4 $ inline $

The above function has minima at the points: (0, 0), (-2, 0), (0, -2), (0, 4), (2, 2), (4, 0), (4, 4 ), (-4, 4), (-4, -4), (3, -5). Global is the minimum at the point (0, 0).
Code for generating test functions:

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

Hyperbolic Potential Functions

The one-extremum function has the form:

$$$ display $$ I_ {D, 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 $$$

This function also has a minimum at a point

$ inline $ c_i $ inline $

, its depth is determined by

$ inline $ d_i $ inline $

. The degree of slope is set using the coefficient

$ inline $ b_i $ inline $

, the larger it is, the narrower the extremum region and the steeper the function.

To obtain a multi-extreme function, it is necessary to apply the summation operator:

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

Example:

Analytical view of the function

$$$ 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_ {D, i} (x-c_i) $$ display $$$

The graph of lines of equal levels of the given function will look as follows:

Slice function at

$ inline $ x_1 = x_2 $ inline $

Slice function at

$ inline $ x_2 = x_1 + 3 $ inline $

The above function has minima at the points: (-4, 0), (0, 0), (-3, 3), (2, 2), (-3, -4). Global is the minimum at the point (-3, 3).

Below the spoiler is the code for generating a test function with additive modular functions in the denominator.

The code

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

Exponential potential functions

The one-extremum function has the form:

$$$ display $$ I_ {E, 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 $$$

Here, all letter designations have the same meaning as in the previous method.
To obtain a multi-extreme function, we also use the summation operator:

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

Example:

Analytical view of the function

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

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

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

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

$$$ display $$ I_ {E, 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_ {Uh, i} (x-c_i) $$ display $$$

The graph of lines of equal levels is presented below:

Slice function at

$ inline $ x_1 = x_2 $ inline $

Slice function at

$ inline $ x_2 = -x_1 $ inline $

The above function has minima at the points: (-4, 0), (0, 0), (-3, 3), (2, 2), (-3, -4). Global is the minimum at the point (-3, 3).

Code for generating an exponential potential function

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

In addition to the above methods, harmonic functions can be used, however, their construction is a more complex process. And the main disadvantage is the inability to control all local lows. You can also combine all of these methods to get even more complex functions.

List of references

Ruban A. I. Construction of multiextremal functions
Wikipedia. Test functions for optimization

Tags:

Test Method Design Methods

Feldbaum Method

Hyperbolic Potential Functions

Exponential potential functions

List of references

Also popular now: