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

я использую[имитация отжига](https://en.wikipedia.org/wiki/Simulated_annealing) решить NP-полную задачу планирования ресурсов. Для каждого кандидата, упорядочивающего задания, я вычисляю несколько разных затрат (или значений энергии). Вот некоторые примеры (хотя специфика, вероятно, не имеет отношения к вопросу):

`global_finish_time`: The total number of days that the schedule spans.
`split_cost`: The number of days by which each task is delayed due to interruptions by other tasks (this is meant to discourage interruption of a task once it has started).
`deadline_cost`: The sum of the squared number of days by which each missed deadline is overdue.

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

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

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

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

Итак, я приложил некоторые усилия к «нормализации» ценности. Первый,`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). Но я еще не пробовал.

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

Возможно лог-преобразование их в и из?

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



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



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



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

Тем не менее, это отказывается от идеи иметь первый приоритет.

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