## Evolutionary Optimization Using C#

Evolutionary optimization is a technique that’s loosely based on biological crossover (combining two parent solutions to produce a child) and mutation. I recently implemented an evolutionary optimization program in Python, for use in neural network hyperparameter tuning. I decided to refactor the Python version to C# as an exercise. See jamesmccaffrey.wordpress.com/2022/11/03/hyperparameter-tuning-using-evolutionary-optimization/.

I set up a problem where a possible solution is an array with 10 cells where each cell can be one of 8 values, 0 through 7. For example, a possible solution might be [7 3 0 2 2 5 6 0 1 4]. I created a dummy error function where the error is the sum of the values in the solution. So the error for the solution above is 7 + 3 + . . + 4 = 30. Therefore, the optimal solution is [0 0 0 0 0 0 0 0 0 0] with error = 0.

The crossover operation takes two parent solutions and creates a child solution by combining half of one parent with half of the second parent. The mutation operation picks a random index and randomly bumps the value there up 1 or down 1.

I defined a Solver class that maintains a population of solutions and does all the work. In pseudo-code:

```create a population of random solutions
loop max_generations times
pick two parent solutions
make child solution (crossover)
mutate child
evaluate child
replace a weak solution with child
end-loop
return best solution found
```

Inside the Solver class, I defined a nested Individual class that holds a solution array and its associated error. I derived the Individual class from the IComparable interface so that I could sort the population of solutions by error, from small to large.

My demo program set up a population of 6 solutions. After 100 generations, the best solution found was [0 4 1 0 0 0 4 2 0 0] with an error of 11. Not too bad because there are a total of 8 * 8 * . . * 8 = 8^10 = 1,073,741,824 possible permutations of solutions.

A fun experiment.

Horse race gambling games have evolved a lot. Left: “Ray’s Track” by Bally from about 1938. You put nickels in the coin slot for one of 9 horses. If your selected horse wins, the payout goes to a hidden compartment. Right: “Fortune Cup” by Konami is quite sophisticated. When I go to Las Vegas for conferences, I like to watch people playing Fortune Cup at the MGM Grand or the Bellagio. I’ve played a couple of times and it’s a lot of fun.

Demo code. Replace “lt” with less-than operator, “((” with less-than operator, “))” with greater-than operator (my blog editor chokes on symbols).

