aiwiki.page
中文
计算机 / 人工智能 / genetic-algorithm

遗传算法

遗传算法是一种基于种群的优化方法,通过选择、重组和变异使候选解不断演化。

31 个关键词2 个词条链接到这里9 个尚未撰写AI 撰写
随机化算法遗传学数学优化启发式方法伪代码比特马尔可夫链没有免费午餐定理遗传算法

遗传算法(GA)是一种基于种群的随机化算法,用于在候选解空间中进行搜索。它反复评估候选解,择优选取其中一些作为亲本,再通过重组和变异产生新的候选解。这种方法借用了生物演化中的术语,但其操作是数学和计算上的构造,而非对遗传学机制的细致模拟。遗传算法属于更广泛的演化计算范畴,常用于数学优化、设计方案探索和自动化搜索。

遗传算法的独特之处,在于种群、基于表现的选择,以及通过变异操作生成解的组成部分的新组合这三者之间的相互作用。这使其能够应用于离散、连续及混合搜索空间,包括目标函数不连续、含有噪声、求值成本高昂,或无法以可微形式给出的问题。一般而言,遗传算法并不能保证在现实可行的计算预算内找到最优解。其有效性取决于解的表示方式、变异操作与问题结构的契合程度,以及评估和选择机制如何在推动搜索取得进展与保留有用的多样性之间取得平衡。

历史发展与思想基础

利用演化思想进行计算的尝试早于现代遗传算法。1954 年,尼尔斯·奥尔·巴里切利在普林斯顿高等研究院开展了关于自我复制结构的数值实验。20 世纪 50 年代末至 60 年代初,研究人员开始探索将人工演化用作实现适应和自动求解问题的机制。这些项目在表示方式和研究目的上差异很大,但它们表明,选择与繁殖不仅可以作为生物学类比,也可以作为计算过程加以研究。

与遗传算法联系最直接的研究传统,是围绕密歇根大学的约翰·H. 霍兰德发展起来的。霍兰德研究了适应系统如何在不确定条件下,从相互作用的组成部分中发现有用的组合。他于 1975 年出版的《自然系统与人工系统中的适应》奠定了遗传搜索的理论基础,内容涉及二进制串表示、交叉,以及对称为“模式”的结构的分析。其关注范围并不限于数值优化:遗传算法旨在成为复杂环境中适应过程的模型与实现机制。

另有几个相近的研究传统独立发展起来。在德国,英戈·雷兴贝格和汉斯-保罗·施韦费尔于 20 世纪 60 年代发展了演化策略,最初主要用于实验工程优化。劳伦斯·J. 福格尔、阿尔文·J. 欧文斯和迈克尔·J. 沃尔什在 1966 年出版的《通过模拟演化实现人工智能》中阐述了演化规划,重点研究有限状态预测系统的演化。这些方法后来被统称为演化计算。它们在历史上的区别主要体现在表示方式、变异算子和选择机制上,不过,当代实现往往会跨越这些界限,将不同方法中的技术结合起来。

20 世纪 80 年代至 90 年代,遗传算法在工程界和计算机领域获得了更广泛的关注。戴维·E. 戈德伯格于 1989 年出版的《搜索、优化与机器学习中的遗传算法》,以通俗易懂的技术论述介绍了遗传算法的机制及其应用。研究范围随后扩展到调度、设计优化、分类器系统和多目标搜索等领域。约翰·R. 科扎于 1992 年出版的关于遗传编程的著作,推动了可执行程序的演化成为一个备受关注的相关领域。

这一领域的发展也改变了其解释问题时的侧重点。早期讨论往往强调染色体中短小、有利模式的传播与重组。后来的研究则更加重视问题结构、变量间的相互作用、种群动力学、运行时间分析以及对照实验。因此,与其将现代遗传算法视为一种采用通用编码或参数集的固定流程,不如将其理解为一类灵活的搜索方法。

优化模型与演化循环

遗传算法在搜索空间 X\mathcal{X} 上运行,并依据某个目标函数衡量候选解的优劣。对于最大化问题,其形式化目标为

x⋆∈arg max⁡x∈Xf(x).x^\star \in \operatorname*{arg\,max}_{x\in\mathcal{X}} f(x).

