Donnerstag, 27. Oktober 2016

Emails senden und empfangen (POP3- und IMAP-Server, mit SSL-Verschlüsselung)

Vor langer Zeit habe ich beschrieben, wie man mit C# Emails senden und empfangen kann. Damals war dies noch ohne SSL-Verschlüsselung möglich, heutzutage ist diese jedoch bei den meisten Anbietern Pflicht. In diesem Post möchte ich daher zeigen, wie man Emails unter Benutzung einer SSL-Verschlüsselung sendet und empfängt. Das Grundprinzip bleibt dabei das gleiche wie in den vorigen Posts beschrieben - für die Grundlagen ist der Leser daher auf diese Posts verwiesen.
Als weiteren Punkt soll dieser Post erklären, wie Emails von einem IMAP Server gelesen werden können - im letzten Post wurde nur ein POP3 Server genutzt. Außerdem wird ein fertiger Email-Client in C# präsentiert und die benötigen Anmeldeinformationen für gängige Email-Anbieter.

Kurz zur Wiederholung der Grundlagen: Für das Senden von Emails können .Net Funktionen genutzt werden. Dafür wird die Klasse SmtpClient benutzt, welcher die Anmeldedaten des Email-Accounts übergeben werden, und die dann eine Email als Instanz der Klasse MailMessage losschickt.

Das Empfangen von Emails ist etwas mühseliger, hierzu müssen manuell Befehle an den Server geschickt und die Antworten verarbeitet werden. Dafür bietet sich die Benutzung diverser Bibliotheken an, welche die Funktionalität abstrahieren.
In diesem Post werde ich aber zeigen, wie die Kommunikation mit einem Email-Server im Detail aussieht, und jeden Aspekt selber implementieren.
Mittels einem TcpClient bauen wir die Verbindung zum Mail-Server auf, und initialisieren dann einen SslStream, mit welchem wir dem Server die Befehle schicken und dessen Antworten empfangen.
Dabei gibt es nun Unterschiede zwischen einem POP3- und einem IMAP-Server.
Mögliche Befehle für einen POP3- und IMAP-Server können hier und hier gefunden werden, außerdem habe ich die Befehle für einen POP3-Server in meinem vorigen Post beschrieben.
Hier setze ich deren Verständnis voraus (denke aber auch, dass sie relativ selbsterklärend sind). Kurz zum Nachrichtenformat: Ein POP3-Server beendet Anfragen zur Auflistung aller verfügbarer und bestimmter Emailnachrichten mit einem ".", daher lassen wir den Client solange vom Stream lesen, bis dieses Zeichen empfangen wurde. Schickt man einem IMAP-Server einen Befehlsnamen mit, antwortet dieser am Ende jeder Nachricht mit X OK - daher warten wir auf diese Zeile.

Unten stehend findet sich der komplette Code eines Email-Clients, mit welchem Emails gesendet und empfangen werden können.
Die benötigen Konteninformationen (d.h. Server, Port, Benutzername und Passwort) sind die gleichen, wie sie zum Beispiel in Outlook eingegeben werden müssen.
Hier eine Übersicht über gänge Email-Anbieter:

Empfangen:

Name: Gmail
Typ: IMAP
Server: imap.gmail.com
Port: 993
Benutzername: Komplette Emailadresse

Name: Gmx
Typ: POP3
Server: pop.gmx.net
Port: 995
Benutzername: Komplette Emailadresse

Name: Web
Typ: POP3
Server: pop3.web.de
Port: 995
Benutzername: Emailadresse bis zum @ (also bei xyz@web.de xyz)


Senden:

Name: Gmail
Server: smtp.gmail.com
Port: 587
Benutzername: Komplette Emailadresse

Name: Gmx
Server: mail.gmx.net
Port: 587
Benutzername: Komplette Emailadresse

Name: Web
Server: smtp.web.de
Port: 587
Benutzername: Emailadresse bis zum @ oder komplette Emailadresse

Der Code:

