4
\$\begingroup\$

Inspired by this article.

I've been trying to learn more C# and OOP. Here is my take on a genetic algorithm as described in the article. Here are some of the results

  • flower

flower

  • jelly

jelly

  • lighthouse

lighthouse

It takes a picture, and generates 10 images composed of 32 random rectangles. It scores the 10 images based on the average color distance of each corresponding point between the target image and the generated image. Then, it eliminates the two weakest scoring images, and replaces them with "cross pollinated" images from a random pair of the 8 remaining images. Finally, a random bit is flipped to add some mutation.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Runtime.InteropServices;

namespace Gene
{
    public partial class Form1 : Form
    {

        public Form1()
        {
            InitializeComponent();
        }

        static int numberOfGenomes = 10;
        static int numberOfChromosomes = 32;
        static int numberOfProperties = 8;
        static int numberOfBitsPerProp = 8;
        static int chromosomeStringLength = numberOfProperties * numberOfBitsPerProp;
        static Size imageSize = new Size(255, 255);

        Bitmap originalImage;
        static DirectBitmap target;

        //binary to gray to binary
        public static class Gray
        {
            //example usage: Convert.ToString((long) grayEncode(i), 2).PadLeft(8,'0')

            //gray encode 0-255 to 0000 0000-1000 0000
            public static ulong GrayEncode(ulong n)
            {
                return n ^ (n >> 1);
            }
            public static ulong GrayDecode(ulong n)
            {
                ulong temp = n ^ (n >> 8);
                temp ^= (temp >> 4);
                temp ^= (temp >> 2);
                temp ^= (temp >> 1);
                return temp;
            }
        }

        private static readonly Random r = new Random();
        private static readonly object syncLock = new object();
        public static int RandomNumber(int min, int max)
        {
            lock (syncLock)
            {
                return r.Next(min, max);
            }
        }

        //a chromosome is the individual rectangle
        public class Chromosome
        {
            //Gene Fields
            // all values are 0-255
            private ulong x;
            private ulong y;
            private ulong width;
            private ulong height;
            private ulong alpha;
            private ulong red;
            private ulong green;
            private ulong blue;
            private string chromosomestring;
            private Rectangle rectangle;
            private Color rectanglecolor;
            readonly int rmin = 0;
            readonly int rmax = 255;

            //Constructor
            public Chromosome()
            {
                RandomizeGenes();
                GenerateShape();
                EncodeChromosomeString();
            }

            //Gene Properties
            public ulong X { get => x; set => x = value; }
            public ulong Y { get => y; set => y = value; }
            public ulong Width { get => width; set => width = value; }
            public ulong Height { get => height; set => height = value; }
            public ulong Alpha { get => alpha; set => alpha = value; }
            public ulong Red { get => red; set => red = value; }
            public ulong Green { get => green; set => green = value; }
            public ulong Blue { get => blue; set => blue = value; }
            public string Chromosomestring { get => chromosomestring; set => chromosomestring = value; }
            public Rectangle Rectangle { get => rectangle; set => rectangle = value; }
            public Color RectangleColor { get => rectanglecolor; set => rectanglecolor = value; }

            //Methods
            public void RandomizeGenes()
            {
                x = (ulong)RandomNumber(rmin, rmax);
                y = (ulong)RandomNumber(rmin, rmax);
                width = (ulong)RandomNumber(rmin, imageSize.Width - (int)x);
                height = (ulong)RandomNumber(rmin, imageSize.Height - (int)y);
                alpha = (ulong)RandomNumber(rmin, rmax);
                red = (ulong)RandomNumber(rmin, rmax);
                green = (ulong)RandomNumber(rmin, rmax);
                blue = (ulong)RandomNumber(rmin, rmax);
            }

            public void EncodeChromosomeString()
            {
            chromosomestring = Convert.ToString((long)Gray.GrayEncode(x), 2).PadLeft(8,'0')+
                Convert.ToString((long)Gray.GrayEncode(y), 2).PadLeft(8, '0') +
                Convert.ToString((long)Gray.GrayEncode(width), 2).PadLeft(8, '0') +
                Convert.ToString((long)Gray.GrayEncode(height), 2).PadLeft(8, '0') +
                Convert.ToString((long)Gray.GrayEncode(alpha), 2).PadLeft(8, '0') +
                Convert.ToString((long)Gray.GrayEncode(red), 2).PadLeft(8, '0') +
                Convert.ToString((long)Gray.GrayEncode(green), 2).PadLeft(8, '0') +
                Convert.ToString((long)Gray.GrayEncode(blue), 2).PadLeft(8, '0');


            }

