Problemlösen in graphischen Strukturen 00857: Optimierung mit intelligenten Strategien

Leseprobe

Autoren: Prof. Dr. Wilhelm Rödder Dr. Friedhelm Kulmann Dr. Heinz Peter Reidmacher

Kapitel 2

Exakte Methoden

2.1 Das Branch & Bound-Verfahren

Das Verfahren Branch & Bound wird klassisch im Rahmen der Ganzzahligen Optimierung vorgestellt (siehe etwa NEUMANN/MORLOCK, 2002). Da wir diese Methode einer vergleichenden Darstellung mit dem A*-Algorithmus unterziehen wollen, werden wir sie an dieser Stelle in ihren Grundzügen skizzieren. Im folgenden bezeichnen wir mit P(Z0) das kombinatorische Optimierungs-problem

minimiere f(x) so dass x ∈ Z0, Z0 endlich.

Die optimale Lösung dieses Problems nennen wir x*(Z0) und den optimalen Zielfunktionswert f(x*(Z0)) bezeichnen wir mit f *(Z0). Die Lösung dieses Pro-blems ist grundsätzlich durch Evaluierung, d.h. Zielfunktionswertberechnung aller Lösungen aus dem Zulässigkeitsbereich möglich. Durch den Vergleich dieser Werte kann die optimale Lösung ermittelt werden:

1. Berechne f(x) für alle x ∈ Z0. 2. x* ist dann optimale Lösung, wenn f(x*) ≤ f(x) für alle x ∈ Z0 gilt.

Diese vollständige Enumeration ist aber nur bei Problemen mit einer sehr kleinen Menge Z0 zulässiger Lösungen einsetzbar. Wesentlich günstiger ist es, den Zulässigkeitsbereich in Teilmengen zu unterteilen und für einige dieser Mengen nachzuweisen, dass sie die Optimallösung nicht enthalten. Da bei dieser Vorgehensweise nicht jede Lösung explizit betrachtet wird, werden solche Verfahren auch implizite Enumeration genannt. Ein bekanntes implizites Enumerationsverfahren ist das Branch & Bound-Verfahren.

Bei dieser Methode wird anstatt des zu lösenden Problems P(Z0) ein relaxiertes Problem P(Z) mit einem größeren Zulässigkeitsbereich Z ⊇ Z0 untersucht. Dies ist deswegen sinnvoll, weil das Problem P(Z) bei günstiger Wahl von Z erheblich

kombinatorisches Optimierungs-problem

vollständige Enumeration implizite Enumeration Branch & Bound

relaxiertes Problem

14 2. Exakte Methoden

leichter zu lösen ist. Ihnen ist sicherlich die übliche Relaxation eines ganzzahligen linearen Optimierungsproblems bekannt, die sich durch die Nichtberücksichtigung der Ganzzahligkeitsbedingungen ergibt. Eine mögliche Relaxation des TSPs ist ein Zuordnungsproblem; es vernachlässigt die Restriktion, die Orte in genau einer Rundreise zu durchlaufen.

Liefert die Lösung des relaxierten Problems P(Z) eine optimale Lösung x*(Z) ∈ Z0, so ist bereits die optimale Lösung des ursprünglichen Problems P(Z0) gefunden. Im anderen Fall stellt f(x*(Z)) eine untere Schranke des Zielfunktionswerts der gesuchten Lösung x*(Z0) wegen Z ⊇ Z0 dar.

Die Hauptkomponenten des Branch & Bound-Verfahrens sind, wie der Name schon sagt, das Verzweigen eines Lösungsweges (Branching) und das Abschnei-den eines Lösungspfades durch die Berechnung von Schranken (Bounding):

Branching bedeutet die Generierung mehrerer Unterprobleme P(Zi) aus einem

Problem P(Z) durch die Aufspaltung des Zulässigkeitsbereichs Z in Untermengen

Zi mit ZZi

i =U . Löst man die Unterprobleme P(Zi), so gilt wegen Zi ⊆ Z

