Я пытаюсь создать алгоритм для оптимизации наблюдаемой f(x), которая зависит от одной переменной x. Я называю это наблюдаемой, потому что это не какая-то известная функция, которую я могу дифференцировать, а некоторая величина, которую я исследую (наблюдаю) для входного значения x.
Теперь функция f(x) имеет максимум, который я и пытаюсь найти. На самом деле это тоже не очень сложная функция; это более или менее похоже на параболу с одним максимумом. Поэтому я считаю, что это относится к классу проблем с поиском оптимизации. Или, может быть, поиск моделей? Оптимизация без деривативов?
Но есть некоторые сложности. Во-первых, система проявляет гистерезис; если я прослежу путь {x_0, x_1, ..., x_N} и наблюдаю f(x) в каждой точке дважды подряд или прослежу путь назад в обратном порядке, я не получу одинаковые значения. И что более важно, максимум не будет в одном месте; кривая обычно немного сдвигается, и поэтому «история» не вполне заслуживает доверия. Поэтому нельзя просто провести исчерпывающий поиск по значениям параметров и go назад, так как максимум, вероятно, переместился бы. Но это происходит только тогда, когда вы делаете большие развертки в x; если вы измените его постепенно, f(x) будет вести себя хорошо.
В дополнение к вышесказанному в системе также присутствует некоторый шум; это в основном означает, что при выполнении очень маленьких шагов направление, в котором изменяется f(x), не всегда является правильным, поскольку это могло быть шумовым всплеском.
Мне было интересно, есть ли у кого-нибудь идея о том, как решать этот тип проблемы алгоритмически. В конце я напишу код на python, но псевдокод / идеи / другой язык были бы совершенно полезны. Ниже я опишу то, что я придумал сам, что, возможно, еще больше прояснит вещи:
inputs: initial_step, minimal_step
direction = 1
step = initial_step
x_current = x #measure the current value of x, basically free
f_current = observe_f() #observe the value of f(x) at the current x, costs a little
while step => minimal_step:
x = x_current + step*direction #set a new value of x, somewhat expensive
f = observe_f() #observe the new value of f
if f < f_current:
direction = direction*-1
f_current = f
if direction == 1:
step = step/2
else:
f_current = f
Это просто шаг x (начиная с указанного начального шага) и посмотрим, увеличилось или уменьшилось f , Если оно увеличилось, продолжайте идти в этом направлении. Если оно уменьшилось, сделайте шаг в обратном направлении. Если он уменьшается вдвое подряд, то половина размера шага, так как мы явно превышаем максимум. Проблема прекращается, когда размер шага падает ниже определенного минимума. Теперь это кажется достаточно надежным, потому что вы находите максимум, превышая его все меньше и меньше. И если вы сбились с пути из-за шума / гистерезиса, через некоторое время вы, как правило, окажетесь на правильном пути, так как все это приведет к неправильному направлению на одну или две итерации и уменьшит размер шага ,
Но алгоритм не особо умный. Если minimal_step во много раз меньше, чем initial_step, вы будете довольно долго колебаться вокруг максимума, получая очень мало, выполняя эти маленькие, бесполезные шаги. Но если я сделаю их слишком похожими, вы рискуете, что после нескольких случаев шума / гистерезиса ваша оптимизация остановится. Это одна из вещей, которую я хотел бы улучшить. Но я доволен любым моментом ввода, а также тем, что предполагает совершенно другой подход.