Минимизация f (x, y), где x и y - целые числа

Question

Мне было интересно, есть ли у кого-нибудь предложения по минимизации функции f (x, y), где x и y - целые числа. Я исследовал множество методов минимизации и оптимизации, таких как BFGS и другие из GSL, и вещи из Numerical Recipes. До сих пор я пытался внедрить несколько различных схем. Первые работы по выбору направления наибольшего спуска f (x + 1, y), f (x-1, y), f (x, y + 1), f (x, y-1) и следуют этому направлению с минимизацией линии. Я также пробовал использовать метод простого спуска (Nelder-Mead). Оба метода застряли далеко от минимума. Они оба работают над более простыми функциями, такими как поиск минимума параболоида, но я думаю, что и то и другое, и особенно первое, предназначены для функций, где x и y являются вещественными (удваивает). Еще одна проблема заключается в том, что мне нужно называть f (x, y) как можно меньше раз. Он разговаривает с внешним оборудованием и занимает пару секунд для каждого вызова. Любые идеи для этого были бы весьма признательны.

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

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) 
} 

Answer 1

Как вы определяете f (x, y)? Минимизация - сложная проблема, в зависимости от сложности вашей функции.

Генетические алгоритмы могут быть хорошим кандидатом.

Ресурсы:

Genetic Algorithms in Search, Optimization, and Machine Learning

Implementing a Genetic Algorithms in C#

Simple C# GA

Answer 2

вы смотрели на генетические алгоритмы? Они очень, очень хорошо разбираются в минимумах и максимумах, избегая локальных минимумов/максимумов.

Answer 3

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

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

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

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

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

Answer 4

Есть много, много решений здесь. Фактически, на эту тему есть целые книги и учебные дисциплины. Я читаю отличный сейчас: How to Solve It: Modern Heuristics.

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

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

Answer 5

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

В частности, я бы рекомендовал посмотреть на non-linear programming и gradient descent. Оба они выглядят вполне подходящими для вашего приложения.

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

Answer 6

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

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

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

Answer 7

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

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) 
} 

Answer 8

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

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

\ SQRT ((а-a_desired)^2 + (б-b_desired)^2 + (с-c_desired)^2)

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

где х = (а, б, в) и Pos (у) = тах (у, 0) означает, что мы хотим "позитивную часть" (это составляет для ваших операторов if). Наконец, мы хотим ограничить себя решениями, где x целая оценка.

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

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

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

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