            public void GenerateShape()
            {
                rectangle = new Rectangle((int) x, (int)y, (int)width, (int)height);
                rectanglecolor = Color.FromArgb((int)alpha, (int)red, (int)green, (int)blue);
            }

            //decode chromosome string  to set other chromosome properties
            public void DecodeChromosomeString()
            {
                x = Gray.GrayDecode(Convert.ToUInt32(chromosomestring.Substring(0, 8),2));
                y = Gray.GrayDecode(Convert.ToUInt32(chromosomestring.Substring(8, 8), 2));
                width = Gray.GrayDecode(Convert.ToUInt32(chromosomestring.Substring(16, 8), 2));
                height = Gray.GrayDecode(Convert.ToUInt32(chromosomestring.Substring(24, 8), 2));
                alpha = Gray.GrayDecode(Convert.ToUInt32(chromosomestring.Substring(32, 8), 2));
                red = Gray.GrayDecode(Convert.ToUInt32(chromosomestring.Substring(40, 8), 2));
                green = Gray.GrayDecode(Convert.ToUInt32(chromosomestring.Substring(48, 8), 2));
                blue = Gray.GrayDecode(Convert.ToUInt32(chromosomestring.Substring(56, 8), 2));
                GenerateShape();
            }

            //not used. for experimentation.
            public void MutateChromosome()
            {
                var length = chromosomestring.Length;
                var randomGenePosition = r.Next(0, length);
                char gene = chromosomestring[randomGenePosition];
                if (gene.Equals('0'))
                {
                    gene = '1';
                }
                else
                {
                    gene = '0';
                }
                char[] mutatedChromosome = new char[chromosomestring.Length];
                for (int i = 0; i < chromosomestring.Length; i++)
                {
                    if (i == randomGenePosition)
                        {
                            mutatedChromosome[i] = gene;
                        }
                        else
                        {
                            mutatedChromosome[i] = chromosomestring[i];
                        }
                    }
                    chromosomestring = new string(mutatedChromosome);                
                    return;
                }                        
            }

            // a genome is 32 chromosomes(rectangles)
            public class Genome
            {
                private Chromosome[] chromosomes = new Chromosome[numberOfChromosomes];
                private string genomestring;

                public Chromosome[] Chromosomes { get => chromosomes; set => chromosomes = value; }     
                public string Genomestring { get => genomestring; set => genomestring = value; }

                public Genome()
                {
                    CreateChromosomes();
                    EncodeGenome();
                }

                public void EncodeGenome()
                {
                    for (int i = 0; i < numberOfChromosomes; i++)
                    {
                        Genomestring += chromosomes[i].Chromosomestring;
                    }
                }

                public void CreateChromosomes()
                {
                    for (int i = 0; i < numberOfChromosomes; i++)
                    {
                        chromosomes[i] = new Chromosome();
                    }
                }

                public void MutateGenome()
                {
                    var length = genomestring.Length;
                    var randomGenePosition = r.Next(0, length);
                    char protein = genomestring[randomGenePosition];
                    if (protein.Equals('0'))
                    {
                        protein = '1';
                    }
                    else
                    {
                        protein = '0';
                    }
                    char[] mutatedGenome = new char[genomestring.Length];
                    for (int i = 0; i < genomestring.Length; i++)
                    {
                        if (i == randomGenePosition)
                        {
                            mutatedGenome[i] = protein;
                        }
                        else
                        {
                            mutatedGenome[i] = genomestring[i];
                        }
                    }
                    genomestring = new string(mutatedGenome);
                    return;
                }

                public void DecodeGenomeString()
                {
                    //use after mutating:
                    //split genomestring into chromosomestrings
                    //then decode the chromosomestrings
                    //so that the chromosome properties  update with mutated chromosome.

                    for (int i = 0; i < numberOfChromosomes; i++)
                    {
                        chromosomes[i].Chromosomestring = genomestring.Substring(i*chromosomeStringLength, chromosomeStringLength);
                        chromosomes[i].DecodeChromosomeString();
                        chromosomes[i].EncodeChromosomeString();
                    }

                }           
            }

            // there are 10 genomes in the gene pool
            public class GenePool
            {
                private Genome[] pool = new Genome[numberOfGenomes];
                private DirectBitmap[] directBitmaps = new DirectBitmap[numberOfGenomes];
                private double[] score = new double[numberOfGenomes];
                private List<int> scoredIndex;

                public Genome[] Pool { get => pool; set => pool = value; }
                public DirectBitmap[] DirectBitmaps { get => directBitmaps; set => directBitmaps = value; }
                public double[] Score { get => score; set => score = value; }
                public List<int> ScoredIndex { get => scoredIndex; set => scoredIndex = value; }


