Feeds:
Posts
Comments

Posts Tagged ‘Python’

In Part 1 we built a basic genetic solver that used mutation to solve problems. In this part we’re going to tackle a slightly more complex problem, the 8 Queens Puzzle, and then expand the solver as necessary.

Get the latest version of this post as a free chapter from my eBook Genetic Algorithms with Python

The 8 Queens Puzzle involves putting 8 queens on a standard chess board such that none are under attack. According to WikiPedia there are only 92 solutions to this puzzle and once we remove mirrorings and rotations there are only 12 unique solutions.

To start with we need to define a genome. The chess board conveniently has the same number of rows as columns (8) so we’ll use the digits 1-8 for our genes.

geneset = '12345678'

Array indexes are zero based however, so we’ll need to convert gene symbols to row and column values. To do that we’ll find the gene’s index into the set of gene symbols then use that index as a row or column, and combine those to make a Point.

class Point:
    Row = None
    Col = None

    def __init__(self, row, col):
        self.Row = row
        self.Col = col

def getPoint(rowGene, colGene, gene_set):
    rowIndex = gene_set.index(rowGene)
    if rowIndex == -1:
        raise ValueError("'" + rowGene + "' is an invalid gene")
    colIndex = gene_set.index(colGene)
    if colIndex == -1:
        raise ValueError("'" + colGene + "' is an invalid gene")
    return Point(rowIndex, colIndex)

We also need to be able plot the Points on a board.

def getBoard(candidate, gene_set):
    board = [['.'] * 8 for i in range(8)]
    for index in range(0, len(candidate), 2):
        point = getPoint(candidate[index], candidate[index + 1], gene_set)
        board[point.Row][point.Col] = 'Q'
    return board

And we want to be able to visualize the board.

def display(candidate, gene_set, startTime):
    timeDiff = datetime.datetime.now() - startTime
    board = getBoard(candidate.Genes, gene_set)
    for i in range(8):
        print(board[i][0],
              board[i][1],
              board[i][2],
              board[i][3],
              board[i][4],
              board[i][5],
              board[i][6],
              board[i][7]
              )
    print("%s\t%i\t%s" % (candidate.Genes, candidate.Fitness, str(timeDiff)))

This will give us output like the following

. Q . . . . . .
. . Q . . . . .
. . . . Q Q . .
. . . . . . . Q
. . . . . . . .
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
7761124823353685	29	0:00:00.013001

The row of digits under the board is the set of genes that created the board layout. The number to the right will be the fitness, a measure of how close this set of genes is to the desired result. To drive improvement we’ll want to increase the fitness value whenever the related board position lets more queens coexist on the board. Let’s think about how we can do that.

We’ll start with counting the number of columns that have a queen. Here’s a layout that gets an optimal score but is undesirable

Q Q Q Q Q Q Q Q
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

We’ll also count the number of rows that have queens. Here’s a revised board where both counts are optimal but the layout still allows queens to attack each other.

Q . . . . . . .
. Q . . . . . .
. . Q . . . . .
. . . Q . . . .
. . . . Q . . .
. . . . . Q . .
. . . . . . Q .
. . . . . . . Q

To fix this problem we’ll include the count of the number of southeast diagonals that have a queen. Again we can find a corner case as follows:

. . . . . . . Q
. . . . . . Q .
. . . . . Q . .
. . . . Q . . .
. . . Q . . . .
. . Q . . . . .
. Q . . . . . .
Q . . . . . . .

To fix this final problem we’ll include the count of the number of northeast diagonals that have a queen.

Our fitness value will be the sum of those four counts, 8+8+8+8 being optimal.

Side note on implementation, we can calculate the northeast diagonals in Excel using the formula =$A2+B$1 which results in a grid as follows

    0   1   2   3   4   5   6   7
0   0   1   2   3   4   5   6   7
1   1   2   3   4   5   6   7   8
2   2   3   4   5   6   7   8   9
3   3   4   5   6   7   8   9   10
4   4   5   6   7   8   9   10  11
5   5   6   7   8   9   10  11  12
6   6   7   8   9   10  11  12  13
7   7   8   9   10  11  12  13  14

The southeast diagonals can be calculated using =(8-1-$A2)+B$1 which we can visualize as follows:

    0   1   2   3   4   5   6   7
