python - 精英主义在遗传算法中的失败

Question

我正在尝试运行我用 Python 编写的遗传算法。不幸的是，当发生突变时，尽管使用精英主义将上一代的最适应解决方案传递给新一代，但最适应解决方案可能比上一代的最适应解决方案更糟糕。像这样:

There are 86825 generations left
Invalid count is:  0
The fittest individual has a fitness of 16.9094. 
The least fit individual has a fitness  of 36.6535
*******************************************************************************
mutation on 107
There are 86824 generations left
Invalid count is:  3
The fittest individual has a fitness of 19.8637. 
The least fit individual has a fitness of 1.1618e+09

我曾尝试实现精英主义，我认为这可以避免这种情况发生，但它仍然发生了。我的算法按以下顺序执行:

NUM_GEN = 100000
print "Running Genetic Algorithm for %d generations." % NUM_GEN
gen_count = 0
while gen_count < NUM_GEN:
    #genetic.add_fitness_key()
    genetic.add_fitness_fast()
    fittest_list = np.append(fittest_list, genetic.fittest_fitness)
    least_fit_list = np.append(least_fit_list, genetic.least_fitness)
    genetic.sort_pop()
    genetic.make_new_pop()
    genetic.elitism()
    genetic.population = genetic.new_pop
    print "There are %g generations left" %(NUM_GEN-gen_count) 
    gen_count+=1

调用的函数是:

def select_parent_from_tournament(self):
    x = random.randint(0, 19)
    player1 = self.population[x]
    y = random.randint(0, 19)
    player2 = self.population[y]
    if player1['fitness'] <= player2['fitness']:
        parent = player1['chrom_list']
    else:
        parent = player2['chrom_list']
    return parent

def crossover(self):
    crossover_point = random.randint(0, self.chromosome_size)*(self.string_length)
    parent1 = self.select_parent_from_tournament()
    parent2 = self.select_parent_from_tournament()
    parent1 = self.mutate(parent1)
    parent2 = self.mutate(parent2)
    child1 = parent1[:crossover_point] + parent2[crossover_point:]
    child2 = parent1[crossover_point:] + parent2[:crossover_point]
    return child1, child2

def mutate(self, chromosome):
    for i in range(len(chromosome)):
        if random.random() < self.mutation_rate:
            print 'mutation on %i' % i
            if chromosome[i] =='0':
                chromosome[i] = '1'
            else:
                chromosome[i] = '0'
    return chromosome

def make_new_pop(self):
    self.new_pop = []
    for i in range(10):
        dictionary1= {}
        dictionary2 = {}
        dictionary1['chrom_list'], dictionary2['chrom_list'] = \
        self.crossover()
        self.new_pop = np.append(self.new_pop, [dictionary1, dictionary2])

def elitism(self):
    r = random.randint(0, 19)
    self.new_pop[r] = self.population[0]

所以我不明白为什么如果发生突变，旧种群中的最适解不会传递给新种群？

Answer 1

在您的交叉方法中，您执行 parent1 = self.select_parent_from_tournament() 返回对原始种群染色体列表的引用。之后，您进行修改列表(在原始群体中)的突变。只有在突变之后，您才能通过 child1 = parent1[:crossover_point] + parent2[crossover_point:] 复制子项中的内容。正如@Xavier 建议的那样，您需要从 mutation() 中的原始群体创建元素的物理副本。

实际上，您的 mutation() 方法改变了原始种群。

作为旁注，通常交叉和变异是两种不同的操作。此外，文献中的引用文献表明突变概率应保持在非常低的水平。否则它会让你无法收敛。