遗传算法代码怎么写：从染色体编码到迭代求解

遗传算法（Genetic Algorithm，GA）是一类受生物进化过程启发的随机优化方法。它把一个候选解表示为“染色体”，通过选择、交叉、变异等操作产生新候选解，再根据目标函数评价结果，逐代更新种群。

遗传算法的吸引力在于实现思路直观，也不要求目标函数可导。但它不是遇到复杂问题就能自动找到好答案的黑盒：编码方式、约束处理、参数设置和计算预算都会影响结果。本文从问题建模开始，逐步实现一个纯 Python 遗传算法，用它求解带边界和线性约束的连续优化问题。

一、遗传算法适合解决什么问题

遗传算法适用于候选解可以明确表示、解的优劣可以计算，但直接穷举或使用常见梯度方法不方便的问题。例如：

• 离散组合问题，如排班、选址、特征子集选择和某些路径规划问题。
• 目标函数不可导、不连续，或由模拟程序、规则系统计算的问题。
• 目标函数存在多个局部最优，值得使用种群探索不同区域的问题。
• 混合变量问题，即决策中同时包含整数、类别和连续变量，且可以设计对应的编码与操作规则。

它通常不适合作为默认优化器。若目标函数平滑、可导、约束简单，梯度法或成熟的数值优化器往往更快、更易分析。变量数量很大、一次评价成本很高时，遗传算法也可能需要大量计算才能得到可用结果。它提供的是搜索策略，不保证在有限时间内找到全局最优解。

还有一个重要边界：遗传算法优化的是你写下来的目标函数，而不是你“实际想要”的目标。目标定义不完整、数据有偏或约束遗漏，都可能让算法稳定地产生不合需求的解。

二、先把优化问题说清楚

实现算法前，至少要明确四件事：

1. 决策变量：需要搜索哪些值，变量是连续数、整数、布尔值还是类别。
2. 取值范围：每个变量允许的边界是什么，是否还有组合约束。
3. 目标函数：如何评价一个候选解；是最小化还是最大化，评价是否可能失败或超时。
4. 资源与停止条件：最多评价多少次、运行多久，或何时认为改进已经足够小。

下面示例要最小化：

f(x, y) = (x - 2)² + (y + 1)²

并要求 -5 ≤ x, y ≤ 5，以及 x + y ≤ 0。不考虑约束时，目标函数在 (2, -1) 处取得最小值，但它不满足 x + y ≤ 0。这个例子可以同时展示变量边界和不可忽略的可行性约束。

三、染色体编码：候选解如何表示

染色体就是算法内部使用的候选解表示。编码必须和问题的变量类型相匹配，遗传操作也必须生成含义有效的候选解。

1. 二进制编码

用 0 和 1 的序列表示候选解，适用于布尔选择、子集选择等问题。例如，长度为 n 的染色体可以表示是否选取每个物品。它便于设计按位交叉和翻转变异，但要把连续变量转成二进制时，需要选定精度并进行解码；精度越高，所需位数通常越多。

2. 整数或排列编码

排班、排序和路径问题往往需要整数或排列表示。操作不能只沿用通用的逐位交叉：普通交叉可能造成重复元素或缺失元素，需要使用适合排列的操作，或者在操作后修复染色体。修复本身也要有明确规则，否则算法实际上在优化另一个问题。

3. 实数编码

连续变量可以直接用浮点数组表示。例如，[0.8, -1.2] 就是二维实数染色体。实数编码不需要二进制解码，适合连续参数搜索。本文代码采用这种表示。

编码不只是存储格式。它决定“相近候选解”在数据结构中是否也相近，并决定哪些交叉、变异操作是合理的。若编码与问题结构不匹配，即使代码没有报错，搜索也可能效率低或产生大量非法解。

四、遗传算法的一次迭代包含什么

经典遗传算法通常维护一组候选解，称为种群。每一代大致执行以下步骤：

