Сообщество Engee
Engee Community
/
Примеры и проекты
/
Оптимизация стохастической целевой функции

Оптимизация стохастической целевой функции

Автор
avatar-artpgchartpgch
Notebook

Оптимизация стохастической целевой функции

Методы оптимизации

Методы IPNewton и GradientDescent можно считать аналогами функции fmincon в Matlab, поскольку они оба предназначены для решения задач нелинейной оптимизации с ограничениями. Fmincon использует различные алгоритмы, включая градиентный спуск и методы Ньютона, для нахождения минимума целевой функции с учетом ограничений (линейных и нелинейных).

Методы NelderMead и SimulatedAnnealing могут рассматриваться как аналогичные функции patternsearch, поскольку все они предназначены для решения задач нелинейной оптимизации без явного использования производных.
Patternsearch в Matlab является глобальным оптимизационным методом, который исследует пространство решений с использованием стратегий поиска по шаблону, что позволяет эффективно решать задачи с множеством локальных минимумов. Он не требует градиента и работает на основе итерационных шагов, что аналогично методам Nelder-Mead и SimulatedAnnealing, которые также не используют производные.

NelderMead — это эвристический метод, который ищет минимум путём перемещения по многоугольной оболочке (симплексу) в многомерном пространстве, адаптируя форму симплекса на каждой итерации для улучшения результата. Это делает его аналогичным patternsearch, который также ориентирован на глобальный поиск через последовательные оценки, но с иной геометрией шагов.

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

Импортируем необходимые пакеты

In [ ]: 
import Pkg
Pkg.add("Optim")
Pkg.add("Random")
Pkg.add("Plots")
using Optim, Random, Plots

Инициализируем исходные данные

In [ ]: 
# Инициализация исходных данных:
X0 = [2.5, -2.5] # Стартовая точка
LB = [-5.0, -5.0] # Нижняя граница
UB = [5.0, 5.0] # Верхняя граница
range = [LB[1] UB[1]; LB[2] UB[2]] # Диапазон
pts = 100 # Количество точек
iter = false # Показывать итерации
detailed = true # Выводить подробный результат

Гладкая целевая функция

In [ ]: 
# Гладкая целевая функция:
function smFcn(x)
    #if any(x .< LB) || any(x .> UB)
    #    return Inf
    #else
        return x[1]^3 - x[2]^2 + 100 * x[2] / (10 + x[1])
    #end
end

Стохастическая целевая функция

Добавим к гладкой целевой функции амплитуду шума, умноженную на случайное число, таким образом получится стохастическая целевая функция:

In [ ]: 
# Стохастическая целевая функция:
function stFcn(x)
    peaknoise = 4.5 # Амплитуда шума
    if any(x .< LB) || any(x .> UB)
        return Inf
    else
        return x[1]^3 - x[2]^2 + 100 * x[2] / (10 + x[1]) + peaknoise * randn()
    end
end

Функция для построения целевой функции

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

