Genetic algorithm to guess password

Question

I was writing a Python script that starts with a random string and then using Genetic Algorithm tries to find the target string. Although I have successfully implemented the algorithm but it's taking too much time to execute, even for a string of length 21 it took around 2mins.

# A utility function that decide which two parents two select for crossover.
# based on Roulette Wheel Sampling 
def select_parent():
    # totalFitness is sum of fitness of all the organism of the current generation
    pick = random.randint(0, totalFitness)  
    current = 0

    # Roulette Wheel Sampling implementation
    # populationSize = 10 * length(targetString)
    for index in range(populationSize):
        current += fitness_all[index]
        if current >= pick:
            return index

# A utility function to perform crossover.
def produce_next_generation():
    for organism in nextGeneration:
        # select two parents using Roulette Wheel Sampling 
        parent_first = currentGeneration[select_parent()] 
        parent_second  = currentGeneration[select_parent()]
        cross_over_point = random.randint(0, targetLength - 1)

        new_genes = [''] * targetLength
        for i in range(targetLength):
            # mutation rate is set to 0.001
            mutate_this_gene = random.randint(0, int(1 / mutationRate))

            # target string contains upper and lower case chars only
            if mutate_this_gene == 0:
                new_genes[i] = random.choice(string.ascii_uppercase + string.ascii_lowercase) # target string is combination of upper and lower case
            elif i <= cross_over_point:
                new_genes[i] = parent_first.genes[i]
            else:
                new_genes[i] = parent_second.genes[i]

        organism.genes = ''.join(new_genes)

    global currentGeneration
    currentGeneration = [organism for organism in nextGeneration]

Here are the two functions, that I feel can be optimized further(rest of the code just defines the fitness function and a loop that runs endlessly unless target string is found.)

I took inspiration from a similar code written in C.

Rest of the code:

import random, datetime, string

# Define some global variables here
target = 'Brevityisthesoulofwit'
targetLength = len(target)
populationSize = 10 * targetLength
currentGeneration = []  # the
# this will store the generation created due to cross-over, will finally be copied into current generation
nextGeneration = []
totalFitness = 0  # this for the simulation of Roullete Wheel Sampling
idealOrganism = None
mutationRate = 0.001


# The Chromosome class
class Chromosome:
    def __init__(self, genes):
        self.genes = genes

    def get_fitness(self, ideal):
        ideal_genes = ideal.genes
        return sum(1 for i in range(targetLength) if self.genes[i] == ideal_genes[i])

    @staticmethod
    def get_new_random_genes():
        return ''.join(random.choice(string.ascii_uppercase + string.ascii_lowercase) for i in range(targetLength))


def create_initial_generation():
    global idealOrganism
    idealOrganism = Chromosome(target)

    for i in range(populationSize):
        currentGeneration.append(Chromosome(Chromosome.get_new_random_genes()))
        nextGeneration.append(Chromosome(Chromosome.get_new_random_genes()))


def evaluate_organism():
    fitness_all_new = [organism.get_fitness(idealOrganism) for organism in currentGeneration]

    global totalFitness
    totalFitness = sum(fitness_all_new)
    return fitness_all_new


def is_generation_perfect():
    for organism in currentGeneration:
        if organism.genes == target:
            return True
    return False


if __name__ == '__main__':
    create_initial_generation()
    generation = 1
    fitness_all = None
    start_time = datetime.datetime.now()

    while True:
        if is_generation_perfect():
            break

        fitness_all = evaluate_organism()
        produce_next_generation()
        generation += 1

    finish_time = datetime.datetime.now()
    print('Program terminated after {} generations.\nTime Taken : {} seconds'.format(generation, finish_time-start_time))

Answer 1

This looks a bit like a code smell:

Chromosome(Chromosome.get_new_random_genes())

You are using the static method of the class to return something from which you can construct a new instance. There is already something like that and they are called classmethods.

I would also rename your class, because it is not actually a chromosome, it is an organism:

GENES = string.ascii_uppercase + string.ascii_lowercase

class Organism:
    mutation_rate = 0.001

    def __init__(self, genes):
        self.genes = genes

    def fitness(self, ideal):
        return sum(self_gene == ideal_gene
                   for self_gene, ideal_gene in zip(self.genes, ideal.genes))

    def __str__(self):
        return self.genes

    @classmethod
    def from_random_genes(cls, target_length):
        return cls(''.join(random.choices(GENES, k=target_length)))

    @classmethod
    def from_parents(cls, parent1, parent2):
        cross_over_point = random.randrange(0, len(parent1.genes))
        new_genes = list(parent1.genes[:cross_over_point] + parent2.genes[cross_over_point:])
        for i, _ in enumerate(new_genes):
            if random.randint(0, int(1 / cls.mutation_rate)) == 0:
                new_genes[i] = random.choice(GENES)
        return cls(''.join(new_genes))

I also changed your variable names to conform to Python's official style-guide, PEP8, which recommends using lower_case. It also recommends not doing multiple imports in a single line.

In addition I made the possible genes a constant and used random.choices, which was introduced in Python 3.6 to generate multiple genes at once.

After this, I noticed that generating a new organism from two parents is not so different from generating a random one, so that should also be a classmethod. Additionally it would be nice if we could look at an organism and see its genes, so I also added a __str__ method.

---

In general you should avoid global variables, they make a script very hard to reason about. Try to make all your functions self-sufficient and take any dependency as an argument.

You currently have comments above some of your functions describing what they do. These should become docstrings instead.