1. 初始化：在允许的范围内创建一批候选解。
2. 评价：计算每个候选解的目标值，并检查约束。
3. 选择：从当前种群中选出更有机会产生后代的个体。
4. 交叉：组合两个或多个父代的特征，产生后代。
5. 变异：随机扰动后代，避免搜索过早集中在狭小区域。
6. 更新：用后代形成下一代；常见做法是保留少数优秀个体。
7. 停止：达到评价预算、代数限制或其他停止条件后返回结果。

“优秀个体”具体如何比较，取决于优化方向、约束和问题结构。下面的实现会先比较可行性：可行解优先于不可行解；可行解之间比较目标值；不可行解之间比较约束违反量。

五、可运行的 Python 实现

以下代码只使用 Python 标准库。将代码保存为 ga_example.py，用 Python 3 运行即可。代码设置固定随机种子，便于重复检查运行结果；这不意味着实际优化过程只有一种结果，换一个种子可能得到不同搜索轨迹。

import random
from typing import List, Tuple

# 每个变量的上下界
BOUNDS = [(-5.0, 5.0), (-5.0, 5.0)]

# 算法参数
POPULATION_SIZE = 80
GENERATIONS = 200
ELITE_COUNT = 2
TOURNAMENT_SIZE = 3
MUTATION_RATE = 0.5  # 每个基因发生变异的概率
MUTATION_SIGMA = 0.10  # 高斯扰动标准差，占变量区间宽度的比例

# 约束容差：允许浮点计算产生极小误差
FEASIBILITY_TOLERANCE = 1e-12


def objective(individual: List[float]) -> float:
    """最小化到 (2, -1) 的平方距离。"""
    x, y = individual
    return (x - 2.0) ** 2 + (y + 1.0) ** 2


def constraint_violation(individual: List[float]) -> float:
    """约束为 x + y <= 0，返回非负违反量。"""
    x, y = individual
    return max(0.0, x + y)


def score(individual: List[float]) -> Tuple[int, float, float]:
    """
    用字典序进行比较：
    1. 可行解优先；
    2. 不可行解比较违反量；
    3. 可行解比较目标函数。
    """
    violation = constraint_violation(individual)
    feasible = violation <= FEASIBILITY_TOLERANCE

    if feasible:
        return (0, 0.0, objective(individual))
    return (1, violation, objective(individual))


def clip(value: float, low: float, high: float) -> float:
    """把实数限制在闭区间 [low, high] 内。"""
    return max(low, min(value, high))


def make_individual() -> List[float]:
    """按各变量边界均匀初始化一个候选解。"""
    return [random.uniform(low, high) for low, high in BOUNDS]


def tournament_select(population: List[List[float]]) -> List[float]:
    """随机抽取若干个体，返回其中排序最好的一个。"""
    contestants = random.sample(
        population,
        k=min(TOURNAMENT_SIZE, len(population)),
    )
    return min(contestants, key=score)[:]


def crossover(
    parent_a: List[float],
    parent_b: List[float],
) -> List[float]:
    """逐变量进行实数混合交叉。"""
    child = []
    for a, b in zip(parent_a, parent_b):
        alpha = random.random()
        child.append(alpha * a + (1.0 - alpha) * b)
    return child


def mutate(individual: List[float]) -> None:
    """对部分变量添加高斯扰动，并将结果裁剪到边界内。"""
    for index, (low, high) in enumerate(BOUNDS):
        if random.random() < MUTATION_RATE:
            sigma = (high - low) * MUTATION_SIGMA
            individual[index] += random.gauss(0.0, sigma)
            individual[index] = clip(individual[index], low, high)


