Tuesday, 7 April 2015

Visualisation of evolution

Even though we know that the end result is what we are after, and speed is one of the most important factors, it would be nice when assessing different mutation and breeding operator combinations, and the affect of the applied fitness function to track the evolution of the population, or at least that of the fittest member(s) graphically to quickly see, and convey to intetrsted parties what is happening.
To this end I will explore the possibility of hooking a visualisation interface into the algorithm with a minimum of code churn, and minimal speed impact.
The approach I will take is to use a consumer object to handle the generation complete event. The responsibility of not blocking the processing thread will fall to this consumer, and all details of the rendering of the interim results will be totally hidden to the gentic algorithm itself.  This approach will mean that if a web enabled front end, or simply a different desktop UI, were needed you merely need to construct this and inject it.

I have chosen to use a WPF Gui as I have experience of automatically updating graphs in this medium. Another technology may be better suited to your skill set. The WPFToolkit offers a very good charting control, which can plot data the is updated in real time very easily with data binding.  I will not go into the details of the WPF application itself, or the structure of such an application, however the details of displaying the evolution are what we are interested in, so that is what I will focus on. But I will say that my chosen architecture employed an MVVM pattern

 The code for each chart is very simple, with the UI layer being simply

  xmlns:chartingToolkit="clr-namespace:System.Windows.Controls.DataVisualization.Charting;assembly=System.Windows.Controls.DataVisualization.Toolkit"  
 <chartingToolkit:Chart Title="Fitness" >  
       <chartingToolkit:Chart.Axes>  
         <chartingToolkit:LinearAxis Orientation="Y" ShowGridLines="False"  Minimum="{Binding MinFitness}" Maximum="{Binding MaxFitness}" />  
       </chartingToolkit:Chart.Axes>  
       <chartingToolkit:LineSeries DependentValuePath="Value" IndependentValuePath="Key" ItemsSource="{Binding GenerationFitness}" IsSelectionEnabled="True" />  
     </chartingToolkit:Chart>  

