Wie Akzeptanz Wahrscheinlichkeitsfunktion für simulierte Glühen mit mehreren unterschiedlich Kosten zu entwerfen?

Question

Ich bin mit simuliertem Tempern ein NP-vollständige Ressourcenplanung Problem zu lösen. Für jeden Kandidaten Reihenfolge der Aufgaben berechnen wir verschiedene Kosten (oder Energiewerte). Einige Beispiele sind (obwohl die Besonderheiten wahrscheinlich irrelevant für die Frage sind):

• global_finish_time. Die Gesamtzahl der Tage, dass der Zeitplan Spannweiten
• split_cost. Die Anzahl der Tage, durch denen jede Aufgabe von anderen Aufgaben aufgrund von Unterbrechungen verzögert wird (dies soll Unterbrechung einer Aufgabe entmutigen, wenn es begonnen hat)
• deadline_cost. Die Summe der quadrierten Anzahl der Tage, die für jede verpasste Frist überfällig

Die traditionelle Akzeptanz Wahrscheinlichkeitsfunktion 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 einem zusammengefasst, indem einfach sie, so dass ich das Ergebnis in acceptance_probability einspeisen kann. Aber was würde ich wirklich will, ist für deadline_cost immer Vorrang vor global_finish_time zu nehmen, und für global_finish_time Vorrang vor split_cost zu nehmen.

Also meine Frage Überlauf Stack ist: Wie kann ich eine Akzeptanzwahrscheinlichkeitsfunktion entwerfen, die mehrere Energien berücksichtigen aber immer die erste Energie halten als die zweite Energie wichtiger zu sein, und so weiter? Mit anderen Worten, würde Ich mag in old_cost und new_cost als Tupel von mehreren Kosten zu übergeben und einen vernünftigen Wert zurück.

Edit: Nach einigen Tagen mit den vorgeschlagenen Lösungen zu experimentieren ich Schluss gekommen, dass der einzige Weg, der für mich gut genug funktioniert, ist Vorschlag Mike Dunlavey, auch wenn dies viele andere Schwierigkeiten mit Kostenkomponenten erzeugt die unterschiedlichen Einheiten. Ich bin praktisch gezwungen, Äpfel mit Birnen zu vergleichen.

Also, habe ich einige Mühe in die „Normalisierung“ der Werte. Zuerst deadline_cost ist eine Summe von Quadraten, so dass es wächst exponentiell, während die anderen Komponenten linear wachsen. Um dem abzuhelfen Ich verwende die Quadratwurzel eine ähnliche Wachstumsrate zu erhalten. Zweitens entwickelte ich eine Funktion, die eine lineare Kombination der Kosten berechnet, sondern passt sich automatisch die Koeffizienten nach der höchsten Kostenkomponente bisher gesehen.

Zum Beispiel, wenn das Tupel der höchst Kosten (A, B, C) und die Eingangskostenvektor (x, y, z), die lineare Kombination BCx + Cy + z. Auf diese Weise, egal wie hoch z bekommt es nie wichtiger sein als ein x-Wert von 1.

Dies schafft „jaggies“ in der Kostenfunktion als neu maximal Kosten entdeckt werden. Wenn beispielsweise C wird dann bis BCx und Cy beide geht höher für einen gegebenen (x, y, z) Eingabe und so werden Unterschiede zwischen den Kosten. Eine höhere Kostenunterschied bedeutet, dass die Annahmewahrscheinlichkeit fällt, als wenn die Temperatur plötzlich einen zusätzlichen Schritt gesenkt wurde. In der Praxis allerdings ist dies kein Problem, da die maximal Kosten nur ein paar Mal am Anfang aktualisiert werden und später nicht ändern. Ich glaube, das könnte auch theoretisch auf ein korrektes Ergebnis konvergieren bewiesen werden, da wir wissen, dass die Kosten zu einem niedrigen Wert konvergieren.

Eine Sache, die immer noch hat mir etwas verwirrt ist, was passiert, wenn die maximal Kosten betragen 1,0 und niedriger, sagt 0,5. Mit einer maximalen Vektor von (0,5, 0,5, 0,5) Dies würde der Linearkombination 0,5 * 0,5 * 0,5 * x + y + z geben, das heißt, die Reihenfolge des Vorrangs wird plötzlich umgekehrt wird. Ich nehme an, der beste Weg, damit umzugehen ist, die maximale Vektor zu verwenden, um alle Werte zu bestimmten Bereichen zu skalieren, so dass die Koeffizienten immer gleich sein können (etwa 100x + 10y + z). Aber ich habe nicht versucht, dass noch.

Answer 1

mbeckish richtig ist.

Könnten Sie eine lineare Kombination der verschiedenen Energien machen, und die Koeffizienten einstellen?

Möglicherweise log-Umwandlung sie in und aus?

Ich habe einige MCMC mit Metropolis-Hastings gemacht. In diesem Fall bin ich der Definition der (nicht normalisierte) log-Wahrscheinlichkeit eines bestimmten Zustands (angesichts seiner Vorstrafen), und ich finde, dass ein Weg, um meine Gedanken über zu klären, was ich will.

Answer 2

Ich würde einen Hinweis von multikriteriellen evolutionären Algorithmus (MOEA) und haben es über wenn alle der Ziele gleichzeitig mit der acceptance_probability Funktion übergeben Sie gab. Dadurch wird die Wirkung der Erforschung der Pareto-Front haben ähnlich wie die Standard-Simulated Annealing erforscht Plateaus gleichgeschlechtlicher Energielösungen.

Dies schließt jedoch verzichten auf die Idee, den ersten Vorrang haben.

Sie werden wahrscheinlich müssen Ihre Parameter optimieren, wie es eine höhere Anfangstemperatur zu geben.

Answer 3

Ich würde etwas entlang der Linien von betrachten

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)

Natürlich jedem der drei Orte, die Sie berechnen die Wahrscheinlichkeit, eine andere Funktion verwenden können.

Answer 4

Es hängt davon ab, was Sie unter „hat Vorrang“. Zum Beispiel, was passiert, wenn geht das deadline_cost von 0.001 nach unten, aber die global_finish_time Kosten steigen von 10000? Haben Sie zurückkehren 1,0, weil die deadline_cost verringert, und das hat Vorrang vor allem anderen? Dies scheint, wie es eine Ermessenssache ist, dass nur Sie machen, wenn Sie genügend Hintergrundinformationen über das Projekt zur Verfügung stellen können, damit andere ihren eigenen fundiertes Urteil Anruf vor.