[Перевод] Двумерные тестовые функции для оптимизации

8261f3703c8f26741f6deb95bf9bf7ba.jpg

Оптимизация функций — это область исследований, где поставлена задача найти некое входное значение [аргумент функции], результат которого — максимум или минимум данной функции. Алгоритмов оптимизации много, поэтому важно развивать алгоритмическое чутьё и исследовать алгоритмы на простых и легко визуализируемых тестовых функциях.

Двумерные функции принимают два входных значения (x и y) и выводят единожды вычисленное на основе входа значение. Эти функции — одни из самых простых для изучения оптимизации. Их преимущество в том, что они могут визуализироваться в виде контурного графика или графика поверхности, показывающего топографию проблемной области с оптимумом и уникальными элементами, которые отмечены точками. В этом туториале вы ознакомитесь со стандартными двумерными тестовыми функциями, которые можно использовать при изучении оптимизации функций. Давайте начнём.

Обзор туториала

Двумерная функция — это функция, которая принимает две входные переменные и вычисляет целевое значение. Можно представить две входные переменные как две оси на графике, x и y. Каждый вход в функцию является единственной точкой на графике, а результат вычисления функции — некоторая высота на графике.

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

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

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

  1. Унимодальные функции.

  1. Унимодальная функция 1.

  2. Унимодальная функция 2.

  3. Унимодальная функция 3.

  1. Мультимодальные функции.

  1. Мультимодальная функция 1.

  2. Мультимодальная функция 2.

  3. Мультимодальная функция 3.

Реализация каждой целевой функции будет представлена на Python в выведена в виде поверхности.

Все целевые функции являются функциями минимизации, то есть задача — найти аргументы, при которых значение функции минимально. Любая максимизирующая функция может быть заменена функцией минимизации путем добавления минуса ко всем её значениям. Аналогичным образом минимизирующая функция заменяется максимизирующей. Кроме того, все функции взяты из литературы, их придумал не я. Ссылки смотрите в разделе «Дальнейшее чтение».

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

Унимодальные функции

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

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

Унимодальная функция 1

Диапазон ограничен промежутком -5,0 и 5,0 и одним глобальным оптимумом в точке [0,0, 0,0].

# unimodal test function
from numpy import arange
from numpy import meshgrid
from matplotlib import pyplot
from mpl_toolkits.mplot3d import Axes3D

# objective function
def objective(x, y):
	return x**2.0 + y**2.0

# define range for input
r_min, r_max = -5.0, 5.0
# sample input range uniformly at 0.1 increments
xaxis = arange(r_min, r_max, 0.1)
yaxis = arange(r_min, r_max, 0.1)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a surface plot with the jet color scheme
figure = pyplot.figure()
axis = figure.gca(projection='3d')
axis.plot_surface(x, y, results, cmap='jet')
# show the plot
pyplot.show()

Код создаёт поверхность согласно графику функции.

График поверхности на основе унимодальной функции оптимизации 1График поверхности на основе унимодальной функции оптимизации 1

Унимодальная функция 2

Диапазон ограничен значениями -10,0 и 10,0 и одним глобальным оптимумом в точке [0,0, 0,0].

# unimodal test function
from numpy import arange
from numpy import meshgrid
from matplotlib import pyplot
from mpl_toolkits.mplot3d import Axes3D

# objective function
def objective(x, y):
	return 0.26 * (x**2 + y**2) - 0.48 * x * y

# define range for input
r_min, r_max = -10.0, 10.0
# sample input range uniformly at 0.1 increments
xaxis = arange(r_min, r_max, 0.1)
yaxis = arange(r_min, r_max, 0.1)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a surface plot with the jet color scheme
figure = pyplot.figure()
axis = figure.gca(projection='3d')
axis.plot_surface(x, y, results, cmap='jet')
# show the plot
pyplot.show()

Код создаёт поверхность согласно графику функции.

График унимодальной функции оптимизации 2График унимодальной функции оптимизации 2

Унимодальная функция 3

Диапазон ограничен -10,0 и 10,0 и одним глобальным оптимумом при [0,0, 0,0], функция известна как функция Изома.

# unimodal test function
from numpy import cos
from numpy import exp
from numpy import pi
from numpy import arange
from numpy import meshgrid
from matplotlib import pyplot
from mpl_toolkits.mplot3d import Axes3D

# objective function
def objective(x, y):
	return -cos(x) * cos(y) * exp(-((x - pi)**2 + (y - pi)**2))

