Dienstag, 19. Juli 2016

Genetische Algorithmen in C#

In diesem Post möchte ich sogenannte genetische Algorithmen (als Oberbegriff wird auch evolutionärer Algorithmus benutzt, wobei die Grenzen verschwimmen) vorstellen. Natürlich wird am Ende eine fertig nutzbare C# Implementierung herauskommen, allerdings ist das Thema auch ein Schritt in die Richtung diesen Blog etwas zu erweitern und auch andere Themen, zum Beispiel aus der theoretischen Informatik, anzureißen.

Was sind nun genetische Algorithmen? Genetische Algorithmen sind stochastische Optimierungsverfahren, welche auf dem Prozess der natürlichen Evolution basieren. Zur Lösungsfindung benutzen sie eine Gruppe von Individuen, welche einzelne Lösungen des zu untersuchenden Problems darstellen. In jeder Runde des Algorithmus wird mittels bestimmter Operationen aus dieser Gruppe eine neue Population erzeugt.
Diese Operationen sind, wie gesagt angelehnt an das Beispiel der Evolution von Lebenwesen:

  • Überleben des Stärksten (die besten Individuen der vorherigen Runde werden in die neue übernommen)
  • Crossover (zwei Individuen der vorigen Runde wirken als "Eltern" eines Individuums der neuen Population) 
  • Mutation (ein Individuum mutiert zufällige Eigenschaften)

Die Hoffnung ist, dass die Individuen der Populationen mit der Zeit immer "fitter" werden, und nach etlichen Runden man ein gutes Individuum, also eine gute Lösung, gefunden hat.
Man benutzt genetische Algorithmen um komplexe Probleme, in der Regel NP-schwere, zu lösen, bei welchen der Suchraum viel zu groß wäre um ihn komplett zu durchsuchen und man auch generell wenige Anhaltspunkte hat, wie man eine gute Lösung konstruieren kann - genetische Algorithmen sind ein guter allgemeiner Ansatz um Probleme aller Art zu lösen.
In dieser Generalität liegt aber auch ein Kritikpunkt dieses Optimierungsverfahrens. Für viele Probleme, auch schwierige, gibt es sehr gute problemspezifische Lösungsverfahren mit welchen genetische Algorithmen nicht mithalten können. Auch ist nicht klar, ob sich das Prinzip der Erbgutübernahme von zwei Eltern sinnvoll in Algorithmen benutzen lässt. Verfahren wie zum Beispiel Simulated Annealing arbeiten mit nur einem "Elternteil", um bei der Analogie zu bleiben, und könnten somit mehr Sinn machen.

Interessenten an diesen Themen seien an die existierende Literatur verwiesen. Hier möchte ich nun mit der Implementierung eines genetischen Algorithmus weitermachen und damit Instanzen des Travelling Salesman Problems (TSP) lösen.
Das Travelling Salesman Problem, zu deutsch das Problem des Handlungsreisenden, ist ein relativ bekanntes NP-schweres Problem. Dabei geht es um das Finden einer kostengünstigen Rundreise zwischen einer Menge von Städten - das heißt, jede Stadt muss genau einmal besucht werden, und der Handlungsreisende muss am Schluss in die Startstadt zurückkehren. Bei n Städten gibt es (n - 1)! mögliche Reihenfolgen dieser zu besuchen. Dies ist eine unglaublich schnell wachsende Funktion, so ergeben sich zum Beispiel bei 10 Städten etwa 360.000 Kombinationen, bei 15 Städten bereits 87 Milliarden und bei 70 Städten mehr, als es Atome im gesamten Universum gibt.
Daher bieten sich genetische Algorithmen also schon einmal prinzipiell an, um eine relativ gut angenäherte Lösung zu finden. Gleichzeitig sei aber auch darauf verwiesen,
dass es sehr gute Approximationsalgorithmen für dieses Problem gibt, man bedenke also die einleitenden Worte.

