ich benutzesimuliertes Glühen ein NP-vollständiges Ressourcenplanungsproblem zu lösen. Für jede Kandidatenreihenfolge der Aufgaben berechne ich verschiedene Kosten (oder Energiewerte). Einige Beispiele sind (obwohl die Einzelheiten für die Frage wahrscheinlich irrelevant sind):

global_finish_time: Die Gesamtzahl der Tage, die der Zeitplan umfasst.split_cost: Die Anzahl der Tage, um die sich jede Aufgabe aufgrund von Unterbrechungen durch andere Aufgaben verzögert (dies soll die Unterbrechung einer Aufgabe nach dem Start verhindern).deadline_cost: Die Summe der quadrierten Anzahl von Tagen, um die jede versäumte Frist überfällig ist.

Die herkömmliche Akzeptanzwahrscheinlichkeitsfunktion sieht wie folgt aus (in 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)

Bisher habe ich meine ersten beiden Kosten zu einer zusammengefasst, indem ich sie einfach addiert habe, damit ich das Ergebnis einspeisen kannacceptance_probability. Aber was ich wirklich möchte, ist fürdeadline_cost immer Vorrang habenglobal_finish_time, und fürglobal_finish_time Vorrang habensplit_cost.

Meine Frage zum Stapelüberlauf lautet also: Wie kann ich eine Akzeptanzwahrscheinlichkeitsfunktion entwerfen, die mehrere Energien berücksichtigt, aber die erste Energie immer für wichtiger hält als die zweite Energie, und so weiter? Mit anderen Worten, ich würde gerne mitmachenold_cost undnew_cost als ein Vielfaches von mehreren Kosten und einen vernünftigen Wert zurück.

Bearbeiten: Nach einigen Tagen des Experimentierens mit den vorgeschlagenen Lösungen bin ich zu dem Schluss gekommen, dass der einzige Weg, der für mich gut genug funktioniert, der Vorschlag von Mike Dunlavey ist, obwohl dies viele andere Schwierigkeiten mit Kostenelementen mit unterschiedlichen Einheiten schafft. Ich bin praktisch gezwungen, Äpfel mit Orangen zu vergleichen.

Also habe ich mir Mühe gegeben, die Werte zu "normalisieren". Zuerst,deadline_cost ist eine Summe von Quadraten, also wächst sie exponentiell, während die anderen Komponenten linear wachsen. Um dies anzugehen, verwende ich die Quadratwurzel, um eine ähnliche Wachstumsrate zu erhalten. Zweitens habe ich eine Funktion entwickelt, die eine lineare Kombination der Kosten berechnet, aber die Koeffizienten automatisch entsprechend der höchsten Kostenkomponente anpasst, die bisher gesehen wurde.

Wenn beispielsweise das Tupel der höchsten Kosten (A, B, C) und der eingegebene Kostenvektor (x, y, z) ist, lautet die Linearkombination BCx + Cy + z. Auf diese Weise wird es nie wichtiger als ein x-Wert von 1 sein, egal wie hoch z wird.

Dies erzeugt "Unebenheiten" in der Kostenfunktion, wenn neue maximale Kosten entdeckt werden. Wenn beispielsweise C steigt, sind sowohl BCx als auch Cy für eine bestimmte (x, y, z) Eingabe höher, und dies gilt auch für die Unterschiede zwischen den Kosten. Ein höherer Kostenunterschied bedeutet, dass die Akzeptanzwahrscheinlichkeit sinkt, als ob die Temperatur plötzlich um einen zusätzlichen Schritt gesenkt würde. In der Praxis ist dies jedoch kein Problem, da die maximalen Kosten anfangs nur wenige Male aktualisiert werden und sich später nicht ändern. Ich glaube, es könnte theoretisch sogar bewiesen werden, dass dies zu einem korrekten Ergebnis führt, da wir wissen, dass die Kosten zu einem niedrigeren Wert hin konvergieren werden.

Eine Sache, die mich immer noch etwas verwirrt, ist, was passiert, wenn die maximalen Kosten 1,0 und niedriger sind, sagen wir 0,5. Bei einem Maximalvektor von (0,5, 0,5, 0,5) würde dies die Linearkombination 0,5 * 0,5 * x + 0,5 * y + z ergeben, d. H. Die Rangfolge wird plötzlich umgekehrt. Ich nehme an, der beste Weg, um damit umzugehen, besteht darin, den Maximalvektor zu verwenden, um alle Werte auf vorgegebene Bereiche zu skalieren, sodass die Koeffizienten immer gleich sein können (z. B. 100x + 10y + z). Das habe ich aber noch nicht ausprobiert.