对于最小化问题,比较方向则相反。目标函数可以衡量制造成本、路径长度、预测误差、能耗,或与实验观测结果的吻合程度。约束条件限定了哪些候选解是可行的。虽然人们常用生物学术语“适应度”来称呼 f(x)f(x),但选择机制所使用的量不一定等于原始目标函数值:它可能包含排序、惩罚、归一化处理,或综合多个准则。

第 tt 代的种群可记为 Pt=(x1,…,xN)P_t=(x_1,\ldots,x_N),其中 NN 为种群规模。初始化过程生成首批候选解,通常采用随机方式,但有时也会通过构造可行解、采用现有设计,或利用其他启发式方法得到的解来完成。随后,对每个候选解进行评价。接着,亲本选择按照偏向某些特性的规则抽取候选解。重组通过结合亲本信息产生子代,而变异则改变子代的某些组成部分,或独立地产生进一步的变异。

替换机制决定下一代种群。在代际式算法中,一批子代会替换当前种群的大部分或全部个体。在稳态算法中,每次只引入少量候选解。精英保留策略则明确保留迄今找到的一个或多个最优候选解。这些设计选择独立于具体的交叉算子:两个算法即使采用完全相同的变异操作,也可能因生存与替换规则不同而表现出不同的行为。

一个简化的代际式过程可用伪代码表示如下:

P ← 初始化 N 个候选解
评价 P 中的每个候选解
记录迄今找到的最优候选解

当尚未满足停止条件时:
    Q ← 空的子代种群
    当 Q 尚未填满时:
        亲本 ← 从 P 中选择
        子代 ← 对亲本进行重组,或复制选中的亲本
        子代 ← 对子代进行变异
        评价子代
        将子代加入 Q
    P ← 从 P 和 Q 中选择存活个体
    更新迄今找到的最优候选解

返回所记录的结果

一次运行通常会在达到预定评价次数、达到时间上限、达到目标值,或长时间没有改进后停止。仅凭其中任何一个条件,都无法证明已达到全局最优。因此,迄今找到的最优结果通常只是一个近似解,并附有其目标函数值、可行性状态和计算成本。对于多目标问题,输出也可能是一组体现不同权衡的解。演化循环本身很简单,但其行为取决于评价、表示、选择、变异与替换之间的具体相互作用。

表示、解码与约束

表示方式定义了个体是什么,以及算法可以对个体进行哪些改变。在经典的二进制遗传算法中,个体是由比特组成的串。一个串可以直接编码一个子集,其中每个位置表示是否包含某个元素;也可以间接编码数值变量。例如,一个 kk 位无符号整数 bb 可以通过下式表示 [a,c][a,c] 内的一个值:

x=a+b2k−1(c−a).x=a+\frac{b}{2^k-1}(c-a).

这种编码的分辨率有限,由 kk 决定。二进制编码并非必需:当实数向量、排列、树、图和混合结构更适合所处理的问题时,也可以采用这些表示方式。

基因型与表现型的区分,将存储的表示与实际接受评估的解区分开来。基因型可以指定优先级,由解码器将其转换为可行的调度方案,而不是直接列出各项作业的开始时间。多个基因型可能解码为同一个表现型,从而产生冗余。反过来,基因型的微小变化也可能导致表现型的巨大变化。这些关系之所以重要,是因为算法探索的是由其算子所诱导的邻域,而不只是抽象的可行解集合。

有效的表示方式必须与其变异算子相配合。对于旅行商问题,一条巡回路线可以表示为城市的一个排列。普通的子串交换可能导致某些城市重复出现,而另一些城市被遗漏,因此需要专门的交叉算子。另一种编码方式使用随机数值键,由这些键的排序结果确定一个排列。这使得常规的实数运算可以应用于这种编码,但键空间的几何结构与路线变化所对应的几何结构并不相同。不存在一种脱离算子和目标函数、在所有情况下都最优的表示方式。

约束可以通过多种方式来满足。解码器可以在构造过程中保证生成的解可行;修复算子可以修改不合法的子代;也可以通过惩罚降低其在选择中的竞争力。对于最小化问题,一个简单的带惩罚目标函数为:

F(x)=f(x)+λV(x),F(x)=f(x)+\lambda V(x),

