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