Eine TSP Instanz verwalten wir in der Klasse TSPInstance. Für n Städte wird die n x n Integer Matrix Connections angelegt, in welcher Eintrag (i, j) die Entfernung von Stadt i nach Stadt j angibt. Gibt es keine Verbindung zwischen diesen Städten, wird der Eintrag auf unendlich (Integer.MAX_VALUE) gesetzt.
Eine solche Instanz wird dann an den genetischen Algorithmus übergeben. Startfunktion ist die Funktion Go() der Klasse GeneticAlgorithm.
In dieser sehen wir den grundlegenden Ablauf des Algorithmus: Zuerst wird die erste Population initialisiert. Dann führen wir eine bestimmte Anzahl an Iterationen durch, in welcher wir die Funktion Breed() aufrufen, die die jeweilige neuen Population aus der vorherigen erzeugt.
Eine Lösung der TSP Instanz stellen wir einfach als Permuation der Städte dar, welche die Reihenfolge angibt, in welcher die Städte besucht werden.
So heißt z.B. ADCB, dass der Reisende die Route A-D-C-B-A fährt. Im Programm haben die Städte durchnummerierte Indizes, sodass wir ein Integer Array verwenden, der Inhalt wäre bei dem Beispiel dann 0, 3, 2, 1. Die "Fitness" eines Individums sind die Kosten der Tour (unendlich wenn die Tour nicht möglich ist).

Zu Beginn des Algorithmus erstellen wir ein Array von Individuen und füllen diese mit zufälligen Touren, also zufälligen Permuationen der Städte. Die Größe des Arrays entspricht der Größe der Population. Wir nehmen als Größe 30. Dieser Parameter, wie generell auch die folgenden Parameter des genetischen Algorithmus, haben sehr große Auswirkungen auf die Lösungsqualität. Bei jedem Problem sollten also verschiedene Parameterwerte ausprobiert werden. Bei der Populationsgröße wird oft eine Größe von etwa 30 genommen.

In der Funktion Breed() iterieren wir zuerst über die aktuelle Population und berechnen die Fitness der Individuen. Anschließend sortieren wir die Individuen nach aufsteigender Fitness.
So können wir die besten Individuen der vorherigen Population in die neue übernehmen. Der Anteil dieser wird in Prozent ausgedrückt, wir benutzen hier 10%, das heißt es werden die besten 3 Individuen aus der vorherigen Population in die neue übernommen.
Die restlichen 27 Plätze der neuen Population müssen wir nun füllen, was mir mittels Crossovern und Mutationen tun.

Beim Durchlaufen über die alte Population erzeugen wir das Array SummedFitness, in welchem die kumulierten Fitnesswerte gespeichert sind. An Position i ist also die Summe der Fitnesswerte
der Individuen 0 - i gespeichert. Mit diesem können wir nun eine sogenannte Fitnessproportionale Selektion durchführen, bei welcher Individuen mit einer höheren Fitness mit höherer Wahrscheinlichkeit als Eltern ausgewählt werden. Dafür erzeugen wir eine zufällige Zahl zwischen 0 und dem letztem Wert von SummedFitness, das Individum, in wessen Intervall die Zahl fällt, wird ausgewählt.
Auf diese Weise wählen wir zwei Elternteile aus. Nun lassen wir wieder per Zufall entscheiden, ob wir eine Crossover Operation durchführen sollen. Ich wähle hier eine Crossover Wahrscheinlichkeit
von 80 % aus. Soll kein Crossover durchgeführt werden, ist das Kind einfach ein Klon von Elternteil 1. Soll ein Crossover durchgeführt werden, wird das Kind eine genetische Mischung beider Elternteile. Für das Mischen gibt es verschiedene Möglichkeiten. Hier benutzen wir den folgenden Ansatz: Wir wählen zufällig einen Crossover Punkt X zwischen 0 und n - 1.
Im Kind entsprechen dann die ersten X - 1 Städte der Tour denen aus Elternteil 1. Die restlichen Städte werden so angeordnet, wie sie in Elternteil 2 vorkommen.
Als Beispiel betrachten wir die Eltern AGEDCBF und FDAGEBC. Als Crossover Punkt wird 3 gewählt. Das Kind startet seine Tour somit mit den Städten AGE. Zu verteilen sind noch die Städte D, C, B und F, welche in der Reihenfolge, wie sie in Elternteil 2 vorkommen, angeordnet werden: FDBC. Damit ergibt sich als komplette Tour für das Kind: AGEFDBC. Es sei nochmal darauf verwiesen, dass dies nur eine mögliche Crossover Operation ist, es gibt zum Beispiel auch die Möglichkeit, den String an 2 Stellen aufzuteilen (Two-point crossover).

