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

Question

Estoy utilizando recocido simulado para resolver un problema de programación de recursos NP-completo. Para cada pedido candidato de las tareas computo 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 el calendario de vanos
• split_cost:. El número de días en que cada tarea se ha retrasado debido a las interrupciones de otras tareas (esto es para desalentar la interrupción de una tarea una vez que ha comenzado)
• deadline_cost:. La suma del número de días al cuadrado por el cual cada vencimiento del plazo está vencido

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 queremos es que deadline_cost siempre tomar precedencia sobre global_finish_time, y por global_finish_time para tomar precedencia sobre split_cost.

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

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, hacer un esfuerzo para "normalizando" los valores. En primer lugar, deadline_cost es una suma de cuadrados, por lo que crece de forma exponencial mientras que los otros componentes crecen linealmente. Para hacer frente a ello utilizo la raíz cuadrada para obtener una tasa de crecimiento similar. En segundo lugar, he desarrollado una función que calcula una combinación lineal de los costos, pero se ajusta automáticamente a los coeficientes de acuerdo con el componente de costo más alto visto hasta ahora.

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

Esto crea el efecto "serrucho" en la función de costes como los nuevos costos máximos que se descubren. Por ejemplo, si C sube entonces BCx y Cy ambos estarán más alta para una (, y, z x) de entrada dado y también lo hará diferencias entre los costos. A diferencia de costo más alto significa que la probabilidad de aceptación se reducirá, como si la temperatura se bajó de repente un paso adicional. Aunque en la práctica esto no es un problema porque los costos máximos se actualizan sólo unas pocas veces en el comienzo y no cambian más tarde. Creo que esto podría incluso ser probada teóricamente a converger a un resultado correcto, ya que sabemos que el costo convergerá hacia un valor inferior.

Una cosa que todavía me tiene un poco confundido es lo que sucede cuando los costos máximos son de 1,0 e inferior, por ejemplo 0,5. Con un vector máximo de (0.5, 0.5, 0.5) esto daría a la combinación lineal 0,5 * 0,5 * x + 0,5 * y + z, es decir, el orden de precedencia se invierte de repente. Supongo que la mejor manera de tratar con él es utilizar el vector máxima de escalar todos los valores a intervalos dados, por lo que los coeficientes pueden ser siempre el mismo (por ejemplo, 100x + 10y + z). Pero no he probado todavía.

Answer 1

mbeckish es correcta.

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

Posiblemente log-transformándolos dentro y fuera?

He hecho algunas MCMC usando Metropolis-Hastings. En ese caso, estoy definiendo el (no normalizada) log-probabilidad de un estado en particular (dadas sus priores), y me parece que una manera de aclarar mi forma de pensar acerca de lo que quiero.

Answer 2

Me gustaría tener un indicio del algoritmo evolutivo multiobjetivo (MOEA) y hacer que la transición si todos de los objetivos pasan simultáneamente con la función acceptance_probability diste. Esto tendrá el efecto de la exploración de la frente de Pareto mucho como el recocido simulado estándar explora mesetas de soluciones misma energía.

Sin embargo, esto se da por vencido en la idea de tener la primera prioridad una sola toma.

probablemente tenga que ajustar sus parámetros, como dándole una temperatura inicial más alto.

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

Depende de lo que entendemos por "tiene prioridad". Por ejemplo, ¿qué pasaría si el deadline_cost disminuye en 0.001, pero el costo global_finish_time sube por 10000? Hacer que regrese 1.0, debido a que el deadline_cost disminuyó, y que tiene prioridad sobre cualquier otra cosa? Esto parece que es una cuestión de criterio que sólo se puede hacer, a menos que pueda proporcionar suficiente información de antecedentes sobre el proyecto para que otros puedan sugerir su propio llamado juicio informado.