Итак, на выходных мы должны весело отдохнуть, а потому попробуем векторизовать изображение генетическим алгоритмом.

Задача

Сделать из полупрозрачных многоугольников изображение максимально похожее на оригинал.

Прежде всего хочу сказать, что использование генетического алгоритма в решении этой задачи не имеет практической пользы из-за очень долгого времени выполнения, и сделано все just for fun.

Демонстрация

В связи с приближающимся наконец-то сентябрем, в качестве примера работы программы была выбрана картинка доктора Хауса.

Итак создание доктора Хауса из ста десятиугольников в течение 20 часов:

Исходные данные

Что для данной задачи будет являться генами? Оказывается, это будут координаты точек многоугольника (далее будем называть его полигоном) и его цвет. Скрещивание мы использовать не будем, только мутацию (это вполне допустимо). Популяция, как ни странно, будет состоять из одного индивида, и это будет картинка с прорисованными на ней полигонами.

Функцией приспособления будет сумма погрешностей цветов всех пикселов. Погрешность для пикселя определяем как
R*R + G*G + B*B, где R — разность между красной составляющей пикселя исходной картинки и полученной, G и B — зеленой и синей. Чем меньше значение функции, тем меньше погрешность и тем лучшую картинку мы получили.

Код

Определим класс точки полигона:

    [Serializable]
    public class Point: ICloneable
    {
        public int X { get; set; }
        public int Y { get; set; }

        public void SetRandom()
        {
            X = Helper.Rand.Next(0, Helper.Width);
            Y = Helper.Rand.Next(0, Helper.Height);
        }

        public void Mutate(Workarea workarea)
        {
            if (Helper.Rand.NextDouble() <= Helper.MutationPointMoveMaxChance)
            {
                SetRandom();
                workarea.IsChange = true;
            }

            if (Helper.Rand.NextDouble() <= Helper.MutationPointMoveMiddleChance)
            {
                X = Math.Min(Math.Max(0, X + Helper.Rand.Next(-Helper.MiddleRange, Helper.MiddleRange + 1)), Helper.Width);
                Y = Math.Min(Math.Max(0, Y + Helper.Rand.Next(-Helper.MiddleRange, Helper.MiddleRange + 1)), Helper.Height);
                workarea.IsChange = true;
            }

            if (Helper.Rand.NextDouble() <= Helper.MutationPointMoveNearChance)
            {
                X = Math.Min(Math.Max(0, X + Helper.Rand.Next(-Helper.NearRange, Helper.NearRange + 1)), Helper.Width);
                Y = Math.Min(Math.Max(0, Y + Helper.Rand.Next(-Helper.NearRange, Helper.NearRange + 1)), Helper.Height);
                workarea.IsChange = true;
            }
        }

        public object Clone()
        {
            return new Point { X = X, Y = Y };
        }
    }

* This source code was highlighted with Source Code Highlighter.

Точка имеет координаты X и Y. Процедура SetRandom задает точке случайные координаты, согласно размерам нашей картинки. Процедура Mutate делится на три части, каждая из которых выполняется согласно своей заданной вероятности выпадения. Первая дает шанс точке переместиться в любое место картинки. Вторая часть перемещает точку на среднее расстояние, далее вы увидите, что у меня это до двадцати пикселов. Третья часть дает шанс переместиться на маленькое расстояние, у меня это до трех пикселов.

Далее идет класс кисти, отвечающей за цвет полигона:

    [Serializable]
    public class Brush: ICloneable
    {
        public int A { get; set; }
        public int R { get; set; }
        public int G { get; set; }
        public int B { get; set; }

        public void SetRandom()
        {
            A = Helper.Rand.Next(30, 60);
            R = Helper.Rand.Next(0, 256);
            G = Helper.Rand.Next(0, 256);
            B = Helper.Rand.Next(0, 256);
        }

        public void Mutate(Workarea workarea)
        {
            if (Helper.Rand.NextDouble() <= Helper.MutationBrushAChance)
            {
                A = Helper.Rand.Next(30, 60);
                workarea.IsChange = true;
            }

            if (Helper.Rand.NextDouble() <= Helper.MutationBrushRChance)
            {
                R = Helper.Rand.Next(0, 256);
                workarea.IsChange = true;
            }

            if (Helper.Rand.NextDouble() <= Helper.MutationBrushGChance)
            {
                G = Helper.Rand.Next(0, 256);
                workarea.IsChange = true;
            }

            if (Helper.Rand.NextDouble() <= Helper.MutationBrushBChance)
            {
                B = Helper.Rand.Next(0, 256);
                workarea.IsChange = true;
            }
        }

        public object Clone()
        {
            return new Brush
            {
                A = A,
                R = R,
                G = G,
                B = B
            };
        }
    }

