Information Technology Reference
In-Depth Information
Problem des Handlungsreisenden
Nehmen wir an, dass eine Menge von
n
Städten (als Punkte in einer Ebene) sowie
die Abstände bzw. Kosten der Wege zwischen den Städten gegeben sind. Wir suchen
eine Rundreise mit minimaler Länge bzw. Kosten durch alle
n
Städte, auf der keine
Stadt mehr als einmal besucht wird. Mathematisch handelt es sich dabei um die Su-
che eines Hamiltonkreises, der jeden Knoten genau einmal enthält, mit minimalem
Gewicht in einem Graphen mit gewichteten Kanten.
Die formelle Definition des Problems des Handlungsreisenden (engl.
traveling
salesman problem (TSP)
)lautetwiefolgt:
Definition 11.1 (Problem des Handlungsreisenden)
Gegeben sei ein Graph G als Drei-
tupel
(
V
,
E
,
d
)
zur Berechnung der Kosten. Dessen Knotenmenge V
= {
v
1
,...,
v
n
}
reprä-
sentiert n verschiedene Städte, die paarweise durch Straßen in der Kantenmenge E
V
V
verbunden sind. Jeder dieser Straßen ist eine Fahrtzeit d
:
E
IR
+
zugeordnet. Dann ist das
Problem des Handlungsreisenden ein Optimierungsproblem
(P
n
,
f
TSP
,
<
)
,wobeiderRaum
aller Permutationen
P
n
die unterschiedlichen Besuchsreihenfolgen der Städte repräsentiert.
Die zu minimierende Bewertungsfunktion f
TSP
ist definiert für
(
1
,...,
n
) P
n
als
n
j
=
1
d
((
v
(
j
)
,
v
((
j
mod
n
)+1)
)).
f
TSP
((
1
,...,
n
)) =
Ein Problem des Handlungsreisenden heißt ferner symmetrisch, wenn für alle
(
v
i
,
v
j
)
E
sowohl
(
v
j
,
v
i
)
Ealsauchd
((
v
i
,
v
i
)) =
d
((
v
j
,
v
i
))
erfüllt sind.
Wie man bereits wissen sollte, ist dieses Problem NP-vollständig. D. h., dass kein
Algorithmus bekannt ist, der dieses Problem in polynomialer Zeit löst. Daher kön-
nen wir für ein großes
n
in annehmbarer Zeit nur eine Näherungslösung berechnen.
Natürlich können wir dabei die beste Lösung finden; dies ist aber nicht garantiert.
Später im Abschnitt 12.2 betrachten und untersuchen wir dieses berühmte Problem
noch genauer.
Zur Lösung des Problems des Handlungsreisenden geben wir zwei Kodierungen
vor:
1. Wir können eine Rundreise durch eine Permutation der Städte darstellen. D. h.,
die Stadt an
k
-ter Position wird im
k
-ten Schritt besucht. Diese Kodierung ver-
ursacht eine geringe Epistasie. So ändert z. B. der Austausch zweier Städte die
Fitness (lies die Kosten der Rundreise) i. Allg. etwa gleich stark. Dies entspricht
einer lokalen Touränderung.
2. Wir können eine Rundreise durch Angabe der Position der jeweils nächsten
Stadt in einer Liste beschrieben, aus der alle besuchten Städte gestrichen wer-
den. Im Gegensatz zur ersten Kodierung birgt diese eine hohe Epistasie. Die
Änderung eines Gens, speziell imChromosom vorn liegender Gene, kann (fast)
die gesamte Rundreise ändern (globale Touränderung) und führt daher oft zu
großen Änderungen der Fitness (siehe Tabelle 11.2).
Zeigt die verwendete Kodierung einerseits eine hohe Epistasie, so ist das Opti-
mierungsproblem oft für einen evolutionären Algorithmus schwer zu lösen, da Re-
gelmäßigkeiten fehlen, die durch ihn ausgenutzt werden könnten. Anders ausge-
