¿Cómo diseñar la función de probabilidad de aceptación para el recocido simulado con múltiples costos distintos?

Question

Estoy usando simulated annealing para resolver un problema de programación de recursos NP-completo. Para cada pedido de candidatos de las tareas, calculo varios costos diferentes (o valores de energía). Algunos ejemplos son (aunque los detalles son probablemente irrelevante para la cuestión):

• global_finish_time: El número total de días que los tramos horarios.
• split_cost: el número de días que cada tarea se retrasa debido a interrupciones por otras tareas (esto tiene como objetivo desalentar la interrupción de una tarea una vez que ha comenzado).
• deadline_cost: La suma del número cuadrado de días por el que se venció cada fecha de vencimiento.

La función tradicional de probabilidad de aceptación es el siguiente (en 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) 

Hasta ahora he combinado mis dos primeros costes en uno por la simple adición de ellos, de modo que pueda alimentar el resultado en acceptance_probability. Pero lo que realmente quiero es que deadline_cost siempre tenga prioridad sobre global_finish_time, y que global_finish_time tenga prioridad sobre split_cost.

Así que mi pregunta para Stack Overflow es: ¿cómo puedo diseñar una función de probabilidad de aceptación que tenga en cuenta múltiples energías pero siempre considera que la primera energía es más importante que la segunda, y así sucesivamente? En otras palabras, me gustaría pasar old_cost y new_cost como tuplas de varios costos y devolver un valor razonable.

Editar: Después de unos días de experimentar con las soluciones propuestas he concluido que la única forma en que funciona lo suficientemente bien como para mí es la sugerencia de Mike Dunlavey, a pesar de que esto crea muchas otras dificultades con componentes de costos que tienen diferentes unidades . Estoy prácticamente obligado a comparar manzanas con naranjas.

Por lo tanto, hice un esfuerzo para "normalizar" los valores. En primer lugar, deadline_cost es una suma de cuadrados, por lo que crece exponencialmente mientras que los otros componentes crecen linealmente. Para abordar esto, uso la raíz cuadrada para obtener una tasa de crecimiento similar. Segundo, desarrollé una función que calcula una combinación lineal de los costos, pero ajusta automáticamente los coeficientes de acuerdo con el componente de costo más alto visto hasta ahora.

Por ejemplo, si la tupla de mayor costo es (A, B, C) y el vector de costo de entrada es (x, y, z), la combinación lineal es BCx + Cy + z. De esta forma, no importa qué tan alto z llegue, nunca será más importante que un valor x de 1.

Esto crea "jaggies" en la función de costos a medida que se descubren nuevos costos máximos. Por ejemplo, si C sube, entonces BCx y Cy serán más altos para una entrada determinada (x, y, z) y también lo serán las diferencias entre los costos. Una mayor diferencia de costos significa que la probabilidad de aceptación disminuirá, como si la temperatura se redujera repentinamente un paso adicional. Sin embargo, en la práctica esto no es un problema porque los costos máximos se actualizan solo unas pocas veces al principio y no cambian más adelante. Creo que incluso podría demostrarse teóricamente que converge hacia un resultado correcto, ya que sabemos que el costo convergerá hacia un valor inferior.

Una cosa que todavía me tiene algo confundida es lo que sucede cuando los costos máximos son 1.0 y menos, digamos 0.5. Con un vector máximo de (0.5, 0.5, 0.5) esto daría la combinación lineal 0.5 * 0.5 * x + 0.5 * y + z, es decirel orden de precedencia se invierte de repente. Supongo que la mejor manera de manejarlo es usar el vector máximo para escalar todos los valores a rangos dados, de modo que los coeficientes siempre puedan ser los mismos (digamos, 100x + 10y + z). Pero aún no lo he intentado.

Answer 1

mbeckish tiene razón.

¿Podría hacer una combinación lineal de las diferentes energías y ajustar los coeficientes?

¿Posiblemente log-transforming ellos dentro y fuera?

He hecho algo de MCMC usando Metropolis-Hastings. En ese caso, estoy definiendo la verosimilitud logarítmica (no normalizada) de un estado particular (dados sus antecedentes), y encuentro que es una forma de aclarar mi forma de pensar sobre lo que quiero.

Answer 2

Depende de lo que quiere decir con "tiene prioridad". Por ejemplo, ¿qué sucede si el deadline_cost baja en 0.001, pero el costo global_finish_time aumenta en 10000? ¿Devuelve 1.0, porque el deadline_cost disminuyó, y eso tiene prioridad sobre cualquier otra cosa? Parece que es una decisión de juicio que solo usted puede hacer, a menos que pueda proporcionar suficiente información de antecedentes sobre el proyecto para que otros puedan sugerir su propio juicio informado.

Answer 3

yo consideraría algo en la línea 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) 

Por supuesto, cada uno de los tres lugares que calcular la probabilidad podría utilizar una función diferente.

Answer 4

Me gustaría tener una pizca de algoritmo evolutivo multiobjetivo (MOEA) y hacer que la transición si todo de los objetivos pasan simultáneamente con la función acceptance_probability diste. Esto tendrá el efecto de explorar el frente de Pareto de manera similar a como el recocido simulado estándar explora las mesetas de soluciones de la misma energía.

Sin embargo, esto se rinde ante la idea de que el primero tenga prioridad.

Probablemente tendrá que modificar sus parámetros, como por ejemplo, darle una temperatura inicial más alta.