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!

Dienstag, 7. Juni 2016

Wissensquiz

Werbung in eigener Sache: Vor kurzem habe ich eine Quiz-App für Android hochgeladen und ich würde mich freuen, wenn der ein oder andere sie mal ausprobiert. Die App enthält viele abwechslungsreiche Fragen und interessante Spielmodi, ich versuche außerdem täglich neue Fragen hinzuzufügen.
Wie auch dieser Blog verfolgt die App das Ziel Wissen zugänglich zu machen und zu verbreiten, weswegen sie mir am Herzen liegt.

Thematisch werde ich demnächst einen Artikel über Genetische Algorithmen veröffentlichen. Die vorigen Posts haben darauf abgezielt, ein Programm vorzustellen, was ich auch für das Quiz benutzt habe: Das automatische Durchsuchen von Wikipedia etc. benutze ich in einem Programm, welches automatisch neue Quizfragen aussucht. Dazu scannt es die Wikipedia Seiten mit regulären Ausdrücken nach bestimmten Phrasen wie "Evolutionäre Algorithmen (EA) sind ... Algorithmen ... ".
Da dies jedoch nicht so gut funktioniert, habe ich davon abgelassen.

Freitag, 11. März 2016

Zufällig durch das Internet browsen mit C#

In diesem Post möchte ich zeigen, wie man mit C# durch das Internet surft indem man zufälligen Links folgt. Dabei ist nicht nur einfach unheimlich interessant und aufschlussreich wo man nach ein paar Klicks landet, sondern dies hat auch eine praktische Anwendung: Zum Beispiel Googles Pagerank Algorithmus zur Bewertung der Popularität von Webseiten nutzt ein ähnliches Modell.

Das folgende C# Programm enthält ein Webbrowser Steuerelement und einen Button. Klickt der Benutzer auf den Button, durchsucht das Programm die aktuelle Webseite, sucht einen zufälligen Link aus und zeigt die Zielseite im Webbrowser an.
Der Code sollte relativ selbst erklärend sein: Die Klasse Browser behandelt das Suchen von neuen Links. Sie speichert die aktuelle Seite sowie den aktuellen Seitenquelltext. Wird die Methode GoNext() aufgerufen, ruft diese FindLink() auf, um einen zufälligen Link zu finden. Dafür wird eine zufällige Startposition im Quelltext der aktuellen Seite bestimmt (der Quelltext wird mit einem Webclient heruntergeladen) und ab da nach dem ersten Vorkommen eines HTML Links gesucht. Ich halte dieses Vorgehen für effizienter anstatt zuerst den kompletten Quellcode zu durchsuchen und danach einen zufälligen Link auszuwählen. Aber Achtung: Auf diese Weise werden bestimmte Links bevor- oder benachteiligt, da wir nicht mehr die tatsächliche Wahrscheinlichkeit der Links benutzen! Wir arbeiten nun mit einer Wahrscheinlichkeit über Zeichenketten, und da die Links höchstwahrscheinlich nicht gleichverteilt im Text sind (am Anfang gibt es zum Beispiel einen großen Header usw.), hat unsere Ziehung ein gewisses Bias.
Haben wir einen Link gefunden benutzen wir die Methode aus dem vorigen Post um ggf. relative Links in absolute umzuwandeln, und folgen diesem Link.
Das Programm funktioniert ist aber noch relativ rudimentär, es kann zum Beispiel in Sackgassen laufen etc., auch wie vorhin angemerkt ist die Linkauswahl nicht völlig zufällig. Ich poste es hier in der Form da ich denke dass es für eine Anwendung vom Benutzer eh noch stark personalisiert werden muss und die Anforderungen dafür stark schwanken.
Viel Spaß beim Ausprobieren und schreibt mir interessante Linkketten in die Kommentare!

Hier der Code:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Net;

