gfoidl 
myCSharp.de-Team (Moderation)
Dabei seit: 07.06.2009
Beiträge: 1.533
Entwicklungsumgebung: VS 2010
Herkunft: Waidring / Tirol
 |
|
(Abbildung1: Beispielanwendung zur Minimierung einer rellen Funktion)
Simulated Annealing
Simualted Annealing (SA) ist ein meta-heuristisches Optimierungsverfahren welches auf kontinuierliche und auf diskrete Probleme angewandt werden kann. Es besitzt den großen Vorteil dass lokale Minima verlassen werden können.
Dieser Artikel ist in zwei Teilen verfasst. Ausführliche Grundlagen sind in einem  separaten Teil als PDF verfasst worden. Dieser Teil beinhaltet eine Kurzeinführung und zwei typsiche Beispiele für SA:Exkurs Wärmebehandlung (hilfreich für das Verständnis)
In der Metallurgie wird ein Metall erhitzt und somit in einen hohen Energiezustand versetzt. Durch langsames Abkühlen (Stunden, Tage, je nach Größe des Metallstücks) haben die Kristalle ausreichend Zeit sich im Gefüge neu anzuordnen und ein stabiles Gefüge zu bilden. Nach der Abkühlung liegt ein Gefügezustand mit minimaler Energie vor, der Nahe am Optimum ist. Aufgrund des niedrigen Energiezustandes wird dies auch als Weichglühen bezeichnet was sich dadurch äußert dass das Metall weich ist ;)
Einführung
Simulated Annealing wurde inspiriert von der Wärmebehandlung von Metallen - dem sogenannten Weichglühen. Daher kommt auch die englische Bezeichnung dieses Verfahrens. Während andere Verfahren zum großen Teil in lokale Minima hängen bleiben können, ist es eine besondere Stärke dieses Algorithmus aus diesen wieder herauszufinden. Die am Ende gefunden Lösung stellt bei unendlicher Abkühlungszeit mit Sicherheit das globale Minimum (oder Maximum) dar, während bei endlicher Abkühlzeit dies nicht immer der Fall sein muss.
Beim langsamen Abkühlen eines Metalls ordnen sich die Kristalle so an dass sich im Gefüge ein Zustand mit möglichst niedriger Energie einstellt. Tritt allerdings eine zu schnelle Abkühlung auf, so haben die Kristalle nicht die Zeit den minimalen Energiezustand zu finden und das System bleibt in einem lokalen Minimum hängen. Ein niedrigerer Energieszustand ist in diesem Fall gleichbedeutend mit einem stabilen Endzustand, also einem stabilen Gefüge im Metall.
Nachfolgend eine grobe Skizzierung des Algorithmus (für ein genauere Betrachtung sei auf den separaten Teil " Einführung in den Simulated Annealing Algorithmus" verwiesen), wo bewusst das Analogon zur Metallurgie aufrecht erhalten wurde, um sich die Schritte bildlicher vorstellen zu können.- Nimm eine zufällige Anfangslösung x aus dem Definitionsbereich des Problems.
- Erwärme auf Glühtemperatur und somit die Energie des Systems.
- Durch den hohen Energiezustand können sich die Kristalle um ihre Anfangsposition bewegen, d.h. es wird eine zufällige Verschiebung dx vorgenommen.
- Ist der Energiezustand der neuen Position niedriger als der alte Energiezustand so wird dieser verwendet.
Das wäre bereits ein Algorithmus zur Suche nach einem Minimum, allerdings mit dem gravierenden Nachteil, dass der Algorithmus sich aus einem lokalen Minimum nicht mehr befreien kann, da er stets zu niedrigeren Energiewerten geht - bis er in einem stabilen Endzustand (= lokales Minimum) hängen bleibt.
Um dieses Problem zu lösen erlaubt SA auch einen Sprung zu höheren Energiezuständen. Diese werden allerdings nur mit einer bestimmten Wahrscheinlichkeit durchgeführt. Diese Wahrscheinlichkeit ist abhängig von der aktuellen Temperatur des Systems sowie der Energiedifferenz und folgt der Boltzmann-Gibbs-Verteilung.
Sinkt die Temperatur gegen 0 so wird die Wahrscheinlichkeit für einen Sprung auf ein höheres (Energie-) Niveau immer geringer. Für kleine Energieunterschiede ist die Wahrscheinlichkeit wiederum nahezu bei 100% und somit kann sich x in seiner näheren Umgebung noch frei bewegen, während für große Energieunterschiede ein Sprung zwar möglich, aber sehr unwahrscheinlich ist.
- Senke die Temperatur und der Zyklus mit der zufälligen Verschiebung beginnt erneut.
- Diese Schritte werden so lange durchgeführt bis die Endtemperatur. Dann beginnt der gesamte Zyklus erneut und wird wiederholt bis die Lösungen konvergieren oder sonst ein Abbruchkriterium erreicht wurde.
Verbildlicht kann sich das auch so vorgestellt werden:
Angenommen, man sucht in einer zweidimensionalen Landschaft den (global) tiefsten Punkt. Die Landschaft selbst besteht aus vielen unterschiedlich tiefen Dellen. Die einfache Suchstrategie (suche den nächsten tiefsten Punkt) entspricht dem Verhalten einer Kugel, welche in dieser Landschaft ausgesetzt wird. Sie rollt zum nächsten lokalen Minimum und bleibt dort. Bei der simulierten Auskühlung wird der Kugel immer wieder ein Stoß versetzt. Dieser ist stark genug, um die Kugel aus einer flachen Delle (lokales Minimum) zu entfernen, reicht aber nicht aus, um aus dem globalen Minimum zu fliehen.
Dieses Verfahren ist somit eine  Heuristik. D.h. es ist ein Verfahren das oft sehr gut funktioniert, aber keine Garantie für eine optimale oder auch nur gute Lösung gibt. Simulated Annealing ist eine Entwicklung die aus dem Metropolisalgorithmus hervorgegangen ist.
Basisimplementierung
Der zugrunde liegende Algorithmus ist als abstrakte Basisklasse implementiert.
(Abbildung2: Basisklasse)
 C#-Code: |
