Simple genetic algorithm

readme.markdown

Simple genetic algotithm

Related article, unfortunately in not in english.

• MainViewModel.cs contains genetics algorithm and have contains property to dwaw chart
• LinqExtension.cs contains fonction to get random item with probability
• MainWindow.xaml represent simple window with oxy plot
• MainWindow.xaml.cs calls Generate() functions from VM on button click

MainViewModel.cs

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using OxyPlot;
using OxyPlot.Series;
using static System.Math;

namespace EvolutionSimpleAlgoritm
{
    public class MainViewModel
    {
        public ObservableCollection<DataPoint> BestFromGenerations { get; } = new ObservableCollection<DataPoint>();
        public ObservableCollection<ScatterPoint> AllGenerations { get; } = new ObservableCollection<ScatterPoint>();

        private static readonly Func<double, double> FittnesFunction =
            x => -(Pow(x - 100, 2) / 100) + (Sin(x) * 50) + 10;


        private static readonly Random Random = new Random();

        private static HashSet<byte> GeneratePopulation(int populationSize)
        {
            HashSet<byte> population = new HashSet<byte>();
            while (population.Count < populationSize)
            {
                population.Add((byte) Random.Next(Byte.MinValue, Byte.MaxValue));
            }
            return population;
        }

        private static HashSet<byte> RecombinePopulation(
            IEnumerable<(byte individual , double fitnessValue)> population,
            int populatationSize, int eliteClons)
        {
            var newPopulation = new HashSet<byte>();
            foreach (var elite in population.OrderByDescending(t => t.Item2).Take(eliteClons))
            {
                newPopulation.Add(elite.Item1); // clone elite individual to new population
            }

            var min = population.Min(t => t.Item2);
            while (newPopulation.Count < populatationSize)
            {
                byte x = population.GetRandomItem(b => b.Item2 - min).Item1;
                byte y = x; // initialize 
                while (y == x)
                {
                    y = population.GetRandomItem(b => b.Item2 - min).Item1;
                }
                newPopulation.Add(RecombineGenomtype(x, y));
            }


            return newPopulation;
        }

        private static byte RecombineGenomtype(byte x, byte y)
        {
            var split = Random.Next(0, 32);
            byte mask = (byte) ((1 << split) - 1);
            byte xpart = (byte) (x & mask);
            byte ypart = (byte) (y & ~mask);
            byte z = (byte) (xpart | ypart);

            while (Random.NextDouble() < 0.2) //mutation
            {
                var mutationBit = Random.Next(0, 31);
                mask = (byte) (1 << mutationBit);
                z ^= mask; // invert bit
            }

            return z;
        }

        public void Recalculate()
        {
            var population = GeneratePopulation(populationSize: 8);
            ClearChart();

            for (int i = 0; i < 100; i++)
            {
                var selection = population
                    .Select(b => (b, FittnesFunction(b)))
                    .ToList();

                AddChartValues(selection, i);

                population = RecombinePopulation(selection, populatationSize: 8, eliteClons: 1);
            }
        }

        private void ClearChart()
        {
            BestFromGenerations.Clear();
            AllGenerations.Clear();
        }

        private void AddChartValues(List<(byte individual, double fitnesValue)> population, int i)
        {
            var eliteFittnes = population
                .OrderByDescending(t => t.Item2)
                .First()
                .Item2; //take fitness value

            BestFromGenerations.Add(new DataPoint(i, eliteFittnes));
            foreach (var p in population)
            {
                AllGenerations.Add(new ScatterPoint(i, p.Item2, 1));
            }
        }
    }
}

LinqExtension.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace EvolutionSimpleAlgoritm
{
    public static class LinqExtension
    {
        static Random Random = new Random();

        public static T GetRandomItem<T>(this IEnumerable<T> pool, Func<T, double> probabylityFunc)
        {
            // get universal probability 
            double u = pool.Sum(probabylityFunc);

            // pick a random number between 0 and u
            double r = Random.NextDouble() * u;

            double sum = 0;
            foreach (var n in pool)
            {
                // loop until the random number is less than our cumulative probability
                if (r <= (sum = sum + probabylityFunc(n)))
                {
                    return n;
                }
            }
            // should never get here
            throw new Exception();
        }
    }
}

MainWindow.xaml

<Window x:Class="EvolutionSimpleAlgoritm.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:EvolutionSimpleAlgoritm"
        xmlns:oxy="http://oxyplot.org/wpf"
        mc:Ignorable="d"
        Title="MainWindow" Height="350" Width="525">
    <Window.DataContext>
        <local:MainViewModel />
    </Window.DataContext>
    <Grid>
        <Grid.RowDefinitions>
            <RowDefinition Height="45*" />
            <RowDefinition Height="274*" />
        </Grid.RowDefinitions>
        <Grid.ColumnDefinitions>
            <ColumnDefinition />
            <ColumnDefinition Width="200" />
        </Grid.ColumnDefinitions>
        <oxy:Plot Grid.ColumnSpan="2" Grid.Row="1">
            <oxy:Plot.Series>
                <oxy:ScatterSeries ItemsSource="{Binding AllGenerations}" Color="DarkOliveGreen" MarkerType="Circle" />
                <oxy:LineSeries ItemsSource="{Binding BestFromGenerations}" Color="GreenYellow" />
            </oxy:Plot.Series>
        </oxy:Plot>
        <Button Content="Generate" Grid.Column="1" HorizontalAlignment="Left" Margin="10,10,0,0" VerticalAlignment="Top"
                Width="180" Click="Button_Click" />
    </Grid>
</Window>

MainWindow.xaml.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows;
using OxyPlot;
using static System.Math;


namespace EvolutionSimpleAlgoritm
{
    /// <summary>
    /// Logika interakcji dla klasy MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
        }


        private void Button_Click(object sender, RoutedEventArgs e)
        {
            ((MainViewModel) DataContext).Recalculate();
        }
    }
}

packages.config

<?xml version="1.0" encoding="utf-8"?>

<packages>
  <package id="OxyPlot.Core" version="1.0.0" targetFramework="net452" />
  <package id="OxyPlot.Wpf" version="1.0.0" targetFramework="net452" />
  <package id="System.ValueTuple" version="4.3.0" targetFramework="net452" />
</packages>