```using System;

namespace EvolutionaryOptimization
{
internal class Program
{
static void Main(string[] args)
{
Console.WriteLine("\nBegin evolutionary demo ");
Console.WriteLine("Setting 10 hyperparams, 8 values ");
Console.WriteLine("Optimal result is all 0s ");

int numHP = 10;
int numHPV = 8;
int numPop = 6;

Solver solver = new Solver(numHP, numHPV, numPop, 999);
Console.WriteLine("\nInitial population: ");
solver.Show();

Console.WriteLine("\nBegin search ");
solver.Solve(100);
Console.WriteLine("\nDone ");

Console.WriteLine("\nFinal population: ");
solver.Show();

Console.WriteLine("\nEnd demo ");
} // Main

} // Program

public class Solver
{
private static Random rnd;
public int numHP;  // number of hyperparameters, like 10
public int numHPV; // number hyperparam values, like 8
public int numPop;
public Individual[] pop;
public int[] bestSoln;
public double bestErr;

public Solver(int numHP, int numHPV, int numPop, int seed)
{
rnd = new Random(seed);
this.numHP = numHP;
this.numHPV = numHPV;
this.numPop = numPop;
this.pop = new Individual[numPop];
for (int i = 0; i "lt" numPop; ++i)
{
this.pop[i] = new Individual(numHP, numHPV);
this.pop[i].err = ComputeError(this.pop[i].soln);
}

Array.Sort(this.pop);  // small err to high

this.bestSoln = new int[numHP];
for (int i = 0; i "lt" this.numHP; ++i)
this.bestSoln[i] = this.pop[0].soln[i];
this.bestErr = this.pop[0].err;
}

public void Show()
{
for (int i = 0; i "lt" this.numPop; ++i)
this.pop[i].Display();  // Individual.Display()
Console.WriteLine("-----");
for (int i = 0; i "lt" this.numHP; ++i)
Console.Write(this.bestSoln[i] + " ");
Console.WriteLine(" | " + this.bestErr.ToString("F4"));
}

public double ComputeError(int[] soln)
{
double err = 0.0;
for (int i = 0; i "lt" soln.Length; ++i)
err += soln[i];
return err;
}

public int[] PickParents()
{
int first = rnd.Next(0, this.numPop / 2);
int second = rnd.Next(this.numPop / 2, this.numPop);
while (second == first)   // not needed
second = rnd.Next(this.numPop / 2, this.numPop);
int flip = rnd.Next(0, 2);  // 0 or 1
if (flip == 0)
return new int[] { first, second };
else
return new int[] { second, first };

}

public int[] CrossOver(int i, int j)
{
int[] child = new int[this.numHP];
for (int k = 0; k "lt" this.numHP / 2; ++k)
child[k] = this.pop[i].soln[k];
for (int k = this.numHP / 2; k "lt" this.numHP; ++k)
child[k] = this.pop[j].soln[k];
return child;
}

public void Mutate(int[] soln)
{
int idx = rnd.Next(0, soln.Length);
int flip = rnd.Next(0, 2);  // 0 or 1
if (flip == 0)
{
soln[idx] -= 1;
if (soln[idx] == -1)  // too small
soln[idx] = this.numHPV - 1;
}
else  // flip == 1
{
soln[idx] += 1;
if (soln[idx] == this.numHPV)  // too big
soln[idx] = 0;
}
}

public void Solve(int maxGen)
{
for (int gen = 0; gen "lt" maxGen; ++gen)
{
// 1. make a child
int[] parents = this.PickParents();
int[] child = this.CrossOver(parents[0], parents[1]);

// 2. mutate and evaluate child
this.Mutate(child);
double childErr = this.ComputeError(child);

// 3. is child new best solution?
if (childErr "lt" this.bestErr)
{
Console.WriteLine("New best soln found at generation " +
gen);
for (int i = 0; i "lt" child.Length; ++i)
this.bestSoln[i] = child[i];
this.bestErr = childErr;
}

// 4. replace a weak soln with child
int idx = rnd.Next(this.numPop / 2, this.numPop);
for (int k = 0; k "lt" this.numHP; ++k)
this.pop[idx].soln[k] = child[k];
this.pop[idx].err = childErr;

// 5. sort
Array.Sort(this.pop);

}
} // Solve

// -----------------------------------------------

// nested class definition

public class Individual : IComparable((Individual))
{
public int[] soln;
public double err;
// knows Solver rnd

public Individual(int numHP, int numHPV)
{
this.soln = new int[numHP];
for (int i = 0; i "lt" this.soln.Length; ++i)
this.soln[i] = Solver.rnd.Next(0, numHPV);
this.err = 0.0;
}

public int CompareTo(Individual ?other)
{
if (other == null)
throw new Exception("null in CompareTo() ");
if (this.err == other.err)
return 0;
else if (this.err "lt" other.err)
return -1;
else
return 1;
}

public void Display()
{
for (int i = 0; i "lt" this.soln.Length; ++i)
Console.Write(this.soln[i] + " ");
Console.WriteLine(" | " + this.err.ToString("F4"));
}

} // Individual

// -----------------------------------------------

} // Solver

} // ns
```

Here’s a version that uses parallel arrays instead of a nested Individual class.