Form1.cs:

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.Sockets;
using System.Net.Security;
using System.IO;
using System.Net.Mail;

namespace Emails
{


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

        EmailReceiver MyReceiver = null;

        private void button1_Click(object sender, EventArgs e)
        {
            if (radioButton1.Checked)
            {
                MyReceiver = new POPReceiver();
            }
            if (radioButton2.Checked)
            {
                MyReceiver = new IMAPReceiver();
            }

            MyReceiver.Connect(textBox1.Text, Int32.Parse(textBox2.Text), textBox3.Text, textBox4.Text);
        }

        private void button2_Click(object sender, EventArgs e)
        {
            textBox6.Text = MyReceiver.ListMails();
        }

        private void button3_Click(object sender, EventArgs e)
        {
            textBox6.Text = MyReceiver.GetMail(Int32.Parse(textBox5.Text));
        }

        private void button5_Click(object sender, EventArgs e)
        {
            // Send an email
            // Setup mail client, input credentials ...
            SmtpClient MailClient = new SmtpClient(textBox10.Text, int.Parse(textBox9.Text));
            // Enable SSL
            MailClient.EnableSsl = true;
            System.Net.NetworkCredential Credentials = new System.Net.NetworkCredential(textBox8.Text, textBox7.Text);
            MailClient.Credentials = Credentials;

            // Define the email and send it
            MailMessage Email = new MailMessage();
            Email.From = new MailAddress(textBox8.Text);
            Email.To.Add(textBox11.Text);
            Email.Subject = textBox13.Text;
            Email.Body = textBox12.Text;

            MailClient.Send(Email);
        }

    }

    // Abstract class, from which the specific classes POPReceiver and IMAPReceiver are derived
    public abstract class EmailReceiver
    {
        // TCP client to connect to the server
        public TcpClient MailServer = null;
        // SSL stream for the secure connection
        public SslStream SslStream = null;
        // StreamListener to read from the stream
        public StreamReader StreamListener;
        // Byte buffer to encode the commands send to the server
        public byte[] CommandBuffer = new byte[1024];

        // Connect to the mail server
        public abstract bool Connect(string server, int port, string user, string password);

        // Close the connection
        public abstract void Quit();

        // List all emails
        public abstract string ListMails();

        // Get specified email
        public abstract string GetMail(int id);

        // Send a command to the server and return the response
        public abstract string ExecuteCommand(string command);
    }

    // To be used with a POP3 server
    public class POPReceiver : EmailReceiver
    {
        public override bool Connect(string server, int port, string user, string password)
        {
            // Connect to the server via TCP
            MailServer = new System.Net.Sockets.TcpClient(server, port);

            // Establish the SSL stream
            SslStream = new System.Net.Security.SslStream(MailServer.GetStream());
            SslStream.AuthenticateAsClient(server);

            StreamListener = new StreamReader(SslStream);

            if (MailServer.Connected)
            {
                // Send the login commands and show the results
                MessageBox.Show(StreamListener.ReadLine());

                CommandBuffer = Encoding.ASCII.GetBytes("USER " + user + "\r\n");
                SslStream.Write(CommandBuffer, 0, CommandBuffer.Length);
                MessageBox.Show(StreamListener.ReadLine());

                CommandBuffer = Encoding.ASCII.GetBytes("PASS " + password + "\r\n");
                SslStream.Write(CommandBuffer, 0, CommandBuffer.Length);
                MessageBox.Show(StreamListener.ReadLine());

                return true;
            }

            return false;
        }

        public override void Quit()
        {
            // Close the connection
            CommandBuffer = Encoding.ASCII.GetBytes("QUIT\r\n");
            SslStream.Write(CommandBuffer, 0, CommandBuffer.Length);
            MessageBox.Show(StreamListener.ReadLine());
        }

        public override string ListMails()
        {
            return ExecuteCommand("LIST\r\n");
        }

        public override string GetMail(int mailNr)
        {
            return ExecuteCommand("RETR " + mailNr + "\r\n");
        }

        public override string ExecuteCommand(string command)
        {
            // Send the specified command
            CommandBuffer = Encoding.ASCII.GetBytes(command);
            SslStream.Write(CommandBuffer, 0, CommandBuffer.Length);

            StringBuilder Res = new StringBuilder();

            // The POP3 commands LIST and RETR, for which this function is used, finished by outputting "."
            // as last line.
            // Thus read as long as this line is found.
            string TempLine = StreamListener.ReadLine();
            while (TempLine != ".")
            {
                Res.Append(TempLine + "\r\n");
                TempLine = StreamListener.ReadLine();
            }

            return Res.ToString();
        }
    }

    public class IMAPReceiver : EmailReceiver
    {
        static int Counter = 0;

        public override bool Connect(string server, int port, string user, string password)
        {
            // Connect to the server via TCP
            MailServer = new System.Net.Sockets.TcpClient(server, port);

            // establish the SSL stream
            SslStream = new System.Net.Security.SslStream(MailServer.GetStream());
            SslStream.AuthenticateAsClient(server);

            StreamListener = new StreamReader(SslStream);

            if (MailServer.Connected)
            {
                // Send command to login
                MessageBox.Show(ExecuteCommand("LOGIN " + user + " " + password + "  \r\n"));

                return true;
            }

            return false;
        }

        public override void Quit()
        {
            // Befehl zum Trennen senden
            CommandBuffer = Encoding.ASCII.GetBytes("QUIT\r\n");
            SslStream.Write(CommandBuffer, 0, CommandBuffer.Length);
            MessageBox.Show(StreamListener.ReadLine());
        }

        public override string ListMails()
        {
            return ExecuteCommand("SELECT INBOX\r\n");
        }

        public override string GetMail(int mailNr)
        {
            return ExecuteCommand("FETCH " + mailNr + " body[header]\r\n") + " " + ExecuteCommand("FETCH " + mailNr + " body[text]\r\n");
        }

        public override string ExecuteCommand(string command)
        {
            // Prefix command with unique line number
            command = "aa" + Counter.ToString() + " " + command;

            CommandBuffer = Encoding.ASCII.GetBytes(command);
            SslStream.Write(CommandBuffer, 0, CommandBuffer.Length);
            SslStream.Flush();

            StringBuilder Res = new StringBuilder();

            string TempLine = StreamListener.ReadLine();
            // An IMAP server specifies the end of its response with "line number OK", thus read until this is found.
            while (!TempLine.Contains("aa" + Counter.ToString() + " OK"))
            {
                Res.Append(TempLine + "\r\n");
                TempLine = StreamListener.ReadLine();
            }

            Counter++;

            return Res.ToString();
        }
    }
}

