I was a little bored this weekend and needed to add in some GA functionality to a side project. I felt like it would be best to create a simple executer to deal with the iterative behavior of a genetic algorithm. The executer take in funcs provided by the consumer and executes based on a simple iterative model.
I've included a zip of the solution with an example of usage within the accompanying test project.
Below is what I came up with. Cheers!
8 #region Dependencies
9
10 using System;
11 using System.Collections.Generic;
12 using System.Diagnostics;
13 using System.Linq;
14
15 #endregion
16
17 namespace GA
18 {
19 /// <summary>
20 /// GeneticAlgorithm runs a genetic algorithm based on an initial population, fitness func, crossover func,
21 /// optional mutation function, and tollerance
22 /// </summary>
23 /// <typeparam name="T">Type to perform the algorithm against</typeparam>
24 public class GeneticAlgorithm<T>
25 {
26 private readonly Func<IEnumerable<FitnessComposite<T>>, IEnumerable<T>> _crossoverFunction;
27 private readonly Func<IEnumerable<T>, IEnumerable<FitnessComposite<T>>> _fitnessFunction;
28 private readonly Func<IEnumerable<T>, IEnumerable<T>> _mutationFunction;
29 private readonly double _tollerance;
30 private IEnumerable<T> _population;
31
32 /// <summary>
33 ///
34 /// </summary>
35 /// <param name="population">initial population</param>
36 /// <param name="fitnessFunction">function for calculating fitness</param>
37 /// <param name="crossoverFunction">breeding fuction</param>
38 /// <param name="mutationFunction">mutation function (optional, use null if not needed)</param>
39 /// <param name="tollerance">fitness tollernance</param>
40 public GeneticAlgorithm(IEnumerable<T> population,
41 Func<IEnumerable<T>, IEnumerable<FitnessComposite<T>>> fitnessFunction,
42 Func<IEnumerable<FitnessComposite<T>>, IEnumerable<T>> crossoverFunction,
43 Func<IEnumerable<T>, IEnumerable<T>> mutationFunction,
44 double tollerance)
45 {
46 _population = population;
47 _fitnessFunction = fitnessFunction;
48 _crossoverFunction = crossoverFunction;
49 _mutationFunction = mutationFunction;
50 _tollerance = tollerance;
51 }
52
53 /// <summary>
54 /// Max number of results to return
55 /// </summary>
56 public int? MaxResults { get; set; }
57
58 /// <summary>
59 /// Max time the algorithm can run
60 /// </summary>
61 public TimeSpan? TimeOut { get; set; }
62
63 /// <summary>
64 /// Result of the algorithm
65 /// </summary>
66 public IEnumerable<FitnessComposite<T>> Results { get; private set; }
67
68 /// <summary>
69 /// Number of generations
70 /// </summary>
71 public int Generations { get; private set; }
72
73 /// <summary>
74 /// Has the algorithm reach the finish criteria (either time has expired, or the tollerance has been reached)
75 /// </summary>
76 public bool IsDone { get; private set; }
77
78 /// <summary>
79 /// The evolving population
80 /// </summary>
81 public IEnumerable<T> Population
82 {
83 get { return _population; }
84 }
85
86 /// <summary>
87 /// Run the algorithm until complete and perform the doneAction at completion
88 /// </summary>
89 /// <param name="doneAction">action to be performed when the algorithm time has expired or tollerance has been reached</param>
90 public void Run(Action<IEnumerable<FitnessComposite<T>>> doneAction)
91 {
92 var executer = new Executer(_population)
93 {
94 BreedingFunc = GetBreedingFunc(),
95 FitnessFunc = _fitnessFunction,
96 };
97
98 if (TimeOut.HasValue)
99 {
100 var timer = new Stopwatch();
101 timer.Start();
102 executer.FinishCriteria = fitnessItems => IsFitnessReached(fitnessItems) || timer.Elapsed > TimeOut;
103 InternalRun(executer, doneAction);
104 timer.Stop();
105 }
106 else
107 {
108 executer.FinishCriteria = IsFitnessReached;
109 InternalRun(executer, doneAction);
110 }
111 }
112
113 private void InternalRun(Executer executer, Action<IEnumerable<FitnessComposite<T>>> doneAction)
114 {
115 while (executer.Run())
116 {
117 _population = executer.Population;
118 Generations++;
119 }
120
121 IsDone = executer.IsDone;
122 Results = executer.Results.Where(FitnessIsLessThanOrEqualToTollerance);
123 if (MaxResults.HasValue && Results.Count() > MaxResults.Value)
124 Results = Results.Take(MaxResults.Value);
125
126 doneAction(Results);
127 }
128
129 private Func<IEnumerable<FitnessComposite<T>>, IEnumerable<T>> GetBreedingFunc()
130 {
131 return _mutationFunction != null
132 ? i => _mutationFunction(_crossoverFunction(i))
133 : _crossoverFunction;
134 }
135
136 private bool IsFitnessReached(IEnumerable<FitnessComposite<T>> fitnessComposites)
137 {
138 return FitnessIsLessThanOrEqualToTollerance(GetBestFitness(fitnessComposites));
139 }
140
141 private FitnessComposite<T> GetBestFitness(IEnumerable<FitnessComposite<T>> fitnessComposites)
142 {
143 return fitnessComposites.OrderBy(i => i.Fitness).First();
144 }
145
146 private bool FitnessIsLessThanOrEqualToTollerance(FitnessComposite<T> ratedObject)
147 {
148 return ratedObject.Fitness <= _tollerance;
149 }
150
151 #region Nested type: Executer
152
153 private class Executer
154 {
155 private IEnumerable<T> _internalPopulation;
156
157 public Executer(IEnumerable<T> initialPopulation)
158 {
159 _internalPopulation = initialPopulation;
160 }
161
162 public bool IsDone { get; private set; }
163 public Func<IEnumerable<FitnessComposite<T>>, bool> FinishCriteria { get; set; }
164 public Func<IEnumerable<T>, IEnumerable<FitnessComposite<T>>> FitnessFunc { get; set; }
165 public Func<IEnumerable<FitnessComposite<T>>, IEnumerable<T>> BreedingFunc { get; set; }
166 public IEnumerable<T> Population { get; private set; }
167 public IEnumerable<FitnessComposite<T>> Results { get; private set; }
168
169 public bool Run()
170 {
171 var fitnessComposites = FitnessFunc(_internalPopulation);
172 IsDone = FinishCriteria(fitnessComposites);
173 if (!IsDone)
174 _internalPopulation = BreedingFunc(fitnessComposites);
175 else
176 Results = fitnessComposites;
177 Population = _internalPopulation;
178 return !IsDone;
179 }
180 }
181
182 #endregion
183 }
184 }