Sorting a Python List of Objects for Evolutionary Algorithms

When I implement an Evolutionary Algorithm using the Python language, I’m faced with the question of how to store possible solutions (typically vectors of floating point values) and their associated errors (typically a single floating point value). There are many design possibilities, each with pros and cons.

One design choice is to use a Python list or NumPy array of objects. For example, a class that defines a possible solution and its associated error could be:

class Solution:
  def __init__(self, soln, err):
    self.soln = soln
    self.error = err

  def show(self):
    print(self.soln, end="")
    print(" | ", end="")
    print("%0.4f" % self.error)

Then, a list of solution-objects could be created like so:

solns = []  # list of objects
solns.append( Solution(np.array([4,3,0,3],
  dtype=np.int64), 10.0 ))
solns.append( Solution(np.array([1,3,1,2],
  dtype=np.int64), 7.0 ))
solns.append( Solution(np.array([0,1,0,3],
  dtype=np.int64), 4.0 ))
solns.append( Solution(np.array([4,3,2,1],
  dtype=np.int64), 10.0 ))
solns.append( Solution(np.array([2,2,2,0],
  dtype=np.int64), 6.0 ))

The first entry has a possible solution of [4,3,0,3] and associated error of 10.0. In a non-demo scenario, the associated error would be computed by some program-defined error function. For simplicity, I made the error for each potential solution the sum of the values in the solution.

A pro of using object-based storage for Evolutionary Algorithms is that the data is very easy to sort by error:

solns.sort(key=lambda x:x.error)  # sorts in place

Other possible designs for Evolutionary Algorithms include 1.) using parallel arrays where one parallel array holds possible solution information (typically a vector) to some problem, and the other parallel array holds the error value associated with each possible solution, 2.) using a Python Tuple with solution and error fields, 3.) a Python List or NumPy Array where each item is a list or array with a possible solution and the associated error.

Even though there are technical pros and cons for each design choice for evolutionary algorithms, just as important to me are the subjective pros and cons. It’s often difficult to articulate subjective pros and cons but recognizing them is a characteristic of experienced engineers, as opposed to engineers who are relatively inexperienced. Inexperienced engineers typically are happy just to get a program up and running.

---

I wrote this blog post while sitting in the London Heathrow Airport, waiting to board a plane to fly back home (to the U.S.) Some of my favorite British authors include Charles Dickens, Ian Fleming, Agatha Christie, Sir Arthur Conan Doyle, and J.K. Rowling. Here are three book cover designs for the first Harry Potter book, “Harry Potter and the Sorcerer’s Stone” (“Harry Potter and the Philosopher’s Stone” in the U.K.) Book cover design is very subjective and most people seem to prefer the version of the cover design that they read.

---

Demo program code:

# object_sort_demo.py

import numpy as  np

# ------------------------------------

class Solution:
  def __init__(self, soln, err):
    self.soln = soln
    self.error = err

  def show(self):
    print(self.soln, end="")
    print(" | ", end="")
    print("%0.4f" % self.error)

# ------------------------------------

solns = []  # list of objects
solns.append( Solution(np.array([4,3,0,3],
  dtype=np.int64), 10.0 ))
solns.append( Solution(np.array([1,3,1,2],
  dtype=np.int64), 7.0 ))
solns.append( Solution(np.array([0,1,0,3],
  dtype=np.int64), 4.0 ))
solns.append( Solution(np.array([4,3,2,1],
  dtype=np.int64), 10.0 ))
solns.append( Solution(np.array([2,2,2,0],
  dtype=np.int64), 6.0 ))

print("\nsolns: ")
for i in range(len(solns)):
  solns[i].show()

solns.sort(key=lambda x:x.error)  # sorts in place

print("\nsorted solns: ")
for i in range(len(solns)):
  solns[i].show()

print("\nEnd demo ")