Where the MinFitness and MaxFitness are values calculated as results are generated to give a sensible range for the graph, and the GenerationFitness property is a collection holding the points to plot in the graph. This is bound to a view model that exposes the data without exposing the detail of the GA, and this takes the form:

 class ViewModel: NotifyingObject  
   {  
     private Model theData;  
     private double _minFitness;  
     private double _maxFitness;  
     private double varf = 0.01d;  
     private string _results;  
     private int _delay=0;  
     public ViewModel()  
     {  
       theData = new Model();  
       GenerationFitness = new ObservableCollection<KeyValuePair<int, double>>();  
       GenerationF = new ObservableCollection<KeyValuePair<int, double>>();  
       GenerationR = new ObservableCollection<KeyValuePair<int, double>>();  
       theData.NewGeneration += GotNewGeneration;  
       theData.FinalResults += GotFinalResults;  
       ResetFitness();  
     }  
     public int PopulationSize { get { return theData.PopulationSize; } set { theData.PopulationSize = value; } }  
     public int MaxGenerations { get { return theData.MaxGenerations; } set { theData.MaxGenerations= value; } }  
     public double MinFitness { get { return _minFitness; } set { _minFitness = value; OnPropertyChanged(); } }  
     public double MaxFitness { get { return _maxFitness; } set { _maxFitness = value; OnPropertyChanged(); } }  
     public string Results { get { return _results; }set{_results = value; OnPropertyChanged();} }  
     public int Delay { get { return _delay; } set { _delay = value; OnPropertyChanged(); } }  
     public ObservableCollection<KeyValuePair<int, double>> GenerationFitness { get; set; }  
     public ObservableCollection<KeyValuePair<int, double>> GenerationR { get; set; }  
     public ObservableCollection<KeyValuePair<int, double>> GenerationF { get; set; }  
     public ICommand Stop { get { return new RelayUICommand("Stop", (p) => theData.Stop(), (p) => theData.IsRunning); } }  
     public ICommand Start  
     {  
       get  
       {  
         return new RelayUICommand("Start", (p) =>  
         {  
           ClearAll();  
           theData.Start();  
         }  
         , (p) => !theData.IsRunning);  
       }  
     }  
     public ICommand Clear  
     {  
       get  
       {  
         return new RelayUICommand("Clear", (p) =>  
         {  
           ClearAll();  
         }  
           , (p) => !theData.IsRunning);  
       }  
     }  
     private void ResetFitness()  
     {  
       _minFitness = 0d;  
       _maxFitness = 1d;  
     }  
     private void GotNewGeneration(object sender, GenerationEventArgs e)  
     {  
       Application.Current.Dispatcher.Invoke(() =>  
         {   
           GenerationFitness.Add(new KeyValuePair<int, double>(e.Generation, e.Fitness));  
           if (e.Generation ==1)  
           {  
             MaxFitness = e.Fitness * (1d + varf);   
             MinFitness = e.Fitness * (1d-varf);  
           }  
           MaxFitness = Math.Max(MaxFitness, e.Fitness *(1d + varf));  
           MinFitness = Math.Min(MinFitness, e.Fitness * (1d - varf));  
           GenerationF.Add(new KeyValuePair<int, double>(e.Generation, e.F));  
           GenerationR.Add(new KeyValuePair<int, double>(e.Generation, e.R));  
           Debug.WriteLine(String.Format("Generation: {0}, Fitness: {1},R: {2}, F: {3}", e.Generation, e.Fitness, e.R, e.F));  
         });  
       Thread.Sleep(Delay );  
     }  
     private void GotFinalResults(object sender, FinalResultsEventArgs e)  
     {  
       Results = String.Format("R: {0}{1}F: {2}{1}Fitness: {3}{1}{1}From Values:{1}{4}", e.R, Environment.NewLine, e.F, e.Fitness, String.Join(Environment.NewLine, e.GeneValues));  
     }  
     private void ClearAll()  
     {  
       ResetFitness();  
       GenerationFitness.Clear();  
       GenerationR.Clear();  
       GenerationF.Clear();  
       Results = "";  
     }  
   }  

