я используюимитация отжига решить 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):

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.

Итак, мой вопрос к переполнению стека: как я могу спроектировать функцию вероятности принятия, которая учитывает несколько энергий, но всегда считает, что первая энергия важнее второй энергии, и так далее? Другими словами, я хотел бы передать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). Но я еще не пробовал.