第二章：遗传算法基础

各位同学，今天我们来聊聊遗传算法。说实话，我第一次接触这个概念时，觉得它特别像科幻小说里的东西——用进化论来解数学问题？听起来有点扯对吧？但后来我在一个无线资源调度的项目里，真真切切用它解决了问题，才明白这玩意儿有多实用。

2.1 达尔文进化论与遗传算法

先说说达尔文进化论的核心思想：物竞天择，适者生存。说白了，就是生物种群中，适应环境的个体更容易活下来，并把优秀基因传给下一代。经过一代代筛选，整个种群会越来越适应环境。

遗传算法（Genetic Algorithm, GA）就是受这个启发来的。我个人的理解是：把问题的解想象成生物个体，把目标函数想象成环境。好的解就像适应环境的个体，更容易被保留下来，然后通过交叉、变异产生更好的后代。

嗯，这里要注意：遗传算法不是模拟生物进化的全部细节，而是提取了最核心的三个操作——选择、交叉、变异。我在做通信资源调度时，经常用GA来优化信道分配，效果还不错。

为什么会这样设计？因为通信资源调度问题往往是非线性、多约束的，传统数学方法很难直接求解。GA这种启发式方法，反而能快速找到不错的解。

2.2 编码与解码

编码是遗传算法的第一步。说白了，就是把问题的解表示成计算机能处理的「染色体」。我习惯用二进制编码，因为简单直观。

举个例子，假设我们要优化5个通信信道的功率分配，每个信道功率范围是0~31（5位二进制表示），那么一个染色体就是25位二进制串：

// 编码示例：5个信道的功率分配
// 信道1: 10110 (22)
// 信道2: 01101 (13)
// 信道3: 11010 (26)
// 信道4: 00111 (7)
// 信道5: 10001 (17)
染色体: 1011001101110100011110001

解码就是反过来，把二进制串还原成实际的功率值。我在项目中遇到过一个问题：编码长度太短，精度不够；太长，搜索空间又太大。后来我总结了一个经验：编码长度 = log2(精度要求 × 取值范围)，这样既保证精度，又不浪费计算资源。

2.3 选择算子

选择算子，就是决定哪些个体能「活下来」并繁殖后代。最常见的两种：

• 轮盘赌选择： 适应度越高的个体，被选中的概率越大。就像抽奖，中奖概率和你的「贡献值」成正比。
• 锦标赛选择： 随机挑几个个体，选最好的那个。我比较喜欢用这个，因为它不会让超级个体垄断整个种群。

我曾经在一个项目中，只用轮盘赌选择，结果算法很快就收敛到局部最优了。后来改成锦标赛选择，种群多样性明显改善。所以我的建议是：如果问题比较复杂，优先考虑锦标赛选择。

// 轮盘赌选择伪代码
function roulette_wheel_selection(population, fitness):
    total_fitness = sum(fitness)
    r = random(0, total_fitness)
    cumulative = 0
    for i in range(len(population)):
        cumulative += fitness[i]
        if cumulative >= r:
            return population[i]

2.4 交叉算子

交叉算子模拟的是生物繁殖中的基因重组。说白了，就是把两个父代个体的染色体「剪开再拼接」，产生新的子代。

最常用的是单点交叉：随机选一个交叉点，交换两个染色体后半部分。比如：

父代1: 10110 | 01101
父代2: 11010 | 00111
交叉后:
子代1: 10110 | 00111
子代2: 11010 | 01101

还有多点交叉和均匀交叉，但我个人觉得，对于通信资源调度这类问题，单点交叉已经够用了。交叉概率一般设在0.7~0.9之间，太高容易破坏优秀基因，太低又探索不够。

2.5 变异算子

变异算子是为了防止算法陷入局部最优。说白了，就是随机改变染色体中的某些基因位。对于二进制编码，变异就是0变1、1变0。

变异概率通常设得很小，0.01~0.1之间。为什么？因为变异太频繁，算法就退化成随机搜索了。我刚开始做GA时，把变异概率设成0.3，结果算法根本不收敛，跟没头苍蝇一样乱撞。

// 二进制变异示例
原始染色体: 1011001101
变异位置: 第3位和第7位
变异后:     1001001001

嗯，这里有个小技巧：自适应变异。就是让变异概率随着进化代数动态调整。早期变异概率大一些，增加探索；后期变异概率小一些，保护优秀解。我在一个5G资源调度的项目里用过这个，收敛速度提升了大概20%。

2.6 知识体系总览

说了这么多，我们来画个图，把遗传算法的核心逻辑串起来。这样你就能一目了然了。

从这张图可以看出，遗传算法的核心就是：初始化 → 评估 → 选择 → 交叉 → 变异 → 再评估 → 直到满足条件。这个循环就是「进化」的过程。

2.7 避坑指南

最后，分享几个我踩过的坑：

• 种群大小： 太小容易早熟，太大计算量爆炸。我一般取50~200之间，具体看问题复杂度。
• 精英保留： 每代把最好的几个个体直接复制到下一代，防止优秀基因丢失。这个技巧很实用。
• 早熟收敛： 如果算法很快就不动了，试试增大变异概率或种群规模。
• 编码冗余： 别让染色体中有大量无效位，那会拖慢搜索速度。

好了，遗传算法的基础就讲到这里。下一章我们会深入讨论适应度函数的设计，以及如何把GA应用到具体的通信资源调度场景中。记住，理论是死的，但应用是活的。多动手写代码，你才能真正理解GA的精髓。

---

公众号:蓝海资料掘金营，微信deep3321