Как автоматически настроить параметры алгоритма?

Question

Вот настройка:

У меня есть алгоритм, который может быть успешным или неудачным. Я хочу, чтобы это удалось с максимально возможной вероятностью. Вероятность успеха зависит от некоторых параметров (и некоторых внешних обстоятельств):

struct Parameters {
  float param1;
  float param2;
  float param3;
  float param4;
  // ...
};

bool RunAlgorithm (const Parameters& parameters) {
  // ...
  // P(return true) is a function of parameters.
}

Как (автоматически) найти лучшие параметры при наименьшем количестве вызовов RunAlgorithm? Я был бы особенно счастлив с библиотекой readl.

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

• Вероятность успеха является гладкой функцией параметров и имеют единый глобальный оптимум.
• Существует около 10 параметров, большинство из которых настраиваются независимо (но некоторые являются взаимозависимыми)
• Я запусту настройку за ночь, я смогу обработать около 1000 вызовов алгоритма Run.

Пояснение:

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

Дополнительные уточнения:

RunAlgorithm на самом деле игровой алгоритм. Он играет целую игру (го или шахматы) против фиксированного противника. Я могу сыграть 1000 игр за ночь. Каждую ночь другой противник.

Я хочу посмотреть, нужны ли разным оппонентам разные параметры.

RunAlgorithm является плавным в том смысле, что небольшое изменение параметра лишь немного меняет алгоритм.

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

Я мог бы попытаться оптимизировать каждый параметр независимо (что привело бы к 100 прогонам на параметр), но я предполагаю, что есть некоторые зависимости.

Вся проблема заключается в разумном использовании скудных данных.

Игры очень рандомизированы, с этим проблем нет.

Answer 1

Может быть, вы ищете генетические алгоритмы .

Answer 2

Основная проблема, с которой вы столкнулись, состоит в том, что при десяти параметрах 1000 прогонов практически ничего не значат, учитывая, что для каждого прогона все, что у вас есть, это результат «истина / ложь», а не «Р» (успех), связанный с параметрами.

Вот идея, которая, с одной стороны, может наилучшим образом использовать ваши 1000 прогонов, а с другой стороны, также иллюстрирует неразрешимость вашей проблемы. Давайте предположим, что десять параметров действительно независимы. Выберите два значения для каждого параметра (например, «высокое» значение и «низкое» значение). Существует 1024 способа выбора уникальных комбинаций этих значений; запустите свой метод для каждой комбинации и сохраните результат. Когда вы закончите, у вас будет 512 тестовых прогонов для каждого значения каждого параметра; с предположением независимости, что может дать вам достойную оценку условной вероятности успеха для каждого значения. Анализ этих данных должен дать вам небольшую информацию о том, как установить ваши параметры, и может предложить уточнения ваших «высоких» и «низких» значений для будущих ночей. В глубине души я выискиваю ANOVA в качестве, возможно, полезного статистического инструмента здесь.

Очень расплывчатый совет ... но, как уже было отмечено, это довольно расплывчатая проблема.

Answer 3

Почему бы не позволить программе бороться с самим собой? Возьмем некоторый вектор v (параметры) и дайте ему бороться с v + (0.1,0,0,0, .., 0), скажем, 15 раз. Затем возьмите победителя и измените другой параметр и так далее. Достаточно удачи, вы получите сильного игрока, способного победить большинство других.

Предыдущий ответ (большая часть его неактуальна после редактирования вопроса) :

С этими допущениями и таким уровнем обобщения вы ничего не достигнете (кроме, возможно, результата невозможности).

Основной вопрос: можете ли вы изменить алгоритм так, чтобы он возвращал вероятность успеха, а не результат одного эксперимента? Затем используйте подходящую оптимизацию методику (никто не скажет вам, что при таких общих предположениях). В Haskell вы можете даже изменить код, чтобы он находил вероятность в простых случаях ( монада вероятностей , вместо того, чтобы давать единственный результат. Как уже упоминалось, вы можете использовать генетический алгоритм, используя вероятность в качестве функции пригодности). Если у вас есть формула, используйте систему компьютерной алгебры , чтобы найти максимальное значение.

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

Плавный или непрерывный? Если гладко, вы можете использовать дифференциальное исчисление ( множители Лагранжа? ). Вы даже можете, с небольшими изменениями в коде (при условии, что ваш язык программирования достаточно общий), автоматически вычислять производные, используя автоматическое дифференцирование .

Я запусту настройку за ночь, я смогу обработать около 1000 вызовов алгоритма Run.

Этот комплекс? Это позволит вам проверить два возможных значения (2 ¹⁰ = 1024) из множества чисел с плавающей запятой. Вы даже не определите порядок величины или даже порядок порядка.

Существует около 10 параметров, большинство из которых настраиваются независимо (но некоторые являются взаимозависимыми)

Если вы знаете, что является независимым, исправьте некоторые параметры и измените те, которые не зависят от них, как в случае «разделяй и властвуй». Очевидно, что гораздо лучше настроить два алгоритма с 5 параметрами.

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

Answer 4

Специально для настройки параметров игровых агентов вас может заинтересовать CLOP

http://remi.coulom.free.fr/CLOP/

Answer 5

Ответ на этот вопрос зависит от:

1. Диапазон параметров. Могут ли ваши параметры иметь маленький или большой диапазон значений?
2. Оценка игры. Должен ли он быть логическим или гладкой функцией?

Одним из подходов, который кажется естественным для этой проблемы, является Скалолазание .

Возможный способ реализации - начать с нескольких баллов и рассчитать их «оценку». Затем определите подходящее направление для следующей точки и попытайтесь «подняться».

Основными проблемами, которые я вижу в этом вопросе, как вы его представили, является огромный диапазон значений параметров, а также тот факт, что результат выполнения является логическим (а не числовым). Это потребует много прогонов, чтобы выяснить, действительно ли набор выбранных параметров действительно хорош, и с другой стороны, есть огромный набор значений параметров, которые еще предстоит проверить. Просто проверка всех направлений приведет к (слишком?) Большому количеству прогонов.

Answer 6

Не уверен, правильно ли я понял ...

Если вы можете выбрать параметры для своего алгоритма, значит ли это, что вы можете выбрать его раз и навсегда?

Тогда вы можете просто:

• пусть разработчик выполнит все / многие случаи только один раз, найдет наилучший случай, а заменит параметры на лучшее значение
• во время выполнения для вашего реального пользователя, алгоритм уже параметризован с лучшими параметрами

---

Или, если лучшие значения меняются для каждого прогона ... Вы ищете Генетические алгоритмы тип подхода?