                //Populate the Pool
                public GenePool()
                {
                    CreatePool();
                }

                public void CreatePool()
                {
                    for (int i = 0; i < numberOfGenomes; i++)
                    {
                        Pool[i] = new Genome();
                    }
                }

                public void DrawGenomes()
                {
                    //draw the decoded genomes to direct bitmaps
                    for (int i = 0; i < numberOfGenomes; i++)
                    {
                        directBitmaps[i] = new DirectBitmap(imageSize.Width, imageSize.Height);
                        using(var g = Graphics.FromImage(directBitmaps[i].Bitmap))
                        {
                            g.FillRectangle(new SolidBrush(Color.Black), 0, 0, imageSize.Width, imageSize.Height);
                            for (int j = 0; j < numberOfChromosomes; j++)
                            {
                                g.FillRectangle(new SolidBrush(pool[i].Chromosomes[j].RectangleColor), pool[i].Chromosomes[j].Rectangle);
                            }
                        }
                    }               
                }

                public void ScoreGenomes()
                {
                    for (int i = 0; i < numberOfGenomes; i++)
                    {
                        double sum = 0;
                        double pointscore = 0;
                        for (int j = 0; j < imageSize.Width; j++)
                        {
                            for (int k = 0; k < imageSize.Height; k++)
                            {
                                sum += ColorDistance(directBitmaps[i].GetPixel(j, k),target.GetPixel(j,k));
                            }
                        }
                        pointscore = sum / (imageSize.Width * imageSize.Height);
                        score[i] = pointscore;
                    }
                }

                public void SortScores()
                {
                    List<double> A = new List<double>();
                    for (int i = 0; i < score.Length; i++)
                    {
                        A.Add(score[i]);
                    }
                    var sorted = A
                        .Select((x, i) => new KeyValuePair<double, int>(x, i))
                        .OrderBy(x => x.Key)
                        .ToList();
                    List<double> B = sorted.Select(x => x.Key).ToList();
                    scoredIndex = sorted.Select(x => x.Value).ToList();
                    //the weakest scoring genomes are at the following:
                    //weakest = scoredIndex[numberOfGenomes-1];
                    //weaker = scoredIndex[numberOfGenomes - 2];
                }

                public void CrossPollElim()
                {
                    //crosspollinate to create 2 new genomes, replace the genomes with the lowest score.

                    //select 2 random genomes (not the weakest- 0-7, 8 and 9 are weakest)
                    int temp1, temp2;
                    int parent1, parent2;
                    int cut;
                    string head1, head2;
                    string tail1, tail2;
                    string child1, child2;

                    temp1 = r.Next(0, numberOfGenomes-2);
                    temp2 = r.Next(0, numberOfGenomes-2);
                    while (temp1 == temp2)
                    {
                        temp2 = r.Next(0, 8);
                    }

                    parent1 = scoredIndex[temp1];
                    parent2 = scoredIndex[temp2];

                    cut = r.Next(0, pool[0].Genomestring.Length - 1);

                    head1 = pool[parent1].Genomestring.Substring(0, cut);
                    head2 = pool[parent2].Genomestring.Substring(0, cut);
                    tail1 = pool[parent1].Genomestring.Substring(cut);
                    tail2 = pool[parent2].Genomestring.Substring(cut);

                    child1 = head1 + tail2;
                    child2 = head2 + tail1;

                    pool[scoredIndex[numberOfGenomes - 1]].Genomestring = child1;
                    pool[scoredIndex[numberOfGenomes - 2]].Genomestring = child2;                               
                }

                public void SelectOneAndMutate()
                {
                    var randomGenome = r.Next(0, numberOfGenomes);
                    pool[randomGenome].MutateGenome();
                }
            }

            public static double ColorDistance(Color c1, Color c2)
            {
                long rmean = ((long)c1.R + (long)c2.R) / 2;
                long r = (long)c1.R - (long)c2.R;
                long g = (long)c1.G - (long)c2.G;
                long b = (long)c1.B - (long)c2.B;
                return Math.Sqrt((((512 + rmean) * r * r) >> 8) + 4 * g * g + (((767 - rmean) * b * b) >> 8));
            }

            public class DirectBitmap : IDisposable
            {
                public Bitmap Bitmap { get; private set; }
                public Int32[] Bits { get; private set; }
                public bool Disposed { get; private set; }
                public int Height { get; private set; }
                public int Width { get; private set; }

                protected GCHandle BitsHandle { get; private set; }