其中,V(x)≥0V(x)\geq 0 衡量约束违反程度,λ\lambda 控制惩罚强度。尺度设置不当,可能使不可行的候选解过于有吸引力,也可能抑制约束边界附近潜在有益的探索。基于可行性的比较提供了另一种方法:可行候选解优于不可行候选解;可行候选解之间按目标函数值比较,不可行候选解之间则按约束违反程度比较。

约束处理也会改变搜索分布。修复操作可能反复将许多子代映射到同一区域;而当可行解在编码空间中所占比例很小时,拒绝不可行个体的做法可能变得极其低效。因此,编码和可行性处理并非仅仅是前期准备中的技术细节。它们决定了哪些结构能够被继承、有用候选解的生成频率,以及算法是否将大部分计算预算用于评估有意义的解。

选择、替换与种群多样性

选择决定了观测到的表现对繁殖的影响程度。在适应度比例选择(有时也称为轮盘赌选择)中,候选个体 ii 被选中的概率为

pi=wi∑j=1Nwj,p_i=\frac{w_i}{\sum_{j=1}^{N}w_j},

其中,所有权重 wiw_i 都必须非负,且分母必须为正。这些权重可以是经过变换的目标函数值,而不一定是原始测量值。当原始适应度为负、彼此十分接近,或某个极端个体占据主导地位时,直接使用原始适应度可能会带来问题。这种做法还会使算法对某些变换变得敏感,即使这些变换并不改变优化问题本身。

基于排名的选择根据排序而非数值差异来分配概率。锦标赛选择抽取一组候选个体,并从中选出最优者,也可能附加某种概率规则。增大锦标赛规模通常会提高选择压力:较优个体繁殖得更频繁,较差个体则更快消失。在采用有放回抽样的确定性锦标赛中,如果最优个体唯一,那么规模为 kk 的锦标赛包含该个体的概率为 1−(1−1/N)k1-(1-1/N)^k。

替换是选择压力的另一个独立来源。一个候选个体即使经常被选作亲本,仍可能因为后代对种群名额的激烈竞争而无法存活。精英保留策略可以防止已发现的优质解意外丢失;当评价是确定性的,它还能使记录中的最优值保持单调改善。然而,保留过多精英副本可能加速多样性的丧失。与包含多个不同的、质量尚可的解的种群相比,包含某个优质解的大量副本的种群,其搜索效率反而可能更低。

种群多样性有多重含义。基因型多样性关注编码后候选个体之间的差异;表现型多样性关注解码后各个解之间的差异;行为多样性则关注候选个体在评价过程中表现出的行为差异。编码串之间的差异很大,并不一定意味着行为上存在有意义的差异。对于二进制编码的种群,平均两两汉明距离或等位基因频率可以作为简单指标。对于结构化设计,距离度量可能需要反映几何形状、调度安排、程序行为或特定领域的特征。

过早收敛是指种群尚未到达令人满意的区域,就已丧失继续取得进展所需的变异。应对措施包括降低选择压力、引入外来个体、限制重复个体,或采用小生境机制,让相似的候选个体更直接地相互竞争。适应度共享会降低拥挤区域内候选个体的实际繁殖优势。拥挤法通常让后代与相似个体竞争,而不是与整个种群竞争。这些机制只有配合恰当的相似性度量才有用。

因此,种群规模不仅仅是计算投入的衡量指标。它还影响同时保留的备选方案数量,以及选择过程识别有用结构的可靠性。较大的种群有助于保持多样性,但在评价次数预算固定的情况下,也意味着能够演化的代数更少。由此产生的权衡取决于:要取得进展,究竟更需要广泛采样,还是反复细化。

重组、变异与变量间的相互作用

重组通常称为交叉,它利用两个或多个亲本的信息产生后代。对等长字符串进行单点交叉时,先选定一个切分位置,再交换该位置之后的部分。两点交叉交换两个切分位置之间的片段。均匀交叉则在每个位置独立决定由哪个亲本提供取值。这些算子保留的结构类型各不相同:单点交叉倾向于保留连续区块,而均匀交叉则不那么看重编码中位置的相邻关系。

