Wednesday, October 26, 2016

Send and Receive Emails (using POP3 and IMAP servers, with SSL encryption)

A long time ago I described how to send and receive emails via C#. At that time this was possible without SSL encryption, but nowadays this is mandatory for the most providers. In this post I thus want to show, how to send and receive emails using the SSL encryption. The core principle stays the same as described in the previous posts - for the basics the reader is thus referred to these.
As another point this post shall explain how emails can be read from an IMAP server - in the last post only a POP3 server was used. Further, a usable email client in C# is presented as well as access information for common email providers.

Briefly repeating the basics: For sending emails .Net functions can be used. For this the class SmtpClient is used, to which we pass the login information, and then send an email as an instance of the class MailMessage.

Receiving emails is a bit more tedious, as for this we have to manually send commands to the server and read its response. For this the usage of external libraries is possible, which abstract the lower layers.
In this post I want to show though how communication with an email server looks like with more details, and implement every part of it.
With a TcpClient we establish the connection to the mail server and then initialize an SslStream, with which we send the commands to the server and receive its responses.
For this there are differencs between a POP3 and an IMAP server.
Possible commands for a POP3 and IMAP server can be found here and here, further I described the commands for a POP3 server in my previous post.
Here I assume your understanding of the concept (but I also think they are kind of self-explanatory). Briefly to the different message format: A POP3 sever ends queries to list all possible emails and show a specific email with the line ".", thus we let the client read as long as it encounters this line. When sending a command name X to an IMAP server, it answers with X OK upon completion - thus we wait for this line.

Below you find the complete code of an email client, with which emails can be sent and received.
The needed accout information (i.e. server, port, username and password) are the same as they have to be entered for example in Outlook.
Here an overview over common providers:

Receive:

Name: Gmail
Type: IMAP
Server: imap.gmail.com
Port: 993
Username: Complete email address

Name: Yahoo
Type: IMAP
Server: imap.mail.yahoo.com
Port: 993
Benutzername: Complete email address


Send:

Name: Gmail
Server: smtp.gmail.com
Port: 587
Username: Complete email address

Name: Yahoo
Server: smtp.mail.yahoo.com
Port: 587
Username: Complete email address

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



    }
}

Tuesday, July 19, 2016

Genetic Algorithms with C#

In this post I want to present so called genetic algorithms, which belong to the larger class of evolutionary algorithms. Of course we will arrive at a complete, ready-to-use C# implementation in the end, but this post is also a step in the direction to broaden the topics of this blog, for example also including theoretical computer science.

What are genetic algorithms? Genetic algorithms are stochastical search heuristics which mimic the process of natural selection. For finding a solution they use a group of individuals, which all represent single solutions of the problem. In every round of the algorithm via certain operators from the old group a new population is created.
These operators are:

  • Survival of the fittest (the best individuals from the previous round are taken in the next one)
  • Crossover (two individuals of the previous round take the role of "parents" of an individual of the new population)
  • Mutation (an individual mutates random properties)
We hope, that the individuals of the populations get "fitter" over time, and after several rounds we get a good individual, and thus a good solution.
Genetic algorithms are or can be used to solve complex problems, usually NP-hard ones, for which the search space is too big to completely traverse it and one generally has little clues about how to solve the problem. Genetic algorithms are a good general approach to solve problems of all kinds.
But in this generality lies also a weakness of this heuristic: For many problems, also hard ones, there are very good problem specific solving approaches with which genetic algorithms cannot compute. Further it is not clear, how the idea of two parents translates to the algorithmic principle. Procedures like Simulated Annealing inherently use one parent, when staying to the analogy, and thus might make more sense.


