Source: Dev.to

使用遗传算法求解 XOR（不使用反向传播）

简介

在神经网络的学习中，反向传播（Backpropagation）是最常见的训练方法。然而，对于一些非常小且结构简单的问题，例如经典的 XOR（异或）逻辑门，我们可以尝试使用 遗传算法（Genetic Algorithm, GA） 来寻找合适的权重，而不必依赖梯度下降。本文将展示如何使用遗传算法来训练一个单隐藏层的前馈神经网络，使其能够正确实现 XOR 功能。

XOR 问题回顾

XOR 是一个 非线性 问题，单层感知机无法解决。我们需要至少一个隐藏层（通常使用 2 个隐藏神经元）来实现它。

遗传算法概述

遗传算法是一种基于自然选择的全局优化方法，主要步骤包括：

1. 初始化种群：随机生成若干个候选解（即网络权重向量）。
2. 适应度评估：计算每个候选解在 XOR 数据集上的误差（如均方误差）。
3. 选择：根据适应度挑选出较好的个体进行繁殖。
4. 交叉（Crossover）：将父代的基因片段进行交换，产生子代。
5. 变异（Mutation）：对部分基因进行小幅随机扰动，保持种群多样性。
6. 迭代：重复 2~5 步，直到满足终止条件（误差低于阈值或达到最大代数）。

网络结构与基因编码

我们使用以下网络结构：

• 输入层：2 个神经元（对应 XOR 的两个输入）
• 隐藏层：2 个神经元，激活函数使用 Sigmoid
• 输出层：1 个神经元，激活函数同样使用 Sigmoid

权重总数：

• 输入 → 隐藏：2 × 2 = 4
• 隐藏层偏置：2
• 隐藏 → 输出：2 × 1 = 2
• 输出层偏置：1

总计 9 个实数。在遗传算法中，这 9 个实数即为 基因（chromosome），每个基因用一个浮点数表示。

Python 实现

下面的代码展示了完整的 GA 流程。代码块保持原样，不进行翻译。

import numpy as np
import random

# ---------- 参数 ----------
POP_SIZE = 200          # 种群规模
NUM_GENERATIONS = 5000  # 最大代数
MUTATION_RATE = 0.1
CROSSOVER_RATE = 0.7
ELITE_COUNT = 5         # 每代保留的精英个体

# ---------- XOR 数据 ----------
X = np.array([[0, 0],
              [0, 1],
              [1, 0],
              [1, 1]])
y = np.array([[0],
              [1],
              [1],
              [0]])

# ---------- 激活函数 ----------
def sigmoid(x):
    return 1 / (1 + np.exp(-x))

def forward_pass(chromosome, X):
    # 解码基因
    w1 = chromosome[0:4].reshape((2, 2))   # 输入→隐藏权重
    b1 = chromosome[4:6].reshape((1, 2))   # 隐藏层偏置
    w2 = chromosome[6:8].reshape((2, 1))   # 隐藏→输出权重
    b2 = chromosome[8]                     # 输出层偏置

    # 前向传播
    hidden = sigmoid(np.dot(X, w1) + b1)
    output = sigmoid(np.dot(hidden, w2) + b2)
    return output

# ---------- 适应度函数 ----------
def fitness(chromosome):
    output = forward_pass(chromosome, X)
    # 均方误差（MSE）
    mse = np.mean((y - output) ** 2)
    # 适应度越大越好，取倒数
    return 1 / (mse + 1e-6)

# ---------- 初始化种群 ----------
def init_population():
    # 权重初始化为 [-1, 1] 区间的随机数
    return [np.random.uniform(-1, 1, 9) for _ in range(POP_SIZE)]

# ---------- 选择 ----------
def select(population, fitnesses):
    # 轮盘赌选择（概率与适应度成正比）
    total_fitness = sum(fitnesses)
    probs = [f / total_fitness for f in fitnesses]
    selected_idx = np.random.choice(len(population), size=POP_SIZE, p=probs)
    return [population[i] for i in selected_idx]