```  public class Solver2
{
// parallel arrays version
public Random rnd;
public int numHP;  // number of hyperparameters, like 10
public int numHPV; // number hyperparam values, like 8
public int numPop;

public int[][] solns;  // defines the population
public double[] errs;

public int[] bestSoln;
public double bestErr;

public Solver2(int numHP, int numHPV, int numPop, int seed)
{
this.rnd = new Random(seed);
this.numHP = numHP;
this.numHPV = numHPV;
this.numPop = numPop;

this.solns = new int[numPop][];  // allocate
for (int i = 0; i "lt" numPop; ++i)
this.solns[i] = new int[numHP];
this.errs = new double[numPop];

for (int i = 0; i "lt" numPop; ++i)  // each soln
{
for (int j = 0; j "lt" numHP; ++j)  // each hyperpram
{
this.solns[i][j] = this.rnd.Next(0, numHPV);
}
this.errs[i] = ComputeError(this.solns[i]);
}

Array.Sort(this.errs, this.solns);  // sort by err

this.bestSoln = new int[numHP];
for (int i = 0; i "lt" this.numHP; ++i)
this.bestSoln[i] = this.solns[0][i];
this.bestErr = this.errs[0];
} // ctor

public void Show()
{
for (int i = 0; i "lt" this.numPop; ++i)
{
for (int j = 0; j "lt" this.numHP; ++j)
{
Console.Write(this.solns[i][j] + " ");
}
Console.WriteLine(" | " + this.errs[i].ToString("F4"));
}

Console.WriteLine("-----");
for (int i = 0; i "lt" this.numHP; ++i)
Console.Write(this.bestSoln[i] + " ");
Console.WriteLine(" | " + this.bestErr.ToString("F4"));
} // Show()

public double ComputeError(int[] soln)
{
double err = 0.0;
for (int i = 0; i "lt" soln.Length; ++i)
err += soln[i];
return err;
}

public int[] PickParents()
{
int first = rnd.Next(0, this.numPop / 2);
int second = rnd.Next(this.numPop / 2, this.numPop);
while (second == first)
second = rnd.Next(this.numPop / 2, this.numPop);
int flip = rnd.Next(0, 2);  // 0 or 1
if (flip == 0)
return new int[] { first, second };
else
return new int[] { second, first };
}

public int[] CrossOver(int i, int j)
{
int[] child = new int[this.numHP];
int[] parent1 = this.solns[i];
int[] parent2 = this.solns[j];

for (int k = 0; k "lt" this.numHP / 2; ++k)
child[k] = parent1[k];
for (int k = this.numHP / 2; k "lt" this.numHP; ++k)
child[k] = parent2[k];
return child;
}

public void Mutate(int[] soln)
{
int idx = rnd.Next(0, soln.Length);
int flip = rnd.Next(0, 2);  // 0 or 1
if (flip == 0)
{
soln[idx] -= 1;
if (soln[idx] == -1)  // too small
soln[idx] = this.numHPV - 1;
}
else  // flip == 1
{
soln[idx] += 1;
if (soln[idx] == this.numHPV)  // too big
soln[idx] = 0;
}
}

public void Solve(int maxGen)
{
for (int gen = 0; gen "lt" maxGen; ++gen)
{
// 1. make a child
int[] parents = this.PickParents();  // two indices
int[] child = this.CrossOver(parents[0], parents[1]);

// 2. mutate and evaluate child
this.Mutate(child);
double childErr = this.ComputeError(child);

// 3. is child new best solution?
if (childErr "lt" this.bestErr)
{
Console.WriteLine("New best soln found at generation " +
gen);
for (int i = 0; i "lt" child.Length; ++i)
this.bestSoln[i] = child[i];
this.bestErr = childErr;
}

// 4. replace a weak soln with child
int idx = rnd.Next(this.numPop / 2, this.numPop);
for (int j = 0; j "lt" this.numHP; ++j)
this.solns[idx][j] = child[j];
this.errs[idx] = childErr;

// 5. sort
Array.Sort(this.errs, this.solns);
//Array.Sort(this.pop);
}  // for
} // Solve

} // Solver2 class
```
This entry was posted in Machine Learning. Bookmark the permalink.

### 1 Response to Evolutionary Optimization Using C#

1. Thorsten Kleppe says:

Optimal solution found with population = 3, seed = 1337 + modified PickParents() method.

public int[] PickParents()
{
int half = this.numPop / 2;
int middle = rnd.Next(half / 2, half + half / 2);
int start = rnd.Next(0, middle);
int first = rnd.Next(start, middle);
int end = rnd.Next(middle, this.numPop);
int second = rnd.Next(middle, end);
int flip = rnd.Next(0, 2); // 0 or 1
if (flip == 0)
return new int[] { first, second };
else
return new int[] { second, first };
}

Will I be hired now? ^^