title: genetic algorithm string guess
body: <p>I am trying to understand how to implement a genetic algorithm and wrote a simple string guess.  I am having trouble understanding why this solution is not working. </p>
  
  <p>I believe that my problem is in my populating my new generations?  The newest generations do not seem to have improved fitness values.  I am also not sure if I am doing the crossover and mutation rates correctly.  Any help would be really appreciated!</p>
  
  <pre><code>POP_SIZE = 300;
  CROSSOVER_RATE = 0.7;
  MUTATION_RATE = 0.01
  GENESET = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"
  target = "Hello World"
  RAND_NUM = random.random()
  
  def generateBasePopulation(population_size):
      population = dict()
  
      for _ in range(POP_SIZE):
          gene = generateParent(len(target))
          population[gene] = 0
  
      return population
  
  
  def generateNewPopulation(population, population_size):
      newPopulation = dict()
  
      while(len(newPopulation) &lt;= POP_SIZE):
          child_one, child_two = crossover(child_one, child_two)
          child_one = mutate(child_one)
          child_two = mutate(child_two)
  
  
      newPopulation[child] = 0
      newPopulation[child_two] = 0
      return newPopulation
  
  
  
  def assignFitness(population):
      for x in population:
          population[x] = getFitness(x)
  
  
  def generateParent(length):
      genes = list("")
      for i in range(0,length):
          random_gene = random.choice(GENESET)
          genes.append(random_gene)
      return(''.join(genes))
  
  def getFitness(candidate):
      fitness = 0
      for i in range(0, len(candidate) - 1):
          if target[i] == candidate[i]:
              fitness += 1
      return(fitness)
  
  def mutate(parent):
      gene_index_to_mutate = random.randint(0, len(parent) - 1)
      mutation_value = random.choice(GENESET)
      genes = list(parent)
      genes[gene_index_to_mutate] = mutation_value
      return(''.join(genes))
  
  def crossover(parentA, parentB):
      if(RAND_NUM &lt; CROSSOVER_RATE):
          random_index = random.randint(0, len(target))
          parentASlice = parentA[:random_index]
          parentBSlice = parentB[random_index:]
  
          return (parentASlice + parentBSlice), (parentBSlice + parentASlice)
      return parentA, parentB
  
  
  def chooseChild(population):
      fitnessSum = sum(population.values())
      pick = random.uniform(0, fitnessSum)
      current = 0
      for pop in population:
          current += population[pop]
          if current &gt;= pick:
              return pop
  
  
  def main():
      population = generateBasePopulation(POP_SIZE)
  
      targetNotFound = True
  
      while(targetNotFound):
          assignFitness(population)
          if target in population:
              print("target found!")
              targetNotFound = False
          if(targetNotFound):
              tempPopulation = generateNewPopulation(population, POP_SIZE)
              population.clear()
              population = tempPopulation
  </code></pre>