# ---------- 交叉 ----------
def crossover(parent1, parent2):
    if random.random() > CROSSOVER_RATE:
        return parent1.copy(), parent2.copy()
    point = random.randint(1, len(parent1) - 2)
    child1 = np.concatenate([parent1[:point], parent2[point:]])
    child2 = np.concatenate([parent2[:point], parent1[point:]])
    return child1, child2

# ---------- 变异 ----------
def mutate(chromosome):
    for i in range(len(chromosome)):
        if random.random() < MUTATION_RATE:
            chromosome[i] += np.random.normal(0, 0.1)  # 加上小的高斯噪声
    return chromosome

# ---------- 主循环 ----------
def genetic_algorithm():
    population = init_population()
    best_chromosome = None
    best_fitness = -np.inf

    for gen in range(NUM_GENERATIONS):
        fitnesses = [fitness(ind) for ind in population]

        # 记录当前最优
        max_idx = np.argmax(fitnesses)
        if fitnesses[max_idx] > best_fitness:
            best_fitness = fitnesses[max_idx]
            best_chromosome = population[max_idx].copy()
            # 当误差足够小（适应度足够大）时提前终止
            if 1 / best_fitness < 1e-4:
                print(f"在第 {gen} 代找到满意解！")
                break

        # 精英保留
        elite_idxs = np.argsort(fitnesses)[-ELITE_COUNT:]
        elites = [population[i].copy() for i in elite_idxs]

        # 选择
        selected = select(population, fitnesses)

        # 产生新一代
        next_population = elites.copy()
        while len(next_population) < POP_SIZE:
            p1, p2 = random.sample(selected, 2)
            c1, c2 = crossover(p1, p2)
            next_population.append(mutate(c1))
            if len(next_population) < POP_SIZE:
                next_population.append(mutate(c2))

        population = next_population

        if gen % 500 == 0:
            print(f"代数 {gen}: 最佳适应度 = {best_fitness:.6f}")

    return best_chromosome

# ---------- 运行 ----------
best = genetic_algorithm()
print("\n=== 最佳权重 ===")
print(best)

# 验证结果
pred = forward_pass(best, X)
print("\nXOR 预测结果（四舍五入到小数点后两位）:")
print(np.round(pred, 2))

结果分析

运行上述脚本后，你会看到类似以下的输出（实际数值会因随机种子不同而略有差异）：

代数 0: 最佳适应度 = 1.234567
代数 500: 最佳适应度 = 45.678901
...
在第 2371 代找到满意解！

=== 最佳权重 ===
[ 5.12 -3.87  2.45 -1.09  0.78 -0.34  8.21 -6.33  0.12]

XOR 预测结果（四舍五入到小数点后两位）:
[[0.01]
 [0.99]
 [0.98]
 [0.02]]

可以看到，网络在四个输入组合上几乎完美地逼近了目标输出，误差已经低于 1e-4，这说明遗传算法成功地找到了能够实现 XOR 功能的权重集合。

优缺点对比

对于 小型、结构固定 的问题（如本例的 XOR），遗传算法是一种有趣且易于实现的替代方案。但在实际的深度学习任务中，仍然建议使用基于梯度的优化方法。

结论

本文演示了如何使用遗传算法来训练一个最小的前馈神经网络，使其能够解决 XOR 逻辑门问题，而无需使用传统的反向传播。通过对权重进行编码、定义适应度函数、并执行选择、交叉和变异操作，我们成功地在数千代内找到了满足误差阈值的解。

如果你对 进化计算 或 神经网络的非梯度训练 感兴趣，可以进一步尝试：

• 调整种群规模、交叉率和变异率，以观察对收敛速度的影响；
• 将网络扩展到更复杂的布尔函数（如 XNOR、奇偶校验）；
• 使用 多目标遗传算法 同时优化网络精度和模型大小。

祝你玩得开心，探索更多进化算法在机器学习中的可能性！

Introduction

我们通常在训练神经网络时听到反向传播和梯度下降。它们是行业标准，是“微积分”式的学习方式。
但是，如果我们退一步，看看自然是如何学习的呢？在本文中，我们使用遗传算法（GA）来解决经典的 XOR 问题（单个神经元无法解决的问题）。不计算梯度；我们模拟“适者生存”。

XOR问题

XOR（异或）门是一个非线性问题。简单的线性直线无法将其输出分离，因此需要神经网络。

遗传算法概述

在 GA 中，我们将神经网络视为种群中的 个体。

• 适应度 – 网络解决 XOR 的效果（误差的倒数）。
• 选择 – 最好的网络进行繁殖。
• 交叉 – 我们混合两个父代的权重。
• 变异 – 添加随机噪声以保持基因多样性。

Python 实现

注意: 此代码假设你已有一个基本的 NeuralNetwork 类，具备 .forward() 方法以及权重矩阵 W1、W2 等。

适应度计算

import numpy as np
from basic_neural_network import NeuralNetwork

def calculate_fitness(nn):
    """
    Measures the XOR performance of the network.
    The lower the error, the higher the fitness (score).
    """
    X_xor = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
    y_target = np.array([[0], [1], [1], [0]])

    predictions = nn.forward(X_xor)
    mse = np.mean((y_target - predictions) ** 2)  # Mean Squared Error

    # Add a tiny constant to avoid division by zero
    return 1 / (mse + 1e-9)

突变

def mutate(nn, mutation_rate=0.1, strength=0.5):
    """
    Adds random noise to the network's weights.
    """
    parameters = [nn.W1, nn.b1, nn.W2, nn.b2, nn.W3, nn.b3]

    for param in parameters:
        if np.random.rand() < mutation_rate:
            # Add random Gaussian noise
            noise = np.random.randn(*param.shape) * strength
            param += noise

交叉

def crossover(parent1, parent2):
    """
    Produces a child by averaging two parents' weights.
    """
    child = NeuralNetwork()
    child.W1 = (parent1.W1 + parent2.W1) / 2
    child.b1 = (parent1.b1 + parent2.b1) / 2
    child.W2 = (parent1.W2 + parent2.W2) / 2
    child.b2 = (parent1.b2 + parent2.b2) / 2
    child.W3 = (parent1.W3 + parent2.W3) / 2
    child.b3 = (parent1.b3 + parent2.b3) / 2
    return child

主进化循环

# --- MAIN LOOP ---

population_size = 50
population = [NeuralNetwork() for _ in range(population_size)]
generation_count = 1000

print("Evolution starting...")

for gen in range(generation_count):
    # Evaluate fitness and sort (highest score first)
    population = sorted(population, key=lambda x: calculate_fitness(x), reverse=True)

    best_individual = population[0]
    best_error = 1 / calculate_fitness(best_individual)

    if gen % 100 == 0:
        print(f"Gen {gen}: Lowest Error (MSE): {best_error:.5f}")
        if best_error < 0.001:
            print("Solution found!")
            break

    # Create new generation (elitism + crossover)
    new_population = []

    # Keep top 5 individuals unchanged (elitism)
    new_population.extend(population[:5])

    # Fill the rest by breeding top performers
    while len(new_population) < population_size:
        parent1 = population[np.random.randint(0, 10)]  # top 20%
        parent2 = population[np.random.randint(0, 10)]

        child = crossover(parent1, parent2)
        mutate(child, mutation_rate=0.3, strength=0.2)
        new_population.append(child)

    population = new_population

最终测试

print("\n--- Training Complete ---")
X_test = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
result = population[0].forward(X_test)

print("XOR Inputs:")
print(X_test)
print("Trained Network Predictions:")
print(np.round(result, 3))

为什么使用遗传算法而不是反向传播？

• 稀疏奖励： 在许多问题中，你只能在最后知道结果（例如，赢得游戏）。
• 不可微分领域： 离散逻辑或复杂的物理仿真可能无法提供可用的梯度。

结论

进化方法可以解决梯度基方法难以应对的问题。你尝试过进化代码吗？在评论中分享你的经验吧！祝编码愉快！ 🚀