Montag, 6. März 2017

Simulated Annealing mit C#

Nachdem ich in einem vorigen Post genetische Algorithmen beschrieben habe, möchte ich in diesem Post ein anderes heuristisches, an der Natur orientiertes Optimierungsverfahren vorstellen: Simulated Annealing.
Vorbild ist das Abkühlen von Stoffen, bei welchem sich die Atome anfangs bei hoher Temperatur viel bewegen und größere Distanzen überwinden (am Anfang der Optimierung legen wir große Schritte im Suchraum zurück). Mit fortschreitender Zeit verringert sich die Bewegung der Atome, das System erreicht einen stabilen Zustand (gegen Ende der Suche suchen wir nur noch lokal nach Verbesserungen und enden in einem lokalen Minimum).
Dieses Verfahren wird zum Beispiel zum Planen von Verbindungswegen auf Computerchips eingesetzt.
Im Gegensatz zu genetischen Algorithmen arbeiten wir bei Simulated Annealing nicht mit einem Pool von Lösungen, sondern stets nur mit einer einzigen. Eine Schar an Lösungen bietet Vorteile bei der Auswahl, verlangsamt den Prozess jedoch natürlich auch. Die Erzeugung einer neuen Lösung lässt sich mit der asexuellen Fortpflanzung vergleichen: Basierend auf unserer aktuellen Lösung modifizieren wir diese um so zu einer neuen Lösung zu gelangen. Hierfür definieren wir uns einen Graph, welcher die Nachbarschaftsbeziehungen der Lösungen repräsentiert, und durchlaufen diesen.
Das wilde Herumspringen der Moleküle bei hoher Temperatur und das dadurch verbundene Durchsuchen eines großen Suchraums modellieren wir mit einer Akzeptanzwahrscheinlichkeit: Ist die neue gefundene Lösung besser als die aktuelle, übernehmen wir diese immer als neue aktuelle Lösung. Ist die gefundene Lösung jedoch schlechter, übernehmen wir diese nur mit einer Wahrscheinlichkeit von e-Δ/T.
Hierbei entspricht Δ der Differenz der Lösungswerte (Ergebnis neuer Lösung - Ergebnis aktuelle Lösung) und T der aktuellen Temperatur. Die Wahrscheinlichkeit, die neue Lösung zu akzeptieren, nimmt also mit der Temperatur ab, und mit der Höhe der Verschlechterung des Lösungswertes (setzt einfach mal ein paar Werte in die Formel ein).
In jedem Schritt des Algorithmus wird die Temperatur nach einem bestimmten Verfahren abgekühlt, wir nehmen hier das geometrische Abkühlungsschema TNeu = TAlt * α.
Als Pseudocode sieht der Algorithmus also wie folgt aus:
Aktuelle_Lösung = Zufällige Lösung
T = TStart
Solange T > TEnde:
   Temp = Zufällige Nachbarlösung von Aktuelle_Lösung
   Wenn Temp besser als Aktuelle_Lösung:
      Aktuelle_Lösung = Temp
   Sonst:
      Aktuelle_Lösung = Temp mit o.g. Wahrscheinlichkeit
   T = T * α. 

Wenden wir nun Simulated Annealing auf das TSP - Problem an, welches bereits im Post zu genetischen Algorithmen vorgestellt wurde. In unserem Nachbarschaftsgraph sind zwei Lösungen benachbart, wenn sie durch Tauschen zweier Städte in der Rundreise ineinander übergeführt werden können. Als Beispiel: Die Lösung ABC ist mit den Lösungen BAC, CAB und ACB benachbart.
Zu Beginn des Algorithmus erstellen wir in der Funktion Initialize() eine zufällige Initiallösung. Hierfür probieren wir solange aus, bis wir eine gültige Lösung gefunden haben, also eine, in welcher alle Städte miteinander verbunden sind. Dies ist nötig, da der Algorithmus allein durch das Tauschen zweier Städte nur sehr schlecht von einer schlechten Lösung mit Kosten unendlich wegfindet.
In der Funktion Go() befindet sich die Hauptschleife des Algorithmus. In jeder Iteration wird mit der Funktion CreateRandomNeighbor() eine zufällige neue Lösung aus der aktuellen heraus erzeugt. Dafür werden, wie gesagt, zwei zufällige Städte in der Rundtour getauscht.
Die Entscheidung, ob die neu erzeugte Lösung akzeptiert wird, wird nach oben beschriebenem Kriterium getroffen.
Als Starttemperatur wähle ich hier 1000, als Endtemperatur 0.01, für α 0.999999.
Mit diesen Parametern erreicht der Algorithmus bei 100 zufälligen Instanzen der Größe 20 im Durchschnitt einen Zielfunktionswert von 4516.
Ich werde demnächst einen eigenen Post zum Vergleich von genetischen Algorithmen und Simulated Annealing und zur Wahl der Parameter schreiben, im ersten Vergleich ist Simulated Annealing damit jedoch besser.
Dies bestätigt auch meine Meinung, ich persönlich ziehe das schlanke, einfache aber effektive Prinzip von Simulated Annealing vor, ebenfalls ist die Geschwindigkeit ein ausschlaggebendes Argument.
Auch ist bei genetischen Algorithmen nicht klar, ob das Prinzip der sexuellen Reproduktion bei mathematischen Problemen sinnvoll angewendet werden kann.