using System;
namespace gfoidl.ComputationalIntelligence.SimulatedAnnealing
{
public abstract class SimulatedAnnealing<T>
{
#region Felder
protected Random _rnd = new Random();
#endregion
#region Eigenschaften
public double StartTemperature { get; set; }
private double _stopTemperatur = 0;
public double StopTemperature
{
get { return _stopTemperatur; }
set { _stopTemperatur = value; }
}
public int Cycles { get; set; }
public double Energy { get; set; }
public double Temperature { get; protected set; }
public abstract T[] Array { get; set; }
#endregion
#region Methoden
public abstract double DetermineEnergy();
public void Anneal()
{
double currentEnergy = this.DetermineEnergy();
T[] bestArray = this.GetArrayCopy();
double bestEnergy = currentEnergy;
this.Temperature = this.StartTemperature;
for (int i = 0; i < this.Cycles; i++)
{
T[] currentArray = this.GetArrayCopy();
this.Randomize();
double newEnergy = this.DetermineEnergy();
if (newEnergy < bestEnergy)
{
bestEnergy = newEnergy;
bestArray = this.GetArrayCopy();
}
double deltaEnergy = newEnergy - currentEnergy;
double probality = Math.Exp(-deltaEnergy / this.Temperature);
if (probality > _rnd.NextDouble())
{
currentEnergy = newEnergy;
}
else
{
this.Array = currentArray;
}
this.Temperature = ReduceTemperature(i);
}
this.Energy = bestEnergy;
this.Array = bestArray;
}
protected virtual double ReduceTemperature(int cycle)
{
return this.StartTemperature * (1d - (double)(++cycle) / this.Cycles);
}
protected abstract T[] GetArrayCopy();
protected abstract void Randomize();
#endregion
}
} |
Anwendung für die Minimierung einer reellen Funktion
Abbildung1 zeigt die Beispielanwendung.
Von der Basisimplementierung muss abgeleitet werden um eine Klasse für das konkrete Problem - hier die Minimierung einer reellen Funktion - zu erhalten. Es ist lediglich nötig die abstrakten Member der Basisklasse zu implementieren. Der restliche Algorithmus ist in der Basisklasse generisch implementiert.
Da die Problemdimension niedrig ist (2 dimensional) wird für die Wahl eines Nachbarn einfach eine neue Zufallsposition aus dem Definitionsbereich der Funkionen gewählt. Im Beispiel besitzen alle Funktion einen Definitionsbereich von [-3,3]x[-3,3].
| C#-Code: |
using gfoidl.ComputationalIntelligence.SimulatedAnnealing;
using SimulatedAnnealing.FunctionMinimizing.Function;
namespace SimulatedAnnealing.FunctionMinimizing
{
public sealed class FunctionMinimizingSimulatedAnnealing :
SimulatedAnnealing<double>
{
private double[] _vector;
private FunctionBase _function;
public override double[] Array
{
get { return _vector; }
set { _vector = value; }
}
public FunctionMinimizingSimulatedAnnealing(FunctionBase function)
{
_function = function;
this.StartTemperature = 500;
this.Cycles = 100;
double x = _rnd.NextDouble() * 6 - 3;
double y = _rnd.NextDouble() * 6 - 3;
_vector = new double[] { x, y };
}
public override double DetermineEnergy()
{
return _function.Function(_vector);
}
protected override double[] GetArrayCopy()
{
double[] tmp = new double[_vector.Length];
_vector.CopyTo(tmp, 0);
return tmp;
}
protected override void Randomize()
{
double x = _rnd.NextDouble() * 6 - 3;
double y = _rnd.NextDouble() * 6 - 3;
_vector = new double[] { x, y };
}
}
} |
Im angehängten Beispielprojekt stehen ein paar Funktionen zur Auswahl bereit und die Anfangslösung - der Startpunkt - kann durch einen Mausklick bestimmt werden.
Das Beispiel meines Artikels " Particle swarm optimization for function optimization" ist mit dem angehängten Beispiel vergleichbar. Dabei ist auch ersichtlich dass SA für diese Art der Probleme wesentlich schneller ist, die Partikelschwärme jedoch interessanter zu beobachten sind ;)
Anwendung für das Problem des Handelsreisenden
(Abbildung3: Beispielanwendung für das Problem des Handelsreisenden. Die Lösung dauerte für die 100 Städte wenige Sekunden.)
Das Problem des Handelsreisenden - auch Traveling Salesman Problem (TSP) genannt - ist ein Vertreter für diskrete kombinatorische Probleme. Für nähere Informationen sei auf die Literatur verwiesen.
Während ein Brute-Force-Ansatz für hunderte Städte auf heutigen CPUs mehrere Jahre benötigen würde und viele andere Verfahren zur Lösung des TSP praktisch nur bis 50...100 Städte verwendbar sind schafft SA eine Tour mit 500 Städten in wenigen Sekunden.
Bevor der Code für die grundlegende Lösung erstellt wird müssen die Rahmenbedingunen zur Lösung aufgestellt werden:- Städte werden durch Vektoren repräsentiert
- als Distanzmaß wird die euklidische Distanz verwendet
- eine Route wird durch den Indexvektor der Städte dargestellt
- SA wird auf diesen Indexvektor angewandt
- für die Wahl werden zwei aufeinander folgende Städte vertauscht und die Route angepasst
Für eine etwas mathematischere Behandlung sei wiederum auf den separaten Teil verwiesen.
Für die Darstellung einer Stadt wird folgende Klasse verwendet:
| C#-Code: |
using System;
namespace SimulatedAnnealing.TravelingSalesMan
{
public class City
{
public int XPos { get; private set; }
public int YPos { get; private set; }
public City(int x, int y)
{
this.XPos = x;
this.YPos = y;
}
public int Distance(City other)
{
return Distance(other.XPos, other.YPos);
}
public int Distance(int x, int y)
{
int deltaX = this.XPos - x;
int deltaY = this.YPos - y;
return (int)Math.Sqrt(deltaX * deltaX + deltaY * deltaY);
}
}
}
|
Die konkrete Implementierung des SA für das TS-Problem:
| C#-Code: |
using gfoidl.ComputationalIntelligence.SimulatedAnnealing;
namespace SimulatedAnnealing.TravelingSalesMan
{
public sealed class TravelingSalesmanSimulatedAnnealing : SimulatedAnnealing<int>
{
private City[] _cities;
private int[] _path;
public override int[] Array
{
get { return _path; }
set { _path = value; }
}
public TravelingSalesmanSimulatedAnnealing(
City[] cities,
double startTemp,
int cycles)
{
this.Temperature = startTemp;
this.StartTemperature = startTemp;
this.Cycles = cycles;
_cities = cities;
_path = new int[_cities.Length];
}
public override double DetermineEnergy()
{
double cost = 0;
for (int i = 1; i < _cities.Length; i++)
{
double dist = _cities[_path[i - 1]].Distance(_cities[_path[i]]);
cost += dist;
}
return cost;
}
protected override int[] GetArrayCopy()
{
int[] result = new int[_path.Length];
_path.CopyTo(result, 0);
return result;
}
protected override void Randomize()
{
for (int i = 0; i < this.Temperature; i++)
{
int index1 = _rnd.Next(_path.Length);
int index2 = _rnd.Next(_path.Length);
double d =
Distance(index1, index1 + 1) +
Distance(index2, index2 + 1) -
Distance(index1, index2) -
Distance(index1 + 1, index2 + 1);
if (d > 0)
{
if (index2 < index1)
{
int tmp = index1;
index1 = index2;
index2 = tmp;
}
for (; index2 > index1; index2--)
{
int tmp = _path[index1 + 1];
_path[index1 + 1] = _path[index2];
_path[index2] = tmp;
index1++;
}
}
}
}
private double Distance(int i, int j)
{
int c1 = _path[i % _path.Length];
int c2 = _path[j % _path.Length];
return _cities[c1].Distance(_cities[c2]);
}
}
} |
Die Beispielanwendung hierfür ist ebenfalls angehängt.
Verwandte Verfahren
Andere Verfahren der Heuristik um ähnliche Problem zu lösen wären:Siehe auch meine  Blogbeiträge über Computation Intelligence und natürlich den separaten Teil ;)
Viel Spass!
mfG Gü
Schlagwörter: Optimierung, Minimum, Minimumsuche, Heuristik, Simulated Annealing, Traveling Salesman, Problem des Handelsreisenden
|
|
