基于遗传算法寻找分隔两类点的指定阶数多项式曲线

我来分享下针对这个多项式分类边界问题的遗传算法设计思路和核心实现要点，刚好之前做过类似的分类拟合任务，应该能帮到你：

1. 染色体编码方案 #

我们的核心目标是求解多项式的系数，假设输入的阶数为k，那么目标多项式的形式为：
y = a_k x^k + a_{k-1} x^{k-1} + ... + a_1 x + a_0

这里的每个系数a_k, a_{k-1}, ..., a_0就是组成染色体的基因，将这些系数按阶数从高到低排列，就构成了一条完整的染色体。比如输入阶数为3时，染色体就是[A, B, C, D]，对应多项式y = A x³ + B x² + C x + D。

• 每个基因（系数）建议用浮点数表示，初始范围可以根据你的数据集坐标分布预先设定（比如先尝试[-100, 100]，后续根据适应度表现调整）。

2. 适应度函数设计 #

这是算法的核心，必须精准惩罚不满足分类条件的情况，同时鼓励边界与点保持合理距离（避免过拟合）。假设：

• 第一类点集合为P1 = {(x_i, y_i) | i=1..m}，要求所有点满足y_i > f(x_i)（f(x)为当前染色体对应的多项式）
• 第二类点集合为P2 = {(x_j, y_j) | j=1..n}，要求所有点满足y_j < f(x_j)

适应度函数可以这么设计：

def calculate_fitness(chromosome, P1, P2, order):
    # 将染色体转换为多项式计算函数
    def f(x):
        result = 0
        # 按阶数从低到高计算（对应染色体从后到前的系数）
        for idx, coeff in enumerate(reversed(chromosome)):
            result += coeff * (x ** idx)
        return result
    
    fitness_score = 0
    penalty_weight = 10  # 惩罚权重，可根据数据集调整

    # 处理第一类点：满足条件则加奖励，否则重罚
    for (x, y) in P1:
        diff = y - f(x)
        if diff <= 0:
            fitness_score -= abs(diff) * penalty_weight
        else:
            fitness_score += diff  # 奖励点与曲线的距离
    
    # 处理第二类点：满足条件则加奖励，否则重罚
    for (x, y) in P2:
        diff = f(x) - y
        if diff <= 0:
            fitness_score -= abs(diff) * penalty_weight
        else:
            fitness_score += diff
    
    return fitness_score

注：惩罚权重和奖励规则可以根据你的数据集调整，比如如果大部分点都满足分类条件，可以加大对“距离过近”的惩罚，或者增加正则项避免系数过大导致曲线波动剧烈。

3. 核心遗传操作实现 #

选择操作 #

推荐用锦标赛选择，比轮盘赌选择更稳定，不容易陷入局部最优：

• 随机从种群中选取k个个体（比如k=3），挑选其中适应度最高的个体作为父代。

交叉操作 #

因为是浮点数编码的染色体，用算术交叉最合适：
比如两个父代染色体parent1 = [a1, a2, ..., an]和parent2 = [b1, b2, ..., bn]，随机生成一个α ∈ [0,1]，子代染色体为：
[α*a1 + (1-α)*b1, α*a2 + (1-α)*b2, ..., α*an + (1-α)*bn]

变异操作 #

对染色体中的随机基因进行小幅扰动，避免种群同质化：

• 随机选择一个基因位置，将其值加上一个服从正态分布的随机数（比如均值为0，标准差为0.5，可根据情况调整），同时确保变异后的系数在预设的范围内（比如[-100, 100]）。

4. 完整算法流程 #

1. 初始化种群：随机生成N条染色体（N根据计算资源调整，比如50-200）。
2. 计算适应度：对种群中每个个体计算适应度得分。
3. 迭代进化：重复以下步骤直到满足终止条件：
   • 选择父代个体生成交配池。
   • 对交配池中的个体进行交叉操作生成子代。
   • 对子代进行变异操作。
   • 替换种群中的低适应度个体（比如保留前20%的高适应度个体，剩下的用子代替换）。
4. 输出结果：迭代结束后，选择适应度最高的染色体，转换为对应的多项式格式输出。

5. 实操注意事项 #

• 初始种群的系数范围要匹配数据集的坐标范围，如果你的点坐标都很小，就不要把系数设得过大，避免一开始生成的曲线完全偏离数据。
• 终止条件可以结合两种规则：比如最大迭代次数设为1000，同时如果连续50代适应度提升小于0.01就提前停止。
• 如果出现多个适应度接近的优秀个体，可以取它们的系数平均值作为最终结果，提升模型的稳定性。

内容的提问来源于stack exchange，提问作者Lew Winczynski