Стохастические алгоритмы оптимизации

Question

Скажем, у нас есть 2 алгоритма стохастической оптимизации (Генетические алгоритмы, Оптимизация роя частиц, Поиск кукушки и т. Д.), A и B, и мы хотим найти глобальные максимумы функции. Тогда, если алгоритм A работает лучше, чем алгоритм B, при оптимизации функции F в одномерном пространстве поиска, он также работает лучше, чем B, при оптимизации функции F в N-мерном пространстве поиска?

Я буду ссылаться на функцию F в N измерениях по F_ND. Обратите внимание, что F_1D и F_ND - это одна и та же функция, за исключением другого числа измерений; "пейзаж" абсолютно одинаков, только разной размерности.

Пример: для функции DeJong имеем:

F_1D(x) = x[0]*x[0]
F_5D(x) = x[0]*x[0] + x[1]*x[1] + x[2]*x[2] + x[3]*x[3] + x[4]*x[4]

F_1D и F_5D имеют одинаковые "тип"/"аспект"

... поставить иначе:

Если general_performance(A,F_1D) > general_performance(B,F_1D), тогда выполняется ли general_performance(A,F_ND) > general_performance(B,F_ND) (для большего N, конечно) также?

Answer 1

В настоящее время неизвестно, будет ли такое свойство иметь. Теорема об отсутствии бесплатного обеда (NFL) здесь не в полной мере применима, поскольку вы говорите об очень ограниченном наборе проблем. Проблема, которую вы нарисовали, все еще независима в более высоких измерениях (можно оптимизировать каждую переменную в отдельности и достичь глобального оптимума). В этом случае можно утверждать, что вы можете разделить эту проблему на 5 задач одного измерения и решить каждое измерение отдельно. Это всегда должно быть дешевле, чем решать их вместе (при условии, что никакие измерения не являются свободными).

Я думаю, что это во многом зависит от типа проблемы, но в целом я бы не поверил, что такое свойство имеет место и что для некоторой проблемы и некоторого N можно найти алгоритм B такой, что A лучше, чем B <=> размерность < N и B лучше, чем A <=> размерность>= N.