Sorting a Python List of Tuples 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) and their associated errors (typically a single float32 value). There are many, many, many design possibilities that have pros and cons — if one technique was best I wouldn’t be writing this blog post.

One design choice is to use a Python List of Array of Tuples where the first tuple item is a possible solution and the second tuple item is the associated error. For example:

solns = []  # list of tuples (array,float)
solns.append( (np.array([4,3,0,3], dtype=np.int64), 10.0) ) 
solns.append( (np.array([1,3,1,2], dtype=np.int64), 7.0) )
solns.append( (np.array([0,1,0,3], dtype=np.int64), 4.0) )
solns.append( (np.array([4,3,2,1], dtype=np.int64), 10.0) )
solns.append( (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. Note that a con of using a Tuple is that items are immutable which can create issues depending on the design of the Evolutionary Algorithm using the tuples.

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

solns.sort(key=lambda tup:tup[1])  # 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 class 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.

The moral of this blog post is that for experienced machine learning engineers, picking the design of a system is usually more difficult than the corresponding implementation.

---

I wrote this blog post while I was sitting in a hotel room in London, waiting for friends and family to run in the 2023 London marathon. London is a very interesting city in many different ways. Many British sports car designs of the 1960s were very beautiful, but implementation, especially electrical and hydraulic systems, was not very good.

Left: A 1967 model Austin-Healey 3000. To my eye, one of the most beautiful classic sports car designs. Center: A Triumph TR6 from about 1969. I played in a band in the 1980s and our lead guitarist, Wayne Ogin, had a beautiful British racing green colored TR6 but it was quite unreliable and was often in the repair shop. Right: A 1963 Aston-Martin DB5 — the famous James Bond car — the epitome of cool design.

---

Demo program code:

# tuple_sort_demo.py

import numpy as  np

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

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

solns.sort(key=lambda tup:tup[1])  # sorts in place

# solns.sort(key=lambda tup:tup[1], reverse=True)
# solns = sorted(soln, key=lambda tup:tup[1])

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

print("\nEnd demo ")