Make me look good. Click on the cell below and press Ctrl+Enter.
from IPython.core.display import HTML
HTML(open('css/custom.css', 'r').read())
A genetic algorithm (GA) is a type of algorithm for optimization problems, inspired by evolutionary biology. A GA tries to mimic the evolutionary process:
How does this work for an optimization problem? We want to find a solution that minimizes a certain objective function or fitness function. Each parent will correspond to a solution to our optimization problem. The value of the fitness function for the parent is the parent's score.
We start a generation by pairing up the parents. Each pair of parents will mate to produce a new solution to our optimization problem, which we call a child. We "grow" the child into an adult by repeatedly modifying the child solution slightly and keeping the change if the child's score gets better.
After a set number of such local modifications, we compare the child to its parents and replace one parent with the child if the child's score is better; otherwise we discard the child. A generation ends when each child has entered the parent pool or been discarded. We repeat the process for a set number of generations.
This process involves many choices: we choose how the parent solutions combine to make a child input, we choose the fitness function, we choose the number of local modifications to the child, the types of local modifications allowed, the number of generations, and the number of parents. This approach is very flexible and not particularly tied to biology: one can incorporate or ignore the sex of parents, you could require three (or just one) parent to produce a child, etc.
Note that in general, genetic algorithms are heuristics: they produce solutions that are only approximately optimal, usually without any guarantee of how close they are to optimal. This seems unsatsifying, but for very hard optimization problems, this might be the best we can do.
We're going to create a genetic algorithm that finds the shortest path between two particular vertices in a graph. We've chosen this problem because (1) it is relatively easy to understand and (2) there exist fast exact algorithms so we can assess the quality of the solutions produced by our genetic algorithm.
We start with a graph $G$ with $n$ vertices or nodes. We assume that each vertex is connected to all the other vertices by an edge. This is known as a complete graph.
The distances along each edge $(i,j)$ are stored in an $n \times n$ matrix $d$. We assume that $d_{ii} = 0$ for all $i$: the distance from a vertex to itself is zero. In addition, we assume that $d_{ij} = d_{ji} > 0$ if $i\neq j$: the distance for an edge is the same in both directions, and all distances between distinct nodes are positive.
We fix a source node $s$ and a terminal node $t$. An $s$-$t$ path is a sequence of vertices starting with the source node $s$ and ending at the terminal node $t$. The total distance of an $s$-$t$ path is the sum of the distances along each edge in the path. We want to find the $s$-$t$ path with the lowest total distance.
How can we set up a genetic algorithm for the shortest path problem?
We define the fitness function to take as input an $s$-$t$ path, and return the total distance of the path. Each parent (and child) corresponds to an $s$-$t$ path and its score. We'll start with a population of, say, 10 parents, each representing randomly generated $s$-$t$ paths.
In each generation, we'll form 5 pairs of parents, using every parent once. Given two parents, $P_0$ and $P_1$, we create a child in the following way.
Note. We will often speak about parents and children as paths. This isn't strictly correct, because a parent or a child is both a path AND a score. We kindly ask for the reader's tolerance. 😊
Case A. If $P_0$ and $P_1$ do not have a common vertex other than $s$ and $t$, then we randomly select a vertex $a$ in $P_0$ and a vertex $b$ in $P_1$. We form the child's path by joining the part of $P_0$ from $s$ to $a$, the edge $(a,b)$, and the part of $P_1$ from $b$ to $t$.
Case B. If $P_0$ and $P_1$ have a common vertex other than $s$ and $t$, then let $x$ be the first vertex in $P_0$ that is in $P_1$. We form the child's path by doing one of the following:
We choose the path whose first part (up until $x$) has the smaller score.
In both cases the new child's path may have loops. For instance if $s=0$ and $t=29$ we might produce a new child's path $0-5-6-9-5-9-19-29$. We remove the loop $5-6-9-5$ starting earliest in the path to get $0-5-9-19-29$. Note that this destroyed a second (entwined) loop $9-5-9$. In general, loops could remain in the resulting path. We continue to remove the earliest loops until none remain, producing our child's path.
For local modifications on a child, we pick two vertices $a$ and $b$ on the child's path, such that $a$ appears earlier than $b$. Then we consider three new candidate paths:
We replace the child's path with the candidate path whose score is lowest. This completes a single local modification of the child. We do a set number of such modifications, say, 100.
After each child grows up, they compete with their two parents. The two paths with the smallest scores remain in the mating pool and the path with the highest score is discarded. This completes a single generation.
We repeat this entire process (pairing parents, mating to produce a child, local improvement of the child, and a fight-to-the-death elimination match pitting two parents against their child — hey, evolution isn't pretty!) over multiple generations, say, 50 times. Then we select the parent with the lowest score and use their path as our solution to the shortest path problem.
Note that our algorithm involves randomization, so running it multiple times will likely produce different solutions. Our algorithm is also a heuristic: it need not produce the shortest path but rather produces the shortest path out of the few paths it considered.
Using the algorithm above, we consider $10+5*3*100*50$ (=75010) $s$-$t$ paths without loops. That is a lot of paths but if $n=30$ there are more than $8.28 \times 10^{29}$ $s$-$t$ paths, so we are only considering a small subset of all paths. It is remarkable that this method often produces the best answer.
We can check our answer using the shortest_path
method in NetworkX, which solves the shortest path problem exactly. Exact algorithms for the shortest path problem, like Dijkstra's algorithm and the Bellman-Ford algorithm, are often taught in SA405 — Advanced Mathematical Programming.
This lesson's classwork will walk you through implementing the genetic algorithm described above for the shortest path problem!
Before starting the classwork, run the code cell below to import NumPy.
import numpy as np
Problem 1.
Write a function make_distance_matrix
that
Hints.
for
loop to go over rows with index $i = 0, 1, \dots, n-1$ and columns with index $j = i + 1, \dots, n - 1$. This will go over only the upper triangular entries of the matrix. Set $d_{ji} = d_{ij}$ so you end up with a symmetric matrix.np.random.randint()
: np.random.randint(a, b)
generates a random integer between a
and b - 1
inclusive.def make_distance_matrix(n):
"""
Make distance matrix on complete graph with n nodes
"""
# Make n x n matrix, filled with 0s
d = np.zeros((n, n))
# Fill in upper diagonal etnries with randomly generated integers
# between 1 and 99 and make matrix symmetric (so d = d.transpose()).
for i in range(n):
for j in range(i + 1, n):
d[i, j] = np.random.randint(1,100)
d[j, i] = d[i, j]
return d
Problem 2. Run the code cell beow.
The code sets some parameters, and calls your make_distance_matrix
function from Problem 1 to create the matrix of distances between vertices in the graph.
# Number of vertices
n = 30
# Source node
s = 0
# Terminal node
t = n - 1
# Number of parents
# Should be even
num_parents = 10
# Number of generations
num_gens = 50
# Number of local improvements
num_loc_improvement = 100
# Generate distance matrix
d = make_distance_matrix(n)
# Print distance matrix to check our work
print(d)
[[ 0. 90. 98. 44. 36. 28. 79. 61. 61. 29. 98. 50. 94. 66. 19. 15. 81. 68. 55. 31. 65. 52. 16. 4. 27. 4. 29. 37. 16. 2.] [90. 0. 95. 26. 64. 10. 45. 65. 70. 57. 57. 93. 42. 18. 89. 22. 60. 61. 99. 91. 10. 58. 15. 84. 7. 66. 36. 60. 37. 40.] [98. 95. 0. 3. 19. 79. 68. 71. 35. 56. 54. 67. 16. 86. 8. 60. 91. 24. 20. 57. 91. 11. 48. 35. 32. 73. 3. 95. 61. 11.] [44. 26. 3. 0. 50. 5. 28. 18. 81. 11. 51. 26. 9. 19. 15. 58. 36. 90. 29. 40. 36. 9. 47. 5. 90. 65. 85. 26. 89. 94.] [36. 64. 19. 50. 0. 85. 34. 33. 39. 80. 53. 25. 93. 56. 25. 18. 52. 63. 92. 4. 2. 43. 37. 99. 10. 70. 80. 82. 46. 42.] [28. 10. 79. 5. 85. 0. 21. 13. 62. 76. 76. 24. 84. 27. 34. 79. 67. 95. 81. 52. 57. 76. 81. 97. 65. 35. 83. 30. 44. 6.] [79. 45. 68. 28. 34. 21. 0. 1. 5. 59. 16. 40. 99. 60. 94. 60. 70. 75. 18. 69. 74. 30. 22. 2. 99. 27. 16. 78. 2. 46.] [61. 65. 71. 18. 33. 13. 1. 0. 92. 48. 74. 87. 2. 3. 55. 55. 99. 73. 24. 70. 46. 40. 53. 61. 91. 2. 79. 63. 39. 46.] [61. 70. 35. 81. 39. 62. 5. 92. 0. 95. 59. 56. 47. 60. 90. 29. 13. 75. 52. 27. 79. 13. 38. 45. 12. 23. 31. 38. 13. 44.] [29. 57. 56. 11. 80. 76. 59. 48. 95. 0. 29. 40. 81. 82. 20. 67. 23. 65. 45. 86. 23. 79. 44. 14. 92. 10. 69. 7. 39. 31.] [98. 57. 54. 51. 53. 76. 16. 74. 59. 29. 0. 86. 61. 89. 83. 23. 77. 52. 31. 19. 44. 53. 62. 47. 44. 54. 29. 72. 13. 91.] [50. 93. 67. 26. 25. 24. 40. 87. 56. 40. 86. 0. 44. 9. 1. 28. 19. 17. 43. 30. 16. 59. 69. 93. 82. 43. 47. 33. 11. 11.] [94. 42. 16. 9. 93. 84. 99. 2. 47. 81. 61. 44. 0. 2. 9. 36. 62. 56. 56. 99. 69. 36. 1. 32. 70. 99. 9. 82. 11. 16.] [66. 18. 86. 19. 56. 27. 60. 3. 60. 82. 89. 9. 2. 0. 92. 34. 47. 51. 91. 79. 95. 21. 8. 38. 58. 92. 84. 97. 68. 41.] [19. 89. 8. 15. 25. 34. 94. 55. 90. 20. 83. 1. 9. 92. 0. 32. 21. 26. 99. 85. 1. 72. 73. 54. 47. 86. 64. 60. 99. 13.] [15. 22. 60. 58. 18. 79. 60. 55. 29. 67. 23. 28. 36. 34. 32. 0. 46. 74. 41. 70. 57. 11. 67. 95. 76. 7. 31. 4. 96. 29.] [81. 60. 91. 36. 52. 67. 70. 99. 13. 23. 77. 19. 62. 47. 21. 46. 0. 68. 60. 53. 76. 77. 28. 97. 80. 61. 33. 59. 40. 55.] [68. 61. 24. 90. 63. 95. 75. 73. 75. 65. 52. 17. 56. 51. 26. 74. 68. 0. 10. 99. 97. 48. 53. 98. 2. 94. 64. 48. 69. 34.] [55. 99. 20. 29. 92. 81. 18. 24. 52. 45. 31. 43. 56. 91. 99. 41. 60. 10. 0. 99. 67. 18. 46. 82. 45. 80. 20. 53. 14. 61.] [31. 91. 57. 40. 4. 52. 69. 70. 27. 86. 19. 30. 99. 79. 85. 70. 53. 99. 99. 0. 69. 43. 5. 67. 23. 17. 65. 32. 5. 92.] [65. 10. 91. 36. 2. 57. 74. 46. 79. 23. 44. 16. 69. 95. 1. 57. 76. 97. 67. 69. 0. 5. 98. 30. 74. 83. 37. 44. 25. 62.] [52. 58. 11. 9. 43. 76. 30. 40. 13. 79. 53. 59. 36. 21. 72. 11. 77. 48. 18. 43. 5. 0. 14. 24. 34. 87. 25. 36. 21. 57.] [16. 15. 48. 47. 37. 81. 22. 53. 38. 44. 62. 69. 1. 8. 73. 67. 28. 53. 46. 5. 98. 14. 0. 74. 15. 30. 54. 84. 16. 51.] [ 4. 84. 35. 5. 99. 97. 2. 61. 45. 14. 47. 93. 32. 38. 54. 95. 97. 98. 82. 67. 30. 24. 74. 0. 45. 74. 39. 14. 38. 4.] [27. 7. 32. 90. 10. 65. 99. 91. 12. 92. 44. 82. 70. 58. 47. 76. 80. 2. 45. 23. 74. 34. 15. 45. 0. 84. 63. 51. 42. 92.] [ 4. 66. 73. 65. 70. 35. 27. 2. 23. 10. 54. 43. 99. 92. 86. 7. 61. 94. 80. 17. 83. 87. 30. 74. 84. 0. 57. 38. 78. 74.] [29. 36. 3. 85. 80. 83. 16. 79. 31. 69. 29. 47. 9. 84. 64. 31. 33. 64. 20. 65. 37. 25. 54. 39. 63. 57. 0. 78. 67. 71.] [37. 60. 95. 26. 82. 30. 78. 63. 38. 7. 72. 33. 82. 97. 60. 4. 59. 48. 53. 32. 44. 36. 84. 14. 51. 38. 78. 0. 22. 52.] [16. 37. 61. 89. 46. 44. 2. 39. 13. 39. 13. 11. 11. 68. 99. 96. 40. 69. 14. 5. 25. 21. 16. 38. 42. 78. 67. 22. 0. 5.] [ 2. 40. 11. 94. 42. 6. 46. 46. 44. 31. 91. 11. 16. 41. 13. 29. 55. 34. 61. 92. 62. 57. 51. 4. 92. 74. 71. 52. 5. 0.]]
Problem 3.
Write a function compute_score
that computes the total distance along a path.
The inputs to this function should be
The path should be represented by a list of nodes, e.g. [0, 5, 8, 12, 29]
This function should return the distance from the source node to the terminal node.
# Write your code below
def compute_score(path, d):
"""
Compute the fitness score of a path, i.e., its total length
"""
# Initialize score to 0
score = 0
# Iterate through the path nodes
# Add the length of each edge to the score
for e in range(len(path) - 1):
score += d[path[e], path[e + 1]]
return score
Check your function by running the code in the cell below. If your function is correct, the code should output True
to the screen.
# Check your compute_score function by running the code in this cell
compute_score([0, 5, 8, 12, 29], d) == d[0, 5] + d[5, 8] + d[8, 12] + d[12, 29]
True
Problem 4.
Next, we will generate a list of parents. The code below defines a function generate_parents
. Read through the code to get a sense of what it does.
def generate_parents(num_parents, s, t, num_nodes, d):
"""
Make a list of parents.
Each parent consists of (1) a path from s to t, and (2) its score
"""
# Initialize list of parents
parents = []
for i in range(num_parents):
# Randomly generate a path p with the following steps
# 1. Create a list of all the nodes
nodes_except_s = list(range(num_nodes))
# 2. Remove the source node from this list
nodes_except_s.remove(s)
# 3. Randomly shuffle the nodes in this list
shuffled_nodes_except_s = list(np.random.permutation(nodes_except_s))
# 4. Where does the terminal vertex appear in the shuffled list?
t_index = shuffled_nodes_except_s.index(t)
# 5. Create a random path by starting at the source node s,
# continue with the nodes in the shuffled list, until we
# reach the terminal node t
# Note that the + operator concatenates lists
path = [s] + shuffled_nodes_except_s[:t_index + 1]
# Compute the score of this random path
score = compute_score(path, d)
# Append this newly generated parent to the list of parents
# Note that a parent is a dictionary
parents.append({'path': path, 'score': score})
return parents
In the next code cell, call the function generate_parents
, and then print out a list of parents to the screen.
# Write your code below
parents = generate_parents(num_parents, s, t, n, d)
print(parents)
[{'path': [0, 2, 20, 9, 18, 3, 21, 11, 22, 27, 5, 6, 23, 7, 29], 'score': 667.0}, {'path': [0, 5, 1, 4, 28, 23, 27, 9, 20, 3, 15, 22, 10, 11, 8, 25, 16, 14, 21, 29], 'score': 829.0}, {'path': [0, 16, 11, 8, 1, 21, 20, 22, 19, 26, 4, 28, 29], 'score': 588.0}, {'path': [0, 12, 9, 4, 16, 24, 19, 10, 1, 15, 13, 29], 'score': 583.0}, {'path': [0, 4, 11, 18, 2, 20, 16, 23, 25, 17, 12, 1, 14, 21, 28, 13, 22, 19, 29], 'score': 1009.0}, {'path': [0, 6, 10, 17, 14, 7, 22, 19, 16, 24, 13, 29], 'score': 518.0}, {'path': [0, 18, 8, 28, 27, 24, 6, 23, 17, 20, 2, 11, 1, 22, 29], 'score': 806.0}, {'path': [0, 9, 11, 7, 1, 10, 22, 20, 26, 6, 29], 'score': 537.0}, {'path': [0, 28, 5, 24, 25, 7, 19, 1, 10, 23, 6, 26, 3, 29], 'score': 673.0}, {'path': [0, 12, 28, 11, 20, 15, 6, 18, 22, 27, 29], 'score': 449.0}]
Problem 5. Now we'll pair the parents for mating.
pairs
consisting of num_parents / 2
inner lists. Each inner list should contain two parents.Hint. You might find the method np.random.permutation()
useful. We used it in the definition of generate_parents
in the previous problem. What does it do? Check the NumPy documentation if you're not sure.
# Create a shuffled list of indices
# One index per parent
random_index = np.random.permutation(list(range(num_parents)))
# Pair up parents according to the shuffled list of indices
pairs = []
for i in range(int(num_parents / 2)):
pairs.append([parents[random_index[2 * i]], parents[random_index[2 * i + 1]]])
# Check our work
print(pairs)
[[{'path': [0, 2, 20, 9, 18, 3, 21, 11, 22, 27, 5, 6, 23, 7, 29], 'score': 667.0}, {'path': [0, 12, 9, 4, 16, 24, 19, 10, 1, 15, 13, 29], 'score': 583.0}], [{'path': [0, 6, 10, 17, 14, 7, 22, 19, 16, 24, 13, 29], 'score': 518.0}, {'path': [0, 16, 11, 8, 1, 21, 20, 22, 19, 26, 4, 28, 29], 'score': 588.0}], [{'path': [0, 28, 5, 24, 25, 7, 19, 1, 10, 23, 6, 26, 3, 29], 'score': 673.0}, {'path': [0, 9, 11, 7, 1, 10, 22, 20, 26, 6, 29], 'score': 537.0}], [{'path': [0, 5, 1, 4, 28, 23, 27, 9, 20, 3, 15, 22, 10, 11, 8, 25, 16, 14, 21, 29], 'score': 829.0}, {'path': [0, 12, 28, 11, 20, 15, 6, 18, 22, 27, 29], 'score': 449.0}], [{'path': [0, 4, 11, 18, 2, 20, 16, 23, 25, 17, 12, 1, 14, 21, 28, 13, 22, 19, 29], 'score': 1009.0}, {'path': [0, 18, 8, 28, 27, 24, 6, 23, 17, 20, 2, 11, 1, 22, 29], 'score': 806.0}]]
Problem 6.
The code cell below defines the function remove_loops
, which removes any loops in a path. Read through the code to get a sense of what it does.
def remove_loops(p):
"""
Remove loops from a path
"""
# Keep doing this loop while there are
# no duplicates in the path (list of nodes) p.
# The while condition uses the *set* data structure, which is
# like a list, but requires that its items are unique.
# list(set(x)) returns a list with all duplicates of x removed.
while len(list(set(p))) != len(p):
for i in list(set(p)):
# Find the index of the first i
a = p.index(i)
# Find the index of the last i
# Remember that p[::-1] is the list p, but in reverse order
b = len(p) - 1 - p[::-1].index(i)
# If the indices of the first and last i are
# not the same, then we have a loop!
if a != b:
# Remove the vertices of the loop
p = p[0: a + 1] + p[b + 1:]
break
return p
Try it out:
remove_loops([0, 1, 2, 3, 5, 6, 3, 8, 5, 28, 21, 17, 29])
[0, 1, 2, 3, 8, 5, 28, 21, 17, 29]
You should get [0, 1, 2, 3, 8, 5, 28, 21, 17, 29]
as output.
Note that when we remove the loop starting at 3, the loop starting at 5 disappears! Removing the loop starting at 5 would kill the loop starting at 3 too. It isn't clear which is preferable. We just get a loopless path and call it a day.
The function remove_loops
is called in the function mate_parents
, which is defined in the code cell below. The function mate_parents
takes as input two parents and the distance matrix $d$. Read through the code for mate_parents
to get a sense of what it does.
def mate_parents(p0, p1, d):
"""
Produce a child by "mating" two parents p0 and p1
"""
# Find the first vertex x after s in p0 that is in p1.
# Such a vertex exists, since the terminal node t is in both p0 and p1.
# (In this case, the loop below would go through all values of i.)
for i in range(1, len(p0['path'])):
if p0['path'][i] in p1['path']:
break
# After the loop above, i is the index of x in p0
x = p0['path'][i]
# CASE A: x = t
# Select vertex a in p0 and vertex b in p1.
# Child = [s,...,a] in p0 + edge [a,b] + [b,...,t] in p1.
if x == p0['path'][-1]:
# CASE A.1: both p0 and p1 have AT LEAST
# one vertex other than s and t in their paths
# (i.e., they both have length > 2)
if len(p0['path']) > 2 and len(p1['path']) > 2:
# Randomly select vertex a in p0 by choosing a random index
# (excluding the 0th and last indices, since they correspond
# to s and t)
a_index = np.random.randint(1, len(p0['path']) - 1)
# Randomly select vertex b in p1 by choosing a random index
b_index = np.random.randint(1, len(p1['path']) - 1)
# Create child path: [s,...a] in p0 + [b,...,t] in p1
child_path = p0['path'][:a_index + 1] + p1['path'][b_index:]
# CASE A.2: p0 has at least one vertex other than s and t in its path,
# but p1 has only s and t in its path
if len(p0['path']) > 2 and len(p1['path']) == 2:
# Randomly select vertex a in p0 by choosing a random index
a_index = np.random.randint(1, len(p0['path']) - 1)
# Select the terminal node from p1
b_index = p1['path'][-1]
# Create child path: [s,...,a] in p0 + [t]
child_path = p0['path'][:a_index + 1] + p1['path'][b_index:]
# CASE A.3: p0 has only s and t in its path,
# but p1 has at least one vertex other than s and t in its path
if len(p0['path']) == 2 and len(p1['path']) > 2:
# Select the source node from p0
a_index = p0['path'][0]
# Randomly select vertex b in p1 by choosing a random index
b_index = np.random.randint(1, len(p1['path']) - 1)
# Create child path: [s] + [b,...,t] in p1
child_path = p0['path'][:a_index + 1] + p1['path'][b_index:]
# CASE A.4: p0 and p1 BOTH only have s and t in their paths
else:
# Set the child path to [s, t]
child_path = p0['path']
# CASE B: x != t
# Select shorter of [s,...,x] on p0 and [s,...,x] on p1.
# Add [x,...,t] from the other path.
else:
# Find index of x in p1
j = p1['path'].index(x)
# Find the shorter [s,...,x]
# Add [x,...,t] from the other path
if compute_score(p0['path'][:i + 1], d) <= compute_score(p1['path'][:j + 1], d):
child_path = p0['path'][:i + 1] + p1['path'][j + 1:]
else:
child_path = p1['path'][:j + 1] + p0['path'][i + 1:]
# Remove loops in the child path
child_path = remove_loops(child_path)
# Get child's score
child_score = compute_score(child_path, d)
# Return child
child = {'path': child_path, 'score': child_score}
return child
When looking at new code, it is a good idea to try to see what the code does to some sample input. The code below defines 3 parents, parent0
, parent1
, and parent2
.
Mate parent0
and parent1
to produce a child. Go line by line through the code for mate_parents
above and predict what the function does. Then run the code to see if the child you predicted was correct.
Do the same with parent0
and parent2
. Here the function will return an answer with some randomness. What is different in this case? Why can't we confidently predict the path of the child?
# Define parents for testing
parent0_path = [0, 5, 8, 12, 21, 29]
parent0_score = compute_score(parent0_path, d)
parent0 = {'path': parent0_path, 'score': parent0_score}
parent1_path = [0, 2, 8, 10, 15, 29]
parent1_score = compute_score(parent1_path, d)
parent1 = {'path': parent1_path, 'score': parent1_score}
parent2_path = [0, 7, 18, 29]
parent2_score = compute_score(parent2_path, d)
parent2 = {'path': parent2_path, 'score': parent2_score}
# Write your testing code below
# Parents 0 and 1
# This is case B with x = 8. The positions i and j are both 2.
child = mate_parents(parent0, parent1, d)
print(child)
# Parents 0 and 2
# This is case A: the paths only intersect at s and t.
# We choose a random vertex on parent0 to get a_index and
# a random vertex on parent2 to get b_index.
child = mate_parents(parent0, parent2, d)
print(child)
{'path': [0, 5, 8, 10, 15, 29], 'score': 201.0} {'path': [0, 5, 8, 12, 21, 29], 'score': 230.0}
Problem 7.
Run the code below to produce a list families
consisting of inner lists, each with 3 items: the first two items are paired parents and the third is their child.
# Mate each pair and store child in family next to its parents
families = []
for [p0, p1] in pairs:
child = mate_parents(p0, p1, d)
families.append([p0, p1, child])
# Check our work
print(families)
[[{'path': [0, 2, 20, 9, 18, 3, 21, 11, 22, 27, 5, 6, 23, 7, 29], 'score': 667.0}, {'path': [0, 12, 9, 4, 16, 24, 19, 10, 1, 15, 13, 29], 'score': 583.0}, {'path': [0, 12, 9, 18, 3, 21, 11, 22, 27, 5, 6, 23, 7, 29], 'score': 630.0}], [{'path': [0, 6, 10, 17, 14, 7, 22, 19, 16, 24, 13, 29], 'score': 518.0}, {'path': [0, 16, 11, 8, 1, 21, 20, 22, 19, 26, 4, 28, 29], 'score': 588.0}, {'path': [0, 6, 10, 17, 14, 7, 22, 19, 26, 4, 28, 29], 'score': 482.0}], [{'path': [0, 28, 5, 24, 25, 7, 19, 1, 10, 23, 6, 26, 3, 29], 'score': 673.0}, {'path': [0, 9, 11, 7, 1, 10, 22, 20, 26, 6, 29], 'score': 537.0}, {'path': [0, 9, 11, 7, 19, 1, 10, 23, 6, 26, 3, 29], 'score': 618.0}], [{'path': [0, 5, 1, 4, 28, 23, 27, 9, 20, 3, 15, 22, 10, 11, 8, 25, 16, 14, 21, 29], 'score': 829.0}, {'path': [0, 12, 28, 11, 20, 15, 6, 18, 22, 27, 29], 'score': 449.0}, {'path': [0, 12, 28, 23, 27, 9, 20, 3, 15, 22, 10, 11, 8, 25, 16, 14, 21, 29], 'score': 786.0}], [{'path': [0, 4, 11, 18, 2, 20, 16, 23, 25, 17, 12, 1, 14, 21, 28, 13, 22, 19, 29], 'score': 1009.0}, {'path': [0, 18, 8, 28, 27, 24, 6, 23, 17, 20, 2, 11, 1, 22, 29], 'score': 806.0}, {'path': [0, 4, 11, 1, 22, 29], 'score': 220.0}]]
Problem 8.
The function improve_child
is defined in the code cell below. It applies the local improvement process to a child. Read through the code to get a sense of what it does.
def improve_child(child, num_loc_improvement, n, d):
"""
Locally improve child
"""
# Local improvement on child's path p
#
# 1. Randomly pick two vertices on path p: a and b
# - Vertex a should be before vertex b in path p
# 2. Compare three candidate paths:
# - original p,
# - [s,...,a] on p + edge [a,b] + [b,...,t] on p,
# - [s,...,a] on p + random vertex c + [b,...,t] on p, after removing loops.
# 3. Pick the best of these paths.
# 4. Do this for num_loc_improvement iterations.
for k in range(num_loc_improvement):
child_path = child['path']
a_index = np.random.randint(0, len(child_path) - 1)
b_index = np.random.randint(a_index + 1, len(child_path))
# Define and score first alternate path
alt1_path = child_path[:a_index + 1] + child_path[b_index:]
alt1_score = compute_score(alt1_path, d)
alt1 = {'path': alt1_path, 'score': alt1_score}
# Define and score second alternate path
s = child_path[0]
t = child_path[-1]
a = child_path[a_index]
b = child_path[b_index]
# Choose a random vertex c, which cannot be s, t, a, or b
found = False
while not found:
c = np.random.randint(0, n)
if c not in [s, t, a, b]:
found = True
alt2_path = remove_loops(child_path[:a_index + 1] + [c] + child_path[b_index:])
alt2_score = compute_score(alt2_path, d)
alt2 = {'path': alt2_path, 'score': alt2_score}
# Decide which path is best (lowest score)
# Create list of candidates
candidates = [child, alt1, alt2]
# Initialize minimum score
min_score = float("inf")
# Initialize placeholder for candidate with minimum score
min_cand = None
for cand in candidates:
if cand['score'] < float("inf"):
min_score = cand['score']
min_cand = cand
# Update child to best path
child = min_cand
return child
The code below defines a child. Predict what will happen to the child after the first iteration of the for
loop in improve_child
above.
Then, run improve_child
on child
. Note that there are many random choices made by improve_child
, and improve_child
will perform many local improvements (num_local_improvements = 100
from above).
child_path = [0, 5, 8, 14, 16, 19, 23, 27, 29]
child_score = compute_score(child_path, d)
child = {'path': child_path, 'score': child_score}
# Write your code below
improve_child(child, num_loc_improvement, n, d)
# In the first iterations, the three candidate paths might be:
# [0, 5, 8, 14, 16, 19, 23, 27, 29] - the child itself
# [0, 5, 14, 16, 19, 23, 27, 29] - from picking a = 5 and b = 14, for example
# [0, 5, 2, 14, 16, 19, 23, 27, 29] - from picking c = 2, for example
# The new child after the first iteration will be the path with the lowest score.
{'path': [0, 1, 26, 29], 'score': 197.0}
Problem 9.
Run the code below to produce a list grown_families
of inner lists, each consisting of two paired parents and their improved "adult" child.
# Locally improve each child and store result with parents
# in the list grown_families
grown_families = []
for [p0, p1, child] in families:
adult = improve_child(child, num_loc_improvement, n, d)
grown_families.append([p0, p1, adult])
Problem 10.
The code cell below defines the function keep_low_two
. What do you think this function does?
In particular, what does the keyword argument key=lambda member: member['score']
do for the sorted
function? Here's the documentation on sorted
- take a look at the "Key Functions" section.
def keep_low_two(p0, p1, child):
family = [p0, p1, child]
sorted_family = sorted(family, key=lambda member: member['score'])
return [sorted_family[0], sorted_family[1]]
# keep_low_two takes as input 3 individuals (dictionaries with paths and their
# scores) and then returns a list of the two individuals with lowest scores.
Use the code below to rebuild the parents
list, replacing some parents with their adult children, as appropriate.
# Rebuild list of parents, possibly using some children
parents = []
for [p0, p1, adult] in grown_families:
[new_p0, new_p1] = keep_low_two(p0, p1, adult)
parents.append(new_p0)
parents.append(new_p1)
Problem 11.
The code from Problems 5, 7, 9 and 10 runs a single generation of our genetic algorithm. Take all this code and put it inside a loop that runs the code num_gens
times. Omit any print statements used to check your work; otherwise, your output will get messy fast!
for gen in range(num_gens):
# P5: Pair parents for mating
random_index = np.random.permutation(list(range(num_parents)))
pairs = []
for i in range(int(num_parents / 2)):
pairs.append([parents[random_index[2 * i]], parents[random_index[2 * i + 1]]])
# P7: Mate each pair and store child
families = []
for [p0, p1] in pairs:
child = mate_parents(p0, p1, d)
families.append([p0, p1, child])
# P9: Locally improve each child
grown_families = []
for [p0, p1, child] in families:
adult = improve_child(child, num_loc_improvement, n, d)
grown_families.append([p0, p1, adult])
# P10: Rebuild list of parents, possibly using some children
parents = []
for [p0, p1, adult] in grown_families:
[new_p0, new_p1] = keep_low_two(p0, p1, adult)
parents.append(new_p0)
parents.append(new_p1)
Problem 12. After running the code that we have so far, we should have a list of very fit parents, constructed and improved over multiple generations.
The code cell below defines the function get_fittest_parent
below. Read the function to get a sense of what it does.
def get_fittest_parent(parents):
"""
Gets the fittest parent from a list of parents
"""
# Sort the parents, using their score as the key
# We use the same technique as in Problem 10
sorted_parents = sorted(parents, key=lambda parent: parent['score'])
# Return parent with lowest
return sorted_parents[0]
Write code that finds the parent with the lowest score and prints that parent's path and score to the screen.
# Write your code below
best_parent = get_fittest_parent(parents)
print(f"The best path found is: {best_parent['path']}.")
print(f"The length of this path is {best_parent['score']}.")
The best path found is: [0, 5, 29]. The length of this path is 34.0.
Problem 13. NetworkX has methods that efficiently solve shortest path problems. Note that the solution we obtained above using our genetic algorithm is heuristic (i.e., approximately optimal), while NetworkX's methods are exact (i.e. produces solutions that are guaranteed to be optimal).
Let's compare our answer against the correct answer. Use the following code to solve the shortest path problem using NetworkX.
import networkx as nx
# Define complete graph
G = nx.complete_graph(n)
# Define distances for graph
for i in range(n):
for j in range(n):
if i != j:
G[i][j]['weight'] = d[i][j]
# Solve shortest path problem
spath = nx.shortest_path(G, source=s, target=t, weight='weight')
spath_length = nx.shortest_path_length(G, source=s, target=t, weight='weight')
print(f'Actual shortest path: {spath}.')
print(f'The length of this path is : {spath_length}.')
Actual shortest path: [0, 29]. The length of this path is : 2.0.
Problem 14. The code cell below contains a nicely organized version of the genetic algorithm that we've contructed above. Run this code or your own several times and see how often the genetic algorithm obtains an optimal solution. When it misses the correct solution, how badly does it miss? Report the error as
$$ \text{error} = \text{genetic algorithm's score} - \text{actual minimum score}. $$What is the highest error that you observe?
#############################################################
##### Import packages
#############################################################
import numpy as np
import networkx as nx
#############################################################
##### Set parameters
#############################################################
# Number of vertices
n = 30
# Source node
s = 0
# Terminal node
t = n - 1
# Number of parents
# Should be even
num_parents = 10
# Number of generations
num_gens = 50
# Number of local improvements
num_loc_improvement = 100
# Generate distance matrix
d = make_distance_matrix(n)
#############################################################
##### Define fitness function (compute_score)
#############################################################
def compute_score(path, d):
"""
Compute the fitness score of a path, i.e., its total length
"""
# Initialize score to 0
score = 0
# Iterate through the path nodes
# Add the length of each edge to the score
for e in range(len(path) - 1):
score += d[path[e], path[e+1]]
return score
#############################################################
##### Randomly generate a list of parents
#############################################################
# Each parent is a dictionary containing a path and its score.
parents = generate_parents(num_parents, s, t, n, d)
#############################################################
##### Enter the main loop: loop over generations
#############################################################
for gen in range(num_gens):
#############################################################
##### Produce children
#############################################################
# P5: Pair parents for mating
random_index = np.random.permutation(list(range(num_parents)))
pairs = []
for i in range(int(num_parents / 2)):
pairs.append([parents[random_index[2 * i]], parents[random_index[2 * i + 1]]])
# P7: Mate each pair and store child
families = []
for [p0, p1] in pairs:
child = mate_parents(p0, p1, d)
families.append([p0, p1, child])
#############################################################
##### Locally improve children
#############################################################
# P9: Locally improve each child
grown_families = []
for [p0, p1, child] in families:
adult = improve_child(child, num_loc_improvement, n, d)
grown_families.append([p0, p1, adult])
#############################################################
##### Each child tries to replace one of their parents
#############################################################
# P10: Rebuild list of parents, possibly using some children
parents = []
for [p0, p1, adult] in grown_families:
[new_p0, new_p1] = keep_low_two(p0, p1, adult)
parents.append(new_p0)
parents.append(new_p1)
#############################################################
##### End main loop
#############################################################
#############################################################
##### Take fittest parent as our solution
#############################################################
best_parent = get_fittest_parent(parents)
print(f"The best path found is: {best_parent['path']}.")
print(f"The length of this path is {best_parent['score']}.")
#############################################################
##### Compare against the answer from NetworkX
#############################################################
# Define complete graph
G = nx.complete_graph(n)
# Define distances for graph
for i in range(n):
for j in range(n):
if i != j:
G[i][j]['weight'] = d[i][j]
# Solve shortest path problem
spath = nx.shortest_path(G, source=s, target=t, weight='weight')
spath_length = nx.shortest_path_length(G, source=s, target=t, weight='weight')
print(f'Actual shortest path: {spath}.')
print(f'The length of this path is : {spath_length}.')
#############################################################
##### Write your code below: what is the error?
#############################################################
print(f"\nThe error is {best_parent['score'] - spath_length}.")
The best path found is: [0, 10, 29]. The length of this path is 30.0. Actual shortest path: [0, 14, 29]. The length of this path is : 8.0. The error is 22.0.
Problem 15. There is a lot that is unknown about genetic algorithms. For example: How should the various parameters be set? Which local and mating processes should be used?
The answers to these questions are typically different for different problems. Can you find better parameter values to use for this problem? One might expect that using more generations or more local modifications or more parents will be better. However, limit yourself: adjust these parameters so that
num_parents * num_gens * num_loc_improvement <= 50000
# Play with the parameters and have fun!
Problem 16. (Variant of the Shortest Path Problem) A variant of the shortest path problem involves a traveler planning a trip from city $s$ to city $t$. Here the vertices of the graph represent cities and the values in $d_{ij}$ represent distances. However, the traveler finds it difficult to leave each wonderful city he visits in his journey; so difficult that we multiply the $d_{ij}$ by 2 each time that he leaves a city. For instance, if $d_{01} = 5$, $d_{12} = 3$, and $d_{23} = 6$ then the $0$-$3$ path $0$-$1$-$2$-$3$ has score $5 + 2(3) + (2^2)6 = 35$.
This problem cannot be solved using the standard shortest path algorithms (e.g. Dijkstra, Bellman-Ford), but it is fairly easy to modify your genetic algorithm above to find a heuristic solution. All you need to do is to modify your compute_score
function!
Make the correct modification and solve the problem for several randomly generated examples. Can you find an instance where the genetic algorithm's solution is better than the path proposed by NetworkX's shortest_path
method (using the usual $d$ matrix for the distances), and the length of the path found is computed manually according to the new scoring rule for the above traveler?
# Redefine the function compute_score as follows:
def compute_score(path, d):
"""
Compute the fitness score of a path, its modified total length
"""
# Lengths are recorded in the matrix d
score = 0
multiplier = 0
for e in range(len(path) - 1):
score += (2 ** multiplier) * d[path[e], path[e + 1]]
multiplier += 1
return score