Как спроектировать функцию вероятности принятия для моделирования отжига с несколькими различными затратами?

Question

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

• global_finish_time:Общее количество дней, охватываемое расписанием.
• split_cost:Количество дней, на которое каждая задача задерживается из-за прерывания другими задачами (это предназначено для предотвращения прерывания задачи после ее запуска).
• deadline_cost:Сумма квадратов числа дней, на которые просрочен каждый пропущенный срок.

Традиционная функция вероятности принятия выглядит следующим образом (на Python):

def acceptance_probability(old_cost, new_cost, temperature):
    if new_cost < old_cost:
        return 1.0
    else:
        return math.exp((old_cost - new_cost) / temperature)

До сих пор я объединял первые две стоимости в одну, просто складывая их, чтобы можно было передать результат в acceptance_probability.Но чего бы мне действительно хотелось, так это deadline_cost всегда иметь приоритет над global_finish_time, и для global_finish_time иметь преимущество над split_cost.

Итак, мой вопрос к Stack Overflow:как я могу разработать функцию вероятности принятия, которая учитывает несколько энергий, но всегда считает первую энергию более важной, чем вторая энергия, и так далее?Другими словами, я хотел бы передать old_cost и new_cost как кортежи нескольких стоимостей и возвращают разумное значение.

Редактировать: После нескольких дней экспериментирования с предложенными решениями я пришел к выводу, что единственный способ, который работает для меня достаточно хорошо, — это предложение Майка Данлави, даже несмотря на то, что это создает множество других трудностей с компонентами затрат, которые имеют разные единицы измерения.Я практически вынужден сравнивать яблоки с апельсинами.

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

Например, если кортеж с наибольшими затратами равен (A, B, C), а вектор входных затрат равен (x, y, z), линейная комбинация равна BCx + Cy + z.Таким образом, независимо от того, насколько высоким будет значение z, оно никогда не будет более важным, чем значение x, равное 1.

Это создает «ступенчатость» функции затрат по мере обнаружения новых максимальных затрат.Например, если C увеличится, то BCx и Cy будут выше для данного входного сигнала (x, y, z), как и разница между затратами.Более высокая разница в стоимости означает, что вероятность приемки снизится, как если бы температура была внезапно снижена еще на один шаг.Однако на практике это не проблема, поскольку максимальные затраты вначале обновляются всего несколько раз и не меняются позже.Я считаю, что можно даже теоретически доказать, что это сходится к правильному результату, поскольку мы знаем, что стоимость будет стремиться к более низкому значению.

Одна вещь, которая до сих пор меня несколько смущает, — это то, что происходит, когда максимальные затраты равны 1,0 и ниже, скажем, 0,5.При максимальном векторе (0,5, 0,5, 0,5) это даст линейную комбинацию 0,5*0,5*x + 0,5*y + z, т.е.порядок старшинства внезапно меняется на противоположный.Я полагаю, что лучший способ справиться с этим — использовать максимальный вектор для масштабирования всех значений до заданных диапазонов, чтобы коэффициенты всегда были одинаковыми (скажем, 100x + 10y + z).Но я еще этого не пробовал.

Answer 1

Мбекиш прав.

Не могли бы вы составить линейную комбинацию различных энергий и откорректировать коэффициенты?

Возможно, их вход и выход из журнала?

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

Answer 2

Я бы воспользовался подсказкой многокритериального эволюционного алгоритма (MOEA) и сделал бы его переход, если все целей одновременно проходят с acceptance_probability функция, которую вы дали.Это приведет к исследованию фронта Парето, подобно тому, как стандартный моделируемый отжиг исследует плато решений с одинаковой энергией.

Однако это отказывается от идеи приоритета первого.

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

Answer 3

Я бы рассмотрел что-то вроде:

If (new deadline_cost > old deadline_cost)
  return (calculate probability)

else if (new global finish time > old global finish time)
  return (calculate probability)

else if (new split cost > old split cost)
  return (calculate probability)

else 
  return (1.0)

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

Answer 4

Это зависит от того, что вы подразумеваете под «имеет приоритет».Например, что, если deadline_cost снижается на 0,001, но global_finish_time стоимость увеличится на 10000?Вы возвращаете 1.0, потому что deadline_cost уменьшилось, и это имеет приоритет над чем-либо еще?Похоже, что это суждение, которое можете вынести только вы, если только вы не предоставите достаточно справочной информации о проекте, чтобы другие могли предложить свое собственное обоснованное суждение.