I have always found the connection between Genetic Algorithms and Biological Evolution very interesting. In many ways, Genetic Algorithms like Borg, emulate Biological Evolution. They start with a random population of potential solutions, the best fit of these solutions are selected to produce the future generation. During the production of offspring, crossover and mutation occur, which leads to more variation in the future generation. Strong (Non-dominated) offspring join the larger population and replace some of the previous weaker solutions (which are now dominated), and the process is repeated until some final condition is met.
In this post, I will briefly discuss Borg’s operators, and then dive deeper into Simplex Crossover (SPX) by Tsutsui et Al. (1999). This is the first of a series of posts in which I will discuss the Borg operators.
General Overview of Borg Operators
Borg uses the six operators shown in the figure 1 below to achieve variation in its solutions. In the figure, the larger dots represent the parent solutions, while the smaller dots represent the offspring solutions (Hadka & Reed, 2013).
The question is how does Borg know which operators are best suited for a new problem? Borg auto-adaptively selects operators to based on their performance to aid the search. Based on section 3.4 in Hadka and Reed, 2013: In the first iteration in Borg assigns an equal probability for using each operator. For K operators, this probability is 1/K. With each iteration, these probabilities are updated, so that the operators that produced more solutions in the epsilon box archive, are assigned higher probabilities, while those with less solutions in the epsilon box dominance archive are assigned a lower probability. Hadka and Reed(2013) use the following weighted average equation to obtain this behavior:
Where:
- K is the number of operators used
- Qi ∈ {Q1,…, Qk} is the probability that an operator is used to produce offspring in the next generation. and is initialized at 1/K
- Ci ∈ {C1,…, Ck} is the number of solutions in the epsilon box dominance archive produced by each operator i.
- Sigma is a positive number that prevents any of the operators from reaching a probability of zero.
Figure 1 (Hadka & Reed, 2013)
Notice in the bottom three operators in Figure 1 show some similarity: the parents form a simplex (which is a triangle in 2 dimensions). However, the way the offspring are distributed around the parents is different. In Parent Centric Crossover, the offspring form around the parent solutions, in Unimodal Normal Distribution Crossover, the offspring are normally distributed around the center of mass of the three parents, and in Simplex Crossover, the solutions are uniformly distributed inside a simplex that is larger than the simplex created by the three parents (Deb et Al., 2002).
Simplex Crossover (SPX)
Discussion based on Tsutsui et Al., 1999
Simplex Crossover (SPX) is a recombination operator that can use more than two parent solutions to generate offspring. The method involves expanding the simplex formed by the parent solutions by a factor of epsilon, and then sampling offspring from the resulting expanded simplex. The expansion of the simplex is centered around the center of mass of the parent solution vectors, and therefore independent of the coordinate system used. The number of parents must be at least 2 and less than or equal to the number of parameters plus one. That is:
Where:
- m: is the number of parents
- n: is the number of parameters
The SPX is denoted as SPX-n-m-ε.
Tsutsui et Al., 1999 states that for low dimensional functions, SPX works best with 3 parent solution vectors, and for high dimensional functions SPX works best with 4 parent solution vectors.
The 3 Parent, 2 Parameter Case
It is easiest to see this in the 2-dimensional three parent, 2 parameter case, i.e. SPX-2-3-ε. This can be done in four steps, referring to figure 2:
Figure 2 (Tsutsui et Al., 1999)
- Let X1, X2, and X3 be the three parent solution vectors. Each of these vectors has two parameters (it’s x and y coordinates). Calculate the center of mass, O, of the parents by computing the average of their two parameters:
- Expand the simplex by epsilon at every vertex:
- Produce offspring by using a uniform distribution to sample inside new expanded simplex defined in step 3.
You can see this in Python using the code below:
import numpy as np
import random
def SPX_2D(X1, X2, X3, epsilon, n_offspring=1, m=2):
# m is the number of parameters in each parent vector
# X1, X2, X3 are the parent vectors as np.arrays, each with m parameters (elements) i.e. len(Xi)=m
# epsilon is a value greated that zero by which the simplex is expanded
# n_offspring is the number of offspring you would like to produce
# Step 0: apply checks and inform the user if the input is wrong
if m<2:
print("error: at least two parameters needed for 2D SPX")
elif len(X1)!= len(X2) | len(X1)!=len(X3) | len(X1)!=len(X2):
print("error: the number of parameters in the parent vectors don't match")
elif len(X1)!=m:
print("error: the number of parameters in the parent vectors is not equal to m")
# if the checks pass, the function can proceed
else:
# Step 1: find the center of mass (CoM) of the three parents
CoM = 1/3 * (X1 + X2 + X3)
# Step 2: Define the vertices (Vi) of the simplex by expanding the simplex in the direction of Xi-CoM by (1+epsilon)
# note that the equation here is slightly different from the one in the paper, since the one in the paper produces the vector
# that translates the center of mass to the new vertices, and so the vectors need to be added to the center of mass coordinates
# to produce the new vertices.
V1=CoM+(X1-CoM)*(1+epsilon)
V2=CoM+(X2-CoM)*(1+epsilon)
V3=CoM+(X3-CoM)*(1+epsilon)
# Step 3: Produce offspring by sampling n_offspring points from the new simplex defined in step 3 using a uniform distribution
offspring = [point_on_triangle(V1, V2, V3) for _ in range(n_offspring)]
return offspring, V1, V2, V3, CoM
#########################################################################################################################
# Point_on_triangle function
# source: https://stackoverflow.com/questions/47410054/generate-random-locations-within-a-triangular-domain
# Solution by Mark Dickinson (Nov 21, 2017)
# Comments added by Sara
def point_on_triangle(pt1, pt2, pt3):
# pt1, pt2, pt3 are the vertices of a triangle
# find two random numbers s and t, note that random produces a float between 0 and 1 using a uniform distribution
s, t = sorted([random.random(), random.random()])
# use s & t to calculate a weighted average of each coordinate. This will produce the offspring vector
return (s * pt1[0] + (t-s)*pt2[0] + (1-t)*pt3[0],
s * pt1[1] + (t-s)*pt2[1] + (1-t)*pt3[1])
#########################################################################################################################
# Let's try an example
X1=np.array([-2,2])
X2=np.array([4,2])
X3=np.array([1,6])
epsilon=0.3
m=2
n_offspring=1000
offspring, V1, V2, V3, CoM = SPX_2D(X1, X2, X3, epsilon, n_offspring, m)
# Finally, you can plot the parents and offspring to produce Figure 3
import matplotlib.pyplot as plt
# Plot the parents
x1, y1 = zip(X1, X2, X3)
plt.scatter(x1, y1, s=50, label='Parents')
# Plot the center of mass
x2, y2 = zip(CoM)
plt.scatter(x2, y2, s=150, label='Center of Mass')
# Plot the expanded simplex
x3, y3 = zip(V1, V2, V3)
plt.scatter(x3, y3, s=100, label='Simplex Vertices')
# Plot the offspring
x4, y4 = zip(*offspring)
plt.scatter(x4, y4, s=0.05, label='Offspring')
plt.legend()
plt.show()
Figure 3
General Case
The general case is denoted as SPX-n-m-ε, with n parameters and n parents.
Each parent solution vector is:
These vectors are in R^n.
Thinking in terms of Biology, this parent vector mimics a chromosome, with m parameters as its different traits.
The general case can be outlined in four steps:
1) Parent vectors are selected from the population pool
2) R^n is space is then divided as follows:
Divide R^n into h sets of R^m-1 spaces and one R^q space. I found this easier when I thought of it in the context of a chromosome, i.e. large parent vector of length n, being divided into smaller sub-vectors of length m-1, and a remainder vector or length q. See figure 4 below:
Figure 4
3) In each R^m-1 space, the m parent vectors are used to generate offspring using the expanded simplex as described in the 2-dimensional, 3 parent, 2 parameters case. Again, using the chromosome analogy, figure 5 shows how this can be depicted for m=3 parents and for example, n=9 parameters. R^9 is divided into four (h=integer(n/(m-1)=4) R^2 (m-1=2) spaces and one R^1 space (q=remainder(n/(m-1)=1).
Figure 5
4) The sets of offspring in R^m-1 produced in step 3 together with the vector in R^q (which remains unchanged), are then combined in their correct positions to form an offspring vector in R^n.
The code for the general SPX case can be found in David Hadka’s github.
References
- Deb, Kalyanmoy, Ashish Anand, and Dhiraj Joshi. “A computationally efficient evolutionary algorithm for real-parameter optimization.” Evolutionary computation 10.4 (2002): 371-395.
- Hadka, David, and Patrick Reed. “Borg: An auto-adaptive many-objective evolutionary computing framework.” Evolutionary computation 21.2 (2013): 231-259.
- Tsutsui, Shigeyoshi, Masayuki Yamamura, and Takahide Higuchi. “Multi-parent recombination with simplex crossover in real coded genetic algorithms.” Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation-Volume 1. Morgan Kaufmann Publishers Inc., 1999.
- Uniform distribution within a triangle code from: https://stackoverflow.com/questions/47410054/generate-random-locations-within-a-triangular-domain
- General SPX-n-m-ε code: https://github.com/MOEAFramework/MOEAFramework/blob/master/src/org/moeaframework/core/operator/real/SPX.java
Water Programming: A Collaborative Research Blog 