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

Question

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

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

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

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

По крайней мере, естьнеобходимо принять два общих решения:

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

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

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

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

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

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

Спасибо за ваш вклад.

Саша

Answer 1

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

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

Answer 2

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

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

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

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

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