handcraftsman/geneticalgorithmswithpython

source code from the book Genetic Algorithms with Python by Clinton Sheppard

Genetic Algorithms with Python

Source code from the book Genetic Algorithms with Python by Clinton Sheppard

Description

Edición española

Get a hands-on introduction to machine learning with genetic algorithms using Python. Step-by-step tutorials build your skills from Hello World! to optimizing one genetic algorithm with another, and finally genetic programming; thus preparing you to apply genetic algorithms to problems in your own field of expertise.

Genetic algorithms are one of the tools you can use to apply machine learning to finding good, sometimes even optimal, solutions to problems that have billions of potential solutions. This book gives you experience making genetic algorithms work for you, using easy-to-follow example projects that you can fall back upon when learning to use other machine learning tools and techniques. Each chapter is a step-by-step tutorial that helps to build your skills at using genetic algorithms to solve problems using Python.

Available from major stores including Amazon, Apple and Barnes & Noble, in paperback, ePub, Kindle and PDF formats.

• https://www.amazon.com/Genetic-Algorithms-Python-Clinton-Sheppard/dp/1540324001/ ISBN-13: 978-1-540324-00-9 (paperback)
• https://www.amazon.com/Genetic-Algorithms-Python-Clinton-Sheppard/dp/1732029806/ ISBN-13: 978-1-7320298-0-4 (hardcover)
• https://itunes.apple.com/us/book/genetic-algorithms-with-python/id1231392098 ISBN-13: 978-1-370764-62-4 (ePub)
• https://www.amazon.com/dp/B01MYOWVJ2/ (Kindle Edition)
• https://leanpub.com/genetic_algorithms_with_python (PDF)

Try the sample chapters.

Table of Contents

A brief introduction to genetic algorithms

Chapter 1: Hello World!

• Guess a password given the number of correct letters in the guess. Build a mutation engine. See the sample.

Chapter 2: One Max Problem

• Produce an array of bits where all are 1s. Expands the engine to work with any type of gene. See the sample.

Chapter 3: Sorted Numbers

• Produce a sorted integer array. Demonstrates handling multiple fitness goals and constraints between genes.

Chapter 4: The 8 Queens Puzzle

• Find safe Queen positions on an 8x8 board and then expand to NxN. Demonstrates the difference between phenotype and genotype.

Chapter 5: Graph Coloring

• Color a map of the United States using only 4 colors. Introduces standard data sets and working with files. Also introduces using rules to work with gene constraints.

Chapter 6: Card Problem

• More gene constraints. Introduces custom mutation, memetic algorithms, and the sum-of-difference technique. Also demonstrates a chromosome where the way a gene is used depends on its position in the gene array.

Chapter 7: Knights Problem

• Find the minimum number of knights required to attack all positions on a board. Introduces custom genes and gene-array creation. Also demonstrates local minimums and maximums.

Chapter 8: Magic Squares

• Find squares where all the rows, columns and both diagonals of an NxN matrix have the same sum. Introduces simulated annealing.

Chapter 9: Knapsack Problem

• Optimize the content of a container for one or more variables. Introduces branch and bound and variable length chromosomes.

Chapter 10: Solving Linear Equations

• Find the solutions to linear equations with 2, 3 and 4 unknowns. Branch and bound variation. Reinforces genotype flexibility.

Chapter 11: Generating Sudoku

• A guided exercise in generating Sudoku puzzles.

Chapter 12: Traveling Salesman Problem (TSP)

• Find the optimal route to visit cities. Introduces crossover and a pool of parents.

Chapter 13: Approximating Pi

• Find the two 10-bit numbers whose dividend is closest to Pi. Introduces using one genetic algorithm to tune another.

Chapter 14: Equation Generation

• Find the shortest equation that produces a specific result using addition, subtraction, multiplication, &c. Introduces symbolic genetic programming.

Chapter 15: The Lawnmower Problem

• Generate a series of instructions that cause a lawnmower to cut a field of grass. Genetic programming with control structures, objects and automatically defined functions (ADFs).

Chapter 16: Logic Circuits

• Generate circuits that behave like basic gates, gate combinations and finally a 2-bit adder. Introduces tree nodes and hill climbing.

Chapter 17: Regular Expressions

• Find regular expressions that match wanted strings. Introduces chromosome repair and growth control.

Chapter 18: Tic-tac-toe

• Create rules for playing the game without losing. Introduces tournament selection.

geneticalgorithmswithpython's Issues

