estou usandorecozimento simulado para resolver um problema de agendamento de recursos NP-completo. Para cada ordenação de candidato das tarefas, eu computo vários custos diferentes (ou valores de energia). Alguns exemplos são (embora os detalhes sejam provavelmente irrelevantes para a questão):

global_finish_time: O número total de dias que a agenda abrange.split_cost: O número de dias em que cada tarefa é atrasada devido a interrupções por outras tarefas (isto significa desencorajar a interrupção de uma tarefa depois de iniciada).deadline_cost: A soma do número quadrado de dias em que cada prazo perdido está em atraso.

A função de probabilidade de aceitação tradicional é assim (em 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)

Até agora eu combinei meus dois primeiros custos em um simplesmente adicionando-os, para que eu possa alimentar o resultado emacceptance_probability. Mas o que eu realmente quero é paradeadline_cost sempre ter precedência sobreglobal_finish_time, e paraglobal_finish_time ter precedência sobresplit_cost.

Então, minha pergunta para o Stack Overflow é: como eu posso projetar uma função de probabilidade de aceitação que leve em consideração múltiplas energias, mas sempre considere a primeira energia como mais importante que a segunda energia, e assim por diante? Em outras palavras, eu gostaria de passarold_cost enew_cost como tuplas de vários custos e retornar um valor sensato.

Editar: Depois de alguns dias experimentando as soluções propostas, concluí que a única maneira que funciona bem para mim é a sugestão de Mike Dunlavey, embora isso crie muitas outras dificuldades com componentes de custo que têm unidades diferentes. Eu sou praticamente forçado a comparar maçãs com laranjas.

Então, eu me esforcei para "normalizar" os valores. Primeiro,deadline_cost é uma soma de quadrados, por isso cresce exponencialmente enquanto os outros componentes crescem linearmente. Para resolver isso eu uso a raiz quadrada para obter uma taxa de crescimento semelhante. Em segundo lugar, desenvolvi uma função que calcula uma combinação linear dos custos, mas ajusta automaticamente os coeficientes de acordo com o componente de custo mais alto visto até agora.

Por exemplo, se a tupla de maiores custos for (A, B, C) e o vetor de custo de entrada for (x, y, z), a combinação linear será BCx + Cy + z. Dessa forma, não importando quão alto z seja, isso nunca será mais importante do que um valor x de 1.

Isso cria "jaggies" na função de custo à medida que novos custos máximos são descobertos. Por exemplo, se C subir, então BCx e Cy serão ambos maiores para uma dada entrada (x, y, z) e assim serão as diferenças entre os custos. Uma diferença de custo mais alta significa que a probabilidade de aceitação diminuirá, como se a temperatura subitamente baixasse um passo extra. Na prática, isso não é um problema porque os custos máximos são atualizados apenas algumas vezes no início e não são alterados posteriormente. Acredito que isso possa até teoricamente comprovar que converge para um resultado correto, já que sabemos que o custo convergirá para um valor menor.

Uma coisa que ainda me deixa um pouco confuso é o que acontece quando os custos máximos são 1,0 e menores, digamos 0,5. Com um vector máximo de (0,5, 0,5, 0,5) isto daria a combinação linear 0,5 * 0,5 * x + 0,5 * y + z, isto é, a ordem de precedência é repentinamente invertida. Suponho que a melhor maneira de lidar com isso é usar o vetor máximo para dimensionar todos os valores para determinados intervalos, para que os coeficientes possam ser sempre iguais (digamos, 100x + 10y + z). Mas ainda não tentei isso.