namespace RandomSurfer
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        Browser B;

        private void Form1_Load(object sender, EventArgs e)
        {
            // start with some arbitrary page, here a random article on Wikipedia
            string StartPage = "https://de.wikipedia.org/wiki/Spezial:Zuf%C3%A4llige_Seite";
            B = new Browser(StartPage);
            webBrowser1.Navigate(StartPage);
        }

        private void button1_Click(object sender, EventArgs e)
        {
            webBrowser1.Navigate(B.GoNext());
        }
    }

    public class Browser
    {
        string CurrentPage; // stores url current website
        string CurrentContent; // stores content of current website

        public Browser(string Start)
        {
            CurrentPage = Start;
            CurrentContent = GetText(CurrentPage);
        }

        private string GetText(string url)
        {
            // use a webclient to download the source code of a website
            WebClient Webclient1 = new WebClient();
         
            Webclient1.Encoding = System.Text.Encoding.UTF8;
            string Content = ((Webclient1.DownloadString(url)));
            return (Content);
        }

        public string GoNext()
        {
            // randomly go to a new website
            CurrentPage = FindLink(); // for this find a random link
            CurrentContent = GetText(CurrentPage); // and for the next seach store the source code of the current webpage
            return CurrentPage;
        }

        private string FindLink()
        {
            // find a random link
            int Length = CurrentContent.Length;
            Random Rnd = new Random();
            int RndStart;
            int LinkStart = -1;
            int LinkEnd;
            string Link = "";

            // select a random starting point in the source code and find the first link after that
            // repeat if none find
            while (LinkStart == -1)
            {
                RndStart = Rnd.Next(Length);
                LinkStart = CurrentContent.IndexOf("a href=\"", RndStart);
            }

            // extract the link
            LinkEnd = CurrentContent.IndexOf("\"", LinkStart + 8);
            Link = CurrentContent.Substring(LinkStart + 8, LinkEnd - LinkStart - 8);

            // resolve its global url
            System.Uri Base = new System.Uri(CurrentPage);
            System.Uri ResolvedAbsoluteURL = new System.Uri(Base, Link);
            return ResolvedAbsoluteURL.ToString();
        }
    }
}

Montag, 7. März 2016

Relative URL mit C# auflösen

Kürzlich wollte ich eine Webseite nach Links durchsuchen und diesen folgen. Dabei wurden natürlich auch relative Links gefunden, und ich stellte fest, dass es im Internet gar nicht so leicht ist, einen Weg, diese mit C# aufzulösen, zu finden. Zuerst dachte ich darüber nach, relative Links selber zu verarbeiten, wurde dann aber doch mit einer sehr einfachen Methode fündig, die ich hier vorstellen möchte.
Zuerst kurz etwas zu Links im Internet: In HTML kann wie folgt auf eine andere Seite verwiesen, also ein Link erstellt werden:

<a href="http://www.sudokudestages.blogspot.de/">Aussagekräftiger Linktext</a>

In obigem Link habe ich eine absolute URL als Ziel angegeben, zu erkennen an http://www.
Ich kann jedoch auch Seiten relativ zu meiner aktuellen Seite referenzieren, zum Beispiel:

<a href="../../p/youtube-konto.html">Aussagekräftiger Linktext</a>

Dieser Link ruft die Seite http://csharp-tricks.blogspot.de/p/youtube-konto.html auf. Da dieser Post in dem virtuellen Ordner "/2016/03/" liegt, gehen wir mittels "../../" zwei Verzeichnisse aufwärts zur Wurzel URL, und rufen von da die Seite /p/youtube-konto.html auf.
Wenn absolute Links angetroffen werden, stellt dies kein Problem dar. Befindet man sich jedoch auf einer Seite und möchte einem relativen Link folgen, ist dies etwas komplizierter, zumal auch alle anderen bekannten Pfadangaben wie oben gesehen "../../target" erlaubt sind.

Um diese Pfade nun nicht manuell zusammen bauen zu müssen kann man die Klasse System.Uri in der Form System.Uri RelativeURL = new System.Uri(BaseUri, "relative Path"); verwenden.
Als Beispiel nehmen wir den Wikipedia Artikel des "Gabelbocks". In diesem findet sich ein relativer Link zu dem Wikipedia Artikel über "Schneidezähne":

<a href="/wiki/Schneidezahn" title="Schneidezahn">Schneidezähne</a>

Um den gültigen absoluten Link zu erhalten führen wir den folgenden Code aus:
System.Uri Base = new System.Uri("https://de.wikipedia.org/wiki/Gabelbock");
System.Uri ResolvedAbsoluteURL = new System.Uri(Base, "/wiki/Schneidezahn");

Mittwoch, 30. September 2015

Sudoku App für Android

Heute mal etwas Offtopic-mäßiges: Neben meiner Sudoku Seite habe ich nun eine App für Android geschrieben, mit welcher die Sudokus einfach und bequem auf dem Smartphone gelöst werden können. Ich würde mich freuen, wenn der eine oder andere sie mal ausprobiert, oder selber Interesse an der App Entwicklung findet. Die App habe ich in Java geschrieben, über die Erstellung von Android Apps mit C# gibt es auf diesem Blog eine Einführung.
Die App kann kostenlos über den Google Play Store heruntergeladen werden.