                public DirectBitmap(int width, int height)
                {
                    Width = width;
                    Height = height;
                    Bits = new Int32[width * height];
                    BitsHandle = GCHandle.Alloc(Bits, GCHandleType.Pinned);
                    Bitmap = new Bitmap(width, height, width * 4, PixelFormat.Format32bppPArgb, BitsHandle.AddrOfPinnedObject());
                }

                public void SetPixel(int x, int y, Color colour)
                {
                    int index = x + (y * Width);
                    int col = colour.ToArgb();

                    Bits[index] = col;
                }

                public Color GetPixel(int x, int y)
                {
                    int index = x + (y * Width);
                    int col = Bits[index];
                    Color result = Color.FromArgb(col);

                    return result;
                }

                public void Dispose()
                {
                    if (Disposed) return;
                    Disposed = true;
                    Bitmap.Dispose();
                    BitsHandle.Free();
                }
            }

            //sets target image to stretched bitmap of orignal
            //then sets picturebox1 image to target image
            private void OpenImage(object sender, EventArgs e)
            {

                if (openFileDialog1.ShowDialog() == DialogResult.OK)
                {
                    originalImage = new Bitmap(openFileDialog1.FileName);
                }
                target = new DirectBitmap(imageSize.Width, imageSize.Height);
                using(var g = Graphics.FromImage(target.Bitmap))
                {
                    g.DrawImage(originalImage,0,0,imageSize.Width,imageSize.Height);
                }
                pictureBox1.Image = target.Bitmap;

                originalImage.Dispose();
            }                      

            //gene pool with 10 genomes which each have 32 chromosomes(rectangles)
            GenePool gp;

            private void CreateGenePool_Click(object sender, EventArgs e)
            {
                GpCreate();
            }

            private void Step_Click(object sender, EventArgs e)
            {
                Evolve(2000);
            }

            public void GpCreate()
            {
                gp = new GenePool();
            }

            public void Evolve(int iterations)
            {
                for (int k = 0; k < iterations; k++)
                {
                    for (int i = 0; i < numberOfGenomes; i++)
                    {
                        if (gp.DirectBitmaps[i] != null)
                        {
                            gp.DirectBitmaps[i].Dispose();
                        }
                        else
                        {
                            continue;
                        }
                    }
                    gp.DrawGenomes();
                    gp.ScoreGenomes();
                    gp.SortScores();
                    pictureBox2.Image = gp.DirectBitmaps[gp.ScoredIndex[0]].Bitmap;
                    pictureBox3.Image = gp.DirectBitmaps[gp.ScoredIndex[1]].Bitmap;
                    pictureBox4.Image = gp.DirectBitmaps[gp.ScoredIndex[2]].Bitmap;
                    pictureBox5.Image = gp.DirectBitmaps[gp.ScoredIndex[3]].Bitmap;
                    pictureBox6.Image = gp.DirectBitmaps[gp.ScoredIndex[4]].Bitmap;
                    pictureBox7.Image = gp.DirectBitmaps[gp.ScoredIndex[5]].Bitmap;
                    pictureBox8.Image = gp.DirectBitmaps[gp.ScoredIndex[6]].Bitmap;
                    pictureBox9.Image = gp.DirectBitmaps[gp.ScoredIndex[7]].Bitmap;
                    pictureBox10.Image = gp.DirectBitmaps[gp.ScoredIndex[8]].Bitmap;
                    pictureBox11.Image = gp.DirectBitmaps[gp.ScoredIndex[9]].Bitmap;

                    pictureBox2.Refresh();
                    pictureBox3.Refresh();
                    pictureBox4.Refresh();
                    pictureBox5.Refresh();
                    pictureBox6.Refresh();
                    pictureBox7.Refresh();
                    pictureBox8.Refresh();
                    pictureBox9.Refresh();
                    pictureBox10.Refresh();
                    pictureBox11.Refresh();
                    gp.CrossPollElim();
                    gp.SelectOneAndMutate();
                    for (int i = 0; i < numberOfGenomes; i++)
                    {
                        gp.Pool[i].DecodeGenomeString();                    
                    }

                }

            }
        }
    }

All feedback is welcome. I will answer what questions you have.

I am satisfied with the performance, and can get some nice computer generated paintings of certain things. There's a strong success bias towards rectangular things or scenes with a lot of horizontal and vertical lines.

I think it could be faster. After 2000 iterations, the generated image begins to resemble the target image.

When I set the evolution loop to 100 000, it starts to consume more memory, but if I set it to 10 000 the memory usage goes down after completing a "step" and it doesn't accumulate when I step again.

I am looking into multithreading or using a background worker so that the UI doesn't become unresponsive during the evolution. My first attempt at doing so caused some cross threading issues when refreshing the picture box, but I am continuing to look into it.