def validate_parameters() -> None:
    """检查本示例的关键参数，避免明显无效的配置。"""
    if POPULATION_SIZE < 2:
        raise ValueError("种群规模至少为 2")
    if not 1 <= ELITE_COUNT < POPULATION_SIZE:
        raise ValueError("ELITE_COUNT 必须大于等于 1 且小于种群规模")
    if TOURNAMENT_SIZE < 1:
        raise ValueError("TOURNAMENT_SIZE 必须至少为 1")
    if GENERATIONS < 0:
        raise ValueError("GENERATIONS 不能为负数")
    if not 0.0 <= MUTATION_RATE <= 1.0:
        raise ValueError("MUTATION_RATE 必须在 [0, 1] 内")
    if MUTATION_SIGMA < 0.0:
        raise ValueError("MUTATION_SIGMA 不能为负数")
    for low, high in BOUNDS:
        if low >= high:
            raise ValueError("每个变量都必须满足 low < high")


def run() -> Tuple[List[float], Tuple[int, float, float]]:
    validate_parameters()
    random.seed(7)

    population = [make_individual() for _ in range(POPULATION_SIZE)]

    for generation in range(GENERATIONS + 1):
        population.sort(key=score)
        best = population[0]

        if generation % 20 == 0 or generation == GENERATIONS:
            violation = constraint_violation(best)
            print(
                f"generation={generation:3d}, "
                f"x={best[0]: .6f}, y={best[1]: .6f}, "
                f"objective={objective(best):.8f}, "
                f"violation={violation:.3e}"
            )

        if generation == GENERATIONS:
            break

        # 精英保留：直接把当前最好的个体复制到下一代
        next_population = [
            individual[:] for individual in population[:ELITE_COUNT]
        ]

        while len(next_population) < POPULATION_SIZE:
            parent_a = tournament_select(population)
            parent_b = tournament_select(population)
            child = crossover(parent_a, parent_b)
            mutate(child)
            next_population.append(child)

        population = next_population

    population.sort(key=score)
    return population[0][:], score(population[0])


if __name__ == "__main__":
    best, best_score = run()
    print("best individual:", best)
    print("best score:", best_score)

这里使用的公式是 Python 代码中的实际语法：在 HTML 中，代码里的小于号和大于号已分别转义为 < 和 >，箭头注解中的大于号也已转义。发布时应保留这些 HTML 转义，浏览器会在代码区显示原字符。

六、逐段理解这段代码

1. 边界与变量维度

BOUNDS 中的每个二元组对应一个变量的下界和上界。示例的染色体有两个实数基因。增加变量时，要同时调整目标函数、约束函数和边界列表；减少变量也需要相应调整。只改其中一处会导致维度不一致，或者让目标函数评价的并不是预期问题。

初始个体在每个变量的边界内独立均匀采样。对于强相关变量或可行区域很窄的问题，这种初始化可能产生很多无用个体。可以考虑使用领域知识构造初始解，但要确保不会因为过度集中而失去探索能力。

2. 约束违反量与比较规则

约束 x + y ≤ 0 被转成违反量 max(0, x + y)：满足约束时违反量为零，超出部分为正数。score 返回三元组，Python 会按从左到右的字典序比较。

因此，任何可行解的第一项都是 0，会排在违反约束的解之前。两个可行解的违反量和第二项都相同，再比较目标值；两个不可行解则先比较违反量。这种规则避免了任意指定“罚多少分才合适”的问题，也让约束优先级在代码中清晰可见。

多条不等式约束可以分别计算违反量，再按明确规则组合。例如，将每条违反量的归一化结果相加；但归一化尺度需要结合问题量纲设计。若不同约束的重要性不同，也应在建模中明示。等式约束常用允许误差带表示，例如 |h(x)| ≤ tolerance，不应假设浮点数计算能精确满足等式。

3. 选择：锦标赛选择

锦标赛选择每次随机抽取几个个体，只从这几位中选表现最好的一位作为父代。锦标赛规模越大，选择压力通常越强；规模太小则选择更温和，优秀解传播较慢。示例使用规模 3，且通过 min 选取排序最好的个体。