0   7   8   9   10  11  12  13  14
1   6   7   8   9   10  11  12  13
2   5   6   7   8   9   10  11  12
3   4   5   6   7   8   9   10  11
4   3   4   5   6   7   8   9   10
5   2   3   4   5   6   7   8   9
6   1   2   3   4   5   6   7   8
7   0   1   2   3   4   5   6   7

Using the above 2 formulas along with the row and column values lets us touch each board position exactly once, which makes our fitness function run fast.

def getFitness(candidate, gene_set):
    board = getBoard(candidate, gene_set)
    rowsWithQueens = {}
    colsWithQueens = {}
    northEastDiagonalsWithQueens = {}
    southEastDiagonalsWithQueens = {}
    for row in range(8):
        for col in range(8):
            if board[row][col] == 'Q':
                rowsWithQueens[row] = 1
                colsWithQueens[col] = 1
                northEastDiagonalsWithQueens[row + col] = 1
                southEastDiagonalsWithQueens[8 - 1 - row + col] = 1

    return len(rowsWithQueens) \
           + len(colsWithQueens) \
           + len(northEastDiagonalsWithQueens) \
           + len(southEastDiagonalsWithQueens)

Finally our main (integration test) method will bring all the parts together.

class EightQueensTests(unittest.TestCase):
    def test(self):
        geneset = '12345678'
        startTime = datetime.datetime.now()
        fnDisplay = lambda candidate: display(candidate, geneset, startTime)
        fnGetFitness = lambda candidate: getFitness(candidate, geneset)
        best = genetic.getBest(fnGetFitness, fnDisplay, 16, 8 + 8 + 8 + 8, geneset)
        self.assertEqual(best.Fitness, 8 + 8 + 8 + 8)

Note that we’ve added a parameter to getBest. This is because in Part 1 the solver determined the optimal fitness internally but now we want pass it in.

def getBest(get_fitness, display, targetLen, optimalFitness, geneSet):
...
    while bestParent.Fitness < optimalFitness:

We can run our test to see if the solver can find a solution.

Q . . . . . . .
. . . . . . . .
. . . . Q . . .
. . . . Q . . .
. Q . . Q . . .
. . . . . . . .
. . . Q . . . .
Q . Q . . . . .
4574811152355583	23	0:00:00
Q . . . . . . .
. . . . . . . .
. . . . Q . . .
. . . . Q . . .
. . . . Q . . Q
. . . . . . . .
. . . Q . . . .
Q . Q . . . . .
4574811158355583	24	0:00:00
Q . . . . . . .
. . . . . . . .
. . . . Q . . .
. . Q . Q . . .
. . . . Q . . Q
. . . . . . . .
. . . Q . . . .
Q . . . . . . .
4574811158355543	25	0:00:00.001000
Q . . . . . . .
. . . . . . . .
. . . . Q . . .
. . Q . Q . . .
. . . . . . Q Q
. . . . . . . .
. . . Q . . . .
Q . . . . . . .
4574811158355743	26	0:00:00.002000
Q . . . . . . .
. . . . . . . .
Q . . . . . . .
. . Q . Q . . .
. . . . . . Q Q
. . . . . . . .
. . . Q . . . .
Q . . . . . . .
4574811158315743	27	0:00:00.003000
Q . . . . . . .
. . . . . . . Q
Q . . . . . . .
. . Q . Q . . .
. . . . . . Q .
. . . . . . . .
. . . Q . . . .
Q . . . . . . .
4574811128315743	28	0:00:00.004000
Q . . . . . . .
. . . . . . . Q
Q . . . . . . .
. . Q . Q . . .
. . . . . . Q .
. . . . . . . .
. . . Q . . . .
. Q . . . . . .
4574821128315743	29	0:00:00.005001
Q . . . . . . .
. . . . . Q . .
Q . . . . . . .
. . Q . Q . . .
. . . . . . Q .
. . . . . . . .
. . . Q . . . .
. Q . . . . . .
4574821126315743	30	0:00:00.009001

After several test runs we find that most of the time it gets close but can’t get all the way to the optimal value of 32. We need to enhance the solver’s capabilities for it to be able to handle this problem.

If at first you don’t succeed, try, try again!