Samstag, 19. September 2015

Matlab Tutorial Teil 5 - Plots

Im heutigen Post möchte ich eine kurze Einführung in die Erstellung von Plots mit Matlab geben.
Dieser Beitrag soll nur einen groben Überblick vermitteln, für genaueres verweise ich auf die Dokumentation von Matlab. Dort sind alle Plot Arten mit Parametern aufgelistet, dort wird auch zum Beispiel erklärt wie man Achsen beschriftet, Farben ändert etc.
Hier möchte ich zwei Arten von 2-dimensionalen Plots erläutern, nämlich einfache Linien- und Balkendiagramme, sowie den Surface Plot als 3-dimensionalen.
Ein Liniendiagramm (line plot) erstellen wir mit der Funktion plot(). Dafür legen wir zuerst ein paar Testdaten mittels x = rand(8, 1) an, also einen Vektor mit 8 zufälligen Werten zwischen 0 und 1.
Dann liefert plot(x) das folgende Ergebnis:






















bar() erstellt ein Balkendiagramm (bar chart) aus den gegebenen Daten. bar(x) sieht wie folgt aus:






















Nun zu einem 3-dimensionalen Plot, dem Surface Plot. Dieser stellt (zum Beispiel) eine übergebene 2-dimensionale Matrix in der dritten Dimension (durch Höhe und Farbe) dar. Am Punkt mit Koordinaten (i, j) wird also der (i, j). - Eintrag der Matrix dargestellt, das heißt sein Wert durch die z - Koordinate dargestellt und zusätzlich passend eingefärbt.
Wir erstellen als Beispiel mittels A = rand(32) eine zufällige 32 x 32 Matrix. surf(A) erstellt dann das folgende Diagramm:



Freitag, 18. September 2015

Matlab Tutorial Teil 4 - Skripte und Funktionen

Um oft benutzten Code nicht jedes mal neu eingeben zu müssen haben wir in Matlab die Möglichkeit diesen in Skripte und Funktionen auszulagern.
Diese werden in Dateien mit der Endung .m gespeichert. Skripte sind einfach Sammlungen von Codezeilen, während Funktionen dazu noch einen Rückgabewert liefern.
Diese Dateien können wir bequem aus der Matlab Entwicklungsumgebung anlegen: Hierzu geben wir edit Name.m ein und bestätigen den Befehl. Daraufhin öffnet sich ein Editor mit der Datei.
Als Beispiel erstellen wir das Skript MyScript.m mit folgendem Inhalt:

A = rand(100);
d = det(A)

Es wird also eine zufällige 100 x 100 Matrix A angelegt und die Determinante d berechnet.
In Matlab können wir nun das Skript durch Eingeben des Namens MyScript aufrufen. Daraufhin wird das Skript ausgeführt und die Variable d ausgegeben. Was ausgegeben wird können mir mit dem Zeichen ";" steuern. Beenden wir eine Zeile mit dem Semikolon, wird diese ohne Ausgabe ausgeführt. Lassen wir dieses weg, wird das Ergebnis der Operation ausgegeben. Lassen wir also in der 1. Zeile des Skripts das Semikolon weg, wird die komplette Matrix ebenfalls ausgegeben.

Als zweites Beispiel legen wir nun eine Funktion an, welche den Durchschnitt über die übergebenen Werte berechnet und zurückgibt. Dafür geben wir edit MyFunction.m ein.
Als Inhalt geben wir ein:

function [y] = MyFunction(x)
y = sum(x);
y = y / numel(x);
end

Wie man sieht, beginnt eine Funktionsdeklaration mit dem Schlüsselwort function und endet mit end. In eckigen Klammern geben wir dann zuerst die Rückgabeparameter an - hier wird nur y zurückgegeben, mehrere Parameter werden einfach per Komma getrennt. Nach dem Gleichheitszeichen geben wir den Namen der Funktion (welcher mit dem Dateinamen übereinstimmten sollte) sowie die Eingabeparameter in runden Klammern an - hier nur x.
In der Funktion summieren wir dann über x (wir erwarten also einen Vektor) und teilen durch die Anzahl der Elemente in x. Das Ergebnis gibt die Funktion in y zurück. In Matlab können wir dann die Funktion wie folgt aufrufen und ihren Rückgabewert benutzten: test = MyFunction([1,2,3,])
(Hinweis: In Matlab lässt sich der Durchschnittswert natürlich einfacher berechnen - zum Beispiel mit der vordefinierten Funktion mean(). Ich habe dieses Beispiel nur zur Erläuterung genommen.)