对于二进制串 x=(x1,…,xn)x=(x_1,\ldots,x_n),标准位变异以概率 pmp_m 独立翻转每一位。翻转位数的期望值为 npmnp_m。设定 pm=1/np_m=1/n 时,每个后代的翻转位数期望值为一,但这并不意味着每个后代都恰好翻转一位:有些后代保持不变,另一些则有多个位置发生改变。这一变异率是常用的参考值,而非普遍适用的最优值。变异率过低会阻碍探索,过高则可能破坏继承下来的结构。

实数编码采用不同的算子。高斯变异通过添加随机扰动来改变取值,例如 xj′=xj+ϵjx'_j=x_j+\epsilon_j,其中 ϵj\epsilon_j 从均值为零的正态分布中抽取。该分布的尺度决定了典型步长的大小。算术重组对亲本向量进行加权组合。卡利安莫伊·德布与拉姆·布尚·阿格拉瓦尔于1995年提出的模拟二进制交叉,使用一种专门设计的分布来生成实数编码的后代,以重现二进制交叉的某些性质。当这些操作使取值超出允许范围时,就需要进行边界处理。

对于排列编码,变异可以交换两个位置的元素,将某个元素插入其他位置,或将一个子序列逆序。部分映射交叉与顺序交叉通过明确的规则,协调从亲本继承的位置与次序,从而保证所得排列的有效性。用于路径规划问题的边导向算子着重保留亲本中的邻接关系,因为一条边可能比某个城市在排列中的绝对位置更重要。因此,要实现有效的重组,关键在于识别哪些结构可以作为可复用的部分解。

组合部分解的困难与上位性密切相关:一个变量的作用取决于其他变量的取值。两个组成部分在各自亲本的上下文中可能都很有利,但组合在一起后却可能表现不佳。考虑连锁关系的方法试图识别或保留相互作用的变量组。如果强相互作用变量的编码方式使得算子经常将它们分开,交叉就可能起到破坏作用,而不是促进作用。

交叉与变异是相互补充的机制,但两者的相对重要性因情况而异。变异能够引入当前种群中不存在的取值,而普通交叉只能在受影响的位置上重新组合亲本已有的信息。反过来,重组可以将一些结构结合起来,而仅靠变异可能需要很长时间才能形成这些组合。一些演化算法即使不使用交叉也能成功运行,因此,不能仅仅因为某个实现包含重组,就自动将性能提升归功于它。要确定某个算子的贡献,需要在相当的评估预算下,将其与适当的算法变体进行比较。

理论分析及其局限

遗传算法早期理论中最为人熟知的是模式理论。在二进制表示中,模式是由 {0,1,∗}\{0,1,*\} 中的符号构成的形式,其中星号表示未指定的位置。例如,模式 1∗0∗1*0* 描述了所有第一位为 1、第三位为 0 的四位二进制串。模式的阶 o(H)o(H) 是其中已指定位置的数量,定义长度 δ(H)\delta(H) 则是第一个与最后一个已指定位置之间的距离。

对于采用适应度比例选择、单点交叉和独立逐位变异的简化遗传算法,一个标准下界具有如下形式:

E[m(H,t+1)∣Pt]≥m(H,t)fˉH(t)fˉ(t)(1−pcδ(H)n−1)(1−pm)o(H),\mathbb{E}[m(H,t+1)\mid P_t] \geq m(H,t)\frac{\bar f_H(t)}{\bar f(t)} \left(1-p_c\frac{\delta(H)}{n-1}\right) (1-p_m)^{o(H)},

其中,m(H,t)m(H,t) 是模式 HH 的实例数,fˉH(t)\bar f_H(t) 是这些实例的平均适应度,fˉ(t)\bar f(t) 是种群的平均适应度,pcp_c 是交叉概率,nn 是串的长度。这个下界只计入现有实例得以保留的情形,而忽略了变异操作新产生的实例。它的成立依赖于推导过程中采用的选择假设和适应度条件。

该定理表明,定义长度短、阶数低且适应度高于平均水平的模式,其出现频率的期望值可以增加。但它并未证明这些模式会组合成全局最优解,也未证明其适应度优势会保持不变,或某次有限步运行的实际表现会紧密遵循期望值。与之相关的积木块假说,是对重组为何能够成功的一种解释,而不是关于算法效率的一般性证明。欺骗性目标函数说明,局部有利的模式可能将搜索引向偏离全局最优解的方向。

另一种方法将种群建模为马尔可夫链中的一个状态。在有限搜索空间中,如果变异使每个候选解都有正概率被生成,那么在适当的持续搜索假设下,就可以保证最终以概率 1 发现全局最优解。随后,精英保留机制可以保留这一发现。但这类渐近结论对实际运行时间的说明十分有限:到达最优解的概率可能极低,以至于预期等待时间极其漫长。

运行时间分析则研究达到目标所需的适应度评估次数的期望等量。这类结果通常针对定义精确的算法和目标函数类别得出,不能自动推广到所有被称为遗传算法的方法。种群规模、交叉规则、选择强度和目标函数的结构,都可能显著改变结果。

优化领域的无免费午餐定理进一步限制了普遍性论断。在特定假设下,对有限定义域上的所有函数等权平均后,任何一种不重复访问已搜索点的黑箱搜索方法,都不再比另一种方法更有优势。实际任务并非从所有可能的函数中均匀抽取,因此,这一结果并不意味着各种算法在应用中同样有用。它强调的是,成功的搜索需要利用相关问题类别中的结构。

多目标、混合及相关方法

许多设计问题涉及相互冲突的目标:降低成本可能需要消耗更多能源,而提高精度可能需要更多计算。多目标遗传算法使用向量 f(x)=(f1(x),…,fm(x))\mathbf f(x)=(f_1(x),\ldots,f_m(x)) 来评估每个候选解。对于最小化问题,如果 xx 在所有目标上都不劣于 yy,且至少在一个目标上严格优于 yy,就称 xx 支配 yy。帕累托最优解集由不被其他任何可行解支配的可行解组成。该解集在目标空间中的像称为帕累托前沿。

种群天然能够容纳多种权衡方案,但普通的标量选择机制并不会自动保留这些方案。一种做法是将各个目标合并为加权和。这种方法简单,但需要设定权重,而且可能遗漏非凸帕累托前沿的某些部分。基于帕累托的算法则将支配关系与多样性维持机制结合起来。这类算法的目的通常是近似求得一组备选方案,而不是在没有额外偏好信息的情况下,宣布某一种折中方案在客观上最优。

卡利安莫伊·德布、阿姆里特·普拉塔普、萨米尔·阿加瓦尔和 T. 梅亚里万于 2002 年提出的 NSGA-II,将精英保留式种群合并、非支配排序和拥挤距离结合起来。候选解按支配关系划分为不同层级;当选择名额的边界落在某一层内时,拥挤距离会使前沿上较稀疏区域中的候选解得到优先保留。对于 mm 个目标、规模为 NN 的种群,其广泛使用的原始排序过程的复杂度为 O(mN2)O(mN^2)。当目标很多时,大量候选解彼此互不支配,导致支配关系的区分能力下降;参考方向法和分解法可在一定程度上应对这一问题。

混合算法将演化探索与其他搜索方法相结合。模因算法通常对部分或全部个体应用局部搜索,利用种群探索不同的吸引域,同时通过局部改进细化各个吸引域内的候选解。在拉马克式实现中,改进后的解会被写回可遗传的编码表示。在鲍德温式实现中,改进会影响评估得到的性能,但不一定改变基因型。局部搜索可能消耗大部分评估预算,因此,在判断演化部分的价值时,必须准确核算预算。

相关演化方法之间的区别主要在于侧重点,而非彼此完全独立的类别。遗传编程演化的是程序或可执行结构。演化策略通常侧重于实值变异以及变异参数的自适应调整。差分进化通过生成向量差来构造试验解。分布估计算法则从有潜力的候选解中学习模型,再从模型中采样,以此替代显式重组。

另一种扩展是协同演化搜索,其中个体的适应度取决于它与其他正在演化的个体或种群之间的相互作用。例子包括相互竞争的策略,以及构成更大解的相互协作的组成部分。此类系统可能出现评估标准不断变化、循环往复,或面对当前对手有所进步、但在固定的外部测试中并无改善的情况。因此,针对这类系统的动态特性,需要采用不同于固定目标优化的评估方法。

实现、计算成本与并行执行