We’re going to do that by introducing a second genetic line. We’ll mutate the 2nd line as long as it is improving. If it ends up with a better fitness than bestParent then it will become the bestParent. Otherwise, we’ll start a new genetic line again with a random gene sequence. We repeat this process over and over until we find an optimal result. Here’s the updated solver loop:

def getBest(get_fitness, display, targetLen, optimalFitness, geneSet):
    random.seed()
    bestParent = generateParent(targetLen, geneSet, get_fitness)
    display(bestParent)

    while bestParent.Fitness < optimalFitness:
        parent = generateParent(targetLen, geneSet, get_fitness)
        attemptsSinceLastImprovement = 0
        while attemptsSinceLastImprovement < 128:
            child = mutate(parent, geneSet, get_fitness)
            if child.Fitness > parent.Fitness:
                parent = child
                attemptsSinceLastImprovement = 0
            attemptsSinceLastImprovement += 1

        if bestParent.Fitness < parent.Fitness:
            bestParent, parent = parent, bestParent
            display(bestParent)

    return bestParent

Now when we run the 8 queens test we find an optimal solution every time.

. Q . . Q . . .
. . . . Q . . .
. . . . . . . Q
. . . . . . . Q
. . . . . . . .
. . . . . . . .
. . . . . . . .
Q . . . . . . .
8148381525122525	20	0:00:00
. . Q . . . . .
. . Q . . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .
. . . Q . . . .
Q . . . . . . .
. . . . Q . . Q
2385884313647137	28	0:00:00.013001
. . . . . . Q .
. . . . . . . .
. . . Q . . . .
. . . . . Q . Q
Q . . . . . . .
. . . . Q . . .
. Q . . . . . .
. . . . Q . . .
3417486546857251	30	0:00:00.041003
. . Q . . . . .
. . . . Q . . .
. Q . . . . . .
. . . Q . . . .
Q . . . . . . .
. . Q . . . . .
. . . . . . . Q
. . . . . Q . .
5178258613324463	31	0:00:00.143008
. . . . Q . . .
. . Q . . . . .
Q . . . . . . .
. . . . . . Q .
. Q . . . . . .
. . . . . . . Q
. . . . . Q . .
. . . Q . . . .
5247312368841576	32	0:00:00.308018

However, when we run the string duplication test from Part 1 it now struggles to find a solution. This is because we ignore our best line completely once we find it and only try to improve by mutating a new genetic line.

JoyEMlECsatqzfBVFkvIHduMg!HAFtnWcC	3	0:00:00
Nj!HBLwEHvdse wGGOKbJctg AriqlNDPP	8	0:00:00.022001
NBiBRlE thoHfFWhW !tnnFyuHAv wputM	11	0:00:00.062004
NUt alx xmusGiwTmEwprder are lKsdG	19	0:00:00.112007
Not allkthosbHnhoCHinvBr OQe losmR	21	0:00:00.852049
NotW!lT NhoJe VhRFwaDderiaCe most.	22	0:00:02.510144
Not alF tQose S!o wDndUZ yre lostA	25	0:00:05.847335
NotXLll those whopwWnder are lost.	30	0:01:33.040322

We need a way to continue to take advantage of the genes in bestParent. One way nature handles this is through crossbreeding so we’ll introduce a crossover strategy where we take one random gene from a 2nd (the best) parent.

def crossover(parent, parent2, get_fitness):
    index = random.randint(0, len(parent.Genes) - 1)
    genes = list(parent.Genes)
    genes[index] = parent2.Genes[index]
    childGenes = (''.join(genes))
    fitness = get_fitness(childGenes)
    return Individual(childGenes, fitness)

And update the main loop to randomly choose whether to use mutation or crossover to improve the 2nd genetic line.

    options = {
        0: lambda p: mutate(p, geneSet, get_fitness),
        1: lambda p: crossover(p, bestParent, get_fitness)
    }

    while bestParent.Fitness < optimalFitness:
        parent = generateParent(targetLen, geneSet, get_fitness)
        attemptsSinceLastImprovement = 0
        while attemptsSinceLastImprovement < 128:
            child = options[random.randint(0, len(options) - 1)](parent)

Now when we run the tests both are able to achieve optimal results every time.

 

Refactor

 

Now that everything works we’re going to do some code hygiene. In solving this problem we used genes “12345678” but it would have been more convenient, and faster, if we could have used raw integers 0-7. So let’s make that change. I’ll show selected changes below but you can get the full set from github.