Form1.Designer.cs:

namespace Emails
{
    partial class Form1
    {
        /// <summary>
       /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
       /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
       /// Required method for Designer support - do not modify
       /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.tabControl1 = new System.Windows.Forms.TabControl();
            this.tabPage1 = new System.Windows.Forms.TabPage();
            this.textBox6 = new System.Windows.Forms.TextBox();
            this.textBox5 = new System.Windows.Forms.TextBox();
            this.button3 = new System.Windows.Forms.Button();
            this.radioButton2 = new System.Windows.Forms.RadioButton();
            this.radioButton1 = new System.Windows.Forms.RadioButton();
            this.button2 = new System.Windows.Forms.Button();
            this.button1 = new System.Windows.Forms.Button();
            this.textBox4 = new System.Windows.Forms.TextBox();
            this.label4 = new System.Windows.Forms.Label();
            this.textBox3 = new System.Windows.Forms.TextBox();
            this.label3 = new System.Windows.Forms.Label();
            this.textBox2 = new System.Windows.Forms.TextBox();
            this.label2 = new System.Windows.Forms.Label();
            this.textBox1 = new System.Windows.Forms.TextBox();
            this.label1 = new System.Windows.Forms.Label();
            this.tabPage2 = new System.Windows.Forms.TabPage();
            this.textBox13 = new System.Windows.Forms.TextBox();
            this.label11 = new System.Windows.Forms.Label();
            this.button5 = new System.Windows.Forms.Button();
            this.textBox12 = new System.Windows.Forms.TextBox();
            this.label10 = new System.Windows.Forms.Label();
            this.textBox11 = new System.Windows.Forms.TextBox();
            this.label9 = new System.Windows.Forms.Label();
            this.textBox7 = new System.Windows.Forms.TextBox();
            this.label5 = new System.Windows.Forms.Label();
            this.textBox8 = new System.Windows.Forms.TextBox();
            this.label6 = new System.Windows.Forms.Label();
            this.textBox9 = new System.Windows.Forms.TextBox();
            this.label7 = new System.Windows.Forms.Label();
            this.textBox10 = new System.Windows.Forms.TextBox();
            this.label8 = new System.Windows.Forms.Label();
            this.tabControl1.SuspendLayout();
            this.tabPage1.SuspendLayout();
            this.tabPage2.SuspendLayout();
            this.SuspendLayout();
            //
            // tabControl1
            //
            this.tabControl1.Controls.Add(this.tabPage1);
            this.tabControl1.Controls.Add(this.tabPage2);
            this.tabControl1.Location = new System.Drawing.Point(3, 2);
            this.tabControl1.Name = "tabControl1";
            this.tabControl1.SelectedIndex = 0;
            this.tabControl1.Size = new System.Drawing.Size(790, 639);
            this.tabControl1.TabIndex = 0;
            //
            // tabPage1
            //
            this.tabPage1.Controls.Add(this.textBox6);
            this.tabPage1.Controls.Add(this.textBox5);
            this.tabPage1.Controls.Add(this.button3);
            this.tabPage1.Controls.Add(this.radioButton2);
            this.tabPage1.Controls.Add(this.radioButton1);
            this.tabPage1.Controls.Add(this.button2);
            this.tabPage1.Controls.Add(this.button1);
            this.tabPage1.Controls.Add(this.textBox4);
            this.tabPage1.Controls.Add(this.label4);
            this.tabPage1.Controls.Add(this.textBox3);
            this.tabPage1.Controls.Add(this.label3);
            this.tabPage1.Controls.Add(this.textBox2);
            this.tabPage1.Controls.Add(this.label2);
            this.tabPage1.Controls.Add(this.textBox1);
            this.tabPage1.Controls.Add(this.label1);
            this.tabPage1.Location = new System.Drawing.Point(4, 22);
            this.tabPage1.Name = "tabPage1";
            this.tabPage1.Padding = new System.Windows.Forms.Padding(3);
            this.tabPage1.Size = new System.Drawing.Size(782, 613);
            this.tabPage1.TabIndex = 0;
            this.tabPage1.Text = "Receive";
            this.tabPage1.UseVisualStyleBackColor = true;
            //
            // textBox6
            //
            this.textBox6.Location = new System.Drawing.Point(28, 271);
            this.textBox6.Multiline = true;
            this.textBox6.Name = "textBox6";
            this.textBox6.ScrollBars = System.Windows.Forms.ScrollBars.Both;
            this.textBox6.Size = new System.Drawing.Size(729, 330);
            this.textBox6.TabIndex = 14;
            //
            // textBox5
            //
            this.textBox5.Location = new System.Drawing.Point(231, 232);
            this.textBox5.Name = "textBox5";
            this.textBox5.Size = new System.Drawing.Size(39, 20);
            this.textBox5.TabIndex = 13;
            //
            // button3
            //
            this.button3.Location = new System.Drawing.Point(150, 230);
            this.button3.Name = "button3";
            this.button3.Size = new System.Drawing.Size(75, 23);
            this.button3.TabIndex = 12;
            this.button3.Text = "Get Email";
            this.button3.UseVisualStyleBackColor = true;
            this.button3.Click += new System.EventHandler(this.button3_Click);
            //
            // radioButton2
            //
            this.radioButton2.AutoSize = true;
            this.radioButton2.Location = new System.Drawing.Point(119, 137);
            this.radioButton2.Name = "radioButton2";
            this.radioButton2.Size = new System.Drawing.Size(51, 17);
            this.radioButton2.TabIndex = 11;
            this.radioButton2.TabStop = true;
            this.radioButton2.Text = "IMAP";
            this.radioButton2.UseVisualStyleBackColor = true;
            //
            // radioButton1
            //
            this.radioButton1.AutoSize = true;
            this.radioButton1.Checked = true;
            this.radioButton1.Location = new System.Drawing.Point(28, 137);
            this.radioButton1.Name = "radioButton1";
            this.radioButton1.Size = new System.Drawing.Size(53, 17);
            this.radioButton1.TabIndex = 10;
            this.radioButton1.TabStop = true;
            this.radioButton1.Text = "POP3";
            this.radioButton1.UseVisualStyleBackColor = true;
            //
            // button2
            //
            this.button2.Location = new System.Drawing.Point(28, 230);
            this.button2.Name = "button2";
            this.button2.Size = new System.Drawing.Size(75, 23);
            this.button2.TabIndex = 9;
            this.button2.Text = "List Emails";
            this.button2.UseVisualStyleBackColor = true;
            this.button2.Click += new System.EventHandler(this.button2_Click);
            //
            // button1
            //
            this.button1.Location = new System.Drawing.Point(28, 170);
            this.button1.Name = "button1";
            this.button1.Size = new System.Drawing.Size(75, 23);
            this.button1.TabIndex = 8;
            this.button1.Text = "Connect";
            this.button1.UseVisualStyleBackColor = true;
            this.button1.Click += new System.EventHandler(this.button1_Click);
            //
            // textBox4
            //
            this.textBox4.Location = new System.Drawing.Point(90, 98);
            this.textBox4.Name = "textBox4";
            this.textBox4.Size = new System.Drawing.Size(135, 20);
            this.textBox4.TabIndex = 7;
            //
            // label4
            //
            this.label4.AutoSize = true;
            this.label4.Location = new System.Drawing.Point(25, 101);
            this.label4.Name = "label4";
            this.label4.Size = new System.Drawing.Size(53, 13);
            this.label4.TabIndex = 6;
            this.label4.Text = "Password";
            //
            // textBox3
            //
            this.textBox3.Location = new System.Drawing.Point(90, 72);
            this.textBox3.Name = "textBox3";
            this.textBox3.Size = new System.Drawing.Size(135, 20);
            this.textBox3.TabIndex = 5;
            //
            // label3
            //
            this.label3.AutoSize = true;
            this.label3.Location = new System.Drawing.Point(25, 75);
            this.label3.Name = "label3";
            this.label3.Size = new System.Drawing.Size(55, 13);
            this.label3.TabIndex = 4;
            this.label3.Text = "Username";
            //
            // textBox2
            //
            this.textBox2.Location = new System.Drawing.Point(90, 46);
            this.textBox2.Name = "textBox2";
            this.textBox2.Size = new System.Drawing.Size(135, 20);
            this.textBox2.TabIndex = 3;
            //
            // label2
            //
            this.label2.AutoSize = true;
            this.label2.Location = new System.Drawing.Point(25, 49);
            this.label2.Name = "label2";
            this.label2.Size = new System.Drawing.Size(26, 13);
            this.label2.TabIndex = 2;
            this.label2.Text = "Port";
            //
            // textBox1
            //
            this.textBox1.Location = new System.Drawing.Point(90, 19);
            this.textBox1.Name = "textBox1";
            this.textBox1.Size = new System.Drawing.Size(135, 20);
            this.textBox1.TabIndex = 1;
            //
            // label1
            //
            this.label1.AutoSize = true;
            this.label1.Location = new System.Drawing.Point(25, 22);
            this.label1.Name = "label1";
            this.label1.Size = new System.Drawing.Size(38, 13);
            this.label1.TabIndex = 0;
            this.label1.Text = "Server";
            //
            // tabPage2
            //
            this.tabPage2.Controls.Add(this.textBox13);
            this.tabPage2.Controls.Add(this.label11);
            this.tabPage2.Controls.Add(this.button5);
            this.tabPage2.Controls.Add(this.textBox12);
            this.tabPage2.Controls.Add(this.label10);
            this.tabPage2.Controls.Add(this.textBox11);
            this.tabPage2.Controls.Add(this.label9);
            this.tabPage2.Controls.Add(this.textBox7);
            this.tabPage2.Controls.Add(this.label5);
            this.tabPage2.Controls.Add(this.textBox8);
            this.tabPage2.Controls.Add(this.label6);
            this.tabPage2.Controls.Add(this.textBox9);
            this.tabPage2.Controls.Add(this.label7);
            this.tabPage2.Controls.Add(this.textBox10);
            this.tabPage2.Controls.Add(this.label8);
            this.tabPage2.Location = new System.Drawing.Point(4, 22);
            this.tabPage2.Name = "tabPage2";
            this.tabPage2.Padding = new System.Windows.Forms.Padding(3);
            this.tabPage2.Size = new System.Drawing.Size(782, 613);
            this.tabPage2.TabIndex = 1;
            this.tabPage2.Text = "Send";
            this.tabPage2.UseVisualStyleBackColor = true;
            //
            // textBox13
            //
            this.textBox13.Location = new System.Drawing.Point(90, 190);
            this.textBox13.Name = "textBox13";
            this.textBox13.Size = new System.Drawing.Size(135, 20);
            this.textBox13.TabIndex = 24;
            //
            // label11
            //
            this.label11.AutoSize = true;
            this.label11.Location = new System.Drawing.Point(25, 193);
            this.label11.Name = "label11";
            this.label11.Size = new System.Drawing.Size(43, 13);
            this.label11.TabIndex = 23;
            this.label11.Text = "Subject";
            //
            // button5
            //
            this.button5.Location = new System.Drawing.Point(90, 579);
            this.button5.Name = "button5";
            this.button5.Size = new System.Drawing.Size(85, 22);
            this.button5.TabIndex = 22;
            this.button5.Text = "Send";
            this.button5.UseVisualStyleBackColor = true;
            this.button5.Click += new System.EventHandler(this.button5_Click);
            //
            // textBox12
            //
            this.textBox12.Location = new System.Drawing.Point(90, 225);
            this.textBox12.Multiline = true;
            this.textBox12.Name = "textBox12";
            this.textBox12.Size = new System.Drawing.Size(657, 335);
            this.textBox12.TabIndex = 21;
            //
            // label10
            //
            this.label10.AutoSize = true;
            this.label10.Location = new System.Drawing.Point(25, 225);
            this.label10.Name = "label10";
            this.label10.Size = new System.Drawing.Size(28, 13);
            this.label10.TabIndex = 20;
            this.label10.Text = "Text";
            //
            // textBox11
            //
            this.textBox11.Location = new System.Drawing.Point(90, 161);
            this.textBox11.Name = "textBox11";
            this.textBox11.Size = new System.Drawing.Size(135, 20);
            this.textBox11.TabIndex = 19;
            //
            // label9
            //
            this.label9.AutoSize = true;
            this.label9.Location = new System.Drawing.Point(25, 164);
            this.label9.Name = "label9";
            this.label9.Size = new System.Drawing.Size(50, 13);
            this.label9.TabIndex = 18;
            this.label9.Text = "Receiver";
            //
            // textBox7
            //
            this.textBox7.Location = new System.Drawing.Point(90, 98);
            this.textBox7.Name = "textBox7";
            this.textBox7.Size = new System.Drawing.Size(135, 20);
            this.textBox7.TabIndex = 16;
            //
            // label5
            //
            this.label5.AutoSize = true;
            this.label5.Location = new System.Drawing.Point(25, 101);
            this.label5.Name = "label5";
            this.label5.Size = new System.Drawing.Size(53, 13);
            this.label5.TabIndex = 15;
            this.label5.Text = "Password";
            //
            // textBox8
            //
            this.textBox8.Location = new System.Drawing.Point(90, 72);
            this.textBox8.Name = "textBox8";
            this.textBox8.Size = new System.Drawing.Size(135, 20);
            this.textBox8.TabIndex = 14;
            //
            // label6
            //
            this.label6.AutoSize = true;
            this.label6.Location = new System.Drawing.Point(25, 75);
            this.label6.Name = "label6";
            this.label6.Size = new System.Drawing.Size(55, 13);
            this.label6.TabIndex = 13;
            this.label6.Text = "Username";
            //
            // textBox9
            //
            this.textBox9.Location = new System.Drawing.Point(90, 46);
            this.textBox9.Name = "textBox9";
            this.textBox9.Size = new System.Drawing.Size(135, 20);
            this.textBox9.TabIndex = 12;
            //
            // label7
            //
            this.label7.AutoSize = true;
            this.label7.Location = new System.Drawing.Point(25, 49);
            this.label7.Name = "label7";
            this.label7.Size = new System.Drawing.Size(26, 13);
            this.label7.TabIndex = 11;
            this.label7.Text = "Port";
            //
            // textBox10
            //
            this.textBox10.Location = new System.Drawing.Point(90, 19);
            this.textBox10.Name = "textBox10";
            this.textBox10.Size = new System.Drawing.Size(135, 20);
            this.textBox10.TabIndex = 10;
            //
            // label8
            //
            this.label8.AutoSize = true;
            this.label8.Location = new System.Drawing.Point(25, 22);
            this.label8.Name = "label8";
            this.label8.Size = new System.Drawing.Size(38, 13);
            this.label8.TabIndex = 9;
            this.label8.Text = "Server";
            //
            // Form1
            //
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(788, 637);
            this.Controls.Add(this.tabControl1);
            this.Name = "Form1";
            this.Text = "Emails";
            this.tabControl1.ResumeLayout(false);
            this.tabPage1.ResumeLayout(false);
            this.tabPage1.PerformLayout();
            this.tabPage2.ResumeLayout(false);
            this.tabPage2.PerformLayout();
            this.ResumeLayout(false);

        }

