遗传算法

定义

遗传算法(Genetic Algorithm, GA)是一类模拟达尔文自然选择与遗传机制的搜索优化算法,由 John Holland 在 20 世纪 70 年代系统提出,属于进化计算的核心分支。

原理

将候选解编码为"染色体"(常用二进制串或实数向量),维护一个种群并循环执行:按适应度函数评估个体;以轮盘赌、锦标赛等策略选择较优个体;对配对个体进行交叉(交换部分基因)产生后代;以小概率变异引入新基因;形成新一代种群,直至满足停止条件。精英保留策略可防止最优解丢失。

应用

函数优化、旅行商与排班等组合问题、天线与结构设计、机器学习中的特征选择与神经架构演化(神经进化)等。

优缺点

不要求目标函数连续可导、天然并行、适合多峰复杂空间;缺点是收敛慢、易早熟收敛,编码方案与参数设置对效果影响显著,且缺乏最优性保证。