Я использую симулированный отжиг для решения 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). Но я еще не пробовал это.
