遗传算法（上）-北京尧图网络

遗传算法自然进化中的智慧设想你要在一片山地中找到最高点。自然的方法是环顾四周沿最陡的方向向上走——这正是数学中的梯度上升法通过求导不断逼近极值。但这个方法有一个苛刻的前提地形必须连续光滑每一点都可导。现实中的优化问题常常不满足这个条件。许多问题本质上是离散的参数只能取特定整数、类别或组合目标函数可能不连续、不可导甚至没有明确的表达式。面对这种崎岖而破碎的地形求导工具无处下手。于是我们需要一种不依赖坡度信息、只凭好坏评价就能探索全局的搜索方式。遗传算法正是为此而生——它模仿自然进化在离散而复杂的空间中迭代筛选、组合用适应性代替可导性为现实难题提供了一条新的求解路径。为什么要向自然学习要解决这类无法求导的难题不妨先看看自然界是如何应对复杂环境的。想象一片辽阔的草原生活着一种奔跑速度各不相同的羚羊。跑得快的个体总能在猎豹的追捕中逃脱活下来并留下后代跑得慢的则大多沦为猎物还没来得及繁衍便已消失。如此一代又一代快跑者的基因在群体中占据更大比例而慢跑者逐渐减少。经过漫长岁月整个群体的平均奔跑速度显著提升。这个现象朴素而深刻环境不断施加压力个体间的差异决定了谁有资格繁衍而每一次繁衍只是将已有的特征重新组合并稍作传递。没有预定的目标没有刻意的设计只是通过持续的选择和代际更替群体便悄然发生了改变——更适应环境的特征被保留下来不适应的被淘汰。这便是进化的力量。从羚羊到算法羚羊的故事讲完了。它说明了一个道理不需要谁去设计只要不断重复变异—筛选—繁衍种群就会自动变好。遗传算法做的就是把这件事搬到电脑里。它把求解问题当成一场进化把每个可能的答案当成一只羚羊。剩下的就是一一对应了羚羊群体在算法里叫作种群每一只羚羊叫作个体也就是一个候选答案决定羚羊跑得快慢的那些内在因素——腿长、肌肉、肺活量——好比个体身上的基因所有基因合在一起构成一条染色体代表一个完整的方案。草原环境对羚羊的筛选对应着适应度函数跑得快的活下来对应着适应度高的被保留。羚羊之间的交配产仔叫作交叉后代从父母那里各继承一部分特征偶尔冒出的新性状叫作变异防止群体原地踏步。如此整个优化就不再是数学公式的推导而是一场电脑里的自然选择——种群一代代更新好解一步步浮现。三个核心算子进化依赖三个基本机制选择、交叉、变异。遗传算法将这三个机制一一对应为可计算的操作在每一代种群中依次执行。选择选择解决的是繁殖资格问题。适应度高的个体以更大概率获得繁殖机会逻辑与自然中适者生存一致。实现方式有两种常见方案轮盘赌选择按适应度占总体的比例分配概率适应度越高被选中的扇形面积越大锦标赛选择则随机抽取若干个体比较适应度最高者胜出。两种方法本质相同——让优秀个体更多贡献后代低适应度个体逐步退出。这里涉及一个概念叫选择压力指算法对优秀个体的偏向程度。压力设置需适度过低则进化迟缓过高则种群多样性快速丧失容易提前收敛至局部最优。选择操作的伪代码轮盘赌选择(种群 P): 计算种群总适应度 S sum(适应度) 生成随机数 r ∈ [0, S) 累积和 0 for 每个个体 ind in P: 累积和适应度(ind) if 累积和 r: return ind锦标赛选择则更简洁锦标赛选择(种群 P, 锦标赛规模 k): 从 P 中随机抽取 k 个个体返回其中适应度最高的个体交叉交叉对应生物的基因重组。两个被选中的个体按一定规则交换部分基因片段生成新个体。以单点交叉为例两条等长编码串随机选定一个断点位置交换断点之后的所有位段。交叉的作用在于将已有优良基因片段重新组合期望产生更优的解。它本身不创造新基因仅对现有信息进行洗牌重组。其内在假设是若两个亲代均表现良好则各自优势片段的组合有较大概率优于任一亲代。单点交叉的伪代码交叉(父, 母, 概率 Pc): 生成随机数 r ∈ [0, 1) if r Pc: return 父, 母 // 不交叉直接复制随机选择断点位置 pos ∈ [1, L-1] // L 为编码长度子1 父[0:pos] 母[pos:L] 子2 母[0:pos] 父[pos:L] return 子1, 子2变异变异以极低概率随机改变个体的某个基因位点。对于二进制编码即某一位翻转。变异不追求短期收益它的意义在于维持种群的长期多样性。若无变异种群在若干代后将趋于同质交叉无法再产生新的组合进化即告终止——这种现象称为早熟收敛。变异相当于持续向种群引入新的遗传信息防范算法固守某一局部区域而丧失全局搜索能力。这里引出探索与利用的平衡探索指在未知区域搜索主要由变异承担利用指在已知优解附近精化主要依赖选择和交叉。两者需要合理协调不可偏废。变异操作的伪代码变异(个体, 概率 Pm): for 每个基因位点 i in 个体: 生成随机数 r ∈ [0, 1) if r Pm: 翻转该位点 // 0变11变0 return 个体选择定方向交叉促组合变异保多样。三者协同运作种群在迭代中逐步优化最终收敛至问题的近似最优解。算法全流程三个算子说完了。现在把它们串起来看一遍遗传算法到底怎么跑。运行图景一开始算法随机生成一批个体数量固定比如一百个——这就是初始种群。然后进入循环先给每个个体打分即计算适应度接着根据分数做选择分数高的被选中做亲代亲代两两配对交换基因片段产生子代子代以极低概率发生变异新的一代就此形成替代旧种群。然后重复打分、选择、交叉、变异一代接一代直到某个条件触发停止——通常是跑满了预设代数或者连续很多代分数都没再涨。整个过程像一台循环运转的机器每一轮输入上一代的种群输出新一代的种群。算法本身不关心问题长什么样只要打分函数能给出数值它就能驱动种群往前走。伪代码输入: 种群规模 N, 交叉概率 Pc, 变异概率 Pm, 最大代数 G 输出: 找到的最优解 1. 随机初始化种群 P(0) // 第 0 代 2. for g 0 to G-1: 3. 计算种群 P(g) 中每个个体的适应度 4. if 满足终止条件: break 5. P ← ∅ // 新一代容器 6. while P 中个体数 N: 7. 父, 母 ← 选择( P(g) ) // 第四章 8. 后代 ← 交叉( 父, 母 ) // 以概率 Pc第四章 9. 后代 ← 变异( 后代 ) // 以概率 Pm第四章 10. P ← P ∪ {后代} 11. 若开启精英保留: 把当代最优直接放进 P 12. P(g1) ← P 13. return 历史最优个体参数说明种群规模 N 决定每代个体数量交叉概率 Pc 和变异概率 Pm 控制两算子的触发频率最大代数 G 提供终止基准。这些数值没有固定标准通常依赖经验或实验调整。不同问题有不同配置套用别人的参数未必好用——这是遗传算法实践中的常态。编码伪代码能跑起来之前还得解决一个问题候选解长什么样算法里的个体“基因”染色体都是比喻落实到计算机中需要一个具体的表示形式。这个从问题表述到算法结构的映射过程叫作编码。编码的选择直接决定了后续算子如何操作。不同的编码方式对应不同的交叉和变异实现也影响算法搜索的效率与范围。常见的有三类二进制编码是最经典的方式。将每个参数用一串0和1表示多参数则拼接成一条完整的二进制串。优点是操作直观交叉和变异实现简单理论分析成熟。缺点是精度受制于串长且与问题本身的几何结构缺乏直接对应。实数编码更贴近连续优化问题。个体直接由一组实数向量表示比如(x₁, x₂, …, xₙ)。交叉和变异相应变为实数运算如算术交叉或高斯变异。这种方式避免了二进制与实数之间的反复转换在函数优化中较为常用。排列编码适用于顺序类问题如路径规划、任务调度。个体是一组有序序列比如城市的访问顺序。交叉和变异需要专门设计确保操作后仍保持合法排列——普通的单点交叉很容易产生重复或缺失因此衍生出顺序交叉、部分映射交叉等变体。编码方式没有绝对优劣取决于问题本身的特性。关键原则只有一个编码空间与解空间之间必须能相互映射且编码后的结构便于算子操作。选对了编码后续的进化就顺畅选错了算法再精巧也无济于事。适用哪些问题讲完编码还有一个问题值得先说清楚遗传算法到底适合拿来做什么不是所有问题都值得用它。有些问题有现成的精确解法又快又好没必要绕远路。遗传算法的价值体现在特定的场景里。最典型的情况是搜索空间太大穷举不现实而传统方法又使不上劲——比如函数不可导、不连续或者连表达式都没有只能靠仿真给结果。这时候遗传算法就派得上用场。它不挑问题只要有个打分函数就能跑起来。旅行商问题是常被拿来举例的几十个城市排列组合的数量远超天文数字遗传算法用排列编码加专门设计的交叉很快能出一条不错的路线。神经网络调参也类似层数、学习率这些参数离散且互相牵制每次训练又耗时遗传算法可以用较少的迭代找到有效配置。但也得认清它的局限。如果每次打分都要跑一个小时的仿真那几千代迭代根本不现实。如果问题本身可以用梯度下降或线性规划精确求解那也没必要用它。遗传算法给的是近似解不是最优解随机性决定了它无法提供数学上的最优性保证。它更适合做探索者而不是精算师。用计算成本换可行性这才是它在现实问题中站得住脚的原因。

遗传算法（上）

相关推荐

从零开始用Python搭建自动化脚本的实用指南

Python靠边儿，PHP才是AI代理领域的沉睡巨人

Codex开源Agent评测闭环：FrontierMath突破与Fable复现实战

更多资讯

外省低压电工证能转过来吗？c级低压电工证千万别踩坑

3分钟看懂国网电工证办理流程在哪考避坑指南来了

同安哪里可以考电工证在哪考的证能全国通用吗

广东电工证复审在哪里保姆级教程之前考的证在外省能不能转过来

电工证有哪些培训机构？郑州报考避坑指南全攻略

特变电工证报考条件多久拿证？实操考试心里没底怕挂科？老电工给你讲明白

今日更新

西昌市电工作业查询怎么查？郑州报考避坑指南帮你少走弯路

西昌市电工作业查询通过率揭秘：怕考不过白交培训费？这几点要记牢

临夏电工证在哪里审官方报名入口怎么找

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？