I would also like to have a start and a stop button, so it can just run and evolve continuously until I press stop.

I also plan to make a new program similar to this, but with more shapes you can select and with controls and displays of whats going on behind the scenes.

Some things I am interested in:

  • Is there anything I did that is blatantly the wrong way of doing it?
  • Are there any techniques I could use that I have not used that would improve the program?
  • Do you see any way to improve the performance or speed?

Here is the designer code (ignore the progress bar/background worker, I'm still implementing it):

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.pictureBox1 = new System.Windows.Forms.PictureBox();
        this.OpenImageButton = new System.Windows.Forms.Button();
        this.openFileDialog1 = new System.Windows.Forms.OpenFileDialog();
        this.pictureBox2 = new System.Windows.Forms.PictureBox();
        this.CreateGenePool = new System.Windows.Forms.Button();
        this.Step = new System.Windows.Forms.Button();
        this.backgroundWorker1 = new System.ComponentModel.BackgroundWorker();
        this.progressBar1 = new System.Windows.Forms.ProgressBar();
        this.pictureBox3 = new System.Windows.Forms.PictureBox();
        this.pictureBox4 = new System.Windows.Forms.PictureBox();
        this.pictureBox5 = new System.Windows.Forms.PictureBox();
        this.pictureBox6 = new System.Windows.Forms.PictureBox();
        this.pictureBox7 = new System.Windows.Forms.PictureBox();
        this.pictureBox8 = new System.Windows.Forms.PictureBox();
        this.pictureBox9 = new System.Windows.Forms.PictureBox();
        this.pictureBox10 = new System.Windows.Forms.PictureBox();
        this.pictureBox11 = new System.Windows.Forms.PictureBox();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox1)).BeginInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox2)).BeginInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox3)).BeginInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox4)).BeginInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox5)).BeginInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox6)).BeginInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox7)).BeginInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox8)).BeginInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox9)).BeginInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox10)).BeginInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox11)).BeginInit();
        this.SuspendLayout();
        // 
        // pictureBox1
        // 
        this.pictureBox1.Location = new System.Drawing.Point(0, 0);
        this.pictureBox1.Name = "pictureBox1";
        this.pictureBox1.Size = new System.Drawing.Size(255, 255);
        this.pictureBox1.TabIndex = 0;
        this.pictureBox1.TabStop = false;
        // 
        // OpenImageButton
        // 
        this.OpenImageButton.Location = new System.Drawing.Point(12, 261);
        this.OpenImageButton.Name = "OpenImageButton";
        this.OpenImageButton.Size = new System.Drawing.Size(75, 23);
        this.OpenImageButton.TabIndex = 1;
        this.OpenImageButton.Text = "Open Image";
        this.OpenImageButton.UseVisualStyleBackColor = true;
        this.OpenImageButton.Click += new System.EventHandler(this.OpenImage);
        // 
        // openFileDialog1
        // 
        this.openFileDialog1.FileName = "openFileDialog1";
        this.openFileDialog1.Filter = "JPEG Files (*.jpg)|*.jpg|PNG Files (*.png)|*.png|BMP Files (*.bmp)|*.bmp|All file" +