代码中 random.sample 要求抽样数不超过种群规模，因此使用了两者的较小值。参数检查保证种群至少有两个个体。实际项目还应根据运行成本和种群规模测试选择压力，而不是照搬示例数字。

4. 交叉：组合父代的实数基因

交叉对两个父代的对应基因做加权平均，生成子代。由于权重在 0 到 1 之间，子代的每个基因会落在两个父代对应值之间。代码随后进行变异和边界裁剪。

这种交叉简单，但也意味着子代不会在单个基因上超出父代的取值区间。若种群已经收缩到局部范围，交叉本身难以扩大搜索区域；变异因此很重要。其他实数交叉方法可以允许在父代区间之外生成子代，但仍要管理边界和探索范围。

5. 变异与边界处理

对每个基因，代码以 MUTATION_RATE 的概率添加零均值高斯扰动。标准差按变量区间宽度计算，因此变量尺度不同的时候，扰动也随之缩放。扰动后用 clip 裁剪到边界内，确保基因不会超出变量范围。

裁剪是一种简单处理方式，但不是总是最佳选择。大量个体如果反复撞到边界，可能聚集在边界值上。其他选择包括反射回边界内、重新采样或专门设计边界感知的变异操作。整数变量不能只靠浮点裁剪，还需在变异后采用明确的取整规则，并评估取整偏差。

6. 精英保留和停止条件

每代直接复制前两个个体到下一代，称为精英保留。它能防止当前最好候选解在交叉或变异中消失，但精英数量过多会降低种群多样性。示例按固定代数停止；实际使用还可以限制目标函数评价次数、运行时间，或在连续若干代没有显著改进时停止。

判断“没有显著改进”时，最好设定相对或绝对改进阈值，并结合最少运行代数与评价预算，避免过早终止。固定代数本身并不等于收敛证明，只是计算预算的一种写法。

七、参数怎么设置：先守住边界，再做实验

遗传算法没有适用于所有问题的固定参数。种群规模、代数、交叉方式、变异率和扰动幅度之间会相互影响；变量数量、目标函数噪声和单次评价成本也很重要。本文数值只是可运行示例，不是推荐的通用配置，也不存在对所有问题都成立的“正确变异率”。

调整时可以按以下顺序操作：

• 先定计算预算：用目标函数评价次数或墙钟时间作为比较基础。种群规模乘以代数只是近似预算；若每次评价失败、缓存或重复调用，实际次数会不同。
• 观察可行解比例：如果长期没有可行解，应检查约束定义、初始化策略和遗传操作，而不是只增加代数。
• 观察种群多样性：候选解过早变得相似，可能是选择压力过强或变异不足；随机搜索占比过高，则可能是选择压力太弱或扰动幅度过大。
• 采用多随机种子：在相同预算下重复运行，报告最好值、中位数、分布和可行率。单次运行的最佳结果不足以评价随机算法的稳定性。
• 和基线比较：至少比较随机采样、已有领域启发式或适用的经典优化方法，确认遗传算法在目标问题上值得采用。

参数值还应进行基本校验。本文检查种群、精英数、变异概率、扰动比例和变量区间的明显错误。不同实现可能有不同限制。例如，若交叉概率或变异概率采用概率解释，通常应限制在 [0, 1]；但具体参数是否允许端点、精英数是否可为零，要以代码实现和算法设计为准，不能把某个库的限制当作遗传算法本身的普遍定律。

八、常见错误及排查方式

错误一：最大化和最小化写反

选择操作若使用 min，就必须保证评价分数越小越好。若原问题是最大化，可对目标取负，或重写比较规则；不能只在打印结果时改符号，否则搜索方向仍然是错的。

错误二：约束只写在说明里，没有进入算法

如果只设置变量上下界，算法仍可能违反其他约束。必须在候选解比较、惩罚、修复或编码中落实所有要求，并在返回结果前再次独立验证约束。修复操作会改变候选解，修复后也要重新评价。

错误三：惩罚系数凭感觉设置