f *(Zi) ≥ f *(Z) für alle i. (2.1)

Ist die optimale Lösung x*(Zi) eines Unterproblems P(Zi) auch zulässig für das Problem P(Z0), dann ist x*(Zi) auch optimale Lösung des Problems P(Z0 ∩ Zi). Wegen (Z0 ∩ Zi) ⊆ Z0 folgt f *(Z0 ∩ Zi) ≥ f *(Z0); f *(Z0 ∩ Zi) ist also eine obere Schranke für f *(Z0). Führt man die Verzweigung mit allen Problemen P(Zi) weiter, so erhält man einen Baum von Problemen mit der Wurzel P(Z).

Unter Bounding versteht man das „Sperren“ eines Unterproblems P(Zi) für eine weitere Verzweigung. Diese hat nämlich nur dann Sinn, wenn die optimale Lösung x*(Z0) in Zi enthalten sein kann. Bezeichnet man mit f̄ die kleinste bisher gefundene obere Schranke, können folgende Schlüsse gezogen werden:

• Gilt f *(Zi) ≥ f̄ , führt eine weitere Verzweigung wegen (2.1) zu keinem besseren Ergebnis; das Problem P(Zi) wird nicht weiter berücksichtigt.

• Gilt f *(Zi) < f̄ , so wird Zi weiter verzweigt.

Das Verfahren bricht ab, wenn kein Problem mehr aufgespalten werden muss. Die Lösung mit dem Zielfunktionswert f̄ ist optimale Lösung des Problems P(Z0).

Branching

Bounding

2.2 Das A*-Verfahren als Bestensuchverfahren 15

Nun schreiben wir das Branch & Bound-Verfahren zur Lösung des kombinatori-schen Optimierungsproblems formalisiert nieder:

Branch & Bound

P(Z) sei relaxiertes Problem f̄ := ∞ Q := {P(Z)} (ITBB) Solange Q ≠ Ø Entnehme ein Element P aus Q Löse P Wenn f < f̄ wenn x zulässig ist x* := x f̄ := f sonst Erzeuge Unterprobleme Pi Q := Q ∪ {Pi} Gehe zu (ITBB) Ausgabe: x* ist eine optimale Lösung mit Zielfunktionswert f̄ .

Branch & Bound ermittelt eine optimale Lösung des Problems P(Z0), wie durch folgende Plausibilitätsbetrachtung leicht nachgewiesen werden kann:

Durch den Verzweigungsprozess werden (unterschiedlich große) Zulässigkeitsbe-reiche Zi mit ii ZZ U= erzeugt. Wegen Z ⊇ Z0 gilt für die Zulässigkeitsbereiche

