Поиск идей / ссылок / ключевых слов: адаптивное управление параметрами алгоритма поиска (онлайн-обучение)

Question

Я ищу идеи / опыт / ссылки / ключевые слова, касающиеся адаптивного управления параметрами параметров алгоритма поиска (онлайн-обучение) в комбинаторной оптимизации.

Немного подробнее:

У меня есть структура, которая отвечает за оптимизацию сложной проблемы комбинаторной оптимизации. Это делается с помощью некоторой "малой эвристики", которая используется итеративным образом (поиск больших окрестностей; подход "разорение и восстановление"). Каждый алгоритм этой "малой эвристики" принимает некоторые внешние параметры, которые в некоторой степени управляют эвристической логикой (на данный момент: просто случайные значения; некоторый шум; диверсифицируйте поиск).

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

Необходимо принять как минимум два общих решения:

• A: Выберите пару алгоритмов (один алгоритм уничтожения и один алгоритм восстановления), которая будет использоваться в следующей итерации.
• B: Выберите случайные параметры алгоритмов.

Единственная обратная связь - функция оценки нового найденного решения. Это приводит меня к теме обучения-подкрепления. Это правильное направление?

На самом деле это не учебное поведение, а упрощенные идеи:

• A: Выбор колеса рулетки в соответствии с некоторым значением производительности, собранным во время итераций (ближайшее прошлое более ценно, чем более старые). Так что, если эвристик 1 действительно нашел все новые лучшие мировые решения -> высокая вероятность выбора этого.
• Б: Понятия не имею. Возможно, можно использовать некоторые неоднородные случайные значения в диапазоне (0,1), и я собираю некоторый импульс изменений. Таким образом, если эвристика 1 в последний раз использовала альфа = 0,3 и не нашла нового лучшего решения, то использовала 0,6 и нашла новое лучшее решение -> есть импульс в направлении 1 -> следующее случайное значение, вероятно, будет больше 0,3. Возможные проблемы: колебание!

Вещи, на которые следует обратить внимание: - параметры, необходимые для хорошей сходимости одного конкретного алгоритма, могут кардинально измениться -> возможно, потребуется больше операций по диверсификации в начале, больше операций по интенсификации, необходимых в конце. - Существует вероятность хороших синергетических эффектов в конкретной паре алгоритма destroy / rebuild (иногда называемой: связанные окрестности). Как можно распознать что-то подобное? Это все еще в области обучения подкреплению? - Различные алгоритмы контролируются разным количеством параметров (некоторые принимают 1, некоторые 3).

Любые идеи, опыт, ссылки (статьи), ключевые слова (мл-темы)?
Если есть идеи относительно решения (б) в манере обучения в автономном режиме. Не стесняйтесь упомянуть об этом.

Спасибо за все Ваши ответы.

Sascha

Answer 1

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

Один из подходов, который вы хотели бы рассмотреть, - это развитие вашего "пространства параметров" с использованием генетического алгоритма. Короче говоря, GA использует аналог процессов естественного отбора, чтобы последовательно выводить все лучшие решения.

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

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

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

Answer 2

Это похоже на гиперэвристику, которую вы пытаетесь сделать. Попробуйте найти это ключевое слово.

В Drools Planner (с открытым исходным кодом, Java) у меня есть поддержка поиска по табу и имитация отжига из коробки. Я еще не реализовал подход "разорение и воссоздание", но это должно быть легко, хотя я не ожидаю лучших результатов. Задача: докажите, что я не прав, раскошелите, добавьте и разбейте меня в примерах. Гиперэвристика в моем списке TODO.