python - 在遗传算法中找到目标数字的好的选择函数是什么？

Question

我正在编写一个遗传算法来找到一个表达目标数字的表达式，即如果目标数字是 10，则解决方案可能是 2*5。我遇到了这样一种情况，即我的整个种群都变成一条相同的染色体，我认为适应度函数负责这一点。

以下是可能的染色体，遵循数字和运算符交替出现在字符串中的规则，任何两个数字或两个运算符都不相邻。合法的字符串将以数字或 +/- 运算符开头。表达式将按原样从左到右计算(忽略算术运算的顺序):

• 1/2+3+5
• -2+4+1+8
• -7+6*2+8
• +2/5-1+8 2+1*2-2
• +2*7*7+3
• +1/2/2/6 5/5*9*1
• +3-1+1*8 3-8+7*1

选择():

    def selection(population):
        total_finesses = Decimal(0.0)

        # Roulette selection:
        for chromosome in population:
            total_finesses += chromosome .fitness
        # Generate random number (spin the roulette).
        pick = Decimal(random.uniform(0, float(total_finesses)))
        current = Decimal(0.0)

        for i, chrom in enumerate(population):
            current += chrom.fitness
            if current > pick:
                return population[i]

健身():

    def fitness_calculator(chromosome):
        current_value = get_value(chromosome) # Returns the decimal value of the chromosome.

        return Decimal(-1 * (abs(target - current_value), 5))

如您所见，适应度越接近 0 越好，因为我正在寻找表达自身与目标数之间增量最小的数字的表达式。

我认为我的选择算法有问题，以轮盘赌的方式选择最低适合的染色体。

Answer 1

我在 computer science stackexchange 上回答了一个类似的问题 here它以最好的方式解释了如何找到适合您的问题的选择方法。

然而，看起来您并没有实现负责维持种群多样性的突变；所以你可能会考虑以某种方式实现它。可以找到几种方法here .

@TomDalton 在对您的问题的评论中也提出了一些公平的观点。如果你的池中有几个相同的解决方案导致了问题，请不要允许它。此外，随机选择很少是一个好主意，而且通常会使评估函数变得无用。您的评估函数对池中的解决方案进行排名。用它!有些方法说采用最好的解决方案并将它们结合起来使最好的变得更好；和其他人说采取最坏的解决方案来保持所有解决方案相当不错。除此之外，还有大量其他可能的选择方法可供您选择。

我的最后一点是(尽管它可能不直接适用于您，但可能会帮助最终进入此线程的人)在查看 GA 时，微调的初始种群大小通常被低估。确保您也尝试了一些变体。

阅读 Material :

Miller, B. L., & Goldberg, D. E. (1995)。遗传算法、锦标赛选择和噪声的影响。复杂系统，9(3)，193-212。

Goldberg, D. E., & Deb, K. (1991)。遗传算法中使用的选择方案的比较分析。厄巴纳，51 岁，61801-2996。

Poon, P. W., & Carter, J. N. (1995)。用于排序应用程序的遗传算法交叉运算符。计算机与运筹学，22(1)，135-147。