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

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

 flodin09 июл. 2009 г., 18:26
Это не академично. Я использую это как альтернативу MS Project. Основная цель программы - облегчить ответ на вопрос "когда ваша команда может добавить функцию X в наше программное обеспечение?"
 Howard May09 июл. 2009 г., 16:53
Мне было бы интересно узнать, является ли это отраслевой или академической проблемой. С уважением
 Mark Feldman15 нояб. 2013 г., 04:01
Я знаю, что этому вопросу уже несколько лет, но для всех, кто сталкивается с этой страницей через Google ... в нечеткой логике взвешенная сумма эквивалентна логическому ИЛИ, так что вы фактически говорите "условие А"OR условие B и т. д. То, что вы действительно хотите, этоAND ВAND С, и для этого вы используете умножение. Есть несколько предостережений (например, ваши веса теперь должны быть полномочиями), но это намного лучше, чем беспорядок, который вы получаете, пытаясь на особый случай все. Вики "Модель взвешенной суммы" и «Модель взвешенного продукта»; Больше подробностей.

Ответы на вопрос(4)

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

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)

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

 09 июл. 2009 г., 18:30
Я думаю, что это эвристический подход, который не редкость в NP-полных решениях.
 flodin11 июл. 2009 г., 15:23
Я опробовал это, и он генерирует довольно хорошие решения. Одна проблема заключается в том, что после того, как компонент с наивысшим приоритетом установил оптимальное значение, алгоритм с большой вероятностью может выпрыгнуть из этого решения даже при низких температурах. Это логично, поскольку переход от (0, 0) к (1, 0) имеет точно такую же вероятность, как и переход от (0, 0) к (0, 1). Я оставлю вопрос на некоторое время открытым и продолжу экспериментировать, чтобы выяснить, не появится ли что-нибудь лучше. Прямо сейчас я рассматриваю некоторую разницу в величине вероятности при оценке компонента с более низким приоритетом.
 flodin09 июл. 2009 г., 18:21
Я попробую и вернусь к вам. Я думал о чем-то похожем, но вижу потенциальную проблему в том факте, что разница X в первом значении представляет такую же вероятность, как разница X во втором значении. Интуитивно понятно, что разница во втором значении должна представлять значение, которое в некотором смысле является бесконечно меньшей вероятностью. Проблема здесь заключается в том, что трудно убедить себя в испытании и Ошибка в том, что ваш алгоритм является здравым. Это может работать для простых случаев, но создавать странное поведение в сложных сценариях. Я желаю некоторого теоретического подтверждения метода.
Решение Вопроса

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

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

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

 09 июл. 2009 г., 19:14
@flodin: Вы хотите, чтобы ваша общая энергетическая поверхность была непрерывной, поэтому я бы стеснялся утверждений IF. Кроме этого, вы можете сделать его довольно нелинейным, как, например, отталкивание квадратов от граничных случаев - просто мысль.
 flodin09 июл. 2009 г., 18:11
Различные количества не всегда имеют совместимые единицы. Например, значение крайнего срока возводится в квадрат, чтобы получить тип оптимизации по методу наименьших квадратов, то есть я предпочитаю откладывать 3 задачи на 1 день, а не 1 задачу на 3 дня. Я рассмотрел это, но я боюсь, что я столкнусь со многими граничными случаями, когда система не работает правильно, потому что я не сделал коэффициенты "просто правильными". (если есть даже такая вещь). Также смотрите ответ на mcbeckish

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

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

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

Ваш ответ на вопрос