Найти глобальный минимум дискретно определенной функции

У меня есть четырехпараметрическая функция, для которой у меня нет математической формы, потому что она на самом деле является результатом нескольких отдельных процессов. В своей простейшей форме его можно представить как черный ящик, который возвращает значение, зависящее от значений параметров a,b,c,d, с помощью которых он вызывается. Вот как это выглядит: 

def my_func(a, b, c, d):
    # Make lots of calculations here to come up with 'func_value',
    # which depends on the values of the parameters given a,b,c,d.
    func_value = x(a, b, c, d)
    return func_value
Пространство этих четырех параметров ограничено не только по диапазону, но и дискретно. Это означает, что параметры могут иметь определенные значения: 
a = [0.004, 0.006, 0.008, 0.010, ...]
b = [0.2, 0.25, 0.3, 0.35, ...]
c = [0.0, 0.01, 0.02, 0.03, ...]
b = [10.1, 10.2, 10.3, 10.4, ...]

, а не те, что между ними (т. е.: они варьируются в шагах).

Мне нужно найти глобальный минимум для этой функции, т. е.: набор, состоящий из тех частных значений параметров [a_i,b_j,c_k,d_l], который возвращает минимальное значение, возможное для my_func.

Я знаю о существовании алгоритмов, таких как scipy.оптимизировать.отжигать или генетические алгоритмы, подобные тем, которые определены в DEAP, PyBrain или Pyevolve это должно быть применимо к такого рода задачам оптимизации. Я не уверен в том, какой из них я мог бы использовать, имея в виду ограничения, наложенные моим кодом, т. е.: функция множественных (четырех) параметров без математической формы, ограниченные и дискретные пространства для параметров. Обзор всех этих методов может занять много времени, поэтому любые указания на то, что я, вероятно, попытаюсь применить, будут высоко оценены.
2 2
python scipy mathematical-optimization genetic-algorithm

2 ответа:

Все алгоритмы "восхождения на холм" основаны на предположении, что небольшие изменения на входе приводят к (как правило) небольшим изменениям на выходе. Ваше описание задачи не содержит абсолютно никаких ограничений на форму графа функций (за исключением вашего интереса к вероятностному восхождению на холм, что подразумевает, что оно действительно применимо к вашей области). Например, вы не можете использовать hill climbing для криптографической хэш-функции.

Но лучший алгоритм в значительной степени зависит от дополнительных характеристики задачи:

  1. Имитация отжига начинается с больших "прыжков", которые становятся все меньше, идея заключается в том, что вы оказываетесь на самом большом" холме " (или долине, поскольку вы формулируете свою цель как минимум), прежде чем ваши прыжки становятся слишком маленькими, и вы попадаете в ловушку.

  2. Генетический алгоритм хорош, когда различные параметры или их группы полунезависимы друг от друга. Идея заключается в том, что малые группы параметров могут быть независимо оптимизируется локальным восхождением на холм, и функция рекомбинации может объединить несколько оптимизированных подгрупп для получения суперрешения. Это бесполезно, если все параметры тесно связаны.

Другие алгоритмы также лучше всего подходят для различных профилей задач. (И, к сожалению, ваше описание проблемы, кажется, не включает в себя соответствующие свойства.)

Короче говоря: в то время как математическая формула не является требованием, вам нужно некоторое понимание того, как ведет себя граф вашей функции, и любые инварианты проекции (величины, которые вносят вклад в x, но не зависят от всех четырех параметров a, b, c, d). Это последнее также будет полезно для ускорения вычисления значений функции, что, как вы говорите, чрезвычайно дорого. Я бы посоветовал вам, по крайней мере, построить график некоторых срезов с низким разрешением в пространстве поиска. Они могут дать вам некоторые идеи.

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

1

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

Для начала я бы предложил один из следующих классических алгоритмы:

1