The model behind this does the work of instantiating the GA and it relays the results of each generation and the completion of the run in a meaningful manner to the view model:

 class Model: NotifyingObject  
   {  
     private double targetR = 0.95d;  
     private double targetF = 0.5d;  
     public double TargetR { get { return targetR; } set { targetR = value; OnPropertyChanged(); } }  
     public double TargetF { get { return targetF; } set { targetF = value; OnPropertyChanged(); } }  
     public EventHandler<DoubleEventArgs> NewFitnessValueArrived;  
     public EventHandler<GenerationEventArgs> NewGeneration;  
     public EventHandler<FinalResultsEventArgs> FinalResults;  
     private IGAProvider gaProvider;  
     private GeneticAlgorithm ga;  
     private int _maxGenerations;  
     private bool _isRunning;  
     public Model()  
     {  
       PopulationSize = 10000;  
       MaxGenerations = 100;  
       ////initialise the GA and hook up events  
       const double crossoverProbability = 0.02;  
       const double mutationProbability = 0.8;  
       gaProvider = GetGaProvider();  
       var crossover = new Crossover(crossoverProbability, true)  
       {  
         CrossoverType = CrossoverType.SinglePoint  
       };  
       //var crossover = new AveragingBreeder() { Enabled = true };  
       //inject the mutation algorithm  
       var mutation = new SwapMutate(mutationProbability);  
       //var mutation = new PairGeneMutatorWithFixedValueSum2(mutationProbability){Enabled = true};  
       //var mutation = new SingleGeneVaryDoubleValueMaintainingSum3(mutationProbability, 1d, 0.2d) { Enabled = true };  
       gaProvider.AddMutator(mutation);  
       gaProvider.AddBreeder(crossover);  
     }  
     public void Start()  
     {  
       const int elitismPercentage = 10;  
       var dh = new DoubleHelpers();  
       ga = gaProvider.GetGA(elitismPercentage, dh, PopulationSize);  
       GAF.GeneticAlgorithm.GenerationCompleteHandler generationComplete = ga_OnGenerationComplete;  
       GAF.GeneticAlgorithm.RunCompleteHandler runComplete = ga_OnRunComplete;  
       gaProvider.HookUpEvents(generationComplete, runComplete);  
       Task.Factory.StartNew(() => ga.Run(gaProvider.Terminate));  
       IsRunning = true;  
     }  
     public void Stop()  
     {  
       ga.Halt();  
       IsRunning = false;  
     }  
     private void ga_OnGenerationComplete(object sender, GaEventArgs e)  
     {  
       (gaProvider as DoubleChromosomes).CurrentGeneration = e.Generation;  
       var fittest = e.Population.GetTop(1)[0];  
       var r = (gaProvider as DoubleChromosomes).GetR(fittest.Genes.Select(x => x.RealValue));  
       var f = (gaProvider as DoubleChromosomes).GetF(fittest.Genes.Select(x => x.RealValue));  
       FireGenerationArrived(e.Generation, fittest.Fitness, r, f);  
     }  
      void ga_OnRunComplete(object sender, GaEventArgs e)  
     {  
       IsRunning = false;  
       var fittest = e.Population.GetTop(1)[0];  
       var r = (gaProvider as DoubleChromosomes).GetR(fittest.Genes.Select(x => x.RealValue));  
       var f = (gaProvider as DoubleChromosomes).GetF(fittest.Genes.Select(x => x.RealValue));        
       FireFinalResults(fittest.Genes.Select(x => x.RealValue), r, f, fittest.Fitness);  
     }  
     public IGAProvider GetGaProvider()  
     {  
       var gaProvider = new DoubleChromosomes(TargetF, TargetR){MaxGenerations = _maxGenerations};  
       return gaProvider;  
     }  
     private void FireGenerationArrived(int generation, double fitness, double r, double f)  
     {  
       var h = NewGeneration;  
       if (h == null)  
         return;  
       h(this, new GenerationEventArgs(generation, fitness, r, f));  
     }  
     private void FireFinalResults(IEnumerable<double> geneValues, double r, double f, double fitness)  
     {  
       var h = FinalResults;  
       if (h == null)  
         return;  
       h(this, new FinalResultsEventArgs(geneValues, r, f, fitness));  
     }  
     public bool IsRunning { get { return _isRunning; } set { _isRunning = value; OnPropertyChanged(); } }  
     public int PopulationSize { get; set; }  
     public int MaxGenerations {   
       get { return _maxGenerations; }   
       set { if (gaProvider != null) { gaProvider.MaxGenerations = value; } _maxGenerations = value; OnPropertyChanged(); }   
     }  
   }  

The NotifyingObject that both view model and model derive from is a useful class for implementing the INotifyPropertyChanged interface:

 public abstract class NotifyingObject : INotifyPropertyChanged  
   {  
     protected void OnPropertyChanged([CallerMemberName] string propertyName = "")  
     {  
       var eh = PropertyChanged;  
       if (eh != null)  
         eh(this, new PropertyChangedEventArgs(propertyName));  
     }  
     public event PropertyChangedEventHandler PropertyChanged;  
   }  

and the RelayUICoommand is an extension of the RelayCommand class which simply adds a Text property for the button caption

The app that I created allows the used to set the number of chromosomes in the population and the maximum number of generations to allow.  As the algorithm progresses, the values of R and F are plotted along with the fitness, all for the best solution of the current generation.  As a reminder the target values are R=0.95 and F=0.5, a fitness of 1 would be the ideal, and the out of the box SwapMutation and a single point Crossover operations are being employed.  Equally the fitness evaluation has not changed.

I have produced videos of the output (slowed down) using a population of just 4 chromosomes and 10000 chromosomes to compare the results.  Due to the very small population size of the first the algorithm actually evaluates to a worse solution than one found earlier in the evolution, but this highlights the plotting of the results.