"s (*.*)|*.*";
        this.openFileDialog1.Title = "Select an Image File";
        // 
        // pictureBox2
        // 
        this.pictureBox2.Location = new System.Drawing.Point(256, 0);
        this.pictureBox2.Name = "pictureBox2";
        this.pictureBox2.Size = new System.Drawing.Size(255, 255);
        this.pictureBox2.TabIndex = 2;
        this.pictureBox2.TabStop = false;
        // 
        // CreateGenePool
        // 
        this.CreateGenePool.Location = new System.Drawing.Point(256, 261);
        this.CreateGenePool.Name = "CreateGenePool";
        this.CreateGenePool.Size = new System.Drawing.Size(124, 23);
        this.CreateGenePool.TabIndex = 3;
        this.CreateGenePool.Text = "Create Gene Pool";
        this.CreateGenePool.UseVisualStyleBackColor = true;
        this.CreateGenePool.Click += new System.EventHandler(this.CreateGenePool_Click);
        // 
        // Step
        // 
        this.Step.Location = new System.Drawing.Point(386, 261);
        this.Step.Name = "Step";
        this.Step.Size = new System.Drawing.Size(38, 23);
        this.Step.TabIndex = 4;
        this.Step.Text = "Step";
        this.Step.UseVisualStyleBackColor = true;
        this.Step.Click += new System.EventHandler(this.Step_Click);
        // 
        // progressBar1
        // 
        this.progressBar1.Location = new System.Drawing.Point(431, 261);
        this.progressBar1.Name = "progressBar1";
        this.progressBar1.Size = new System.Drawing.Size(69, 23);
        this.progressBar1.TabIndex = 5;
        // 
        // pictureBox3
        // 
        this.pictureBox3.Location = new System.Drawing.Point(512, 0);
        this.pictureBox3.Name = "pictureBox3";
        this.pictureBox3.Size = new System.Drawing.Size(255, 255);
        this.pictureBox3.TabIndex = 6;
        this.pictureBox3.TabStop = false;
        // 
        // pictureBox4
        // 
        this.pictureBox4.Location = new System.Drawing.Point(768, 0);
        this.pictureBox4.Name = "pictureBox4";
        this.pictureBox4.Size = new System.Drawing.Size(255, 255);
        this.pictureBox4.TabIndex = 7;
        this.pictureBox4.TabStop = false;
        // 
        // pictureBox5
        // 
        this.pictureBox5.Location = new System.Drawing.Point(1024, 0);
        this.pictureBox5.Name = "pictureBox5";
        this.pictureBox5.Size = new System.Drawing.Size(255, 255);
        this.pictureBox5.TabIndex = 8;
        this.pictureBox5.TabStop = false;
        // 
        // pictureBox6
        // 
        this.pictureBox6.Location = new System.Drawing.Point(512, 256);
        this.pictureBox6.Name = "pictureBox6";
        this.pictureBox6.Size = new System.Drawing.Size(255, 255);
        this.pictureBox6.TabIndex = 9;
        this.pictureBox6.TabStop = false;
        // 
        // pictureBox7
        // 
        this.pictureBox7.Location = new System.Drawing.Point(768, 256);
        this.pictureBox7.Name = "pictureBox7";
        this.pictureBox7.Size = new System.Drawing.Size(255, 255);
        this.pictureBox7.TabIndex = 10;
        this.pictureBox7.TabStop = false;
        // 
        // pictureBox8
        // 
        this.pictureBox8.Location = new System.Drawing.Point(1024, 256);
        this.pictureBox8.Name = "pictureBox8";
        this.pictureBox8.Size = new System.Drawing.Size(255, 255);
        this.pictureBox8.TabIndex = 11;
        this.pictureBox8.TabStop = false;
        // 
        // pictureBox9
        // 
        this.pictureBox9.Location = new System.Drawing.Point(512, 512);
        this.pictureBox9.Name = "pictureBox9";
        this.pictureBox9.Size = new System.Drawing.Size(255, 255);
        this.pictureBox9.TabIndex = 12;
        this.pictureBox9.TabStop = false;
        // 
        // pictureBox10
        // 
        this.pictureBox10.Location = new System.Drawing.Point(768, 512);
        this.pictureBox10.Name = "pictureBox10";
        this.pictureBox10.Size = new System.Drawing.Size(255, 255);
        this.pictureBox10.TabIndex = 13;
        this.pictureBox10.TabStop = false;
        // 
        // pictureBox11
        // 
        this.pictureBox11.Location = new System.Drawing.Point(1024, 512);
        this.pictureBox11.Name = "pictureBox11";
        this.pictureBox11.Size = new System.Drawing.Size(255, 255);
        this.pictureBox11.TabIndex = 14;
        this.pictureBox11.TabStop = false;
        // 
        // Form1
        // 
        this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
        this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
        this.ClientSize = new System.Drawing.Size(1279, 767);
        this.Controls.Add(this.pictureBox11);
        this.Controls.Add(this.pictureBox10);
        this.Controls.Add(this.pictureBox9);
        this.Controls.Add(this.pictureBox8);
        this.Controls.Add(this.pictureBox7);
        this.Controls.Add(this.pictureBox6);
        this.Controls.Add(this.pictureBox5);
        this.Controls.Add(this.pictureBox4);
        this.Controls.Add(this.pictureBox3);
        this.Controls.Add(this.progressBar1);
        this.Controls.Add(this.Step);
        this.Controls.Add(this.CreateGenePool);
        this.Controls.Add(this.pictureBox2);
        this.Controls.Add(this.OpenImageButton);
        this.Controls.Add(this.pictureBox1);
        this.Name = "Form1";
        this.Text = "Form1";
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox1)).EndInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox2)).EndInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox3)).EndInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox4)).EndInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox5)).EndInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox6)).EndInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox7)).EndInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox8)).EndInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox9)).EndInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox10)).EndInit();
        ((System.ComponentModel.ISupportInitialize)(this.pictureBox11)).EndInit();
        this.ResumeLayout(false);

    }

    #endregion

    private System.Windows.Forms.PictureBox pictureBox1;
    private System.Windows.Forms.Button OpenImageButton;
    private System.Windows.Forms.OpenFileDialog openFileDialog1;
    private System.Windows.Forms.PictureBox pictureBox2;
    private System.Windows.Forms.Button CreateGenePool;
    private System.Windows.Forms.Button Step;
    private System.ComponentModel.BackgroundWorker backgroundWorker1;
    private System.Windows.Forms.ProgressBar progressBar1;
    private System.Windows.Forms.PictureBox pictureBox3;
    private System.Windows.Forms.PictureBox pictureBox4;
    private System.Windows.Forms.PictureBox pictureBox5;
    private System.Windows.Forms.PictureBox pictureBox6;
    private System.Windows.Forms.PictureBox pictureBox7;
    private System.Windows.Forms.PictureBox pictureBox8;
    private System.Windows.Forms.PictureBox pictureBox9;
    private System.Windows.Forms.PictureBox pictureBox10;
    private System.Windows.Forms.PictureBox pictureBox11;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Do you happen to have it on GitHub or could add the designer code too? I'd like to run it ;-] Oh, and links to the original images you tested it with would be great too so we can compare the performance. \$\endgroup\$ – t3chb0t Jan 25 at 16:11
  • 1
    \$\begingroup\$ I added the designer code. The original images were just the Sample Pictures in My Pictures folder, I think if you just google "windows 7 jelly fish/hydrangea/lighthouse picture" you can find them. I also added a line to start the bitmap with a black background, it seems to go a little faster than a white/empty background. I also added the 9 other picture boxes to display each individual in the gene pool as they change. After around 2000 iterations, which is what I have the button set to, it starts to look pretty close as far as colors and rough shapes go. \$\endgroup\$ – jreese Jan 25 at 16:26
  • 1
    \$\begingroup\$ cool :D, I should mention that first you open a target image, then create the gene pool, then step. You can step again after, or open a new image and see how it adapts to that from the previous image. The Create gene pool button is probably unnecessary but for making sure everything works it made sense. I had a console output for debugging but that's unnecessary too. OH and because it's not on a background worker yet, click continue when it cries about pumping windows messages, it'll keep going. \$\endgroup\$ – jreese Jan 25 at 16:37
  • 1
    \$\begingroup\$ I've let ReSharper profiler measure it and currently as far as calculations are concerned the ColorDistance is the most time consuming method which is called millions of times and consequently of course ScoreGenomes ;-) mhmm there should be a way to paralleize it... \$\endgroup\$ – t3chb0t Jan 25 at 16:51
  • \$\begingroup\$ Interesting, I'm going to check out ReSharper I hadn't heard of it. That sort of makes sense, its a bunch of double and long arithmetic and math for each of the 65025 points that it compares. That is the bulk of the scoring method too. I've read about several different color comparison methods. I might try to implement some other color distance calculations. It's a trade off though, RGB difference is less accurate, RGB^2 difference is more accurate but more math, and the human vision color channel weighting is even more accurate but with more math. \$\endgroup\$ – jreese Jan 25 at 16:59