Im letzten Schritt wird das Kind noch zufällig mutiert. Auch hiefür gibt es verschiedene Möglichkeiten, wir benutzen die folgende: Wir gehen jedes Element der Tour durch und mutieren mit einer Wahrscheinlichkeit von 10%. Ist die Mutationsrate zu niedrig, kann der Algorithmus nicht genug gute Lösungskandidaten generieren und bleibt eher in lokalen Minima stecken, ist sie zu hoch, wird der Algorithmus zu einer zufälligen Suche. Falls wir mutieren, bestimmen wir zufällig einen anderen Punkt in der Tour und tauschen die zwei Städte.

Damit haben wir, basierend auf der alten Population, ein neues Kind hinzugefügt, diesen Vorgang wiederholen wir, bis wir wieder 30 Elemente in der neuen Population haben.
Auf Grund der Übernahme der besten Individuen in die neue Population wird die Fitness des besten Individuums nie schlechter, pro Runde steigt sie hoffentlich. Am Ende geben wir die beste Lösung aus.

Hier der Code der Konsolenanwendung, ich denke dieser sollte mit obiger Erklärung relativ gut verständlich sein:

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

namespace GA_TSP
{
    class Program
    {
        static void Main(string[] args)
        {
            TSPInstance Instance = CreateRandomTSPInstance(20);
            GeneticAlgorithm GA = new GeneticAlgorithm();
            GA.Go(Instance, true, 0.8, 0.1, 0.1, 30, 10000);
        }

        // Create a random TSP instance, connect two cities with probability 50 % 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 GeneticAlgorithm
    {
        public class Individual : ICloneable, IComparable<Individual>
        {
            public double Fitness;
            public int[] Tour;

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

            // needed for sorting, sort individuals by their fitness
            public int CompareTo(Individual other)
            {
                if (other.Fitness < Fitness)
                    return -1;
                if (other.Fitness > Fitness)
                    return 1;
                else
                    return 0;
            }

            // 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;
            }
        }

        // algorithm parameters, experiment!
        double CrossoverFrequency;
        double MutationFrequency;
        double ElitistFrequency;
        int PopulationSize;
        int NrIterations;

        Individual[] Population;
        Individual Best = null;
        TSPInstance Instance;
        Boolean Print;

        public Individual Go(TSPInstance inst, Boolean print, double co, double mu, double el, int popsize, int it)
        {
            CrossoverFrequency = co;
            MutationFrequency = mu;
            ElitistFrequency = el;
            PopulationSize = popsize;
            NrIterations = it;

            Instance = inst;
            Population = new Individual[PopulationSize];
            Print = print;

            for (int i = 0; i < PopulationSize; i++)
            {
                Population[i] = new Individual(inst.n);
            }

            Initialize();

            for (int i = 0; i < NrIterations; i++)
            {
                Breed();
                if (Print && i % 100 == 0)
                {
                    Console.WriteLine("Iteration: " + i.ToString());
                }
            }

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

            return Best;
        }