Not an issue but a newbie question

Very nice book. I bought it an hour ago.
Syntax of code for get_fitness(genes, target): has stumped me.
what does
sum(1 for expected, actual in zip(target, genes) if expected == actual)
mean?
return 1 if for all {expected, all} tuples if one comes across a value of expected equaling actual Else do nothing?

Please bear with me for such silly question

No module named 'genetic'

No funciona :(

No funciona :(. Falta el archivo "exnsd16.ukp", sitio inactivo. El código de muestra tampoco funciona. ¿Me pueden ayudar?

import datetime
import random
import sys
import unittest
import genetic

class Resource:
    Name = None
    Value = None
    Weight = None
    Volume = None
    def __init__(self, name, value, weight, volume):
        self.Name = name
        self.Value = value
        self.Weight = weight
        self.Volume = volume


class ItemQuantity:
    Item = None
    Quantity = None
    def __init__(self, item, quantity):
        self.Item = item
        self.Quantity = quantity
    def __eq__(self, other):
        return self.Item == other.Item and self.Quantity == other.Quantity

class Fitness:
    TotalWeight = None
    TotalVolume = None
    TotalValue = None
    
    def __init__(self, totalWeight, totalVolume, totalValue):
        self.TotalWeight = totalWeight
        self.TotalVolume = totalVolume
        self.TotalValue = totalValue
        
    def __gt__(self, other):
        return self.TotalValue > other.TotalValue
    
    def __str__(self):
        return "wt: {0:0.2f} vol: {1:0.2f} value: {2}".format( self.TotalWeight, self.TotalVolume, self.TotalValue)
    
def get_fitness(genes):
    totalWeight = 0
    totalVolume = 0
    totalValue = 0
    
    for iq in genes:
        count = iq.Quantity
        totalWeight += iq.Item.Weight * count
        totalVolume += iq.Item.Volume * count
        totalValue += iq.Item.Value * count
        
    return Fitness(totalWeight, totalVolume, totalValue)

def max_quantity(item, maxWeight, maxVolume):
    return min(int(maxWeight / item.Weight)
        if item.Weight > 0 else sys.maxsize, int(maxVolume / item.Volume)
        if item.Volume > 0 else sys.maxsize)
        
def create(items, maxWeight, maxVolume):
    genes = []
    remainingWeight, remainingVolume = maxWeight, maxVolume
    
    for i in range(random.randrange(1, len(items))):
        newGene = add(genes, items, remainingWeight, remainingVolume)
        if newGene is not None:
            genes.append(newGene)
            remainingWeight -= newGene.Quantity * newGene.Item.Weight
            remainingVolume -= newGene.Quantity * newGene.Item.Volume
            
    return genes


def add(genes, items, maxWeight, maxVolume):
    usedItems = {iq.Item for iq in genes}
    item = random.choice(items)
    
    while item in usedItems:
        item = random.choice(items)

    maxQuantity = max_quantity(item, maxWeight, maxVolume)
    return ItemQuantity(item, maxQuantity) if maxQuantity > 0 else None

def mutate(genes, items, maxWeight, maxVolume, window):
    window.slide()
    fitness = get_fitness(genes)
    remainingWeight = maxWeight - fitness.TotalWeight
    remainingVolume = maxVolume - fitness.TotalVolume

    removing = len(genes) > 1 and random.randint(0, 10) == 0
    if removing:
        index = random.randrange(0, len(genes))
        iq = genes[index]
        item = iq.Item
        remainingWeight += item.Weight * iq.Quantity
        remainingVolume += item.Volume * iq.Quantity
        del genes[index]

    adding = (remainingWeight > 0 or remainingVolume > 0) and (len(genes) == 0 or (len(genes) < len(items) and random.randint(0, 100) == 0))

    if adding:
        newGene = add(genes, items, remainingWeight, remainingVolume)
        if newGene is not None:
            genes.append(newGene)
            return

    index = random.randrange(0, len(genes))
    iq = genes[index]
    item = iq.Item
    remainingWeight += item.Weight * iq.Quantity
    remainingVolume += item.Volume * iq.Quantity

    changeItem = len(genes) < len(items) and random.randint(0, 4) == 0
    if changeItem:
        itemIndex = items.index(iq.Item)
        start = max(1, itemIndex - window.Size)
        stop = min(len(items) - 1, itemIndex + window.Size)
        item = items[random.randint(start, stop)]
    maxQuantity = max_quantity(item, remainingWeight, remainingVolume)
    
    if maxQuantity > 0:
        genes[index] = ItemQuantity(item, maxQuantity
        if window.Size > 1 else random.randint(1, maxQuantity))
    else:
        del genes[index]

def display(candidate, startTime):
    timeDiff = datetime.datetime.now() - startTime
    genes = candidate.Genes[:]
    genes.sort(key=lambda iq: iq.Quantity, reverse=True)

    descriptions = [str(iq.Quantity) + "x" + iq.Item.Name for iq in genes]
    
    if len(descriptions) == 0:
        descriptions.append("Empty")
    print("{}\t{}\t{}".format(', '.join(descriptions), candidate.Fitness, timeDiff))



def fill_knapsack(self, items, maxWeight, maxVolume, optimalFitness):
    startTime = datetime.datetime.now()
    
    def fnDisplay(candidate):
        display(candidate, startTime)
        
    def fnGetFitness(genes):
        return get_fitness(genes)
    
    def fnCreate():
        return create(items, maxWeight, maxVolume)
    
    def fnMutate(genes):
        mutate(genes, items, maxWeight, maxVolume)    
        
    best = genetic.get_best(fnGetFitness, None, optimalFitness, None, fnDisplay, fnMutate, fnCreate, maxAge=50)
    self.assertTrue(not optimalFitness > best.Fitness)
    
def test_cookies(self):
    items = [
        Resource("Flour", 1680, 0.265, .41),
        Resource("Butter", 1440, 0.5, .13),
        Resource("Sugar", 1840, 0.441, .29)
    ]
    
    maxWeight = 10
    maxVolume = 4
    
    optimal = get_fitness(
            [ItemQuantity(items[0], 1),
             ItemQuantity(items[1], 14),
             ItemQuantity(items[2], 6)])
    self.fill_knapsack(items, maxWeight, maxVolume, optimal)

unittest.main()

Problem in installing genetic-pacakge

Hi,

I am glad I found your book and think that it could be a big help to my work.
I just started Python and today I found that I need to install genetic-package while running through your book's pages.
I am using Python 3.5 and PyCharm IDE, and trying to install the package with pip ( pip install genetic ) but got this error:

Collecting genetic
  Using cached genetic-0.1.dev3.tar.gz
    Complete output from command python setup.py egg_info:
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "C:\Users\Widha\AppData\Local\Temp\pycharm-packaging\genetic\setup.py", line 39, in <module>
        packages=find_packages("./"),
      File "C:\Python35\lib\site-packages\setuptools\__init__.py", line 58, in find
        convert_path(where),
      File "C:\Python35\lib\distutils\util.py", line 127, in convert_path
        raise ValueError("path '%s' cannot end with '/'" % pathname)
    ValueError: path './' cannot end with '/'

How can I fix this? I have no problem installing other packages so far.

Thank you in advance,
Widha

file not found!

where is the genetic.py file of the graph coloring problem in ch 5?

Missing "R100_1gb.col" in Ch05

The file "R100_1gb.col" is missing. Hence the code/tests don't run.

def test_R100_1gb(self):
        self.color("R100_1gb.col",
                   ["Red", "Orange", "Yellow", "Green", "Blue", "Indigo"])

Ch_05: Graph Coloring- Hashing and Uniqueness query

Hello Clinton,

This is regarding,

Chapter 05: Graph Coloring
Subsection 5.3 Rule under Hashing and Uniqueness

You have mentioned an implementation where you multiply the hash of state code with prime and XOR it with the hash of adjacent state code.
@ return hash(self.Node) * 397 ^ hash(self.Adjacent)

What is the significance of using such hashing technique? Can you relate this to any reference?
Why not something as simple as hash(self.Node + '-' + self.Adjacent) ?

Chapter 3 code runs slow for me

Hi,
I'm really enjoying your book! I've learned a lot in just the first three chapters.

I've run into an issue however running the chapter 3 code from the book. ( sorted number list ) The benchmark test sorts 40 numbers. I'm running exactly the same code (copied from github) and it takes 63 seconds to complete. Something has to be wrong here. I'm on a Dell Laptop (Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz, 1992 Mhz, 4 Core(s), 8 Logical Processor(s)).

I'm running the same code that in the book it says on page 44: "1-2 seconds to run on average". I know processors vary but this seems extreme.

Is this normal behavior? I'm new to python and benchmarking so would appreciate any clarification.
Thanks,
Marc