estoy usandorecocido simulado para resolver un problema de planificación de recursos NP-completa. Para cada orden de candidato de las tareas calculo varios costos diferentes (o valores de energía). Algunos ejemplos son (aunque los detalles son probablemente irrelevantes para la pregunta):

global_finish_time: El número total de días que abarca el horario.split_cost: El número de días en que cada tarea se retrasa debido a interrupciones por otras tareas (esto pretende desalentar la interrupción de una tarea una vez que ha comenzado).deadline_cost: La suma del número al cuadrado de días por los cuales se vence cada fecha límite perdida.

La función tradicional de probabilidad de aceptación se ve así (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 costos en uno, simplemente agregándolos, de modo que pueda incluir el resultado enacceptance_probability. Pero lo que realmente quisiera es paradeadline_cost tener siempre prioridad sobreglobal_finish_time, y paraglobal_finish_time tener prioridad sobresplit_cost.

Entonces, mi pregunta a 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 que siempre considere que la primera energía es más importante que la segunda, y así sucesivamente? En otras palabras, me gustaría pasarold_cost ynew_cost Como tuplas de varios costos y devuelven un valor razonable.

Editar: Después de unos días de experimentar con las soluciones propuestas, llegué a la conclusión de que la única manera que me funciona bien es la sugerencia de Mike Dunlavey, aunque esto crea muchas otras dificultades con los componentes de costo que tienen diferentes unidades. Estoy prácticamente obligado a comparar manzanas con naranjas.

Entonces, puse un poco de esfuerzo en "normalizar" los valores. Primero,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. En segundo lugar, desarrollé una función que calcula una combinación lineal de los costos, pero que ajusta automáticamente los coeficientes de acuerdo con el componente de mayor costo visto hasta ahora.

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

Esto crea "jaggies" en la función de costo 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 dada (x, y, z) y también lo serán las diferencias entre los costos. Una mayor diferencia de costo significa que la probabilidad de aceptación disminuirá, como si la temperatura se hubiera reducido repentinamente en un paso adicional. En la práctica, aunque esto no es un problema porque los costos máximos se actualizan solo unas pocas veces al principio y no se modifican más adelante. Creo que esto podría incluso probarse teóricamente para converger a un resultado correcto, ya que sabemos que el costo convergerá hacia un valor más bajo.

Una cosa que todavía me tiene algo confundido es lo que sucede cuando los costos máximos son 1.0 y menores, 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 decir, el orden de precedencia se invierte repentinamente. Supongo que la mejor manera de lidiar con esto es usar el vector máximo para escalar todos los valores a rangos dados, de modo que los coeficientes puedan ser siempre los mismos (por ejemplo, 100x + 10y + z). Pero no lo he intentado todavía.