        public void Initialize()
        {
            // fill the initial population, for each individual create a random permutation of the cities
            Random Rnd = new Random();
            for (int i = 0; i < PopulationSize; i++)
            {
                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);
                    Population[i].Tour[Counter++] = Cities[Index];
                    Cities.RemoveAt(Index);
                }
            }
        }

        public void Breed()
        {
            double[] SummedFitness = new double[PopulationSize];
            // first calculate the fitness of each individual and sort in ascending order
            double SumFitness = 0;
            for (int i = 0; i < PopulationSize; i++)
            {
                Population[i].Fitness = CalculateFitness(Population[i]);
            }
            Array.Sort(Population);

            for (int i = 0; i < PopulationSize; i++)
            {
                if (Best == null || Population[i].Fitness < Best.Fitness)
                {
                    Best = Population[i];
                    if (Print)
                        Console.WriteLine("New best found, fitness: " + Best.Fitness.ToString());
                }
                SumFitness += Population[i].Fitness;
                SummedFitness[i] = SumFitness;
            }

            Random Rnd = new Random();

            Individual[] NewPopulation = new Individual[PopulationSize];

            // take best individuals from last population
            for (int i = 0; i < Math.Ceiling(PopulationSize * ElitistFrequency); i++)
            {
                NewPopulation[i] = (Individual)Population[i].Clone();
            }

            // fill the rest of the new populaton
            for (int i = (int)Math.Ceiling(PopulationSize * ElitistFrequency); i < PopulationSize; i++)
            {
                double RParent1 = Rnd.NextDouble() * SummedFitness[PopulationSize - 1];
                double RParent2 = Rnd.NextDouble() * SummedFitness[PopulationSize - 1];

                Individual Parent1 = null;
                Individual Parent2 = null;
                Individual Child = new Individual(Instance.n);
                // roulette wheel selection of the parents
                for (int j = 0; j < PopulationSize; j++)
                {
                    if (Parent1 == null && SummedFitness[j] >= RParent1)
                    {
                        Parent1 = Population[j];
                    }
                    if (Parent2 == null && SummedFitness[j] >= RParent2)
                    {
                        Parent2 = Population[j];
                    }
                }

                // do a crossover with chance CrossoverFrequency
                Child = (Individual)Parent1.Clone();
                if (Rnd.NextDouble() <= CrossoverFrequency)
                {
                    // when doing a crossover, first copy the tour from parent 1, then starting from COPoint fill in the remaining spots in the order of parent 2
                    int COPoint = Rnd.Next(Instance.n);
                    List<int> VisitedCities = new List<int>();
                    for (int j = 0; j < COPoint; j++)
                    {
                        VisitedCities.Add(Parent1.Tour[j]);
                    }
                    int Pos = COPoint;
                    for (int j = 0; j < Instance.n; j++)
                    {
                        if (!VisitedCities.Contains(Parent2.Tour[j]))
                        {
                            Child.Tour[Pos++] = Parent2.Tour[j];
                        }
                    }
                }

                for (int j = 0; j < Instance.n; j++)
                {
                    // for each position of the tour, do a mutation with chance MutationFrequency
                    if (Rnd.NextDouble() <= MutationFrequency)
                    {
                        // when mutating, switch 2 cities
                        int End = Rnd.Next(Instance.n);
                        int Temp = Population[i].Tour[j];
                        Population[i].Tour[j] = Population[i].Tour[End];
                        Population[i].Tour[End] = Temp;
                    }
                }
                NewPopulation[i] = Child;
            }
            Population = NewPopulation;
        }

        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;
        }
    }
}

Spielt ein wenig damit rum, schreibt mir in die Kommentare wofür ihr den genetische Algorithmus einsetzt, oder ob ihr bessere Parameter und / oder Verbesserungen am Algorithmus für das TSP Problem findet, würde mich sehr interessieren!

Kommentare:

  1. Email empfangen geht nicht mehr bei deinem Block. bei gmx wird eins ssl verschlüsselung verlangt. kannst du mir da weiterhelfen? :)

    AntwortenLöschen
    Antworten
    1. Hallo, es hat ein wenig gedauert, aber im neuen Post erkläre ich die Benutzung der SSL Verbindung: http://csharp-tricks.blogspot.de/2016/10/emails-senden-und-empfangen-pop3-und.html
      :)

      Löschen
    2. Wahnsinn :D
      danke dir, weiter so! :)

      Löschen