class EightQueensTests(unittest.TestCase):
    def test(self):
        geneset = [0, 1, 2, 3, 4, 5, 6, 7]
    ...
        fnDisplay = lambda candidate: display(candidate, startTime)
        fnGetFitness = lambda candidate: getFitness(candidate)
    ...

This means both Point and getPoint can go away, simplifying getBoard to:

def getBoard(candidate):
    board = [['.'] * 8 for i in range(8)]
    for index in range(0, len(candidate), 2):
        board[candidate[index]][candidate[index + 1]] = 'Q'
    return board

In display we go the other way so we can show all the genes as a string.

def display(candidate, startTime):
    timeDiff = datetime.datetime.now() - startTime
    board = getBoard(candidate.Genes)
    for i in range(8):
        print(board[i][0],
              board[i][1],
              board[i][2],
              board[i][3],
              board[i][4],
              board[i][5],
              board[i][6],
              board[i][7]
              )
    print("%s\t%i\t%s" % (''.join(map(str, candidate.Genes)), candidate.Fitness, str(timeDiff)))

To support the geneset being an array in the solver we only have to eliminate the line in crossover, mutate and generateParent that converts the child gene sequence to a string.

Read more of this series in my book Genetic Algorithms with Python

 

Advertisements

Read Full Post »

The goal of this, my first program in Python, is to reproduce a target string (like Hello World!) without looking directly at it. I’ll do this with a simple genetic algorithm that randomly generates an initial sequence of characters and then mutates one random character in that sequence at a time until it matches the target. Think of this like playing a Hangman variant where you pass a letter sequence to the person who knows the target word, and the only feedback you get is how many of your letters are correct. It is also reminiscent of the game Hotter Colder, except we’re doing it with code.

We start off with a standard set of letters for genes and a target string:

    geneset = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
    target = "Not all those who wander are lost."

Next we need a way to generate a random gene sequence from the gene set.

def generateParent(length):
    genes = list("")
    for i in range(0,length):
        geneIndex = random.randint(0, len(geneset) -1);
        genes.append(geneset[geneIndex])
    return(''.join(genes))

There are many ways to calculate a fitness value (how close the guess is to the target) for the generated string. For this particular problem we’ll simply count the number of characters that are the same between the candidate string and the target string.

def getFitness(candidate, target):
   fitness = 0
   for i in range(0, len(candidate)):
       if target[i] == candidate[i]:
           fitness += 1
   return(fitness)

We also need a way to produce a new child gene sequence by mutating the existing (parent) string.  The point is to create a copy of the parent then replace 1 letter/gene in the copy with a randomly selected one from the set of all possible genes/letters.

def mutate(parent):
   geneIndex = random.randint(0, len(geneset) -1);
   index = random.randint(0, len(parent) - 1)
   genes = list(parent)
   genes[index] = geneset[geneIndex]
   return(''.join(genes))

Next we need a way to display a gene sequence, its fitness value and how much time has elapsed.

def display(candidate, startTime):
    timeDiff = datetime.datetime.now() - startTime
    fitness = getFitness(candidate, target)
    print ("%s\t%i\t%s" % (candidate, fitness, str(timeDiff)))

The heart of the genetic solver is a loop that uses the functions above to generate a candidate gene sequence, compare it to the previous best, and randomly mutate it until all the genes match those in the target.

bestParent = generateParent(len(target))
bestFitness = getFitness(bestParent, target)
display(bestParent, startTime)

while bestFitness < len(bestParent):
   child = mutate(bestParent)
   childFitness = getFitness(child, target)

   if childFitness > bestFitness:
      bestFitness = childFitness
      bestParent = child
      display(bestParent, startTime)

Sample output:

Python 3.4.3 (v3.4.3:9b73f1c3e601, Feb 24 2015, 22:44:40) [MSC v.1600 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
<<< ================================ RESTART ================================
<<<
iEjRmPrBUUDosXupcEw.Ji.qTCtRYawlry	1	0:00:00
iEjRmPrBUUDosXupcEw.Ji.qTCtRYaolry	2	0:00:00.004001
iEjRmPr UUDosXupcEw.Ji.qTCtRYaolry	3	0:00:00.007001
iEjRmPr UUDosXupcEw.JieqTCtRYaolry	4	0:00:00.011001
iEjRmPr UUDosXupcEw.nieqTCtRYaolry	5	0:00:00.014002
iEjRmPl UUDosXupcEw.nieqTCtRYaolry	6	0:00:00.016002
iEjRmPl UhDosXupcEw.nieqTCtRYaolry	7	0:00:00.023003
iEjRmPl UhoosXupcEw.nieqTCtRYaolry	8	0:00:00.026003
iEjRmPl UhossXupcEw.nieqTCtRYaolry	9	0:00:00.029003
iEjRmPl UhossXupcEw.nierTCtRYaolry	10	0:00:00.032003
iEj mPl UhossXupcEw.nierTCtRYaolry	11	0:00:00.036004
iEj mPl UhossXupcEw.nierTCrRYaolry	12	0:00:00.038004
iEj aPl UhossXupcEw.nierTCrRYaolry	13	0:00:00.041004
iEj aPl UhossXupcEw.nderTCrRYaolry	14	0:00:00.044005
iEj aPl UhossXupcEw.nderTCreYaolry	15	0:00:00.045005
iEj aPl UhossXupoEw.nderTCreYaolry	16	0:00:00.047005
iEj aPl UhoseXupoEw.nderTCreYaolry	17	0:00:00.051005
iEj aPl UhoseXupoEw.nderTCreYlolry	18	0:00:00.054006
iEj aPl UhoseXupoEw.nderTCreYlolr.	19	0:00:00.057006
iEj aPl thoseXupoEw.nderTCreYlolr.	20	0:00:00.059006
iEj aPl thoseXupoEwanderTCreYlolr.	21	0:00:00.065007
iEj aPl thoseXupo wanderTCreYlolr.	22	0:00:00.068007
NEj aPl thoseXupo wanderTCreYlolr.	23	0:00:00.073008
NEj aPl thoseXupo wander CreYlolr.	24	0:00:00.075008
NEj aPl thoseXupo wander CreYlolt.	25	0:00:00.081008
NEj aPl thoseXwpo wander CreYlolt.	26	0:00:00.083009
Noj aPl thoseXwpo wander CreYlolt.	27	0:00:00.090009
Noj aPl thoseXwho wander CreYlolt.	28	0:00:00.093010
Noj aPl thoseXwho wander CreYlost.	29	0:00:00.097010
Not aPl thoseXwho wander CreYlost.	30	0:00:00.106011
Not all thoseXwho wander CreYlost.	31	0:00:00.117012
Not all thoseXwho wander areYlost.	32	0:00:00.120012
Not all thoseXwho wander are lost.	33	0:00:00.123013
Not all those who wander are lost.	34	0:00:00.151015

Refactor

 

Good, it works. Now we need to separate the solver code from that specific to the string duplication problem so we can use it to solve other problems. We’ll start by moving our main loop into a function called getBest. That function’s parameters will include the functions it should call to get the candidate’s fitness and to display a new best sequence.

def getBest(get_fitness, display, targetLen, geneSet):
    random.seed()
    bestParent = generateParent(targetLen, geneSet)
    bestFitness = get_fitness(bestParent)
    display(bestParent)

    while bestFitness < len(bestParent):
       child = mutate(bestParent, geneSet)
       childFitness = get_fitness(child)

       if childFitness > bestFitness:
          bestFitness = childFitness
          bestParent = child
          display(bestParent)
    return bestParent

We also need to pass the gene set to generateParent and mutate so they aren’t using global variables.

def mutate(parent, geneSet):
   geneIndex = random.randint(0, len(geneSet) -1);
   index = random.randint(0, len(parent) - 1)
   genes = list(parent)
   genes[index] = geneSet[geneIndex]
   return(''.join(genes))

def generateParent(length, geneSet):
    genes = list("")
    for i in range(0,length):
        geneIndex = random.randint(0, len(geneSet) -1);
        genes.append(geneSet[geneIndex])
    return(''.join(genes))

Now move the rest of the code to a new file named stringDuplicationTests.py. Notice that display and getFitness no longer have the same number of parameters as those above.

def getFitness(candidate, target):
   fitness = 0
   for i in range(0, len(candidate)):
       if target[i] == candidate[i]:
           fitness += 1
   return(fitness)

def display(candidate, target, startTime):
    timeDiff = datetime.datetime.now() - startTime
    fitness = getFitness(candidate, target)
    print ("%s\t%i\t%s" % (candidate, fitness, str(timeDiff)))

In our main test method we’ll pass lambdas that take the candidate gene sequence passed by the solver as a parameter and call the local methods with additional required parameters as necessary.

def test_string_duplication():
    geneset = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
    startTime = datetime.datetime.now()
    target = "Not all those who wander are lost."
    fnDisplay = lambda candidate: display(candidate, target, startTime)
    fnGetFitness = lambda candidate: getFitness(candidate, target)
    best = genetic.getBest(fnGetFitness, fnDisplay, len(target), geneset)

Next we’ll make it so that executing this file calls our test function.

if __name__ == '__main__':
    test_string_duplication()

That’s it. We now have separation of concerns and when we run the test code the program still works. You can get the updated code from this checkin on Github.

Next, we’ll modify the test file to make it compatible with Python’s built in test framework.

import unittest
import datetime
import genetic

def getFitness(candidate, target):
   fitness = 0
   for i in range(0, len(candidate)):
       if target[i] == candidate[i]:
           fitness += 1
   return(fitness)

def display(candidate, target, startTime):
    timeDiff = datetime.datetime.now() - startTime
    fitness = getFitness(candidate, target)
    print ("%s\t%i\t%s" % (candidate, fitness, str(timeDiff)))

class StringDuplicationTests(unittest.TestCase):
    def test(self):
        geneset = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
        startTime = datetime.datetime.now()
        target = "Not all those who wander are lost."
        fnDisplay = lambda candidate: display(candidate, target, startTime)
        fnGetFitness = lambda candidate: getFitness(candidate, target)
        best = genetic.getBest(fnGetFitness, fnDisplay, len(target), geneset)
        self.assertEqual(best, target)

if __name__ == '__main__':
    unittest.main()

This allows us to run the tests from the commandline and without writing the output, which, by the way, makes it run twice as fast.

python -m unittest -b geneticTests.py
.
----------------------------------------------------------------------
Ran 1 test in 0.108s

OK

The final refactoring will be to introduce an Individual object that has both Genes and Fitness attributes.

class Individual:
   Genes = None
   Fitness = None
   def __init__(self, genes, fitness):
        self.Genes = genes
        self.Fitness = fitness

This lets us pass those values around as a unit and reduces some double work in the display function.

import random

def mutate(parent, geneSet, get_fitness):
   geneIndex = random.randint(0, len(geneSet) -1);
   index = random.randint(0, len(parent.Genes) - 1)
   genes = list(parent.Genes)
   genes[index] = geneSet[geneIndex]
   childGenes = (''.join(genes))
   fitness = get_fitness(childGenes)
   return Individual(childGenes, fitness)

def generateParent(length, geneSet, get_fitness):
    genes = list("")
    for i in range(0,length):
        geneIndex = random.randint(0, len(geneSet) -1);
        genes.append(geneSet[geneIndex])
    childGenes = (''.join(genes))
    fitness = get_fitness(childGenes)
    return Individual(childGenes,fitness)

def getBest(get_fitness, display, targetLen, geneSet):
    random.seed()
    bestParent = generateParent(targetLen, geneSet, get_fitness)
    display(bestParent)

    while bestParent.Fitness < targetLen:
       child = mutate(bestParent, geneSet, get_fitness)

       if child.Fitness > bestParent.Fitness:
          bestParent = child
          display(bestParent)
    return bestParent

We also have to make compensating changes to the test file methods.

def display(candidate, target, startTime):
    timeDiff = datetime.datetime.now() - startTime
    print ("%s\t%i\t%s" % (candidate.Genes, candidate.Fitness, str(timeDiff)))

class StringDuplicationTests(unittest.TestCase):
    def test(self):
        geneset = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
        startTime = datetime.datetime.now()
        target = "Not all those who wander are lost."
        fnDisplay = lambda candidate: display(candidate, target, startTime)
        fnGetFitness = lambda candidate: getFitness(candidate, target)
        best = genetic.getBest(fnGetFitness, fnDisplay, len(target), geneset)
        self.assertEqual(best.Genes, target)

Go on to Part 2 in which we evolve the solver to handle the 8 Queens Puzzle.

Learn more in my book Genetic Algorithms with Python

Read Full Post »

%d bloggers like this: