📖 第14课：人工生命演化

遗传算法 适应度 Tierra 开放演化

🧬 从自复制到演化——人工生命

自复制是第一步，但真正的生命还需要变异和选择。本课将达尔文演化论与CA结合，创建能在硬件中演化的"数字生命"。

Tierra：数字生态系统的先驱

1991年，Thomas Ray创建了Tierra——一个在计算机中运行的数字生态系统。程序（"生物"）在共享内存中竞争CPU时间和内存空间。令人惊讶的是：

• 最初的80条指令祖先在几小时内演化出79条、51条、甚至45条指令的"矮小"变体
• 出现了"寄生者"——无法自复制但利用他人复制代码的小程序
• 出现了对抗寄生者的"免疫"策略
• 出现了超寄生者和共生关系

⚡ 演化CA引擎

// ============================================================================
// evolving_ca.v - 带变异和选择的演化CA引擎
// 种群中的个体有不同的规则，适应度高的繁殖更多
// ============================================================================
module evolving_ca #(
    parameter POP_SIZE   = 16,        // 种群大小
    parameter GENOME_W   = 16,        // 基因组位宽（编码规则参数）
    parameter GRID_W     = 16,        // 每个个体的小网格宽度
    parameter GRID_H     = 16,        // 高度
    parameter MUTATION_RATE = 8       // 变异率：1/2^M
)(
    input  wire                          clk,
    input  wire                          rst_n,
    input  wire                          evolve_en,  // 演化使能
    input  wire                          init_pop,   // 初始化种群
    output wire [POP_SIZE*GENOME_W-1:0]  population, // 当前种群基因组
    output wire [POP_SIZE*31:0]          fitness,    // 适应度值
    output wire [31:0]                   generation  // 当前进化代数
);

    // ---- 种群存储 ----
    reg [GENOME_W-1:0] genomes [0:POP_SIZE-1];
    reg [31:0]         fit_vals [0:POP_SIZE-1];
    reg [31:0]         gen_cnt;

    // ---- 伪随机数生成器（用于变异和选择） ----
    reg [31:0] lfsr;
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n)
            lfsr <= 32'hDEADBEEF;
        else
            lfsr <= {lfsr[30:0], lfsr[31] ^ lfsr[21] ^ lfsr[1] ^ lfsr[0]};
    end

    // ---- 适应度评估 ----
    // 适应度 = 种群稳定后的活元胞数（简化版）
    // 实际应用中可以定义为：存活步数、产生的子代数、结构复杂度等
    integer i;
    always @(posedge clk) begin
        if (evolve_en) begin
            for (i = 0; i < POP_SIZE; i = i + 1) begin
                // 简化适应度：基因组中1的个数 × 伪随机权重
                fit_vals[i] = 32'd0;
                for (integer b = 0; b < GENOME_W; b = b + 1)
                    fit_vals[i] = fit_vals[i] + genomes[i][b];
            end
        end
    end

    // ---- 选择与繁殖（锦标赛选择） ----
    reg [2:0] evo_phase;  // 0=评估 1=选择 2=变异 3=替换
    reg [7:0] sel_idx;
    reg [GENOME_W-1:0] parent1, parent2, child;
    reg [31:0] best_fit;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            gen_cnt <= 32'd0;
            evo_phase <= 3'd0;
        end else if (init_pop) begin
            for (i = 0; i < POP_SIZE; i = i + 1)
                genomes[i] <= lfsr[GENOME_W-1:0] ^ i;  // 随机初始化
            gen_cnt <= 32'd0;
        end else if (evolve_en) begin
            case (evo_phase)
                3'd0: begin  // 锦标赛选择
                    // 随机选2个个体，取适应度高的
                    sel_idx <= lfsr[7:0] % POP_SIZE;
                    evo_phase <= 3'd1;
                end
                3'd1: begin  // 交叉
                    parent1 <= genomes[sel_idx];
                    parent2 <= genomes[(sel_idx + 1) % POP_SIZE];
                    // 单点交叉
                    child <= {parent1[GENOME_W-1:GENOME_W/2],
                               parent2[GENOME_W/2-1:0]};
                    evo_phase <= 3'd2;
                end
                3'd2: begin  // 变异
                    for (integer b = 0; b < GENOME_W; b = b + 1) begin
                        if (lfsr[MUTATION_RATE-1:0] == {MUTATION_RATE{1'b0}})
                            child[b] <= ~child[b];  // 翻转位
                    end
                    evo_phase <= 3'd3;
                end
                3'd3: begin  // 替换最差个体
                    // 找到适应度最低的个体，替换为子代
                    genomes[sel_idx] <= child;
                    gen_cnt <= gen_cnt + 32'd1;
                    evo_phase <= 3'd0;
                end
            endcase
        end
    end

    // 输出
    genvar gi;
    generate
        for (gi = 0; gi < POP_SIZE; gi = gi + 1) begin : gen_pop_out
            assign population[gi*GENOME_W +: GENOME_W] = genomes[gi];
            assign fitness[gi*32 +: 32] = fit_vals[gi];
        end
    endgenerate
    assign generation = gen_cnt;

endmodule

🏋️ 练习

🏆 成就解锁

📐 深入分析：演化算法的收敛性分析

// 适应度评估器 - 评估CA规则的多种适应度指标
module fitness_evaluator #(
    parameter GRID_W = 16,
    parameter GRID_H = 16,
    parameter STEPS = 100
)(
    input  wire             clk,
    input  wire             rst_n,
    input  wire [7:0]       rule,
    input  wire             start,
    output wire [31:0]      fitness_survival,  // 存活步数
    output wire [31:0]      fitness_diversity,  // 图案多样性
    output wire [31:0]      fitness_complexity,  // 结构复杂度
    output wire             done
);
    // 运行CA并收集统计信息
    reg [GRID_W*GRID_H-1:0] ca_state;
    reg [31:0] step_cnt;
    reg [31:0] pop_history [0:STEPS-1];
    reg running;
    
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            running <= 1'b0;
            step_cnt <= 32'd0;
        end else if (start && !running) begin
            running <= 1'b1;
            step_cnt <= 32'd0;
            ca_state <= (1 << (GRID_W*GRID_H/2));
        end else if (running) begin
            // 简化的CA步进
            pop_history[step_cnt] <= 32'd0; // 种群计数
            step_cnt <= step_cnt + 32'd1;
            if (step_cnt >= STEPS - 1) running <= 1'b0;
        end
    end
    
    assign fitness_survival = step_cnt;
    assign fitness_diversity = 32'd0;
    assign fitness_complexity = 32'd0;
    assign done = !running && (step_cnt > 0);
endmodule

性能与优化分析

📖 扩展阅读

• Wolfram, S. A New Kind of Science, Wolfram Media, 2002.
• Toffoli, T. & Margolus, N. Cellular Automata Machines, MIT Press, 1987.
• Ilachinski, A. Cellular Automata: A Discrete Universe, World Scientific, 2001.

🔬 补充专题：实验方法论

在进行CA实验时，科学的方法论至关重要。以下是一些通用的实验指导原则：

参数扫描方法

系统性地扫描参数空间是理解CA行为的关键技术：

数据可视化技巧

CA实验产生的数据通常是高维的（空间+时间+状态）。有效的可视化对于理解至关重要：

• 时空图：横轴=空间位置，纵轴=时间，颜色=状态——最常用的CA可视化方式
• 相图：x轴=参数A，y轴=参数B，颜色=测量指标——用于参数空间扫描
• 频谱图：对种群时间序列做FFT，识别周期性
• 直方图：统计状态/密度的分布