Zu guter Letzt der Code:


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SA_TSP
{
    class Program
    {
        static void Main(string[] args)
        {
            TSPInstance Instance = CreateRandomTSPInstance(20);
            SimulatedAnnealing SA = new SimulatedAnnealing();
            SA.Go(Instance, true, 1000, 0.01, 0.999999);
        }

        // Create a random TSP instance, connect two cities with probability 70 % and choose a length between 0 and 1000.
        public static TSPInstance CreateRandomTSPInstance(int n)
        {
            TSPInstance Instance = new TSPInstance(n);
            Random Rnd = new Random();
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (Rnd.Next(100) < 70)
                    {
                        Instance.AddConnection(i, j, Rnd.Next(1000));
                    }
                }
            }
            return Instance;
        }

    
    }

    public class TSPInstance
    {
        public int n;
        public int[][] Connections;

        public TSPInstance(int _n)
        {
            n = _n;
            Connections = new int[n][];
            for (int i = 0; i < n; i++)
            {
                Connections[i] = new int[n];
                for (int j = 0; j < n; j++)
                {
                    Connections[i][j] = int.MaxValue;
                }
            }
        }

        public void AddConnection(int start, int end, int distance)
        {
            Connections[start][end] = distance;
        }
    }

    public class SimulatedAnnealing
    {
        public class Individual : ICloneable
        {
            public double Fitness;
            public int[] Tour;

            public Individual(int length)
            {
                Tour = new int[length];
            }

            // creates a deep copy of an individual
            public object Clone()
            {
                Individual Cloned = new Individual(Tour.Length);

                for (int i = 0; i < Tour.Length; i++)
                {
                    Cloned.Tour[i] = Tour[i];
                }
                Cloned.Fitness = Fitness;
                return Cloned;
            }
        }

        Individual CurrentSolution;
        TSPInstance Instance;

        public void Initialize()
        {
            // fill the initial population, for each individual create a random permutation of the cities

            Random Rnd = new Random();
            double Fitness = int.MaxValue;

            // create random permutations, as long as a valid tour is found
            while (Fitness == int.MaxValue)
            {
                List<int> Cities = new List<int>();
                for (int j = 0; j < Instance.n; j++)
                {
                    Cities.Add(j);
                }
                int Counter = 0;
                while (Cities.Count > 0)
                {
                    int Index = Rnd.Next(Cities.Count);
                    CurrentSolution.Tour[Counter++] = Cities[Index];
                    Cities.RemoveAt(Index);
                }
                CurrentSolution.Fitness = CalculateFitness(CurrentSolution);
                Fitness = CurrentSolution.Fitness;
            }
        }

        public Individual CreateRandomNeighbor()
        {
            // switch to random cities in the tour
            Random Rnd = new Random();
            Individual Cloned = (Individual)CurrentSolution.Clone();
            int End = Rnd.Next(Instance.n);
            int Start = Rnd.Next(Instance.n);
            int Temp = Cloned.Tour[Start];
            Cloned.Tour[Start] = Cloned.Tour[End];
            Cloned.Tour[End] = Temp;
            Cloned.Fitness = CalculateFitness(Cloned);
            return Cloned;
        }

        public Individual Go(TSPInstance inst, Boolean print, double tstart, double tend, double alpha)
        {
            Instance = inst;
            double T = tstart;
            CurrentSolution = new Individual(inst.n);

            Initialize();

            double LastPrint = tstart;

            // repeat as long as the temperature is over some threshold
            while (T > tend)
            {
                Individual NewSolution = CreateRandomNeighbor();
                if (NewSolution.Fitness < CurrentSolution.Fitness)
                    CurrentSolution = NewSolution;
                else
                {
                    double AcceptanceProbability = Math.Exp(-(NewSolution.Fitness - CurrentSolution.Fitness) / T);
                    Random Rnd = new Random();
                    if (Rnd.NextDouble() <= AcceptanceProbability)
                        CurrentSolution = NewSolution;
                }
                T = T * alpha;
                if (print && (LastPrint - T > 50))
                {
                    Console.WriteLine("Temperature: " + T.ToString());
                    Console.WriteLine("Current Solution: " + CurrentSolution.Fitness.ToString());
                    LastPrint = T;
                }
            }

            if (print)
                Console.WriteLine("Best: " + CurrentSolution.Fitness.ToString());

            return CurrentSolution;
        }

        public int CalculateFitness(Individual ind)
        {
            // sum over entire tour and return costs
            int Costs = 0;
            for (int i = 0; i < ind.Tour.Length; i++)
            {
                if (i == ind.Tour.Length - 1)
                {
                    if (Instance.Connections[ind.Tour[i]][ind.Tour[0]] == int.MaxValue)
                        return int.MaxValue;
                    Costs += Instance.Connections[ind.Tour[i]][ind.Tour[0]];
                }
                else
                {
                    if (Instance.Connections[ind.Tour[i]][ind.Tour[i + 1]] == int.MaxValue)
                        return int.MaxValue;
                    Costs += Instance.Connections[ind.Tour[i]][ind.Tour[i + 1]];
                }
            }
            return Costs;
        }
    }
}

Keine Kommentare:

Kommentar veröffentlichen