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 ");
      Console.ReadLine();
    } // 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);
        //this.Show(); Console.ReadLine();

      }
    } // 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);
        //this.Show(); Console.ReadLine();
      }  // for
    } // Solve

  } // Solver2 class