Readers interested in this wide topic are referred to the existing literature. Here I now want to continue with the implementation of the genetic algorithm and solve instances of the Travelling Salesman Problem (TSP) with it.
The Travelling Salesman Problem is a relatively well-known NP-hard problem. It is about finding a cheap round trip between a set of cities - that means, every city has to be visited exactly once, and the salesman has to return to his starting city in the end. With n cities there are (n - 1)! possible orders to visit them. This is an incredibly fast growing function, for example for 10 cities we get 360.000 combinations, for 15 cities there are already 87 billion combinations and for 70 cities more than there are atoms in the entire universe.
Thus in principle genetic algorithms seem like a good candidate to get a relative good approximate solution. But on the other hand there are very good approximation algorithms for this problem, so think of the introductory words.

We manage a TSP instance in the class TSPInstance. For n cities the n x n integer matrix Connections is created, in which entry (i, j) describes the distance from city i to j. If there is no connection between these cities, the entry is set to infinity (Integer.MAX_VALUE).
Such an instance then is passed to the genetic algorithm. Starting function is the function Go() of the class GeneticAlgorithm.
In this we see the basic flow of the algorithm: First we initialize the starting population. Then we run for a certain number of iterations, in which we call the function Breed(), which creates the new population out of the previous one.
We represent a solution of the TSP instance simply as a permutation of the cities, which describes the order in which these are visited. So ADBC for example stands for the route A-D-B-C-A. In the program the cities are numbered, so we use an integer array, the content would then for example be 0, 3, 1, 2. The "fitness" of an individual are the costs of the tour (infinity if the tour is not possible).

At the beginning of the algorithm we create an array of individuals and fill this with random tours, so random permutations of the city. The size of the array corresponds to the size of the population. As a size we take 30. This parameter, as the following ones, has a huge impact on the quality of the solution. For every problem different parameters should be tried. For the population size a size of 30 is often used.

In the function Breed() we first iterate over the current population and calculate the fitness of the individuals. Then we sort them by ascending fitness.
This way we can simply take the best individuals from the previous population into the new one. The percentage of these is expressed in percent, here we use 10, which means that the 3 best individuals of the previous population are taken into the new one.
We then have to fill the remaining 27 spots in the new population, which we do via crossover and mutation.

When iterating over the old population we create the array SummedFitness, in which cumulated fitness values are saved. So at position i the sum of the fitness values of the individuals 0 - i is saved. With this we can do a so called fitness proportionate selection, in which individuals with a higer fitness are chosen preferably as parents. For this we create a random number between 0 and the last value of SummedFitness, the individual, in whose interval the number falls, is selected.
This way we choose two parents. Now we again let a random coin decide whether we want to do a crossover operation. I here chose a crossover probability of 80 %. If no crossover is done, the child is simply a clone of parent 1. If a crossover is done, the child becomes a genetic combination of both parents. For mixing the genomes there are different possibilites. Here we use the following approach: We randomly choose a crossover point X between 0 and n - 1.
In the child we then select the first X - 1 cities from the tour directly from parent 1. The remaining cities are ordered in the order how they occur in parent 2.
As an example let us consider the parents AGEDCBF and FDAGEBC. As a crossover point we choose 3. The child thus starts its tour with the cities AGE. Remaining are the cities D, C, B and F, which are ordered like in parent 2: FDBC. Thus we get as the complete tour for the child: AGEFDBC. Again let me say, this is just one possible way to do a crossover, for example there is also the possibility to split the string in 2 parts (Two-point crossover).

In the last step the child is randomly mutated. Also for this there are different possibilities, we use the following one: We iterate over every element of the tour and mutate with a probability of 10 %. If the mutation rate is too low, the algorithm cannot create enough good solution candidates and gets stuck in a local minimum, if it is too high, the algorithm becomes random search. If we mutate, we randomly select another city in the tour and switch the two.

With this, we created, based on the old population, a new child. We repeat this process until there are again 30 individuals in the new population.
Since the best individuals remain in the populations, the fitness of the best individual never decreases and hopefully increases over time. In the end we output the best solution.

Here the code of a console application, I think this should be relatively good readable with the above explanation:

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

Play with it, write me in the comments for what you use genetic algorithms and whether you can find better parameters / improvements of the algorithm for the TSP problem, I am very interested in that!