* This source code was highlighted with Source Code Highlighter.

У кисти есть A, R, G, B составляющие цвета. SetRandom инициализирует их случайными значениями. В процедуре Mutate каждая из составляющих может случайно измениться согласно своей вероятности выпадения мутации.

Вот мы и подошли к классу полигона:

    [Serializable]
    public class Polygon: ICloneable
    {
        public List<Point> Points { get; set; }
        public Brush Brush { get; set; }

        public void SetRandom()
        {
            Points = new List<Point>();

            Point center = new Point();
            center.SetRandom();

            for (int i = 0; i < Helper.MinPointsPerPolygon; i++)
            {
                Point point = new Point();
                point.X = Math.Min(Math.Max(0, center.X + Helper.Rand.Next(-3, 4)), Helper.Width);
                point.Y = Math.Min(Math.Max(0, center.X + Helper.Rand.Next(-3, 4)), Helper.Height);
                Points.Add(point);
            }

            Brush = new Brush();
            Brush.SetRandom();
        }

        public void Mutate(Workarea workarea)
        {
            if (Helper.Rand.NextDouble() <= Helper.MutationPolygonAddPointChance)
            {
                AddPoint();
                workarea.IsChange = true;
            }

            if (Helper.Rand.NextDouble() <= Helper.MutationPolygonDelPointChance)
            {
                DelPoint();
                workarea.IsChange = true;
            }

            Brush.Mutate(workarea);
            Points.ForEach(p => p.Mutate(workarea));
        }

        private void AddPoint()
        {
            if (Points.Count < Helper.MaxPointsPerPolygon)
            {
                Point point = new Point();
                int index = Helper.Rand.Next(1, Points.Count - 1);
                Point p1 = Points[index - 1];
                Point p2 = Points[index];
                point.X = (p1.X + p2.X) / 2;
                point.Y = (p1.Y + p2.Y) / 2;
                Points.Insert(index, point);
            }
        }

        private void DelPoint()
        {
            if (Points.Count > Helper.MinPointsPerPolygon)
            {
                int index = Helper.Rand.Next(0, Points.Count);
                Points.RemoveAt(index);
            }
        }

        public void Draw(Graphics g)
        {
            using (SolidBrush brush = new SolidBrush(Color.FromArgb(Brush.A, Brush.R, Brush.G, Brush.B)))
            {
                System.Drawing.Point[] points = Points.Select(p => new System.Drawing.Point(p.X,p.Y)).ToArray();
                g.FillPolygon(brush, points);
            }
        }

        public object Clone()
        {
            Polygon newpolygon = new Polygon();
            newpolygon.Brush = Brush.Clone() as Brush;
            newpolygon.Points = new List<Point>();
            Points.ForEach(p => newpolygon.Points.Add(p.Clone() as Point));
            return newpolygon;
        }
    }

* This source code was highlighted with Source Code Highlighter.

Полигон включает в себя массив точек и кисть (цвет). Процедура SetRandom инициализирует кисть, а также строит минимальное количество точек вокруг случайно выбранной. Мутация полигона представляет собой мутацию кисти и каждой точки полигона, а также с некоторой вероятностью может произойти добавление или удаление какой-то точки. Процедура Draw отрисовывает наш полигон.