00 ZZZ ii ∩= : 00ii ZZ U= . Da )(*)(* 00 ZfZf i ≥ ist, folgt insgesamt f *(Z0) =

))(*min( 0iZf .

Diese Aussage gilt auch dann, wenn man die Zi ausschließt, die mit Sicherheit nicht zu einer optimalen Lösung führen (Bounding).

2.2 Das A*-Verfahren als Bestensuchverfahren

Sehr stark verwandt mit dem Branch & Bound-Verfahren ist das A*-Verfahren. Den Grundstein hierzu legten bereits 1980 HART et al. Im folgenden wird es skiz-ziert und im Anschluss auf das TSP angewendet. Dazu ist das TSP genauer zu präzisieren.

Branch & Bound Algorithmus

Kapitel 4

Simulated Annealing

4.1 Physikalischer Hintergrund und Idee des Simulated Annealing

Wie bereits in Kapitel 3 erwähnt wurde, ist ein Weg zur Lösung nicht-polynomialer Probleme die Verwendung heuristischer Verfahren. Eine andere Alternative bieten sogenannte approximative Algorithmen, die wie die Heuristiken nicht nachweislich zu einer Optimallösung führen, deren „fast sichere“ Konvergenz jedoch bewiesen werden kann. Eines der bekanntesten approximativen Verfahren ist Simulated Annealing (SA), ein stochastisches Verbesserungsverfahren. Hier wird eine Folge von zulässigen Lösungen erzeugt, deren Zielfunktionswert sich nicht unbedingt in jedem Schritt verbessert. Seinen Ursprung hat dieses Verfahren in der physikalischen Thermodynamik, die das Verhalten von Teilchen eines sich im thermischen Gleichgewicht befindlichen Stoffes zum Untersuchungsgegenstand hat. Obwohl die vielzitierten physikalischen Hintergründe nicht den eigentlichen Kern eines ökonomisch orientierten Kurses treffen, halten wir es für sinnvoll, Ihnen diese detaillierter als üblich zu erläutern. Damit wird hoffentlich Ihr tieferes Verständnis für SA geweckt.

In der Statistischen Mechanik studiert man das energetische Verhalten von Teilchen bei einer gegebenen Temperatur. Aufgrund der immens hohen Anzahl von Atomen pro Kubikzentimeter kann nur das wahrscheinlichste Verhalten eines Systems bei gegebener Temperatur in Experimenten beobachtet werden. HELMHOLTZ entwickelte die Modellvorstellung eines Systems als einer großen Menge identischer, kleiner Ensembles oder Parzellen. Jeder Zustand eines Ensembles ist durch die (Mikro-)Zustände der aus den Impulsen und den Positionen der in ihr enthaltenen Teilchen gekennzeichnet. Die Energie eines Teilchens ergibt sich aus der kinetischen Energie als Funktion des Impulses und der potentiellen Energie als Funktion seiner Position im Potentialfeld; die Gesamtenergie einer Parzelle ist die Energie ihrer Teilchen. Das

approximative Algorithmen stochastisches Verbesserungs-verfahren

kinetische Energie potentielle Energie

46 4. Simulated Annealing

wahrscheinlichste Verhalten eines Systems wird nun durch die Zustände aller Parzellen bestimmt.

Während in einem abgeschlossenen System alle möglichen Zustände gleichwahr-scheinlich sind, gilt diese Aussage in einem nicht abgeschlossenen System nicht. Aus der statistischen Mechanik ist bekannt, dass im thermischen Gleichgewicht, das sich nach gewisser Zeit bei konstanter Umgebungstemperatur einstellt, die Wahrscheinlichkeit eines Zustands z in den Ensembles zum Boltzmannfaktor

TkzE

Be)(−

proportional ist. Hierbei ist E(z) [Joule] die Energie des Zustands z, T die Temperatur und kB [Joule/Kelvin] die Boltzmannkonstante (kB = 1,380658⋅10–23). Für die Verhältnisse der Wahrscheinlichkeiten p(zi) und p(zj) zweier Zustände zi und zj mit den Energien Ei und Ej gilt also

TkEE

TkE

TkE

j

i B

ij

B

j

B

i

e

e

ezpzp

−

−

−

==)()( . (4.1)

Insbesondere sind nach dieser Aussage Zustände gleicher Energie auch gleich-wahrscheinlich. Aus Gleichung (4.1) lässt sich jedoch nicht folgern, dass bei gegebener Energie E auch die Wahrscheinlichkeit eines Zustands mit der Energie E proportional zum Boltzmannfaktor ist. Denn zu jedem Energieniveau gibt es eine unterschiedlich hohe Anzahl möglicher Zustandskombinationen aller Teilchen.

Beispiel 4.1

Für 3 Teilchen, die jeweils 4 mögliche (Einzel-)Zustände annehmen können, exi-stieren insgesamt 43 = 64 mögliche Zustände. Die Einzelzustände w1, w2, w3, w4 mögen die Energien E1 = 0, E2 = 1, E3 = 2 und E4 = 3 haben; damit ist für das Gesamtsystem eine Energie zwischen 3⋅E1 = 0 und 3⋅E4 = 9 möglich. Es existiert nur jeweils ein Zustand mit der Gesamtenergie 0 und 9, nämlich die Zustandskombinationen z = (w1w1w1) bzw. (w4w4w4), während bereits 6 Kombi-nationen (w1w1w3), (w1w2w2), (w1w3w1), (w2w1w2), (w2w2w1), (w3w1w1) die Gesamtenergie 2 haben. Die Anzahl Anz(E) möglicher Kombinationen in Abhängigkeit der Gesamtenergie ist in Abbildung 4.1 dargestellt.

abgeschlossenes System

thermisches

Gleichgewicht

Boltzmannfaktor

Boltzmann-konstante

4.1 Physikalischer Hintergrund und Idee des Simulated Annealing 47

0 1 2 3 4 5 6 7 8 9

Energie E

0

2

4

6

8

10

12

0 1 2 3 4 5 6 7 8 9

Energie E

Anzahl möglicher Zustandskombinationen Anz (E)

Abb. 4.1: Anzahl der möglichen Zustandskombinationen in Abhängigkeit der Energie für das Beispiel 4.1

In der Physik interessiert nun die Dichtefunktion über die möglichen Energieni-veaus der Zustandskombinationen einer im Gleichgewicht befindlichen Flüssigkeit bei konstanter Temperatur. Diese kann für jedes Energieniveau aus der Anzahl möglicher Zustände gewichtet mit dem Boltzmannfaktor gewonnen werden:

p(Ei) ∝ TBkiE

i

TBkiE

eEAnze iEzEz

−−

⋅=∑=

)()(:

. (4.2)

Anz(Ei) steht für die Anzahl der Zustände z mit der Energie Ei und das Zeichen ∝ für „proportional“. Da diese Berechnungsmethode bei M Zuständen und N Teilchen eine Summation über insgesamt MN Werte erfordert, ist sie praktisch nicht durchführbar. Einen Ausweg bietet bekanntlich die Monte Carlo-Methode. Die Dichtefunktion über die möglichen Energieniveaus wird hierbei auf der Basis zufällig und gleichverteilt ausgewählter Zustände approximativ bestimmt. Leider werden bei diesem Vorgehen selten Zustände mit niedriger oder hoher Energie erfasst, obwohl diejenigen mit niedriger Energie aufgrund ihres hohen Boltzmannfaktors sehr wahrscheinlich sind. Bei der modifizierten Monte Carlo-Methode werden deswegen Zustände mit der Energie E(z) proportional zur

Wahrscheinlichkeit TBkzE

e)(−

ausgewählt und gleichgewichtet addiert. Da auch dieses Verfahren Schwächen hat, schlugen 1953 METROPOLIS et al. ein Verfahren zur Ermittlung der Energieverteilung einer im Gleichgewicht befindlichen Flüssigkeit auf der Grundlage der Markovtheorie vor.

Energieniveau

Monte Carlo Methode Markovtheorie

48 4. Simulated Annealing

Wird ein bewegtes Teilchen probeweise in eine zufällige, zusätzliche Bewegungs-richtung mit einem zufällig großen Betrag versetzt, so ergibt sich aus dieser Zu-standsänderung von zi nach zj eine Energiedifferenz ΔE = Ej – Ei. Führt der neue Zustand zu einem geringeren Energieniveau (ΔE < 0), so wird die Zustandsänderung beibehalten; im anderen Fall wird sie nur mit der Wahrscheinlichkeit p(ΔE,T) =

TBkE

TBkjEiE

eeΔ−−

= akzeptiert, mit der Gegenwahrscheinlichkeit jedoch rückgängig gemacht. Es lässt sich nachweisen, dass nach unendlich häufiger Wiederholung dieses Vorgangs die Auftrittswahrscheinlichkeit eines Zustands proportional zum Boltzmannfaktor ist. Auf den allgemeinen Beweis dieser Aussage wird natürlich hier verzichtet. Zur Verdeutlichung stellen wir jedoch für 2 mögliche Zustände folgende Betrachtung an:

Allgemein lässt sich ein stationärer Markovprozess mit endlich vielen Zuständen durch eine Übergangsmatrix P beschreiben, deren Komponenten pij die Wahr-scheinlichkeit des Übergangs vom Zustand zi in den Zustand zj bedeuten. Liegt eine Wahrscheinlichkeitsverteilung π1 über die möglichen Zustände vor, so er-rechnet sich die Wahrscheinlichkeitsverteilung π2

nach einer Zustandsänderung mittels π2 = P⋅π1. Existiert eine Grenzverteilung π* nach unendlich vielen Übergängen, so gehorcht diese der Gleichung π* = P⋅π*.

Auf den beschriebenen physikalischen Prozess übertragen bestimmen die Boltz-mannfaktoren den Vektor π*.

Beispiel 4.2

Für 2 Zustände z1 und z2 eines Ensembles mit den Energien E1 und E2 ergeben sich folgende Komponenten von π*:

TBkE

eZT1

*1

−

⋅=π und TBkE

eZT2

*2

−

⋅=π mit 1)(21

−−−

+= TBkE

TBkE

eeZT .

Gilt o.B.d.A. E1 < E2, so erfolgt bei der Simulation nach METROPOLIS auf jeden Fall eine Zustandsänderung von z2 nach z1. Für die Übergangsmatrix

⎟⎟⎠

⎞⎜⎜⎝

⎛=

2212

2111pppp

P

gilt dann p21 = 1 und p22 = 0. Die Lösung der Gleichung π* = P⋅π* mit ⎟⎟⎠

⎞⎜⎜⎝

⎛

ππ=π *

2

*1*

ergibt dann die Matrix

Markovprozess

Übergangsmatrix

4.1 Physikalischer Hintergrund und Idee des Simulated Annealing 49

.0

1

*1

*2

*1

*2

*1

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

π

ππ

π−π

=P

Für die Übergangswahrscheinlichkeit vom Zustand z1 in den Zustand z2 gilt schließlich

TBkE

epΔ−

=π

π= *

1

*2

12 mit ΔE = E2 – E1.

Dieses Ergebnis lässt sich wie folgt zusammenfassen: Werden, ausgehend von einer beliebigen Zustandskombination unendlich viele Zustandsänderungen mittels der Übergangsmatrix P durchgeführt, so ist die Grenzverteilung eine Boltzmannverteilung der Zustände. Sie ergibt sich aus den Boltzmannfaktoren zu

TzE

TT eZzB)(

)(−

⋅= mit der Normierungskonstanten 1)( −−

⎟⎟⎠

⎞⎜⎜⎝

⎛= ∑

z

TzE

T eZ .

Boltzmannfaktoren

Energie

0

0,2

0,4

0,6

0,8

1

0 1 2 3 4 5 6 7 8 9

T = 3 T = 1

Abb. 4.2 : Die Boltzmannfaktoren für die Temperaturen T=1 und T=3 in Abhängigkeit der Energie

Beispiel 4.3 (Fortsetzung von Beispiel 4.1)

Wir führen das Beispiel fort, indem wir für die Temperaturen T = 1 und T = 3 die Energieverteilung berechnen. Die Boltzmannkonstante kB werden wir im folgenden vernachlässigen, da sie sowohl für das Verständnis des physikalischen

Normierungs-konstante

50 4. Simulated Annealing

Hintergrunds als auch für den Ablauf des daraus abgeleiteten Algorithmus nicht notwendig ist.

In Abbildung 4.2 sind die Boltzmannfaktoren für die Energiezustände E = 1,...,9 dargestellt, in Abbildung 4.3 ist die resultierende Verteilung über die möglichen Gesamtenergien graphisch veranschaulicht.

0 1 2 3 4 5 6 7 8 9

Energie E

0

0,05

0,1

0,15

0,2

0,25

0,3

p(E)

0 1 2 3 4 5 6 7 8 9

Energie E

T = 3 T = 1

Abbildung 4.3: Verteilung der Gesamtenergiezustände für die Temperaturen T=1 und T=3.

Die resultierende Verteilung ist unimodal mit einem Erwartungswert größer als Null für T > 0. Da die im System enthaltene kinetische Energie von T abhängig ist, ist es auch die Verteilungsfunktion der Energie. Für T gegen 0 [Kelvin] strebt auch der Erwartungswert dieser Verteilung gegen E = 0 [Joule], d.h. nur der (gesuchte) Zustand minimaler potentieller Energie (= 0) ist möglich.

Die Varianz der Energieverteilung nimmt mit wachsender Anzahl N betrachteter Teilchen ab. Für den Beobachter ist daher der Energiezustand des Stoffes makros-kopisch betrachtet bei gegebener Temperatur praktisch konstant.

Während sich die Teilchen bei Gasen und Flüssigkeiten frei bewegen können, herrschen bei festen Stoffen ihre Bewegungsfreiheit einschränkende Anziehungs- und Abstoßungskräfte. Eine besondere Rolle spielen Kristalle. Von einem Kristall spricht man dann, wenn sich alle Atome auf speziellen Zuständen mit minimaler potentieller Energie, den Gitterplätzen befinden. Für T > 0 ist jedoch auch die Besetzung sogenannter Nebengitterplätze oder Fehlstellen, die bezüglich der po-tentiellen Energie lokale Minima darstellen, nicht ausgeschlossen. Im Gegensatz zu Gasen ist bei diesen Strukturen zum Erreichen eines stabilen Zustands ein

Gitterplätze

Nebengitterplätze

lokales Minimum

4.2 Algorithmische Realisierung 51

Umgitterungsprozess notwendig, der ein gewisses Maß an Energie benötigt. Senkt man die Temperatur zu schnell auf T = 0 ab, ist eine Zustandsänderung der Atome aufgrund der zu niedrigen Energie nicht mehr möglich. Ein Gesamtzustand minimaler potentieller Energie kann nicht erreicht werden. Um sicherzustellen, dass alle Atome einen Gitterplatz einnehmen, wird zur Herstellung eines Kristalls das Material sehr langsam abgekühlt.

Dieser Kristallisationsprozess kann auf kombinatorische Optimierungsprobleme übertragen werden.

4.2 Algorithmische Realisierung

Im letzten Abschnitt wurde der von METROPOLIS et al. entwickelte Algorithmus zur Simulation der Abkühlung eines festen Stoffes beschrieben. KIRKPATRIK et al. wendeten 1983 diese Erkenntnisse als erste auf kombinatorische Optimierungs-probleme an. Die Analogie zwischen dem physikalischen Abkühlungsprozess von Kristallen und dem Simulated Annealing für Optimierungsprobleme entnehmen Sie der folgenden Aufzählung:

• Die möglichen Zustände entsprechen den zulässigen Lösungen eines Optimierungsproblems.

• Der Energie eines Zustands entspricht der Zielfunktionswert einer zu-lässigen Lösung, die es zu minimieren gilt.

• Dem Zustand minimaler Energie entspricht die globale Lösung des Optimie-rungsproblems.

Ein Verbesserungsverfahren zur Ermittlung eines lokalen Minimums des Problems entspricht dem Metropolis-Algorithmus für die Temperatur T = 0. Ähnlich wie Teilchen eines Kristalls in Nebengitterplätzen verharren, kann das Simulated Annealing in einem lokalen Optimum „hängen bleiben“. So wie dem Kristall von außen kinetische Energie durch eine Erhöhung der Temperatur zugeführt wird, um die Teilchen zum Verlassen der Nebengitterplätze zu bewegen, wird auch bei Simulated Annealing ein „Temperatur“-Parameter T verwendet. T > 0 bestimmt die Akzeptanzwahrscheinlichkeit für schlechtere Lösungen als die zuletzt generierte. Die langsame Abkühlung kristalliner Strukturen zur Vermeidung von Nebengitterplätzen entspricht einem langsamen Absenken des Parameters T.