为什么所有生成的种群都变得相同？

Question

所以我在做遗传算法，其中最合适的染色体是全1的染色体[1,1,1,1…]。我在调试时对下面的代码进行了编码，我发现交叉、变异、生成_种群是有效的，我对其他函数的代码进行了检查，它们都是有意义的。但每当我运行它时，我发现在第二代或第三代之后，我的所有其他代人都是一样的。所以我的问题是，为什么会发生这种情况，因为我仔细阅读了我的代码，每一代人都应该有一个不同的和“更适合”的群体，每个群体之间应该有多样性。任何帮助都将不胜感激result image

import random

def generate_population(size):
    population = []
    for i in range(size):
        individual = []
        for g in range(64):
          x = random.randrange(0,2)
          individual.append(x)
        population.append(individual)
    return population

def fitnessFunc(individual):
  fit = 0
  for i in individual:
    if i == 1:
      fit += 1
    else:
      fit = fit 
  return fit


def choice_by_roulette(sorted_population, fitness_sum):
    offset = 0
    normalized_fitness_sum = fitness_sum
    lowest_fitness = fitnessFunc(sorted_population[0])
    if lowest_fitness < 0:
        offset = lowest_fitness
        normalized_fitness_sum += offset * len(sorted_population)

    draw = random.uniform(0, 1)

    accumulated = 0
    for individual in sorted_population:
        fitness = fitnessFunc(individual)+offset
        probability = fitness / normalized_fitness_sum
        accumulated += probability

        if draw <= accumulated:
            return individual

def sort_population_by_fitness(population):
    return sorted(population, key=fitnessFunc)

def crossover(individual_a, individual_b):
  for i in range(64):
    pop = random.randint(1,2)
    if pop == 1:
      individual_a[i] = individual_b[i]
    else:
      individual_a = individual_a
  return individual_a

def mutate(individual):
    rand = random.randrange(0,10)
    if rand == 5:
      if individual[rand]==1:
        individual[rand]=0
      else:
        individual[rand]=1
    return individual

def make_next_generation(previous_population):
    next_generation = []
    sorted_by_fitness_population = sort_population_by_fitness(previous_population)
    population_size = len(previous_population)
    fitness_sum = sum(fitnessFunc(individual) for individual in population)
    for i in range(population_size):
        choice = choice_by_roulette(sorted_by_fitness_population, fitness_sum)
        schoice = choice_by_roulette(sorted_by_fitness_population, fitness_sum)
        if choice != None:
          first_choice = choice
        if schoice != None:
          second_choice = schoice
        individual = crossover(first_choice, second_choice)
        individual = mutate(individual)
        next_generation.append(individual)
    return next_generation


population = generate_population(size=10)
generations = 1000

i = 1
while True:
    print(f" GENERATION {i}")

    for individual in population:
        print(individual, fitnessFunc(individual))
    if i == generations:
        break
    i += 1
    population = make_next_generation(population)

best_individual = sort_population_by_fitness(population)[-1]
print(" FINAL RESULT")
print(best_individual, fitnessFunc(best_individual))

Answer 1

我发现了三个主要问题。我将尝试将其分解，但由于我不完全确定预期结果是什么，因此很难确定应该如何进行

问题1：交叉功能在创建下一代的同时“原地”变异父代。这意味着约25%的父母基因将向其他父母基因组突变

问题2：make_next_generation（）无法确保将两个不同的个体发送到交叉。这有时会导致个人一成不变地传给下一代

问题3：突变（个体）只影响64个基因中的一个。（非故意猜测）

import random


def generate_individual():
    # Use list comprehensions
    return [random.randrange(0,2) for g in range(64)]


def generate_population(size):
    # Same result, only less code
    return [generate_individual() for i in range(size)]

def fitnessFunc(individual):
  # Yes, this line does the same work.
  return sum(individual)
  # fit = 0
  # for i in individual:
  #   if i == 1:
  #     fit += 1
  # The following two lines did nothing
  #   else:
  #     fit = fit 
  # return fit

轮盘赌（）的选择确实存在问题。但我不知道该怎么做。评论如下

def choice_by_roulette(sorted_population, fitness_sum):
    offset = 0
    normalized_fitness_sum = fitness_sum
    lowest_fitness = fitnessFunc(sorted_population[0])
    # Lower than 0? fitnessFunc() will never return that.
    # Could it be lowest_fitness > 0?
    if lowest_fitness < 0:
        offset = lowest_fitness
        normalized_fitness_sum += offset * len(sorted_population)

    draw = random.random()

    accumulated = 0
    for individual in sorted_population:
        fitness = fitnessFunc(individual)+offset
        probability = fitness / normalized_fitness_sum
        accumulated += probability

        if draw <= accumulated:
            return individual

def sort_population_by_fitness(population):
    return sorted(population, key=fitnessFunc)

交叉不应突变老个体（？）。由于同一个体可能会被挑选不止一次，因此在同一代中，它们会向另一个体变异约50%。这可能是你最大的问题

def crossover(individual_a, individual_b):
  for i in range(64):
    pop = random.randint(1,2)
    if pop == 1:
      individual_a[i] = individual_b[i]
    else:
      individual_a = individual_a
  return individual_a

我的建议是：

def crossover(individual_a, individual_b):
  return [random.choice(genes) for genes in zip(individual_a, individual_b)]

在这里，你不需要归还任何东西。你实际上是在原地变异个体。而且，只有基因5可以变异，但也许应该是这样

def mutate(individual):
    rand = random.randrange(0,10)
    if rand == 5:
      individual[rand] = 1 - individual[rand]  # Toggle: 1-0=1, 1-1=0
      # if individual[rand]==1:
      #   individual[rand]=0
      # else:
      #   individual[rand]=1

def make_next_generation(previous_population):
    next_generation = []
    sorted_by_fitness_population = sort_population_by_fitness(previous_population)
    population_size = len(previous_population)
    fitness_sum = sum(fitnessFunc(individual) for individual in population)
    for i in range(population_size):
        choice = choice_by_roulette(sorted_by_fitness_population, fitness_sum)
        schoice = choice_by_roulette(sorted_by_fitness_population, fitness_sum)
        # This code will not work. first_choice will be user without being declared below if any of there are None.
        # if choice != None:
        #   first_choice = choice
        # if schoice != None:
        #   second_choice = schoice
        # choice and schoice will sometimes be the same individual. That will definitely diminish the genetic diversity.
        while choice == schoice:
            schoice = choice_by_roulette(sorted_by_fitness_population, fitness_sum)
        individual = crossover(choice, schoice)
        mutate(individual)
        next_generation.append(individual)
    return next_generation


population = generate_population(size=10)
generations = 1000

for i in range(1, generations+1):
    print(f" GENERATION {i}")
    for individual in population:
        print(individual, fitnessFunc(individual))
    population = make_next_generation(population)

best_individual = sort_population_by_fitness(population)[-1]
print(" FINAL RESULT")
print(best_individual, fitnessFunc(best_individual))