Ну и наконец заключительный основной класс представляет собой рабочую область, содержащую наши многоугольники:

    [Serializable]
    public class Workarea: ICloneable
    {
        public List<Polygon> Polygons { get; set; }

        [XmlIgnore]
        public bool IsChange { get; set; }

        public void SetRandom()
        {
            Polygons = new List<Polygon>();

            for (int i = 0; i < Helper.MinPolygons; i++)
            {
                AddPolygon();
            }

            IsChange = true;
        }

        public void Mutate()
        {
            if (Helper.Rand.NextDouble() <= Helper.MutationWorkareaAddPolygonChance)
            {
                AddPolygon();
                IsChange = true;
            }

            if (Helper.Rand.NextDouble() <= Helper.MutationWorkareaDelPolygonChance)
            {
                DelPolygon();
                IsChange = true;
            }

            Polygons.ForEach(p => p.Mutate(this));
        }

        private void AddPolygon()
        {
            if (Polygons.Count < Helper.MaxPolygons)
            {
                Polygon polygon = new Polygon();
                polygon.SetRandom();
                Polygons.Add(polygon);
            }
        }

        private void DelPolygon()
        {
            if (Polygons.Count > Helper.MinPolygons)
            {
                int index = Helper.Rand.Next(0, Polygons.Count);
                Polygons.RemoveAt(index);
            }
        }

        public double Fitness(Color[,] colors)
        {
            double fitness = 0;
            Bitmap img = Draw();
            FastBitmap fastimg = new FastBitmap(img);
            for (int i = 0; i < Helper.Width; i++)
            {
                for (int j = 0; j < Helper.Height; j++)
                {
                    Color c1 = fastimg.GetPixel(i, j);
                    Color c2 = colors[i, j];
                    int r = c1.R - c2.R;
                    int g = c1.G - c2.G;
                    int b = c1.B - c2.B;
                    fitness += r * r + g * g + b * b;
                }
            }
            fastimg.Release();
            img.Dispose();
            return fitness;
        }

        public Bitmap Draw()
        {
            Bitmap img = new Bitmap(Helper.Width, Helper.Height);
            using (Graphics g = Graphics.FromImage(img))
            {
                g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.HighQuality;
                g.Clear(Color.Black);

                Polygons.ForEach(p => p.Draw(g));
            }
            return img;
        }

        public object Clone()
        {
            Workarea newarea = new Workarea();
            newarea.Polygons = new List<Polygon>();
            Polygons.ForEach(p => newarea.Polygons.Add(p.Clone() as Polygon));
            return newarea;
        }
    }

* This source code was highlighted with Source Code Highlighter.

Истинность свойства IsChange показывает, что где-то произошла мутация. SetRandom инициализирует минимальное начальное число полигонов. Mutate запускает мутацию для каждого полигона, а также с заданной вероятностью может произойти добавление или удаление полигона. Функция Fitness вычисляет функцию приспособления, ей передается массив цветов оригинальной картинки. Ну и функция Draw возвращает нашу отрисованную картинку.

Сам алгоритм выглядит так:

        private void Start()
        {
            if (workarea == null)
            {
                workarea = new Workarea();
                workarea.SetRandom();
            }

            while (isRunning)
            {
                Workarea newarea;
                lock (workarea)
                {
                    newarea = workarea.Clone() as Workarea;
                }
                newarea.Mutate();

                if (newarea.IsChange)
                {
                    double newfitness = newarea.Fitness(sourceColors);

                    if (newfitness <= fitness)
                    {
                        lock (workarea)
                        {
                            workarea = newarea;
                        }
                        fitness = newfitness;
                    }
                }
            }
        }

* This source code was highlighted with Source Code Highlighter.

Инициализируем начальную популяцию, далее делаем копию и мутируем ее, вычисляем функцию приспособления для новой популяции и, если она меньше текущей (напоминаю, у нас, чем меньше значение функции, тем лучше), то перезаписываем текущую популяцию новой, более лучшей.

Еще у нас остался вспомогательный класс, где хранятся настройки:

    public static class Helper
    {
        public static readonly Random Rand = new Random();

        public static int Width = 0;
        public static int Height = 0;

        public static int MinPointsPerPolygon = 3;
        public static int MaxPointsPerPolygon = 10;

        public static int MinPolygons = 0;
        public static int MaxPolygons = 100;

        public static int NearRange = 3;
        public static int MiddleRange = 20;
        
        public static double MutationPointMoveMaxChance = 0.0007;
        public static double MutationPointMoveMiddleChance = 0.0007;
        public static double MutationPointMoveNearChance = 0.0007;
        
        public static double MutationBrushAChance = 0.0007;
        public static double MutationBrushRChance = 0.0007;
        public static double MutationBrushGChance = 0.0007;
        public static double MutationBrushBChance = 0.0007;
        
        public static double MutationPolygonAddPointChance = 0.0007;
        public static double MutationPolygonDelPointChance = 0.0007;
        
        public static double MutationWorkareaAddPolygonChance = 0.0014;
        public static double MutationWorkareaDelPolygonChance = 0.0007;
    }

* This source code was highlighted with Source Code Highlighter.

Здесь у нас хранятся ширина и высота исходной картинки (инициализируется при загрузке), минимальное и максимальное количество точек в полигоне, минимальное и максимальное число полигонов, вероятности мутаций для каждой компоненты (единица — стопроцентная мутация) и расстояния, на которые может переместиться точка.
Проект целиком можно слить здесь.

UPD: спасибо за карму, перенес в блог Алгоритмы.
_________
Текст подготовлен в ХабраРедакторе