Минимизация f (x, y), где X и Y являются целыми числами

Have you looked at genetic algorithms? They are very, very good at finding minimums and maximums, while avoiding local minimum/maximums.

Здесь есть много, много решений. Фактически, существуют целые книги и учебные дисциплины, основанные на предмете. Я сейчас читаю отличный: Как это решить: современная эвристика .

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

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

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

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

Если бы вы могли предоставить более подробную информацию, я мог бы предложить кое-что более конкретное.

Если это произвольная функция, нет удобного способа сделать это.

Предположим, у нас есть функция, определенная как:

f(x, y) = 0 for x==100, y==100
          100 otherwise

Как любой алгоритм может реально найти (100, 100) как минимум? Это может быть любая возможная комбинация значений.

Вы знаете что-нибудь о тестируемой функции?

Ответ Джона Скита правильный. Вам действительно нужна информация о f и его производных, даже если f везде непрерывно.

Самый простой способ оценить трудности того, что вы спрашиваете (минимизация f только для целых значений), - это просто подумать о f: R- > R (f - вещественная функция от вещественных чисел) одной переменной, которая делает большие колебания между отдельными целыми числами. Вы можете легко построить такую ​​функцию, чтобы не было никакой корреляции между локальными минимумами на действительной прямой и минимумами целых чисел, а также не было никакой связи с первой производной.

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

Извините, форматирование было таким плохим раньше. Вот пример функции ошибок

double Error(x,y)
{
SetDeviceParams(x,y);
double a = QueryParamA();
double b = QueryParamB();
double c = QueryParamC();
double _fReturnable = 0;
if(a>=A_desired)
{
  _fReturnable+=(A_desired-a)*(A_desired-a);
}
if(b>=B_desired)
{
 _fReturnable+=(B_desired-b)*(B_desired-b);
}
if(c>=C_desired)
{
  _fReturnable+=(C_desired-c)*(C_desired-c);
}
return Math.sqrt(_fReturnable)
}

Итак, давайте посмотрим на вашу задачу с помощью математики. Все это при условии, что я понимаю ваша проблема полностью. Не стесняйтесь поправлять меня, если я ошибаюсь.

мы хотим минимизировать следующее:

\ sqrt ((a-a_desired) ^ 2 + (b-b_desired) ^ 2 + (c-c_desired) ^ 2)

или в других обозначениях || Pos (x - x_desired) || _2

где x = (a, b, c) и Pos (y) = max (y, 0) означает, что нам нужна «положительная часть» (это учитывает для ваших операторов if). Наконец, мы хотим ограничить себя к решениям, где x имеет целочисленное значение.

В отличие от вышеупомянутых плакатов, я не думаю, что генетические алгоритмы - это то, что вам вообще нужно.
На самом деле, я думаю, что решение намного проще (при условии, что я понимаю вашу проблему).

1) Запустите любую процедуру оптимизации для указанной выше функции. Это даст вам решение x ^ * = (a ^ *, b ^ *, c ^ *). Поскольку эта функция возрастает относительно к переменным, лучшее целочисленное решение, на которое вы можете надеяться, это (ceil (a ^ *), ceil (b ^ *), ceil (c ^ *)).

Теперь вы говорите, что вашу функцию, возможно, трудно вычислить. Есть инструменты для этого, которые не основаны на эвристике. Под названием Derivative-Free Оптимизация. Люди используют эти инструменты для оптимизации цели на основе моделирования (у меня даже слышал о случае, когда целевая функция основана на урожайности кукареки!)

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