# define range for input
r_min, r_max = -10, 10
# sample input range uniformly at 0.01 increments
xaxis = arange(r_min, r_max, 0.01)
yaxis = arange(r_min, r_max, 0.01)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a surface plot with the jet color scheme
figure = pyplot.figure()
axis = figure.gca(projection='3d')
axis.plot_surface(x, y, results, cmap='jet')
# show the plot
pyplot.show()

Код создаёт поверхность согласно графику функции.

График унимодальной функции оптимизации 3График унимодальной функции оптимизации 3

Мультимодальные функции

Мультимодальная функция — это функция с более чем одной »модой» или оптимумом (например долиной на графике).

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

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

Мультимодальная функция 1

Диапазон ограничен -5,0 и 5,0 и одним глобальным оптимумом при [0,0, 0,0]. Эта функция известна как функция Экли.

# multimodal test function
from numpy import arange
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import e
from numpy import pi
from numpy import meshgrid
from matplotlib import pyplot
from mpl_toolkits.mplot3d import Axes3D

# objective function
def objective(x, y):
	return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20

# define range for input
r_min, r_max = -5.0, 5.0
# sample input range uniformly at 0.1 increments
xaxis = arange(r_min, r_max, 0.1)
yaxis = arange(r_min, r_max, 0.1)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a surface plot with the jet color scheme
figure = pyplot.figure()
axis = figure.gca(projection='3d')
axis.plot_surface(x, y, results, cmap='jet')
# show the plot
pyplot.show()

Код создаёт поверхность согласно графику функции.

Мультимодальная функция оптимизации 1Мультимодальная функция оптимизации 1

Мультимодальная функция 2

Диапазон ограничен [-5,0 и 5,0], а функция имеет четыре глобальных оптимума при [3,0, 2,0], [-2,805118, 3,131312], [-3,779310, -3,283186], [3,584428, -1,848126]. Эта функция известна как функция Химмельблау.

# multimodal test function
from numpy import arange
from numpy import meshgrid
from matplotlib import pyplot
from mpl_toolkits.mplot3d import Axes3D

# objective function
def objective(x, y):
	return (x**2 + y - 11)**2 + (x + y**2 -7)**2

# define range for input
r_min, r_max = -5.0, 5.0
# sample input range uniformly at 0.1 increments
xaxis = arange(r_min, r_max, 0.1)
yaxis = arange(r_min, r_max, 0.1)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a surface plot with the jet color scheme
figure = pyplot.figure()
axis = figure.gca(projection='3d')
axis.plot_surface(x, y, results, cmap='jet')
# show the plot
pyplot.show()

Код создаёт поверхность согласно графику функции.

Мультимодальная функция оптимизации 2Мультимодальная функция оптимизации 2

Мультимодальная функция 3

Диапазон ограничен промежутком [-10,0 и 10,0] и функцией с четырьмя глобальными оптимумами в точках [8,05502, 9,66459], [-8,05502, 9,66459], [8,05502, -9,66459], [-8,05502, -9,66459]. Эта функция известна как табличная функция Хольдера.

# multimodal test function
from numpy import arange
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import sin
from numpy import e
from numpy import pi
from numpy import absolute
from numpy import meshgrid
from matplotlib import pyplot
from mpl_toolkits.mplot3d import Axes3D

# objective function
def objective(x, y):
	return -absolute(sin(x) * cos(y) * exp(absolute(1 - (sqrt(x**2 + y**2)/pi))))

# define range for input
r_min, r_max = -10.0, 10.0
# sample input range uniformly at 0.1 increments
xaxis = arange(r_min, r_max, 0.1)
yaxis = arange(r_min, r_max, 0.1)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a surface plot with the jet color scheme
figure = pyplot.figure()
axis = figure.gca(projection='3d')
axis.plot_surface(x, y, results, cmap='jet')
# show the plot
pyplot.show()

Код создаёт поверхность согласно графику функции.

График мультимодальной функции оптимизации 3График мультимодальной функции оптимизации 3

Резюме

Если вы хотите глубже погрузиться в тему — обратите внимание на сопутствующие материалы ниже.

fd55943d24b0abcb220c7125b978f311.png

Узнайте, как прокачаться в других специальностях или освоить их с нуля:

Другие профессии и курсы

ПРОФЕССИИ

КУРСЫ

© Habrahabr.ru