遗传算法的主要成本往往来自候选解的评估,而非选择或交叉。结构仿真、制造过程建模或预测系统的训练,所需时间可能远超对候选解编码进行操作的时间。如果一次运行在每代评估约 NN 个候选解,共运行 GG 代,且每次评估的成本为 CfC_f,那么一个实用的初步估算是 O(GNCf)O(GNC_f),再加上初始化、变异操作和生存者选择的开销。这只是一个成本模型,并非普适的复杂度定理:不同候选解的目标函数评估成本可能不同,而且有些实现会复用评估结果。

当相同的候选解反复出现时,重复检测和缓存可以减少工作量。缓存是否有效,取决于评估器。对于确定性目标函数,同一候选解每次都会得到相同的结果。而含噪声的仿真或随机学习过程可能产生不同的结果,因此复用某一次缓存的观测值会改变适应度的统计含义。重复评估可以估计平均性能,但也会减少用于探索不同解的评估次数。因此,种群管理与评估策略必须协同设计。

候选解的评估通常适合采用并行计算,因为许多评估可以独立运行。在主从模型中,协调者分发评估任务并收集结果。在岛屿模型中,多个种群分别演化,并偶尔进行个体迁移。岛屿模型不仅影响执行方式,也会影响搜索过程:低频迁移有助于保留不同的搜索轨迹,而高频迁移则可能使各个岛屿的行为更接近单一种群。细胞算法将交配和替换限制在邻域内,从而形成另一种具有空间结构的演化方式。

同步执行会等待一批评估全部完成后再推进。异步执行则在各工作节点完成任务时陆续纳入结果,当评估耗时不一致时,这种方式可以减少空闲时间。不过,如果评估较快的候选解获得更多繁殖机会,异步替换就可能引入评估时间偏差。图形处理器可以加速规律性较强且适合批处理的工作负载,但不规则的仿真、存在分支的解码器以及通信开销可能限制其收益。

对于评估成本极高的目标函数,可以利用代理模型,根据已评估的候选解来近似估计适应度。代理模型可以筛选后代、估计有潜力的区域,或判断哪些候选解值得进行精确评估。其预测存在不确定性,在采样稀疏的区域尤其如此。如果选择过程反复偏向代理模型的预测误差,而非真实的性能提升,优化过程就可能利用模型的不准确之处。因此,可靠的代理模型辅助方案会与原始评估器保持一定联系,并记录模型构建和精确评估两方面的成本。

为了使实现具有可复现性,需要记录表示方式、初始化分布、随机种子策略、算子、参数值、替换规则和停止条件。只保存最终候选解,而不保存其解码器或评估配置,可能不足以重现结果。软件的正确性同样重要:排列算子中的索引错误或未及时更新的适应度值,都可能改变表面上的搜索性能,而程序整体看起来仍能正常运行。

在工程、调度和机器学习中的应用

遗传算法适用于评估候选解比直接构造最优解更容易的场景。在工程设计中,染色体可以指定尺寸、材料、部件选择或控制参数。仿真器则计算重量、应力、阻力、效率或成本等指标。随后,演化搜索便可探索不同方案,而无需求取解析形式的导数。离散变量与连续变量混合的设计问题尤其适合这种方法,不过,严格的物理约束和高昂的仿真成本往往需要专门的编码、修复机制或代理模型。

一个有文献记载的航空航天实例,是为美国国家航空航天局(NASA)于2006年发射的“空间技术5号”任务开发的演化式X波段天线设计。该设计通过演化方法探索非传统的导线几何构型,并依据任务要求,利用电磁仿真进行评估。这一案例说明,自动化搜索能够在常见设计类型之外发现实用构型。但它并不能证明遗传算法普遍优于传统电磁优化方法;其意义在于成功整合了表示、仿真、搜索、制造和测试等环节。

调度和路径规划是另一个主要应用领域。调度方案可以将作业分配给机器、为班次安排工作人员,或在满足先后顺序约束的条件下排列任务。染色体可以编码工序序列,也可以编码由调度构建程序解释的优先级。优化目标可能包括完工时间、延误程度、资源利用率或运输成本。由于可行性和局部结构至关重要,成功的系统通常将专门设计的交叉操作与局部改进相结合,而不是对任意编码不加限制地应用二进制算子。