罚分过小，算法可能宁愿违反约束以换取更好的目标值；罚分过大，目标差异可能被淹没，搜索难以区分可行解。本文用可行性优先的字典序比较，避免为这个例子挑选惩罚系数。对更复杂的问题，惩罚法仍可使用，但尺度、归一化和系数变化策略需要明确验证。

错误四：变异后超出边界，或修复后忘记重新评价

变量越界可能造成目标函数异常，也可能让算法悄悄优化错误的可行域。示例在变异后立即裁剪；如果采用重采样或复杂修复，必须确保边界和组合约束都得到处理。

错误五：把随机算法当作确定性算法

固定种子适合复现调试，不代表算法能保证相同质量，也不代表单次结果可靠。部署或报告时应使用多个独立种子做验证，并保留种子、参数、代码版本和数据版本。

错误六：只看代数，不统计目标函数实际调用

目标函数可能包含远程请求、模拟器或模型推理，一次评价可能比遗传算法的其他操作昂贵得多。应统计调用次数和耗时，对超时、异常、无效数值设置明确处理策略。不能让一个目标函数异常悄悄变成极佳适应度，否则算法可能会主动偏向失败样本。

错误七：把示例操作直接用于不同编码

本例是两个连续变量。直接把这套实数交叉应用于排列编码，会产生无效路径；直接用于类别变量也没有自然含义。先设计编码、合法性判定和适配的遗传操作，再移植迭代框架。

九、结果验证、性能和安全边界

优化结果应在算法外部再次验证：检查变量维度、上下界、所有业务约束、目标值的单位和实际业务意义。对重要任务，可将候选解交给独立的验证程序或仿真流程复核。遗传算法返回“最优个体”，只表示它是在已评估候选解中按当前比较规则排名靠前，不等于已证明全局最优。

如果目标函数很慢，可以考虑缓存重复输入、并行评估或使用近似模型。但缓存键要能准确区分输入；并行执行要确认目标函数没有不安全的共享状态；近似模型的误差需要在最终候选解上用真实目标函数复查。若目标函数带随机噪声，可对候选解重复评价或采用稳健统计量，避免把偶然的低值误认为真实优势。

安全方面，遗传算法本身不是安全控制、密码算法或访问控制机制，也不应被描述为能保证安全。它可以用于特定建模条件下的搜索、调度或参数优化，但优化目标和约束可能无法涵盖所有风险。涉及安全关键场景时，候选解需要独立验证、故障保护和专业审查；不能仅凭算法找到可行解就直接投入使用。

此外，运行时应限制评价次数、时间和内存。若目标函数调用外部程序、数据库或网络服务，应使用受控权限和超时；不要把不可信输入当作代码执行，也不要为了优化而绕过验证或授权。使用第三方遗传算法库时，要按具体库的文档和许可证检查其输入限制、依赖与适用范围；没有查阅文档时，不应臆造其参数上限。

十、把示例改成自己的问题

迁移到实际任务时，按这个顺序修改最不容易漏项：

1. 为每个变量定义类型和范围，并选择能表达问题结构的染色体编码。
2. 实现目标函数，确认它返回可比较的有限数值；若会产生异常、无穷或缺失值，先定义可靠的失败处理方式。
3. 把每条业务约束写成可测试的校验逻辑，明确容差、单位和多个约束之间的优先关系。
4. 设计适合编码的交叉、变异和必要的修复算子，并为边界与非法个体编写测试。
5. 记录随机种子、评价次数、可行率、最佳目标值和耗时，用多个种子进行对照实验。
6. 将最终候选解交由独立验证步骤检查，不把搜索器的内部排名当作正确性证明。

总结来说，遗传算法代码的核心不是几行“选择—交叉—变异”，而是一个闭环：编码准确表达决策，评价真实反映目标，约束比较与业务规则一致，搜索预算可控，最终结果能够独立验证。先把这个闭环搭好，再讨论参数调优，算法才有机会解决实际问题。