AuK/Approximationsalgorithmen
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Python</language>
Bereits von [[AuK/Randomisierte Algorithmen|probabilistischen Algorithmen]] ist bekannt, dass diese in manchen Fällen nicht die optimale Lösung bestimmen. Aber sie sind effizient und in vielen Fällen die einzige Möglichkeit praktisch überhaupt ein brauchbares Ergebnis zu erzielen. Ganz ähnlich verhält es sich mit Approximationsalgorithmen. Der Hauptunterschied besteht jedoch darin, dass nicht der Zufall allein bestimmt, wie gut das Ergebnis wird, sondern dass durch analytisches Vorgehen eine Lösung angenähert wird.
Eine Approximation verfolgt immer eine bestimmte Idee (eine Heuristik) von der man glaubt, dass sie (zumindest im Mittel) einen direkteren Weg hin zur Lösung bietet. Eine Approximation wird damit zu einer '''gezielten Suche''', bei der jeder Schritt (direkt oder indirekt) etwas näher zum Ergebnis führt.
==Lokale Suche==
Eine sehr einfache Heuristik ist die ganz allgemeine Idee, von den momentan zur Verfügung stehenden Schritten, einfach den auszuwählen, der vermeintlich am ehesten zur Lösung führt. Die Lokalität der Suche bezieht sich hierbei nicht auf einen bestimmten Ort, sondern eine begrenzte Menge von momentan verfügbaren Informationen. Anhand dieser ''lokalen'' Informationen wird die Entscheidung getroffen, in welche Richtung weiter gesucht wird.
===Hill Climbing===
Der Name steht für das anschauliche Beispiel der Suche nach dem Gipfel eines Berges, wobei an jeder Kreuzung stets der Weg eingeschlagen wird, der am steilsten nach oben führt (Gradientenaufstieg). Ohne Zweifel wird man auf diesem Weg den nächstgelegenen Gipfel erreichen. Bei dieser sehr einfachen Art der lokalen Suche wird versucht, basierend auf der aktuellen Situation, diese zu verbessern. Dazu wird die aktuelle Lösung leicht verändert und untersucht, ob sich eine Verbesserung ergeben hat. Wenn dem so ist, wird eben diese Lösung zur aktuellen Lösung und weitere Veränderungen können folgen.
Wir betrachten als Beispiel das $n$-Damen-Problem, das nach konfliktfreien Aufstellungen von möglichst vielen Damen auf einem $n$x$n$-Schachbrett fragt. (Aufgrund der gegebenen Spielregeln ist sofort einzusehen, dass es höchstens $n$ Damen sein können.) Würde man dieses Problem systematisch mittels Backtracking (Tiefensuche) lösen, würde das einen exponentiellen Aufwand nach sich ziehen.
Die Hill-Climbing-Strategie beginnt mit einer beliebigen Anfangsaufstellung von Damen, die dann solange verändert wird, bis sich keine Verbesserung mehr ergibt. Um ein Verbesserung feststellen zu können, muss eine Bewertung der aktuellen Damen-Positionen vorgenommen werden. Dies kann sehr einfach bewerkstelligt werden, indem die Anzahl der Konflikte ermittelt wird, also die Anzahl der Möglichkeiten in denen sich zwei Damen wechselseitig bedrohen, d.h. schlagen, können.
Im folgenden Programm wird eine Damenbelegung als Liste der Länge $n$ repräsentiert. Jedes Element der Liste steht für eine Linie (Spalte) des Schachbretts und kann die Werte $0$ bis $n$ annehmen. $0$ steht dafür, dass in der entsprechenden Linie gar keine Dame steht. Die übrigen Zahlen $1$ bis $n$ stehen für die Reihe (Zeile) in der die Dame steht.
In der folgenden Abb. sind drei Damen auf einem $4$x$4$-Schachbrett aufgestellt. Obwohl die sie sich zwar nicht bedrohen, stellt diese Aufstellung keine (exakte) Lösung dar, denn es können $4$ (allg. $n$) Damen konfliktfrei untergebracht werden.
[[Datei:Approx_Queens.png|center|200px]]
<code id="5f3a866d37913">
import math
import heapq
import random
</code>
<code id="5f3a866d379f4">
def conflicts(queens): # zählt die Konflikte auf dem Schachbrett
# zwei Damen in der gleichen Spalte sind bei dieser Datenstruktur nicht möglich
c = 0;
for col in range(len(queens)):
if queens[col] == 0:
c += 1 # keine Dame in dieser Spalte
continue
for col2 in range(col+1,len(queens)):
if queens[col2] == 0: continue;
if queens[col] == queens[col2]: c += 1; # in einer Reihe
if queens[col] - queens[col2] == col2-col: c += 1; # auf Diagonale
if queens[col2] - queens[col] == col2-col: c += 1; # auf Diagonale
return c;
def queensHillClimbing(queenPositions):
n = len(queenPositions)
best = queenPositions # initiale Positionen der n Damen
cBest = conflicts(best) # Anzahl der Konflikte
while True:
if cBest == 0: # Damen können sich nicht schlagen
return (best,cBest) # Lösung gefunden
better = None
for i in range(n-1):
for j in range(i+1,n):
# Damenpositionen zweier Spalten werden getauscht
neighbor = best.copy()
neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
cNeighbor = conflicts(neighbor)
if cNeighbor < cBest: # weniger Konflikte?
better = neighbor
cBest = cNeighbor
if not better: # keine Verbesserung durch einfachen Tausch erreichbar
return (best,cBest) # lokales Optimum gefunden
else: # es gab eine Verbesserung
best = better # Ausgangssituation für den nächsten Durchlauf
</code>
<run id="5f3a8557d6c0b">
print(queensHillClimbing(list(range(1,5))))
print(queensHillClimbing(list(range(1,6))))
print(queensHillClimbing(list(range(1,7))))
print(queensHillClimbing(list(range(1,8))))
print(queensHillClimbing(list(range(1,9))))
print(queensHillClimbing(list(range(1,10))))
print(queensHillClimbing(list(range(1,30))))
</run>
Die Ergebnisse zeigen, dass auch für große Schachbretter ein Ergebnis in relativ kurzer Zeit erzielt wird. Es ist aber auch erkennbar, dass selbst bei kleinen Schachbrettern (z.B. $n=6$ und $n=8$) nicht immer die Lösung, sondern nur eine Näherung mit sehr wenigen Konflikten gefunden wird.
Hill Climbing ist in dieser Form ein ''deterministisches'' Verfahren und selbst bei mehrfacher Wiederholung ändern sich die Ergebnisse nicht. Die einzige Möglichkeit, das Ergebnis zu beeinflussen, besteht hier darin, die Ausgangssituation, also die initialen Damenpositionen, zu verändern. Allgemein gilt: Die Güte der Ergebnisse von Hill Climbing Algorithmen ist in hohem Maße davon abhängig, wie die Initialsituation beschaffen ist.
<run id="5f3a866d37d44">
d8 = list(range(1,9)) # [1,2,3,4,5,6,7,8]
for _ in range(10):
random.shuffle(d8) # Mischen der Liste
print(queensHillClimbing(d8))
</run>
<!--
([1, 5, 8, 6, 3, 7, 2, 4], 0)
([4, 8, 1, 5, 7, 2, 6, 3], 0)
([3, 5, 7, 1, 4, 2, 8, 6], 0)
([2, 4, 6, 8, 3, 1, 7, 5], 0)
([4, 1, 3, 6, 2, 7, 5, 8], 1)
([4, 2, 7, 3, 6, 8, 5, 1], 0)
([3, 7, 4, 8, 1, 5, 6, 2], 1)
([5, 3, 6, 2, 7, 1, 4, 8], 1)
([1, 3, 6, 2, 7, 5, 8, 4], 2)
([3, 7, 4, 1, 5, 2, 6, 8], 1)
-->
===Plateau Search===
Das Hill Climbing wird immer nur solange fortgesetzt, bis von der aktuellen Situation aus keine bessere Situation mehr erreicht werden kann. Eine solche Situation wird '''lokales Optimum''' genannt. Im Allgemeinen ist man aber am '''globalen Optimium''' interessiert. Ein erster Schritt um nicht bei einem lokalen Optimum ''stecken zu bleiben'' ist die Plateau-Suche. Hier werden nicht nur bessere Teillösungen weiterverfolgt, sondern auch die, die genauso gut sind. Eine einfache Ersetzung von '''<''' durch '''<=''' reicht allerdings nicht aus für eine stabile Plateau-Suche. Die 6-Damen Ausgangssituation '''[1,2,3,4,5,6]''' würde dann z.B. mit o.a. Programm zu einer Endlosschleife führen.
Das Problem ist, dass es bei der Plateau-Suche nun möglich ist, durch Veränderung der Damen-Positionen eine Situation herbeizuführen, die bereits in einem vorherigen Schritt Ausgangssituation war. Beim einfachen Hill Climbing sind solche Zyklen nicht möglich. Um diese zu vermeiden, dürfen bereits geprüfte Situationen nicht erneut geprüft werden. Eine '''Tabu-Liste''' ist erforderlich. So führt auch o.g. Damen-Situation zu einem Ergebnis und die Chance ein globales Optimum zu ermitteln, ist um einiges gestiegen.
<code id="5f3a866d37ab7">
def queensPlateau(queenPositions):
n = len(queenPositions)
best = queenPositions # initiale Positionen der n Damen
cBest = conflicts(best) # Anzahl der Konflikte
tabu = set() # Tabu-Liste
while True:
if cBest == 0: # Damen können sich nicht schlagen
return (best,cBest) # Lösung gefunden
better = None
tabu.add(str(best)) # jedes verfolgte Element wird aufgenommen
for i in range(n-1):
for j in range(i+1,n):
# Damenpositionen zweier Spalten werden getauscht
neighbor = best.copy()
neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
if str(neighbor) in tabu:
continue # Tabu-Einträge werden nicht nochmals geprüft
cNeighbor = conflicts(neighbor)
if cNeighbor <= cBest: # weniger Konflikte?
better = neighbor
cBest = cNeighbor
if not better: # keine Verbesserung durch einfachen Tausch erreichbar
return (best,cBest) # lokales Optimum gefunden
else: # es gab eine Verbesserung
best = better # Ausgangssituation für den nächsten Durchlauf
</code>
<run id="5f3a8587b0c8c">
print(queensPlateau([1,2,3,4,5,6]))
print(queensPlateau([1,2,3,4,5,6,7,8]))
print(queensPlateau(list(range(1,30))))
</run>
<!--
([1, 2, 5, 3, 6, 4], 1)
([6, 4, 2, 8, 5, 7, 1, 3], 0)
([17, 23, 12, 3, 6, 16, 29, 20, 24, 21, 9, 4, 1, 18, 22, 5, 13, 8, 10, 14, 26, 28, 25, 27, 2, 19, 11, 7, 15], 0)
-->
'''Hinweis:''' ''Bei komplexeren Problemen, kann die Tabu-Liste sehr groß werden. Sie nimmt damit sehr viel Speicherplatz ein und die Bestimmung ob ein Element enthalten ist dauert zunehmend länger. Um das zu vermeiden, wird meist in regelmäßigen Abständen die Größe der Liste geprüft und bei Überschreiten eines Limits Elemente aus dieser entfernt. Am sinnvollsten ist die Entfernung genau der Elemente, die sich am längsten in der Liste befinden.''
===Threshold Accepting===
Bei der Plateau-Suche werden alle Teillösungen weiterverfolgt, die mindestens genauso gut sind wie die vorherige. Durch Threshold Accepting wird die Menge der weiterzuverfolgenden Teillösungen noch einmal erweitert. Hier werden auch '''schlechtere Teillösungen''' weiterverfolgt, solange sie nicht viel schlechter sind als die vorherigen. Dieses ''viel schlechter'' muss natürlich im Einzelfall konkret definiert werden. Beim oben beschriebenen $n$-Damen-Problem könnte z.B. die Differenz zwischen den Anzahlen der Konflikte zweier Situationen herangezogen werden. Lösungen, die z.B. nur einen Konflikt mehr haben als die Ausgangssituation, dürften dann weiterverfolgt werden. Auch hier ist eine Tabu-Liste erforderlich, um Zyklen zu vermeiden. Für das $6$-Damen-Problem mit der Ausgangssituation '''[1,2,3,4,5,6]''' wird durch Akzeptieren von Kandidaten, die um einen Konflikt schlechter sind, nun eine Lösung gefunden.
<code id="5f3a866d37b4c">
def queensThreshold(queenPositions, t):
n = len(queenPositions)
best = queenPositions # initiale Positionen der n Damen
cBest = conflicts(best) # Anzahl der Konflikte
tabu = set() # Tabu-Liste
while True:
if cBest == 0: # Damen können sich nicht schlagen
return (best,cBest) # Lösung gefunden
better = None
tabu.add(str(best)) # jedes verfolgte Element wird aufgenommen
cBest += t # erweitern um akzeptable Verschlechterung
for i in range(n-1):
for j in range(i+1,n):
# Damenpositionen zweier Spalten werden getauscht
neighbor = best.copy()
neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
if str(neighbor) in tabu:
continue # Tabu-Einträge werden nicht nochmals geprüft
cNeighbor = conflicts(neighbor)
if cNeighbor <= cBest: # nicht viel schlechter?
better = neighbor
cBest = cNeighbor
if not better: # keine Verbesserung durch einfachen Tausch erreichbar
return (best,cBest-t) # lokales Optimum gefunden
else: # es gab eine Verbesserung
best = better # Ausgangssituation für den nächsten Durchlauf
</code>
<run id="5f3a866d37dd5">
print(queensThreshold([1,2,3,4,5,6],1)) # Verschlechterung um 1 akzeptabel
</run>
<!--
([4, 1, 5, 2, 6, 3], 0)
-->
'''Hinweis:''' In diesem Programm ist <tt>better</tt> nach einem Durchlauf nicht zwangsläufig eine Verbesserung gegenüber <tt>best</tt> da auch schlechtere Teillösungen akzeptabel sind. Im Folgedurchlauf ist <tt>best</tt> damit nicht unbedingt das beste bereits gefundene Ergebnis. Gibt es z.B. eine zeitliche Begrenzung, dann sollte man sich das wirklich beste gefundene Ergebnis an anderer Stelle merken, um bei Ablauf des Zeitlimits dieses liefern zu können.<br>
Viele weitere Variationen sind ebenfalls denkbar. So könnte der nächste Nachbar zufällig gewählt werden (nicht wie hier der bestmögliche) oder bei der Überprüfung auf Verbesserung könnte mit dem bisher besten Ergebnis verglichen werden (nicht wie hier mit dem zuletzt gefundenen) oder der übergebene Schwellwert <tt>t</tt> könnte im Verlauf gesenkt werden.
===Simulated Annealing===
Bei dieser Variation der lokalen Suche wird das Zulassen einer zwischenzeitlichen Verschlechterung einer gewissen Wahrscheinlichkeit unterworfen. Eine Verschlechterung ist also im Verlauf der Suche nur mit einer immer niedriger werdenden Wahrscheinlichkeit wirklich akzeptabel. Dieses ''Niedrigerwerden'' (diese Verringerung) wird in der Literatur oft mit dem Abkühlen eines geschmolzenen Materials verglichen. Praktisch ist es nur die stetige Verringerung eines Faktors, der bei der Entscheidung über die Akzeptanz der Verschlechterung mit einbezogen wird. Die Größe dieses Faktors und die Art und Weise wie dieser verringert wird, ist vom Problem abhängig und muss immer individuell festgelegt werden.
Im folgenden Programm ist ersichtlich, dass die Laufzeit, neben dem vorzeitigen Abbruch, wenn die Lösung gefunden wurde, nur durch die Verringerung des Faktors <tt>temp</tt> bestimmt wird. Das ist äußerst praktisch, da die maximale Dauer auf diese Weise weitestgehend unabhängig von der Größe des Problems ist.
<code id="60045e28c9f84">
def queensSimAnn(queenPositions):
n = len(queenPositions)
best = queenPositions # initiale Positionen der n Damen
cBest = conflicts(best) # Anzahl der Konflikte
cur = best
cCur = cBest
temp = 1000 # Anfangs-"Temperatur"
while temp > 0.1:
if cBest == 0: # Damen können sich nicht schlagen
return (best,cBest) # Lösung gefunden
# zufällige Wahl eines Nachbarn
i = j = random.randint(0, n - 1)
while j == i:
j = random.randint(0, n - 1)
nb = cur.copy()
nb[i], nb[j] = nb[j], nb[i]
cNb = conflicts(nb)
# besser oder zufällig ist die Verschlechterung erlaubt
if cNb <= cCur or math.exp((cCur - cNb) / temp) > random.random():
cur = nb
cCur = cNb
if cCur < cBest: # besser als momentan beste Lösung
best = cur
cBest = cCur
temp *= 0.999 # "Abkühlung"
return (best, cBest)
</code>
<run id="60045e28ca024">
print(queensSimAnn([1, 2, 3, 4, 5, 6]))
print(queensSimAnn(list(range(1, 30))))
</run>
''Sollte der Browser während der Ausführung ein langsames Script melden, wählen Sie die Option „Warten“.''
<!--
''Ausführung benötigt möglicherweise bis zu einer Minute. '''Beispielergebnis:'''''
([2, 4, 6, 1, 3, 5], 0)
([38, 4, 19, 7, 16, 28, 3, 26, 6, 33, 12, 24, 20, 23, 29, 15, 36, 39, 32, 35, 11, 2, 27, 1, 10, 14, 37, 34, 18, 22, 17, 13, 9, 25, 30, 5, 31, 8, 21], 1)
-->
'''Hinweis:''' Eine Tabu-Liste ist hier nicht erforderlich, da die weiter zu verfolgenden Kandidaten zufällig ausgewählt werden. Zyklen sind so zwar immer noch möglich, aber es gibt die Möglichkeit diese auch wieder zu verlassen. Wird der nächste Kandidat systematisch ausgewählt (so wie in den Beispielen zu Plateau-Search und Threshold Accepting), gibt es diese Möglichkeit nicht.
==Evolutionäre Algorithmen==
Diese Art von Algorithmen beruht auf dem Prinzip der natürlichen Evolution bzw. der Genetik (genetische Algorithmen). Es geht also darum, Dinge miteinander auf zufällige Art zu kreuzen, um so Änderungen hervorzurufen, die möglicherweise zu Verbesserungen führen. Durch geziehlte Kreuzung ("Züchtung") kann Einfluss auf die Ergebnisse der Evolution genommen werden. Anders als bei der lokalen Suche, wo immer ausgehend von '''einem''' Momentanzustand '''ein''' Folgezustand ermittelt wird, wird hier mit '''Populationen''' gearbeitet, also einer ganzen Menge von Momentan- und Folgezuständen.
Aufbauend auf einer Basispopulation (einer Menge von Initialzuständen) werden folgende Schritte immer wieder durchlaufen:
# Auswahl einer Teilmenge aus der Basispopulation (Selektion für Rekombination)
# Kreuzungen innerhalb dieser Teilmenge erweitern die Basispopulation (Rekombination)
# Entfernen einer Teilmenge aus der Basispopulation (Selektion für Aussortierung: Fitness-Funktion)
Beim $n$-Damen-Problem könnten diese Schritte z.B. ausgehend von einer Population von 20 zufällig generierter Damen-Situationen folgendermaßen modelliert werden.
# Auswahl der 3 Damen-Situationen mit der geringsten Anzahl von Konflikten
# 4-fache Kreuzung der 3 Situationen führt zu 12 neuen Situationen
# Entfernung der 12 Situationen mit der höchsten Anzahl von Konflikten
<code id="5f3a866d37c6e">
def queensGenetic(n,iterations):
size = 20 # Größe der Population
select = 3 # Selektion für Kreuzung
recomb = 4 # Anzahl der Kreuzungen pro Paar
swap = (select*select-select)//2*recomb # Ersetzungen in der Basispopulation
print("Evolution:", iterations, "times swap", swap, "from", size)
if swap > size or swap == 0:
return "Error: swap size invalid"
# zufällige Basispopulation von Damen-Situationen generieren
s = list(range(1,n+1))
pp = [random.sample(s, k=n) for _ in range(size)]
cf = [conflicts(a) for a in pp]
population = [(cf[i],pp[i]) for i in range(size)]
heapq.heapify(population) # sortiert nach Konflikten
best = heapq.nsmallest(1,population)[0] # momentan beste
for i in range(iterations): # Evolutionsschritte
A = heapq.nsmallest(select,population) # die besten
for a in A:
for b in A:
if a == b: break # für jedes Paar der Selektion
for _ in range(recomb): # neue Situation rekombinieren
# zufällig einige Stellen von a übernehmen, Rest leer lassen
new = [a[1][r] if random.randint(0,1) else None for r in range(n)]
for bx in b[1]: # die Stellen von b durchgehen
if bx in new: continue # kommen schon in new vor
ai = 0
while new[ai]: ai += 1 # leere Stelle in new finden
new[ai] = bx # dort den Wert von b setzen
cnew = conflicts(new)
if cnew < best[0]: # gab es Verbesserungen
best = (cnew,new)
heapq.heappush(population,(cnew,new))
population = heapq.nsmallest(size,population)
return best
</code>
<run id="5f3a866d37ee5">
print(queensGenetic(30,1000))
</run>
<!--
Evolution: 1000 times swap 12 from 20
(6, [16, 8, 4, 15, 29, 18, 25, 7, 5, 20, 27, 6, 13, 23, 19, 9, 24, 26, 14, 11, 2, 3, 17, 12, 22, 10, 1, 30, 21, 28])
-->
Nicht für jedes Problem sind genetische Algorithmen geeignet. Auch beim $n$-Damen-Problem ist es, vor allem bei größeren $n$, äußerst unwahrscheinlich durch Rekombination eine Lösung zu finden. Neben der hier verwendeten '''Permutations-Rekombination''' gibt es viele weitere Varianten z.B. '''k-point-crossover''', um Probleminstanzen zu neuen Instanzen zu kombinieren. Meist wird in genetischen Algorithmen auch '''Mutation''' zugelassen. Bei dieser werden neben der Änderung durch zufällige Kreuzung noch weitere zufällige spontane Änderungen mit einer gewissen Wahrscheinlichkeit zugelassen. Generell zeigen evolutionäre Ansätze eine Vielzahl von Parametern mit denen die Vorgänge gesteuert werden können. Hier die passenden Parameterwerte für ein konkretes Problem zu ermitteln, stellt eine nicht zu unterschätzende Schwierigkeit dar.