遗传算法

遗传算法

遗传算法（Genetic Algorithm, GA）是一类受达尔文自然选择启发的启发式搜索与全局优化算法，由John Holland于1975年在其著作《Adaptation in Natural and Artificial Systems》中系统提出。GA模拟生物进化机制——选择、交叉、变异——在解空间中并行搜索最优解，属于进化计算的核心分支。其核心思想：将候选解编码为"染色体"，通过适应度函数评价"个体"质量，适应度高的个体以更大概率繁殖后代，经多代迭代逼近全局最优。GA不依赖梯度信息，适用于不可微、非凸、组合爆炸等传统优化方法失效的复杂问题。

核心组件与机制

编码：将解映射为染色体。二进制编码最经典，每个基因位取0/1，适用于组合优化；实数编码直接使用浮点数向量，适用于连续优化，配合模拟二进制交叉(SBX)和多项式变异；排列编码用于旅行商问题等序列优化，需要特殊的交叉算子（如PMX、OX、CX）以保持排列合法性。

适应度函数 $f(\cdot)$：评价个体优劣的标量函数，直接来源于目标函数或经缩放变换。适应度必须非负，通常通过线性变换 $f'(x) = f(x) - f_{\min} + \xi$ 处理负目标值。适应度尺度变换（fitness scaling）防止早期"超级个体"主导选择导致早熟收敛：线性缩放 $f' = af + b$、截断（只保留前 $T\%$）、排名缩放（按排名而非绝对值分配选择概率）。

选择算子：轮盘赌选择——个体选中概率正比于适应度 $p_i = f_i / \sum_j f_j$，简单但有随机误差；锦标赛选择——随机取 $k$ 个个体选最优，$k$ 控制选择压力，$k$ 越大收敛越快但多样性越低；精英保留——直接将最优若干个体复制到下一代，保证已发现的最优解不丢失，理论证明精英策略是GA收敛到全局最优的必要条件。

交叉算子：父代染色体以概率 $p_c$（通常 0.6–0.9）重组产生子代。单点交叉：随机选一个断点互换尾部基因；两点/多点交叉：多个断点交替互换；均匀交叉：每个基因位以概率独立决定来自哪个父代，破坏建筑块的风险更高但探索性更强。

变异算子：以概率 $p_m$（通常 0.001–0.05）随机翻转基因位，维持种群多样性，防止陷入局部最优。二进制编码下翻转位值，实数编码下加高斯扰动 $x_i' = x_i + \mathcal{N}(0, \sigma^2)$。

理论基础：模式定理与建筑块假设

模式定理（Schema Theorem, Holland 1975）：模式是带有通配符的染色体模板（如 $H = *1*0$），其阶 $o(H)$ 为确定位数量，定义距 $\delta(H)$ 为首尾确定位距离。模式定理表明：低阶、短定义距、适应度高于种群均值的模式（即建筑块）在迭代中呈指数增长：

其中 $m(H,t)$ 为第 $t$ 代含模式 $H$ 的个体数。该定理解释了GA的隐并行性：每次迭代同时评估 $O(n^3)$ 个模式，虽仅处理 $n$ 个个体，却隐式搜索了大量模式。

建筑块假设：GA通过组合低阶、短定义距、高适应度的建筑块来逼近全局最优。交叉算子设计应有利于建筑块的保留与重组，这是编码和算子选择的理论指引。

经济学与计量经济学应用

参数估计与模型选择：当极大似然估计或GMM的目标函数高度非凸、多峰时，GA可替代梯度下降进行全局优化。例如ARIMA-GARCH模型的联合参数估计、马尔可夫转换模型的隐状态推断，GA有效规避EM算法对初值敏感的缺陷。

博弈论与机制设计：GA用于搜索纳什均衡：种群中每个个体代表一个策略，适应度为该策略对种群中其他策略的收益。迭代选择与变异模拟策略演化，收敛时种群中心近似纳什均衡。在拍卖机制设计中，GA自动搜索最优竞拍规则。

投资组合优化：均值-方差模型引入整数约束（最小交易单位、基数约束）后成为NP难问题，GA通过实数+二进制混合编码同时优化权重与资产选择，在实践中常优于二次规划松弛。

宏观代理人基模型（ABM）：GA赋予代理人自适应行为规则——代理人根据过去表现用GA更新决策规则，模拟经济系统中有限理性主体的学习与适应过程。

收敛性、局限与改进

GA以概率1收敛到全局最优的条件：精英保留 + 各态历经变异算子 + 无穷迭代。但实际中收敛速度可能极慢，早熟收敛是主要风险——种群过早丧失多样性，陷入局部最优。对策：增大变异率、使用小生境技术（共享适应度惩罚过于拥挤的区域）、岛屿模型（多子种群独立进化，定期迁移个体）。

变体与扩展：遗传规划(GP)——进化计算机程序（树结构）；进化策略(ES)——侧重变异自适应性，实参数优化；差分进化(DE)——基于向量差的变异，在连续优化中收敛极快；NSGA-II——多目标GA，基于Pareto支配与非支配排序，搜索Pareto前沿。

口诀：编码→种群→适应度→选择→交叉→变异→迭代→收敛。GA不保证最快，但保证在最不友好的地形上也能找到路径——它是优化工具箱中"没有假设条件"的通用武器。