In addition, your logic is a bit weird. Normally fitness is a GoodThing™, so you want it to increase, not reach zero. In addition it is sufficient if one organism has found the target, no need for the whole population to be the target.

With that being said, let's go through the other functions one by one:

def create_initial_generation(population_size, target_length):
    return [Organism.from_random_genes(target_length) for _ in range(population_size)]

def evaluate_organisms(organisms, ideal_organism):
    return [organism.fitness(ideal_organism) for organism in organisms]

These functions no longer uses global. The first one also takes advantage of the different class structure. Both use list comprehensions, instead of manual for loops.

def produce_next_generation(current_generation, fitness):
    """A utility function to perform crossover."""
    next_generation = []
    for _ in range(len(current_generation)):
        # select two parents using Roulette Wheel Sampling
        parent1 = current_generation[select_parent(fitness)]
        parent2 = current_generation[select_parent(fitness)]
        next_generation.append(Organism.from_parents(parent1, parent2))
    return next_generation

This function also takes advantage of a new classmethod of Organism. The actual cross-over is implemented there, so this is just a simple wrapper around doing this multiple times.

The select_parent function is also dramatically changed, by using itertools:

from itertools import dropwhile, accumulate, count

def select_parent(fitness):
    """A utility function that decide which parent to select for crossover.

    Based on Roulette Wheel Sampling
    """
    pick = random.randint(0, sum(fitness))
    return next(dropwhile(lambda x: x[1] < pick, enumerate(accumulate(fitness))))[0]

This does just what it says when you read it in English: "Take the next element of the enumerated and accumulated fitness, where all elements are dropped as long as the accumulated fitness is less than the pick value. Choose the index from that element."

Note that the itertools.accumulate function was only introduced in Python 3.6.

And finally for the calling code. This I would also encapsulate into a function that just takes the target string as input:

def break_pw_genetic(target):
    population_size = 10 * len(target)
    ideal_organism = Organism(target)
    current_generation = create_initial_generation(population_size, len(target))
    for generation in count():
        fitness = evaluate_organisms(current_generation, ideal_organism)
        # print(max(fitness), max(current_generation, key=lambda organism: organism.fitness(ideal_organism)))
        if max(fitness) == len(target):
            break
        current_generation = produce_next_generation(current_generation, fitness)
    return generation

if __name__ == '__main__':
    start_time = datetime.datetime.now()
    generation = break_pw_genetic('Brevityisthesoulofwit')
    duration = datetime.datetime.now() - start_time

    print(f'Program terminated after {generation} generations.')
    print(f'Time Taken: {duration} seconds')

In the printing I used the f-strings which were also introduced in Python 3.6.

---

One thing to note, though, is that this is of course completely useless for cracking passwords, because it requires you to already know the password.

---

All together this gives:

import random
import datetime
import string
from itertools import dropwhile, accumulate, count

GENES = string.ascii_uppercase + string.ascii_lowercase

class Organism:
    mutation_rate = 0.001

    def __init__(self, genes):
        self.genes = genes

    def fitness(self, ideal):
        return sum(self_gene == ideal_gene
                   for self_gene, ideal_gene in zip(self.genes, ideal.genes))

    def __str__(self):
        return self.genes

    @classmethod
    def from_random_genes(cls, target_length):
        return cls(''.join(random.choices(GENES, k=target_length)))

    @classmethod
    def from_parents(cls, parent1, parent2):
        cross_over_point = random.randrange(0, len(parent1.genes))
        new_genes = list(parent1.genes[:cross_over_point] + parent2.genes[cross_over_point:])
        for i, _ in enumerate(new_genes):
            if random.randint(0, int(1 / cls.mutation_rate)) == 0:
                new_genes[i] = random.choice(GENES)
        return cls(''.join(new_genes))


def create_initial_generation(population_size, target_length):
    return [Organism.from_random_genes(target_length) for _ in range(population_size)]


def evaluate_organisms(organisms, ideal_organism):
    return [organism.fitness(ideal_organism) for organism in organisms]


def select_parent(fitness):
    """A utility function that decide which parent to select for crossover.

    Based on Roulette Wheel Sampling
    """
    pick = random.randint(0, sum(fitness))
    return next(dropwhile(lambda x: x[1] < pick, enumerate(accumulate(fitness))))[0]


def produce_next_generation(current_generation, fitness):
    """A utility function to perform crossover."""
    next_generation = []
    for _ in range(len(current_generation)):
        # select two parents using Roulette Wheel Sampling
        parent1 = current_generation[select_parent(fitness)]
        parent2 = current_generation[select_parent(fitness)]
        next_generation.append(Organism.from_parents(parent1, parent2))
    return next_generation

def break_pw_genetic(target):
    population_size = 10 * len(target)
    ideal_organism = Organism(target)
    current_generation = create_initial_generation(population_size, len(target))
    for generation in count():
        fitness = evaluate_organisms(current_generation, ideal_organism)
        # print(max(fitness), max(current_generation, key=lambda organism: organism.fitness(ideal_organism)))
        if max(fitness) == len(target):
            break
        current_generation = produce_next_generation(current_generation, fitness)
    return generation

if __name__ == '__main__':
    start_time = datetime.datetime.now()
    generation = break_pw_genetic('Brevityisthesoulofwit')
    duration = datetime.datetime.now() - start_time

    print(f'Program terminated after {generation} generations.')
    print(f'Time Taken: {duration} seconds')