Como conceber função de probabilidade de aceitação para o recozimento simulado com vários custos distintos?

Question

Eu estou usando simulado recozimento para resolver um problema de agendamento de recursos NP-completos. Para cada ordenação candidato das tarefas I computar vários custos diferentes (ou valores de energia). Alguns exemplos são (embora os detalhes são provavelmente irrelevante para a questão):

• global_finish_time:. O número total de dias em que a expectativa de programação
• split_cost:. O número de dias em que cada tarefa é adiada devido a interrupções por outras tarefas (esta é para desencorajar a interrupção de uma tarefa, uma vez que já começou)
• deadline_cost:. A soma do número quadrado de dias em que cada um prazo não cumprido é atrasada

Os tradicionais olhares função aceitação probabilidade como este (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 por simplesmente adicionando-os, para que eu possa alimentar o resultado em acceptance_probability. Mas o que eu realmente quero é que deadline_cost para sempre têm precedência sobre global_finish_time, e por global_finish_time ter precedência sobre split_cost.

Então, minha pergunta para Stack Overflow é: como eu posso projetar uma função de probabilidade de aceitação que leva várias energias em conta, mas sempre considera a primeira energia a ser mais importante do que a segunda energia, e assim por diante? Em outras palavras, eu gostaria de passar em old_cost e new_cost como tuplas de vários custos e retornar um valor razoável.

Editar: Depois de alguns dias de experimentação com as soluções propostas cheguei à conclusão de que a única maneira que funciona bem o suficiente para mim é a sugestão de Mike Dunlavey, mesmo que isso cria muitas outras dificuldades com componentes de custo que tem unidades diferentes. Estou praticamente forçado a comparar maçãs com laranjas.

Então, eu colocar algum esforço para "normalizar" os valores. Primeiro, deadline_cost é uma soma de quadrados, assim que cresce exponencialmente enquanto os outros componentes crescem linearmente. Para lidar com isso, eu uso a raiz quadrada para obter uma taxa de crescimento similar. Em segundo lugar, eu desenvolvi uma função que calcula uma combinação linear dos custos, mas auto-ajusta os coeficientes de acordo com o maior componente de custo visto até agora.

Por exemplo, se o tuplo de custos mais elevados é (A, B, C) e o vector de custo de entrada é (x, y, z), a combinação linear é BCx + Cy + z. Dessa forma, não importa o quão alto z recebe-lo nunca será mais importante do que um valor de x de 1.

Isso cria "jaggies" na função de custo como novos custos máximos são descobertos. Por exemplo, se C sobe então BCx e de Cy ambos serão mais elevada para um dado (x, y, z) de entrada e assim que as diferenças entre os custos. Um meio mais elevados de diferença de custo que a probabilidade de aceitação cairão, como se a temperatura foi reduzido de repente um passo extra. Na prática, embora este não é um problema porque os custos máximos são atualizados apenas algumas vezes no começo e não mudam mais tarde. Eu acredito que isso ainda poderia ser teoricamente comprovada a convergir para um resultado correto, pois sabemos que o custo irá convergir para um valor inferior.

Uma coisa que ainda tem me um pouco confuso é o que acontece quando os custos máximos são de 1,0 e inferior, dizem 0,5. Com um vector máxima de (0,5, 0,5, 0,5), este daria a combinação linear de 0,5 * 0,5 * 0,5 * x + y + z, isto é, a ordem de precedência é subitamente invertida. Acho que a melhor maneira de lidar com isso é usar o vector máxima para escalar todos os valores para determinadas gamas, de modo que os coeficientes podem ser sempre o mesmo (por exemplo, 100x + 10y + z). Mas eu não tentei isso ainda.

Answer 1

mbeckish é certo.

Você poderia fazer uma combinação linear das diferentes energias, e ajustar os coeficientes?

Possivelmente log-transformando-os dentro e fora?

Já fiz alguns MCMC utilizando Metropolis-Hastings. Nesse caso, eu estou definindo o (não-normalizado) log-probabilidade de um determinado estado (dados os seus antecedentes), e eu acho que uma forma de esclarecer o meu pensamento sobre o que eu quero.

Answer 2

Gostaria de dar uma dica de algoritmo evolutivo multi-objetivo (MOEA) e tê-lo transição se todas dos objectivos passam simultaneamente com a função acceptance_probability que você deu. Isto terá o efeito de explorar a Pareto frente muito parecido com o padrão simulado recozimento explora planaltos de soluções mesma energia.

No entanto, isso não desistir da idéia de ter a primeira prioridade uma tomada.

Você provavelmente terá que ajustar seus parâmetros, como dando-lhe uma maior temperatura inicial.

Answer 3

Eu consideraria algo ao longo das linhas de:

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)

É claro que cada um dos três lugares que você calcular a probabilidade poderia usar uma função diferente.

Answer 4

Depende do que você entende por "tem prioridade". Por exemplo, que se o deadline_cost vai para baixo por 0,001, mas o custo global_finish_time sobe 10000? Você retornar 1.0, porque o deadline_cost diminuiu, e que tem precedência sobre qualquer outra coisa? Isto parece que é um julgamento que só você pode fazer, a menos que você pode fornecer informações suficientes sobre o projeto para que outros possam sugerir seu próprio julgamento informado.