Algorithmen

aufweisen (Sicherstellung einer hohen Reproduzierbarkeit). Die Arbeitsweise der SA-Metaheuristik lässt sich sehr gut im Debug-Modus von Visual Studio 2010 nachvollziehen. Interessant ist dabei die Veränderung der Variablen, wie Temperatur und Distance , zu beobachten.
    public void SA()
{
// Initialisierungen int iteration = -1;
double temperature = 10000.0;
double deltaDistance = 0;
double coolingRate = 0.9999;
double absoluteTemperature = 0.00001;
LoadCities();
double distance = GetTotalDistance(currentOrder);
// SA-Algorithmus while (temperature > absoluteTemperature)
{
// Bestimmung einer neuen Reihenfolge der Orte nextOrder = GetNextArrangement(currentOrder);
deltaDistance =
GetTotalDistance(nextOrder) - distance;
// Akzeptanz oder Ablehnung der neuen Lösung
if ((deltaDistance < 0) ||
(distance > 0 && Math.Exp
(-deltaDistance / temperature) >
random.NextDouble()))
{
for (int i = 0; i < nextOrder.Count; i++)
currentOrder[i] = nextOrder[i];

distance = deltaDistance + distance;
}
temperature *= coolingRate;
iteration++;
}
shortestDistance = distance;
}
    Listing 1

2.3Anmerkungen und Fazit
    Wir beenden an dieser Stelle unseren Ausblick auf die Implementierung von Algorithmen. Es ging um die Funktionsweise von Metaheuristiken. Diese dienen der Steuerung von Lösungsverfahren, wenn exakte Rechenverfahren oder das Durchsuchen des gesamten Lösungsraums zu aufwändig sind. Die Anwendung ist vielfältig und überall dort möglich, wo Optimierungsprobleme zu lösen sind. Soll ein solches Verfahren in einem Programm zum Einsatz kommen, wird es sicherlich im Rahmen des Fachkonzepts näher beschrieben. Einen Vorteil hat jedoch derjenige Entwickler oder Softwarearchitekt, der darüber schon mal etwas gehört hat. Außerdem bestand eines der Motive für diesen Beitrag darin, Ihre Neugier für interessante und neue Lösungsansätze zu wecken.
    Ein kleines Lexikon – Begriffe im Überblick
    Nachbarschaft
    Als Nachbarschaft bezeichnet man die Menge der Lösungen, die von einer existierenden Lösung durch eine einfache (lokale) Veränderungsoperation (Zug) erreicht werden können.
    Graph
    Ein Graph besteht aus einer Menge von Knoten (Punkten) und Kanten (Verbindungen zwischen den Punkten). Eine praktische Anwendung für einen Graphen ist der Netzplan eines lokalen Verkehrsbetriebs einer Stadt. Die Bus- und Straßenbahnhaltestellen sind dabei die Knoten und die Wege zwischen den Haltestellen die Kanten des Graphen.
    Gewichteter Graph
    Man spricht von einem gewichteten Graphen, wenn man den Kanten entsprechende Bewertungen zuweist. Handelt es sich beispielsweise bei den Kanten um Verbindungen zwischen realen Orten, so stellt die Gewichtung eine Entfernungsangabe dar. Die Beschreibung (Speicherung) der Gewichtung erfolgt in Form einer quadratischen Bewertungsmatrix.
    Komplexität von Problemen
    Anhand der Komplexitätstheorie werden Probleme klassifiziert, um deren Lösbarkeit (durch Computer) zu bestimmen. Die Zeitkomplexität quantifiziert den Berechnungsaufwand anhand der maximal notwendigen Schritte. Es ist zwischen Problemen der Klasse P und NP-vollständig zu unterscheiden. Man sagt Probleme der Klasse P sind deterministisch in Polynominalzeit lösbar; oder anders – diese Probleme sind praktisch lösbar (zum Beispiel das Sortierproblem). Die Klasse der NP-vollständigen Probleme umfasst die Menge aller nicht deterministisch in Polynominalzeit lösbaren Probleme. Ein bekanntes Problem ist das Rucksackproblem. Die hier vorgestellten Metaheuristiken unterstützen die Suche nach zulässigen Lösungen (nicht zwingend das Optimum!) für NP-vollständige Probleme.
    Traveling-Salesman-Problem (TSP)
    Das Travelling-Salesman-Problem (TSP) ist eines der bekanntesten und meist untersuchten Optimierungsprobleme. Ein Handlungsreisender soll in einer Rundreise (Tour) n vorgegebene Orte besuchen. Er startet dazu an einem Ort, besucht nacheinander die restlichen Orte, und kehrt schließlich zu seinem Ausgangspunkt zurück. Das Ziel ist es, die Tour so zu planen, dass deren Gesamtstrecke minimal wird. Die Entfernungen zwischen allen Paaren von Orten sind gegeben. Neben Entfernungsangaben kann es sich auch um Reisezeiten oder um andere Kostenarten (zum Beispiel Treibstoff) handeln. Ziel ist es, die Rundreise so zu planen, dass die Zielgröße minimiert wird [12].
    Links & Literatur
http://www.zaik.uni-koeln.de/AFS/publications/annualreports/97-98/html/node6.html
Robert Sedgewick: Algorithmen, Verlag Addision-Wesley, 1992
Richard Vahrenkamp: