Our second project involves maximizing the number of 1’s in an array of 100 1-bit numbers. For this project the gene set will be only 0 or 1.
import unittest
import datetime
import genetic
class OneMaxTests(unittest.TestCase):
def test(self, length=100):
geneset = [0, 1]genetic to work with listsThe genetic module is currently hard coded to work with strings, so we need to modify it to work with lists instead. We can start by using Python’s array slicing feature to copy the genes in _mutate instead of using the list constructor.
def _mutate(parent, geneSet, get_fitness):
childGenes = parent.Genes[:]
...Then remove the following line from _mutate and _generate_parent since we no longer need to convert the list back to a string:
genes = ''.join(childGenes)Next, update those functions to use the list, as follows:
def _mutate(parent, geneSet, get_fitness):
childGenes = parent.Genes[:]
index = random.randrange(0, len(parent.Genes))
newGene, alternate = random.sample(geneSet, 2)
childGenes[index] = alternate \ ①
if newGene == childGenes[index] \ ②
else newGene
fitness = get_fitness(childGenes) ③
return Chromosome(childGenes, fitness) ④def _generate_parent(length, geneSet, get_fitness):
...
fitness = get_fitness(genes) ⑤
return Chromosome(genes, fitness) ⑥To keep guessPasswordTests.py working, we must recombine the genes into a string in its display function
def display(candidate, startTime):
timeDiff = datetime.datetime.now() - startTime
print("{}\t{}\t{}".format(
''.join(candidate.Genes), ⑦
candidate.Fitness,
timeDiff))and the assertion in guess_password.
class GuessPasswordTests(unittest.TestCase):
def guess_password(self, target):
...
self.assertEqual(''.join(best.Genes), target)OK, back to the One Max problem. The fitness will be the number of 1’s in the array.
def get_fitness(genes):
return genes.count(1)Since 100 numbers would be a lot to display, we’ll just show the first and last 15 along with the fitness and elapsed time.
def display(candidate, startTime):
timeDiff = datetime.datetime.now() - startTime
print("{}...{}\t{:3.2f}\t{}".format(
''.join(map(str, candidate.Genes[:15])),
''.join(map(str, candidate.Genes[-15:])),
candidate.Fitness,
timeDiff))And here’s the full test harness.
def test(self, length=100):
geneset = [0, 1]
startTime = datetime.datetime.now()
def fnDisplay(candidate):
display(candidate, startTime)
def fnGetFitness(genes):
return get_fitness(genes)
optimalFitness = length
best = genetic.get_best(fnGetFitness, length, optimalFitness, geneset,
fnDisplay)
self.assertEqual(best.Fitness, optimalFitness)Now it can find the solution very quickly.
010101101010010...101010110100101 50.00 0:00:00.001000
010101101010010...101010110100101 51.00 0:00:00.001000
...
110111101111111...111111110111111 95.00 0:00:00.008000
110111111111111...111111110111111 96.00 0:00:00.008000
110111111111111...111111110111111 97.00 0:00:00.009000
110111111111111...111111111111111 98.00 0:00:00.009000
111111111111111...111111111111111 99.00 0:00:00.010000
111111111111111...111111111111111 100.00 0:00:00.011000Since it runs so fast we’ll benchmark this project with a longer array. As with the Guess Password benchmark I’m choosing an array length that takes between 1 and 2 seconds on average on my box. You may want to select a different length.
def test_benchmark(self):
genetic.Benchmark.run(lambda: self.test(4000))We can see in the updated benchmarks that eliminating the string conversion may also have given us a tiny performance improvement in Guess Password.
Updated Benchmarks
project | average (seconds) | standard deviation
-----------------------------------------------------------
Guess Password | 1.21 | 0.25
One Max | 1.25 | 0.17
In this project the genetic engine randomly chooses an array index to change, even if the array already contains a 1 at that index, because the engine doesn’t know the change it is making is useless until after it has called the fitness function. A physical equivalent is to take 100 coins and put green sticky dots on one side and yellow sticky dots on the other. Then have a partner blindfold you and drop the coins on a table top. Your goal is to turn all the coins yellow-side up. If you turn one yellow-side up they tell you it was a success. Otherwise, they undo the change and tell you it was a failure. To keep you from building a mental map they could optionally move the coin somewhere else afterward. Tough game right?
Now think about possible changes to the coin game that would make it solvable. For example, what if they were to remove the coin from the table if you turn it yellow-side up. That would be extremely useful right? Assuming every coin started yellow-side up, you would at most turn each coin twice, meaning you could turn all coins yellow-side up in at most 200 turns no matter which way they started. If the genetic algorithm, instead of the engine, had control of choosing the next index, then the equivalent would be for it to record the index it changes. Then, if display is called next by the engine instead of get_index, the algorithm would know that the array contains a 1 at that index. It could then simply add the index to a list of indexes it ignores when guessing. A side benefit of this solution is that, like the human player in the coin game, the genetic algorithm does not need to know the state of the entire array. It can begin with zero knowledge and start tracking indexes that improve the fitness, just like
the classic Battleship game.
In this chapter the flexibility of the genetic module was increased by allowing the genes to be any type instead of only characters in a string. This is a critical feature, as before long we will want to use something other than just keyboard characters for genes.
The final code for this chapter is available from:
https://github.com/handcraftsman/GeneticAlgorithmsWithPython/tree/master/ch02