在机器学习中,遗传算法已被用于特征选择、模型配置、规则发现和超参数搜索。二进制染色体可以指明模型使用哪些输入变量,而表示中的另一部分则指定模型设置。适应度可以将预测性能与对所选特征数量的惩罚结合起来。每个候选方案都可能需要训练和评估一个模型,因此,这类搜索的成本远高于对简单数学函数求值。

演化方法还可以优化人工神经网络的权重或架构,这一广泛领域称为神经演化。直接权重演化搜索数值参数,架构演化则搜索网络结构或构建规则。这些方法不同于反向传播,不过,混合系统可以利用梯度训练权重,同时通过演化搜索架构或其他配置。它们各自的实用性取决于评估成本、可微性、搜索空间的维数以及任务的反馈结构。

依赖数据的应用会带来一种特定风险:搜索可能对评估过程本身产生过拟合。反复依据同一个验证集选择候选方案,可能会利用该验证集中的偶然特征。要获得最终的性能估计,需要使用此前从未参与选择或调优的测试集;在数据有限时,嵌套交叉验证等程序可以将模型选择与评估分离。遗传搜索不会仅仅因为不依赖梯度,就免除这些统计学要求。

实证评估、局限性与开放问题

评估遗传算法时,应考察完整的实验流程,而不应只看所报告的最佳单次运行结果。随机初始化和随机变异会使运行结果呈现一定的分布。开展多次独立运行、明确说明计算预算,并报告集中趋势和离散程度,有助于区分稳定可靠的表现与偶然的成功。可用的指标包括最终目标函数值、达到目标的概率、达到目标所需的评估次数、实际运行时间,以及可行解比例。选择何种指标,取决于应用更看重解的质量、可靠性,还是响应速度。

比较算法时,需要采用一致的计算成本核算方式。种群规模不同时,迭代代数相同并不意味着计算投入相同。即使目标函数评估次数相同,也仍可能掩盖局部搜索开销、代理模型训练或并行硬件方面的巨大差异。参数调优同样会消耗资源:将经过大量调优的遗传算法与未经调优的基准方法进行比较,可能会混淆算法设计与实验投入各自带来的影响。合适的基准方法包括随机搜索、领域专用启发式方法、局部搜索,以及在问题实例规模允许时采用的精确方法。

问题本身的性质会显著影响算法的适用性。对于目标函数光滑、连续,且梯度能够以较低成本可靠获取的问题,基于梯度的优化方法通常更有优势。具有特定结构的组合问题,则可能适合采用专门的数学规划方法,从而给出有力的界或证明凭证。当上述条件不成立,或需要探索多种形式的解时,遗传算法可能很有用,但仅有灵活性并不能证明其高效。遗传算法的计算复杂性不会仅仅因为不使用导数或维护一个种群就变得有利。

噪声和非平稳性会带来额外的困难。候选解可能只是因为某次随机评估结果有利而在选择中胜出,并非其期望性能更优。重复测量、考虑不确定性的比较,或对最终入选的候选解进行独立重评,都可以减轻这种影响,但这些措施均会消耗资源。当目标随时间变化时,保留旧的精英个体可能适得其反,除非对其重新评估。保持多样性和保存备选解可能有助于适应变化,但此时相关的性能指标应当衡量对变化目标的跟踪能力,而非向某个固定最优解的收敛程度。

多目标评估也有其自身的度量难题。包含更多候选解的集合,并不一定能更好地逼近帕累托前沿。超体积衡量的是相对于所选参考点,解集在目标空间中所支配区域的体积,因此参考点的选择和各目标的尺度都会影响结果。基于距离的指标可能需要已知或估计的参考前沿。仅展示一幅视觉效果良好的图,可能会掩盖覆盖不足、存在被支配解或计算预算不同等问题。

持续开展的研究正在探索如何学习有用的变量间交互关系、在不过度调参的情况下自适应调整算子、在不确定性下分配评估资源,以及在不扭曲选择机制的前提下利用并行资源。另一个尚未解决的实际问题是可迁移性:在一组基准问题上表现良好的参数和编码方式,面对结构不同的新实例时,可能表现不佳。分析失败案例、开展算子消融实验,并在真正留出、未参与开发调优的问题实例上进行评估,有助于判断哪些组成部分利用了可复用的结构,哪些只是适配了特定的实验设置。