        #endregion

        private System.Windows.Forms.TabControl tabControl1;
        private System.Windows.Forms.TabPage tabPage1;
        private System.Windows.Forms.RadioButton radioButton2;
        private System.Windows.Forms.RadioButton radioButton1;
        private System.Windows.Forms.Button button2;
        private System.Windows.Forms.Button button1;
        private System.Windows.Forms.TextBox textBox4;
        private System.Windows.Forms.Label label4;
        private System.Windows.Forms.TextBox textBox3;
        private System.Windows.Forms.Label label3;
        private System.Windows.Forms.TextBox textBox2;
        private System.Windows.Forms.Label label2;
        private System.Windows.Forms.TextBox textBox1;
        private System.Windows.Forms.Label label1;
        private System.Windows.Forms.TabPage tabPage2;
        private System.Windows.Forms.TextBox textBox6;
        private System.Windows.Forms.TextBox textBox5;
        private System.Windows.Forms.Button button3;
        private System.Windows.Forms.TextBox textBox12;
        private System.Windows.Forms.Label label10;
        private System.Windows.Forms.TextBox textBox11;
        private System.Windows.Forms.Label label9;
        private System.Windows.Forms.TextBox textBox7;
        private System.Windows.Forms.Label label5;
        private System.Windows.Forms.TextBox textBox8;
        private System.Windows.Forms.Label label6;
        private System.Windows.Forms.TextBox textBox9;
        private System.Windows.Forms.Label label7;
        private System.Windows.Forms.TextBox textBox10;
        private System.Windows.Forms.Label label8;
        private System.Windows.Forms.Button button5;
        private System.Windows.Forms.TextBox textBox13;
        private System.Windows.Forms.Label label11;



    }
}

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!