Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Simple genetic algorithm

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
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));
}
}
}
}
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();
}
}
}
<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>
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();
}
}
}
<?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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment