此前动态规划入门强调状态、转移与最优性证明。遗传算法处理的是另一种搜索思路：维护一批候选解，按目标值选择父代，再用交叉和变异产生新候选。

本篇归入算法与竞赛的“优化与启发式搜索”方向。它适合用来理解随机优化机制，但不会替代背包的精确算法：我们反而会把小容量动态规划作为参照，测量有限预算下找到了什么、漏掉了什么。

编码对应方案

一位表示选或不选，目标和约束单独计算。

算子定义搜索

选择、交叉、变异各有不同职责。

用基线验收

同评估预算比较，并报告精确最优值和多种子差异。

父代1000与0110在第二位后交叉得到1010，最后一位变异得到1011并违反容量约束；精英0110保留其价值9
新组合不保证更好，精英保留也不保证最优。 图示采用正文四件物品的手工操作，不是某次随机运行的收敛曲线。查看原图

先固定问题与二进制编码

给定 n 件物品，重量 w_i>0，价值 v_i≥0，容量 C≥0。二进制染色体 b∈{0,1}^n 表示方案，b_i=1 代表选择第 i 件。目标是最大化 Σv_i b_i，并满足 Σw_i b_i≤C。

本文适应度定义为：可行时返回价值，不可行时返回 −1。由于所有可行价值非负，它严格区分可行与不可行，但所有不可行解之间没有进一步引导信号；约束很紧时，这可能使搜索效率很差。

这是一种明确的教学约束策略，不是通用约束优化方案。罚函数、修复算子和可行优先排序都会改变搜索行为，不能在比较时偷偷替换。也不能把任意实数向量的交叉直接当成排列问题的合法操作。

四个算子分别做什么

环节 本文规则 作用及限制
选择 有放回抽 3 个个体，取适应度最高者 偏向当前较好方案，不表示知道全局最优
交叉 概率 0.8，在内部随机切一刀 组合父代前后片段，可能破坏好组合或约束
变异 每位独立以 1/n 概率翻转 提供新变化，不是每个子代恰好翻一位
精英保留 当前最优个体直接复制到下一代 保护当前最好值，不维持全部多样性

逐位变异的期望翻转数是 n×(1/n)=1，但实际可能是 0、1 或更多。选择也不等于抽样后把父代“用掉”：同一父代可以被多次抽到。

DEAP 官方算子文档分别提供了锦标赛选择、单点交叉和逐位翻转；官方教程还提醒使用变异、交叉与适应度时要处理个体复制和失效的评分。本文自行实现一个固定变体，不声称与某个库的默认算法完全一致。

四件物品怎样手算一次操作

物品重量为 [2,3,4,5]，价值为 [3,4,5,8]，容量 C=7。位串从左到右对应第 1 到第 4 件：

候选 选择物品 总重量 总价值 适应度 含义
1000 1 2 3 3 父代示例
0110 2、3 7 9 9 可保留的当前精英
1100 1、2 5 7 7 可行候选
1110 1、2、3 9 12 −1 超重，不能只看价值
1010 1、3 6 8 8 1000 与 0110 在第二位后交叉
1011 1、3、4 11 16 −1 上一子代再翻转第 4 位
1001 1、4 7 11 11 此例的精确最优方案

这里是指定父代、切点和变异位置的教学演算，不是伪装成随机抽样的运行日志。一次操作可以变差；保留 0110 只说明当前的 9 不会被这批差子代丢掉，并不意味着已经找到了 1001。

能证明的是不变量，不是有限步全局最优

初始化时放入空背包，其价值为 0，保证至少有一个可行候选。若当前精英可行，复制到下一代后仍可行；新个体只有在适应度更高时才能替代它，所以每一代报告的最优值单调不降，且对应一个真正满足约束的位串。

这个归纳证明没有说“最后等于最优”。如果新生成的个体一直没有探索到更好的区域，精英可能长时间不变；停滞也不能证明已收敛到全局最优。无约束地增加选择压力还可能过早丢掉多样性。

对比实验必须固定评估预算

设种群规模 N，迭代 G 代。初始种群调用适应度 N 次；每代直接保留一名精英，另外 N−1 名子代各评价一次。因此总评估次数严格为：

1
B = N + G(N−1)

重复出现的位串仍计一次评估，不使用评分缓存。随机基线也先评价一个空背包，然后独立随机生成 B−1 个位串，保留最佳可行解。精确动态规划单独用于计算参照最优值，其工作不算进这两个搜索算法的 B。

同样的评估次数不表示运行时间完全相同：遗传算法还有选择、交叉、复制的开销。多种子结果也只描述指定实例和预算，不能证明它优于所有问题上的随机搜索。

完整 C++17 实现

输入第一行是 n、容量、种群规模、代数、种子数，随后 n 行为重量与价值。代码限制输入规模，避免把教学程序当作无限资源求解器：n≤60、容量≤100000、nC≤2000000、种群 2—128、代数 0—200、种子数 1—50，并限制搜索的总逐位评估工作。

随机种子从 20261019 依次递增。相同编译器与标准库可复现本实现；C++ 随机分布的具体映射不保证在不同标准库间逐位相同，因此跨实现比较应核对不变量与结果分布，不强求同一条轨迹。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <random>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
using namespace std;

struct Problem { int n, capacity; vector<int> weight, value; };
struct Individual { vector<int> bits; long long fit; };
struct Result { Individual best; long long calls; vector<long long> trace; };

Individual evaluate(vector<int> bits, const Problem& p) {
    long long weight = 0, value = 0;
    for (int i = 0; i < p.n; ++i) {
        weight += 1LL * bits[i] * p.weight[i];
        value += 1LL * bits[i] * p.value[i];
    }
    return {move(bits), weight <= p.capacity ? value : -1};
}
vector<int> random_bits(int n, mt19937& rng) {
    bernoulli_distribution bit(0.5);
    vector<int> out(n);
    for (int& x : out) x = bit(rng);
    return out;
}
const Individual& best_of(const vector<Individual>& pop) {
    return *max_element(pop.begin(), pop.end(),
        [](const Individual& a, const Individual& b) { return a.fit < b.fit; });
}
const Individual& tournament(const vector<Individual>& pop, mt19937& rng) {
    uniform_int_distribution<int> pick(0, static_cast<int>(pop.size())-1);
    int winner = pick(rng);
    for (int k = 1; k < 3; ++k) {
        int other = pick(rng);
        if (pop[other].fit > pop[winner].fit) winner = other;
    }
    return pop[winner];
}
Result genetic(const Problem& p, int size, int generations, uint32_t seed) {
    mt19937 rng(seed);
    long long calls = 0;
    auto score = [&](vector<int> b) { ++calls; return evaluate(move(b), p); };
    vector<Individual> pop;
    pop.push_back(score(vector<int>(p.n, 0)));
    for (int i = 1; i < size; ++i) pop.push_back(score(random_bits(p.n, rng)));
    vector<long long> trace{best_of(pop).fit};
    bernoulli_distribution cross(0.8), mutate(1.0/p.n);
    for (int generation = 0; generation < generations; ++generation) {
        vector<Individual> next;
        next.reserve(size);
        next.push_back(best_of(pop));
        while (static_cast<int>(next.size()) < size) {
            const auto& a = tournament(pop, rng);
            const auto& b = tournament(pop, rng);
            vector<int> child = a.bits;
            if (p.n > 1 && cross(rng)) {
                int cut = uniform_int_distribution<int>(1, p.n-1)(rng);
                for (int j = cut; j < p.n; ++j) child[j] = b.bits[j];
            }
            for (int& bit : child) if (mutate(rng)) bit ^= 1;
            next.push_back(score(move(child)));
        }
        pop = move(next);
        trace.push_back(best_of(pop).fit);
    }
    return {best_of(pop), calls, move(trace)};
}
Result random_search(const Problem& p, long long budget, uint32_t seed) {
    mt19937 rng(seed);
    Individual best = evaluate(vector<int>(p.n, 0), p);
    for (long long i = 1; i < budget; ++i) {
        auto candidate = evaluate(random_bits(p.n, rng), p);
        if (candidate.fit > best.fit) best = move(candidate);
    }
    return {move(best), budget, {}};
}
long long exact_optimum(const Problem& p) {
    vector<long long> dp(p.capacity+1, 0);
    for (int i = 0; i < p.n; ++i)
        for (int c = p.capacity; c >= p.weight[i]; --c)
            dp[c] = max(dp[c], dp[c-p.weight[i]] + p.value[i]);
    return dp[p.capacity];
}
string bit_string(const Individual& x) {
    string s;
    for (int bit : x.bits) s += static_cast<char>('0'+bit);
    return s;
}
int main() {
    try {
        Problem p; int size, generations, runs;
        if (!(cin >> p.n >> p.capacity >> size >> generations >> runs))
            throw invalid_argument("header");
        if (p.n < 1 || p.n > 60 || p.capacity < 0 || p.capacity > 100000 ||
            1LL*p.n*p.capacity > 2000000 || size < 2 || size > 128 ||
            generations < 0 || generations > 200 || runs < 1 || runs > 50)
            throw invalid_argument("limits");
        long long budget = size + 1LL*generations*(size-1);
        if (budget*runs*p.n > 50000000) throw invalid_argument("work budget");
        p.weight.resize(p.n); p.value.resize(p.n);
        for (int i = 0; i < p.n; ++i) {
            if (!(cin >> p.weight[i] >> p.value[i]) || p.weight[i] < 1 ||
                p.weight[i] > 1000000 || p.value[i] < 0 || p.value[i] > 1000000)
                throw invalid_argument("item");
        }
        string extra;
        if (cin >> extra) throw invalid_argument("extra input");
        cout << "{\"optimum\":" << exact_optimum(p) << ",\"budget\":" << budget << ",\"runs\":[";
        for (int run = 0; run < runs; ++run) {
            uint32_t seed = 20261019u + static_cast<uint32_t>(run);
            auto ga = genetic(p, size, generations, seed);
            auto baseline = random_search(p, budget, seed);
            if (run) cout << ',';
            cout << "{\"seed\":" << seed << ",\"ga\":" << ga.best.fit
                 << ",\"random\":" << baseline.best.fit
                 << ",\"ga_bits\":\"" << bit_string(ga.best)
                 << "\",\"random_bits\":\"" << bit_string(baseline.best)
                 << "\",\"evaluations\":" << ga.calls
                 << ",\"random_evaluations\":" << baseline.calls << ",\"trace\":[";
            for (size_t j = 0; j < ga.trace.size(); ++j) {
                if (j) cout << ',';
                cout << ga.trace[j];
            }
            cout << "]}";
        }
        cout << "]}\n";
    } catch (const exception&) {
        cerr << "invalid input\n";
        return 1;
    }
}

编译使用 g++ -std=c++17 -O2 -Wall -Wextra -pedantic。示例输入：

1
2
3
4
5
6
7
8
9
10
11
12
13
12 26 32 40 40
2 3
3 4
4 8
5 8
9 10
7 9
6 7
8 12
10 14
11 16
13 18
1 2

输出包含精确最优值、每个种子的两种结果、可复核位串、评估次数，以及含第 0 代的精英轨迹。应汇总全部 40 个种子，而不是只展示最好的一次。

这次运行得到了什么

本机使用 MinGW g++ 13.1.0 和上述编译选项，运行种子 20261019—20261058。精确 DP 最优值为 41，N=32、G=40，所以两种搜索每个种子都评价 1272 个候选（包含重复位串）：

方法 最低最好值 平均最好值 最高最好值 命中最优值 平均最优差距
本文遗传算法 38 40.7 41 30/40 0.3
同预算随机搜索 38 40.225 41 13/40 0.775

这里的“最好值”是每次运行截至预算结束找到的最佳可行价值。遗传算法有 10 个种子没有达到最优；本实例上的均值较高不能推广成通用优势，也没有衡量真实业务的运行成本。尤其是这个小容量背包，精确 DP 直接给出了最优答案。

验证程序 tests/verify-genetic-article.cjs 无警告编译本文源码，用 180 个随机小实例的全子集穷举核对最优参照，逐项核对返回位串、容量、单调精英轨迹与评估次数；另检查零代、单物品、零容量、40 件物品参考、完整示例复现与 18 类非法输入。

这次运行得到了什么

本机使用 MinGW g++ 13.1.0 和上述编译选项，运行种子 20261019—20261058。精确 DP 最优值为 41，N=32、G=40，所以两种搜索每个种子都评价 1272 个候选（包含重复位串）：

方法 最低最好值 平均最好值 最高最好值 命中最优值 平均最优差距
本文遗传算法 38 40.7 41 30/40 0.3
同预算随机搜索 38 40.225 41 13/40 0.775

这里的“最好值”是每次运行截至预算结束找到的最佳可行价值。遗传算法有 10 个种子没有达到最优；本实例上的均值较高不能推广成通用优势，也没有衡量真实业务的运行成本。尤其是这个小容量背包，精确 DP 直接给出了最优答案。

验证程序 tests/verify-genetic-article.cjs 无警告编译本文源码，用 180 个随机小实例的全子集穷举核对最优参照，逐项核对返回位串、容量、单调精英轨迹与评估次数；另检查零代、单物品、零容量、40 件物品参考、完整示例复现与 18 类非法输入。

遗传搜索时间 O((G+1)Nn)，种群空间 O(Nn)，轨迹另占 O(G)。随机基线时间 O(Bn)，候选状态 O(n)。容量 DP 为 O(nC) 时间、O(C) 空间，它是伪多项式算法：当容量足够小时应优先考虑；不能因为它出现在“基线”一栏就说它不实用。

失败边界与下一步

现象 优先检查
最好值很快不再改善 种群是否过早同质化，而不是立即宣布全局最优
多数子代不可行 编码与约束策略是否让可行区域太难到达
价值很高却超重 目标与适应度是否把可行性分开处理
换个种子结果差很多 报告多种子分布和失败次数，不只选最好种子
新子代仍沿用父代分数 必须在交叉和变异后重新评价
对比其他算法更快 同时核对评估预算、实际耗时、参数调优成本和参考最优值
想用在排列或实数优化 先重新设计合法编码与算子，不照搬二进制切片
自检：精英轨迹一直上升，能否证明最终全局最优？

不能。精英保留只证明当前最好值不会丢失。有限预算可能没有访问到更好的方案；小实例可用精确 DP 或穷举计算差距，大实例则需要界、独立基线与重复实验。

如果需要严格最优性，先回到动态规划、二分答案和贪心证明理解问题结构。启发式搜索的价值在于探索另一类求解方式，而不是取消约束、正确性检查和实验基线。