3
\$\begingroup\$

Optimization

You can achieve a significant perfomance improvement by using a so-called 'dirty rectangles' approach. Instead of calculating the color-distance of every single pixel every single time, you only need to recalculate the distance of pixels that have been modified. Every step, you're eliminating two genomes, so they will have to be fully recalculated. You're also mutating another genome, which only affects a single property of a single rectangle, so you only need to recalculate pixels affected by that change. All the other genomes are unaffected, so they don't need to be recalculated at all. Some quick testing shows that this can make things up to 10x faster.

Design

The Chromosome, Genome and Genepool classes are tightly coupled to Form1. They're also difficult to use correctly due to various implicit assumptions and a lack of protection against inconsistent state:

  • Instead of depending on 'constants' in Form1, pass in the number of chromosomes and genomes via the relevant constructors: new Genepool(genomeCount: 10, chromosomeCount: 32). The same goes for Random - pass it to the constructors or methods that need it. This makes dependencies clearly visible, and makes it easier to reuse these classes in a different context.
  • Instead of setting Chromosomestring and then having to call DecodeChromosomeString, create a void Decode(string chromosomeString) method. This forces a caller to provide the required data. And instead of calling EncodeChromosomeString and then fetching Chromosomestring, create a method string Encode() that returns that string directly. This clearly presents the resulting data to the caller.
  • Chromosome.Rectangle and Chromosome.RectangleColor can easily go out-of-sync with the properties they depend on. All properties having public setters doesn't exactly make it easy to maintain a consistent state. Creating a rectangle or color upon request (such as public Rectangle Rectangle => new Rectangle(X, Y, Width, Height);) would simplify this.