In [ ]: 
# Функция построения целевой функции:
function buildFcn(Fcn,range)
    span = diff(range', dims=1) ./ (pts - 1)
    X = range[1, 1]:span[1]:range[1, 2]
    Y = range[2, 1]:span[2]:range[2, 2]
    values = zeros(Float64, pts * pts, 1)
    k = 1
    for i in 1:pts
        for j in 1:pts
            values[k] = Fcn([X[i], Y[j]])
            k += 1
        end
    end
    values = reshape(values, pts, pts)
        return X, Y, values
    end

Оптимизация гладкой целевой функции

Выполним оптимизацию гладкой целевой функции методами IPNewton и GradientDescent (аналоги метода interior-point функции fmincon в Matlab)

In [ ]: 
# Оптимизация гладкой целевой функции методами IPNewton и GradientDescent
# аналоги метода interior-point функции fmincon в Matlab
smResultIP = optimize(smFcn, LB, UB, X0, IPNewton(), Optim.Options(show_trace = iter))
smResultGD = optimize(OnceDifferentiable(smFcn, X0), LB, UB, X0, Fminbox(GradientDescent()), Optim.Options(show_trace = iter))

Оптимизация стохастической целевой функции

Методы IPNewton и GradientDescent

Выполним оптимизацию стохастической целевой функции методами IPNewton и GradientDescent (аналоги метода interior-point функции fmincon в Matlab)

In [ ]: 
Random.seed!(0)
# Оптимизация стохастической целевой функции методами IPNewton и GradientDescent
# аналоги метода interior-point функции fmincon в Matlab
#stResult = optimize(OnceDifferentiable(stFcn, X0), LB, UB, X0, Fminbox(GradientDescent()), Optim.Options(show_trace = true))
stResultIP = optimize(stFcn, LB, UB, X0, IPNewton(), Optim.Options(show_trace = iter))
stResultGD = optimize(OnceDifferentiable(stFcn, X0), LB, UB, X0, Fminbox(GradientDescent()), Optim.Options(show_trace = iter))

Методы NelderMead и SimulatedAnnealing

Выполним оптимизацию стохастической целевой функции методами NelderMead и SimulatedAnnealing
(аналоги функции patternsearch в Matlab)

In [ ]: 
# Оптимизация стохастической целевой функции методами NelderMead и SimulatedAnnealing
# аналоги функции patternsearch в Matlab
stResultNM = optimize(stFcn, LB, UB, X0, NelderMead(), Optim.Options(show_trace = iter))
stResultSA = optimize(stFcn, LB, UB, X0, SimulatedAnnealing(), Optim.Options(show_trace = iter))

Выведем результаты оптимизации гладкой целевой функции:

In [ ]: 
# Вывод результатов
if detailed
    println("\nГладкая целевая функция:\n")
    println("\nМетод IPNewton")
    println("Найденная точка минимума: ", Optim.minimizer(smResultIP))
    println("Значение функции в найденной точке минимума: ", Optim.minimum(smResultIP),"\n")
    println("\nМетод GradientDescent")
    println("Найденная точка минимума: ", Optim.minimizer(smResultGD))
    println("Значение функции в найденной точке минимума: ", Optim.minimum(smResultGD),"\n")
end

Гладкая целевая функция:


Метод IPNewton
Найденная точка минимума: [-4.999999999999992, -4.999999999999973]
Значение функции в найденной точке минимума: -249.99999999999847


Метод GradientDescent
Найденная точка минимума: [-4.999999999670888, -4.999999998957812]
Значение функции в найденной точке минимума: -249.99999993746877

Трёхмерное отображение гладкой функции

Построим трёхмерную фигуру гладкой целевой функции с указанием на ней стартовой точки и найденных оптимальных значений. Обратите внимание: так как результаты выполнения методов IPNewton и GradientDescent, точки найденных оптимальных значений накладываются друг на друга.

In [ ]: 
plotlyjs()
# Отображение гладкой функции
smX, smY, smVal = buildFcn(smFcn, range)
smFig = surface(smX, smY, smVal; alpha = 0.9, c=:viridis, legend=:bottomright, legendfontsize = 7, colorbar = false, title = "Гладкая целевая функция", titlefont = font(12))
plot!(smFig, camera=(-19, -4)) 
scatter!(smFig, [X0[1]], [X0[2]], [smFcn(X0)+30], color=:red, markersize = 2, label = "Стартовая точка", seriestype = :scatter3d)
scatter!(smFig, [Optim.minimizer(smResultIP)[1]], [Optim.minimizer(smResultIP)[2]], [Optim.minimum(smResultIP)], color =:magenta, marker = (:diamond, 2), label = "Метод IPNewton", seriestype =:scatter3d)
scatter!(smFig, [Optim.minimizer(smResultGD)[1]], [Optim.minimizer(smResultGD)[2]], [Optim.minimum(smResultGD)], color =:green, marker = (:diamond, 2), label = "Метод GradientDescent", seriestype =:scatter3d)
display(smFig)

Целевая функция гладкая (дважды непрерывно дифференцируемая). На представленной фигуре найденные точки минимума накладываются друг на друга и соответствуют действительности. Для оптимизации гладкой целевой функции подходят методы IPNewton и GradientDescent.

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

In [ ]: 
# Вывод результатов
if detailed
    println("\n\nСтохастическая целевая функция - неподходящие методы:\n")
    println("\nМетод IPNewton")
    println("Найденная точка минимума: ", Optim.minimizer(stResultIP))
    println("Значение функции в найденной точке минимума: ", Optim.minimum(stResultIP),"\n")
    println("\nМетод GradientDescent")
    println("Найденная точка минимума: ", Optim.minimizer(stResultGD))
    println("Значение функции в найденной точке минимума: ", Optim.minimum(stResultGD),"\n")
    println("\n\nСтохастическая целевая функция - подходящие методы:\n")
    println("\nМетод NelderMead")
    println("Найденная точка минимума: ", Optim.minimizer(stResultNM))
    println("Значение функции в найденной точке минимума: ", Optim.minimum(stResultNM),"\n")
    println("\nМетод SimulatedAnnealing")
    println("Найденная точка минимума: ", Optim.minimizer(stResultSA))
    println("Значение функции в найденной точке минимума: ", Optim.minimum(stResultSA),"\n")
end


Стохастическая целевая функция - неподходящие методы:


Метод IPNewton
Найденная точка минимума: [2.4999421713343426, -2.4999864886566523]
Значение функции в найденной точке минимума: -0.17441677198130812


Метод GradientDescent
Найденная точка минимума: [2.5028070939500946, -2.502871909347813]
Значение функции в найденной точке минимума: -13.320807591581392



Стохастическая целевая функция - подходящие методы:


Метод NelderMead
Найденная точка минимума: [-4.984159874916077, -4.605382007360452]
Значение функции в найденной точке минимума: -253.10101564285972


Метод SimulatedAnnealing
Найденная точка минимума: [-4.951924251950035, -4.7539826883835685]
Значение функции в найденной точке минимума: -245.68220743237163

Трёхмерное отображение стохастической функции

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

In [ ]: 
# Отображение стохастической функции
stX, stY, stVal = buildFcn(stFcn, range)
stFig = surface(stX, stY, stVal; alpha = 0.9, c=:viridis, legend=:bottomright, legendfontsize = 7, colorbar = false, title="Стохастическая целевая функция", titlefont = font(12))
plot!(stFig, camera=(-19, -4)) 
scatter!(stFig, [X0[1]], [X0[2]], [stFcn(X0)+30], color=:red, markersize = 2, label = "Стартовая точка", seriestype = :scatter3d)
scatter!(stFig, [Optim.minimizer(stResultIP)[1]], [Optim.minimizer(stResultIP)[2]], [Optim.minimum(stResultIP)], color=:yellow, marker = (:diamond, 2), label = "Метод IPNewton", seriestype =:scatter3d)
scatter!(stFig, [Optim.minimizer(stResultGD)[1]], [Optim.minimizer(stResultGD)[2]], [Optim.minimum(stResultGD)], color=:cyan, marker = (:diamond, 2), label = "Метод GradientDescent", seriestype =:scatter3d)
scatter!(stFig, [Optim.minimizer(stResultNM)[1]], [Optim.minimizer(stResultNM)[2]], [Optim.minimum(stResultNM)], color=:blue, marker = (:diamond, 2), label = "Метод NelderMead", seriestype =:scatter3d)
scatter!(stFig, [Optim.minimizer(stResultSA)[1]], [Optim.minimizer(stResultSA)[2]], [Optim.minimum(stResultSA)], color=:green, marker = (:diamond, 2), label = "Метод SimulatedAnnealing", seriestype =:scatter3d)
display(stFig)

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

На полученном изображении явно видно, что точки минимума, найденные методами IPNewton и GradientDescent не соответствуют действительности. А точки минимума, найденные методами NelderMead и SimulatedAnnealing практически соответствуют действительности.

Выводы

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

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

Группа видимости
ПубличноПросматривать контент могут все пользователи сообщества

Тип

Интерактивные скрипты

Краткое описание

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

Связанные материалы

Пусто

Теги

Категории

Расчеты в EngeeГрафики и визуализация2-D и 3-D графикиПоверхности
Расчеты в EngeeПрограммированиеJulia
Расчеты в EngeeМатематика и оптимизацияОптимизация

Языки

    Julia

Форматы

    engee
    ngscript

Уровень

    Средний

Статус

Опубликовано

Обновлено

Источник

Сообщество