那个遗传算法的继续改进

Garfileo posted @ 2011年2月20日 07:12 in 业余程序猿的足迹 with tags 遗传算法 , 5366 阅读

想了一下，还是决定把种群的最佳个体从历史课本里拿出来，用它来替换每一代种群中最差的个体。虽然这样做容易导致局部最优个体的基因片段会急速增加从而使进化有可能限于局部解，但是我们可以通过增大变异概率的方法来提高种群中个体染色体的多样性来帮助种群跳离局部最优。

因此，可将 reproduct_elitist 函数修改为：

# 修改后的 Population 类成员函数 reproduct_elitist () 

    def reproduct_elitist (self):
        # 与当前种群进行适应度比较，更新最佳个体
        j = -1
        for i in range (self.size):
            if self.elitist['fitness'] < self.fitness[i]:
                j = i
                self.elitist['fitness'] = self.fitness[i]
        if (j >= 0):
            self.elitist['chromosome'][0] = self.individuals[j][0]
            self.elitist['chromosome'][1] = self.individuals[j][1]
            self.elitist['age'] = self.age

        # 用当前最佳个体替换种群新个体中最差者
        new_fitness = [self.fitness_func (v[0], v[1]) for v in  self.new_individuals]
        best_fitness = max (new_fitness)
        if self.elitist['fitness'] > best_fitness:
            # 寻找最小适应度对应个体
            j = 0
            for i in range (self.size):
                if best_fitness > new_fitness[i]:
                    j = i
                    best_fitness = new_fitness[i]
            # 最佳个体取代最差个体
            self.new_individuals[j][0] = self.elitist['chromosome'][0]
            self.new_individuals[j][1] = self.elitist['chromosome'][1]

另外，就是在种群进化过程中，不再对种群所包含个体数量进行偶数限制，因为那样太不自然了。我们只需将进化操作修改为：

# Population 类的成员函数 run () 修改后的代码片段

        # 进化操作
        i = 0
        while True:
            # 选择两名个体，进行交叉与变异，产生 2 名新个体
            idv1 = self.select ()
            idv2 = self.select ()
            
            # 交叉
            (idv1_x, idv1_y) = (indvs[idv1][0], indvs[idv1][1])
            (idv2_x, idv2_y) = (indvs[idv2][0], indvs[idv2][1])
            (idv1_x, idv2_x) = self.cross (idv1_x, idv2_x)
            (idv1_y, idv2_y) = self.cross (idv1_y, idv2_y)
            
            # 变异
            (idv1_x, idv1_y) = (self.mutate (idv1_x), self.mutate (idv1_y))
            (idv2_x, idv2_y) = (self.mutate (idv2_x), self.mutate (idv2_y))
            
            if random.randint (0, 1) == 0:
                (new_indvs[i][0], new_indvs[i][1]) = (idv1_x, idv1_y)
            else:
                (new_indvs[i][0], new_indvs[i][1]) = (idv2_x, idv2_y)
            
            # 判断进化过程是否结束
            i = i + 1
            if i >= self.size:
                break

这个策略可以这样描述：假设种群所包含的个体数量为 n，那么执行一个次数为 n 的循环。在每一轮循环中，使用遗传算法的个体选择函数从当前个体集合中选出 2 名个体，然后对其进行交叉和变异操作，从而产生 2 名新个体；对这 2 名新个体，采用随机的方法淘汰掉一个（就当它夭折了），然后将剩下的那名新个体添加到种群的新个体集合中。

采用这种方法，便可以不用考虑种群所包含个体的数量是偶数还是奇数了，并且还可以增加种群基因片段的数量。

事实上，对于每一轮循环所产生的 2 名新个体，我本来的打算是保留其中适应度较大的那个，但是尝试了一下，发现种群很快就被那些优秀个体的基因充满了，程序很快就收敛为一个局部最优解。还是随机选择比较合理。

改进后的程序通常可以很快收敛置全局最优解。例如，将种群所包含的个体数量设为 51，染色体长度设为 25，交叉概率设为 0.9，变异概率设为 0.4，最大进化世代设为 150，进化结果如下图所示：