Other notes

  • C# supports auto-properties, so you don't explicitly need to define a backing field: public int X { get; set; }. The setter can be left out or made private for read-only properties or properties that should only be modified from within the class itself. Nowadays it's also possible to initialize properties: public string Name { get; set; } = "Unknown";.
  • Why are all Chromosome properties of type ulong? There's a comment stating they'll only have values ranging from 0-255, so byte seems more appropriate. Otherwise, int is typically used by default.
  • You may want to document the purpose of GrayEncode and GrayDecode. Apparently Gray encoding reduces the frequency of 'radical' mutations?
  • Instead of doing for (int i = 0; i < constantName; i++), consider doing for (int i = 0; i < array.Length; i++). That'll work regardless of whether array was initialized using a constant or a more dynamic value.
  • Genepool creates and contains a bunch of bitmaps, but Form1.Evolve disposes them. It's better to clearly define 'ownership'. In this case, Genepool creates and uses these images, so it should also dispose them (and so it should also implement IDisposable itself).
  • Why create new bitmaps instead of reusing old ones?
  • SolidBrushes should be disposed. For common colors, you can use Brushes.<colorname> instead of creating a new brush.

Genome.MutateGenome can be simplified to:

var chars = genomestring.ToCharArray();
var mutationIndex = r.Next(0, chars.Length);
chars[mutationIndex] = chars[mutationIndex] == '0' ? '1' : '0';
genomestring = new string(chars);

GenePool.SortScores can be simplified to:

scoredIndex = score
    .Select((score, index) => new { score, index })
    .OrderBy(scoring => scoring.score)
    .Select(scoring => scoring.index)
    .ToList();

The anonymous object (new { score, index }) lets you use more descriptive field names than Key and Value, but otherwise serves the same purpose.

\$\endgroup\$
  • \$\begingroup\$ Pieter, this is great! thank you. This is exactly the kind of feed back I was hoping for. It's a lot to go through, and I will post an update in the future. The dirty rectangle is a great idea! It seems so obvious, I've done similar things in other projects with drawing a game tile board. I will try to implement the structural design changes. As for some of the notes - I right clicked and used the auto refactoring to make the properties, your'e right though I could clean them all up. I used ulong because the gray encoding took in ulong, and the gray encoding was working. \$\endgroup\$ – jreese Jan 30 at 13:38
  • \$\begingroup\$ gray encoding is to prevent "hamming walls", two mutations must occur for "1.9" to mutate into "2.0", 1 to 2, and 9 to 0. gray code makes it so that one mutation can more smoothly mutate up and down a range without getting stuck on a place where two mutations would have been necessary. Gray encoding is commonly used for this type of genetic evolutionary algorithm. The bitmaps gave me a headache! I will see what I can do about reusing and managing the disposal better. Initially I had a lot of issues with memory usage from the bitmaps. Thanks again! I'll post again to show progress. \$\endgroup\$ – jreese Jan 30 at 13:40
2
\$\begingroup\$

I have two small sugestions...


Without using different math in ColorDistance which is the bottleneck (according to ReShaprer profiler (dotTrace)) as a quick speed improvement you can paralleize ScoreGenoms by using Parallel.For replacing the original for

Parallel.For(0, numberOfGenomes, i => 
{
   ...
})

Evolve on the other hand could use Application.DoEvents(); at the end of the the outher loop to quickly fix the unresponsive UI (until it runs in a task...)

\$\endgroup\$
  • \$\begingroup\$ Thank you so much I appreciate the feedback! I will try those out, I haven't come across them before. So, as far as the object oriented approach goes, does it look OK? Am I on the right path? I know I haven't really used any interfaces or inheritance, but I didn't really feel like I needed to in order to achieve these results. \$\endgroup\$ – jreese Jan 25 at 17:38
  • 2
    \$\begingroup\$ @jreese I just took a quick look at it so I think I'll add more comments later when I've studied the algorithm and the application as this is quite interesting and a little bit complex at first. I'll let you know when I've done some changes... although others might be quicker than me ;-] anyway... as far as design is concerned there is plenty room for improvement but I first need to take a closer look. As a matter of fact you never need any special design to achieve the desired results. The only reason why we carefuly design our apps is because we want them to be maintainable & testable ;-) \$\endgroup\$ – t3chb0t Jan 25 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.