标准规范下载简介：

内容预览由机器从pdf转换为word，准确率92%以上，供参考

0392.基于遗传算法的水资源系统优化方法.docx

m(H, k +1) = (1+ c)m(H, k) (2.11)

若从 k=0 开始，则可得

DB51／T 2795-2021 沥青路面厂拌热再生技术指南.pdfm(H, k) = m(H,0)(1+ c)k (2.12)

上式表明，经选择操作后，平均适应度值高于（或低于）整个群体的平均适应度值 的模式，它所含个体的数目将以指数形式增加（或减少）。

上述是仅考虑选择操作的作用。设单点杂交概率、单点变异概率分别为pc 和pm，某 模式 H 经杂交、变异操作后的生存概率（survival probability）分别为psc 和psm ，则[33]

≥1 一 . (1 一 pm )O(H)

~ 1 一 O(H)pm

于是，某模式 H 在下次进化迭代中经 GA 的选择、杂交、变异操作作用后，该模式所含 个体的数目为

m(H, k +1) ≥ m(H, k) fE |L1 一 e 一 1 pc 一 O(H)pm 」| (2.15)

上式就是 GA 的基本定理——模式定理（schema theorem）。模式定理表明：长度δ (H) 短、阶 O(H)低且平均适应度高于整个群体平均适应度的模式，它所含个体串的数目在 GA 的运行过程中将以指数形式增加。这个结果是指导标准遗传算法（SGA）编码设计 的重要原则。选择的编码策略须尽量使δ (H)短的、 O(H)低的、和问题的本质紧密相关 的模式对应于所求问题的解。例如，选择一个使问题得以自然表达的最小字母表进行编 码，这样使确定规模的群体中包含尽可能多的模式。由于二进制编码方案能获得最大的 模式数，故在 GA 中被广泛采用。

上述分析表明，作为 GA 基本理论的模式定理，为我们提供了一种解释 GA 运行机 理的数学方法，同时对选择和设计编码策略和遗传操作算子策略具有重要的指导作用。

GA 的另一理论是欺骗问题（deceptive problem）。称那些引导遗传算法出错的函数 与编码组合为遗传算法的欺骗问题[33，34]。已有的研究结果表明 ，GA 欺骗问题往往包含 弧立的最优点，即最好的点往往被差点所包围。文献[33]提出了建筑块假设：在 GA 运 行中短的、低阶的、高于群体平均适应度的模式（建筑块，building blocks）逐步组合形 成高阶高于平均的模式，直至产生最优解。根据模式定理，如果一个问题的编码满足建 筑块假设，用 GA 求解效率较高，否则效率较低。低阶建筑块错误地引导搜索过程，不 能发现高阶高于平均的模式，最终使算法发散，找不到最优解，这种现象就是欺骗问题。 研究欺骗问题是为了预测给定问题用 GA 求解的难易程度。Goldberg 设计了一个最小欺

骗问题，旨在尽可能使问题的编码违背建筑块假设，使高阶建筑块最优解不能生成；实 验结果表明，用 GA 求解包含欺骗的问题时得到最优解与得不到最优解的情况均可能发 生，这欺骗不是衡量用 GA 解决问题的难易程度的唯一标准[103]。

2.2.3 遗传算法的收敛性分析[24]

收敛性和收敛速度是评价迭代算法性能的重要指标。 目前对 GA 收敛性分析的各种 结论都是基于标准遗传算法（SGA）模型，而复杂遗传算法的收敛性分析仍是困难的。

定义 2.1 设 Fk *=max{f(s(j，k)j|=1，2，…，n}是第 k 次进化迭代时群体{s(j ，k)} 中的最大适应度值，F*=max{f(s(j)|j=1，2，…，2e }是 GA 所求问题的全局最大适应度值。 则当且仅当

p(Fk* = F* ) = 1 (2.16)

成立时，称 GA 是概率性全局收敛的。其中，p (Fk *= F*)为 Fk *= F*的概率。

定义 2.2[101] 设全局最优串为 s*= g1 * g2 * … ge *，则称任一 gi *为有效基因。若在 某位基因位上，群体中所有串都没有该基因位的有效基因，则称群体有效基因缺失，否 则称群体有效基因不缺失。

lk3 , f < fE

lk4 , f < fE

0 < k1 , k2 , k3 , k4 ≤1

式中，fmax 为群体中最大适应度，fE 为群体的平均适应度，f ，为用于杂交操作的二个串 中较大的适应度，f 是变异串的适应度。

由式(2.17)、(2.18)和(2.19)知，0≤pc 或pm ≤1；当f ，=fmax 时pc=0，当f =fmax 时pm=0。 因此，通过这种自适应杂交算子操作和自适应变异算子操作，可同样实现最优串保存。

GA 的极限分析定理[34，101]：如果在进化迭代过程中，GA 保留最优串，并且算法以 杂交和变异为随机性搜索算子，则对于一个全局优化问题，随着进化代数趋于无穷，GA 将以概率 1 找到全局最优解。该定理表明，GA 能够对搜索空间进行持续的搜索，因此 GA 特别适于全局优化问题。

实现 GA 的全局收敛的基本策略是生成的群体的有效基因不缺失的概率尽可能大， 并在 GA 运行中把已发现的最优串保存下来。最优串保存可以通过合适的选择、杂交、 变异算子操作来实现。随机产生的初始父代群体， 它的有效基因缺失的概率为

选择算子操作是产生有效基因缺失的主要原因。对于非线性强的多峰优化问题，GA 在某次进化迭代过程中获得的最优解很可能是局部最优解，从而选择较多此类基因串， 造成有效基因缺失。这种过强的选择会把群体强有力地吸引到强的局部最优状态，是出 现早熟收敛（premature convergence）的主要原因。理论上，变异算子操作能够避免有效 基因缺失。但由于在标准遗传算法中，变异概率pm 很小，而且变异算子操作是在串的随 机基因位上进行的。因此，标准遗传算法的变异算子操作实际上并不能有效地避免有效 基因缺失。

为阻止 GA 的早熟收敛，需设计合适的选择算子操作，以避免选择算子操作过度受 适应度的影响；另外需设计合适的杂交算子操作、变异算子操作和引入新的基因算子操 作，以保持群体基因的多样性，摆脱局部最优状态。

另外，Rudolph[52]和恽为民等[104]应用齐次有限马尔科夫链证明了标准遗传算法 （SGA）能遍历群体空间，但 SGA 不是全局收敛的。这，SGA 具有全局搜索的能 力，能发现全局最优解，但不能保证每次运行都能收敛于全局最优解，即使计算时间趋 于无穷大。这一点也为许多数值实验所证实。

2.2.4 标准遗传算法的改进方式

标准遗传算法（SGA），至今仍是国内外 GA 应用中常用的实现方案， SGA 由二进 制数编码、随机产生初始群体、个体适应度评价、比例选择算子、单点杂交算子、随机 位变异算子和进化迭代共 7 个步骤组成[33]。大量的理论和应用研究表明， SGA 存在的主 要问题有[24，105]：①SGA 的拓扑结构尚未统一。群体规模、选择方式、杂交方式、变异 方式、收敛判据和其它算法控制参数均需经验确定，易出现早熟收敛。②SGA 的全局优 化性能部分来自于初始群体的随机生成和杂交算子，但由于群体的有限性与解空间的高 维性之间的矛盾，使得搜索的全局性受到很大限制。另外，由于变异概率一般较小，使 得这些少量变异新个体会被大量老个体迅速“同化”，因此 SGA 的全局搜索能力十分有 限。特别是较小的群体规模和选择操作不可避免地使 SGA 存在“近亲繁殖”、早熟收敛。 ③SGA 适于解决缺乏解析知识、复杂、有噪声的动态系统， 目前更适于求解组合优化问 题，对实变量优化问题不太适合。④SGA 的计算精度受编码长度控制， 为得到所需精度

的解通常需要耗费比较长的计算时间，对解空间的大小变化缺乏适应性。为完善 SGA 理论基础和拓宽其应用领域，迫切需要对 SGA 进行多方面的改进[24，71，105]。

实际上 GA 是优化计算的一种方法论，它提供的只是一种算法框架[24，28，71] ，在该 框架的每一步中，都可有多种不同的实现方法，从而可构成多种不同格式的 GA 实现方 案，SGA 只是 GA 最早实现的一种经典格式。换言之，在 SGA 各步骤中都可有不同的 替代方案和改进方式来提高 SGA 的求解效率，以更好地解决各种复杂的实际问题。鉴 于此，本节拟对 SGA 的各种改进方式进行系统深入的探讨， 旨在促进 GA 更深入的理论 研究和更广泛的工程应用。

2.2.4.1 改进编码方式

编码是把各种优化问题的解空间表示为统一形式的数字串空间，其逆过程称为解 码。 借助编码，遗传算子可以有独立于具体优化问题的统一形式，从而使 GA 具有广泛 的适用性。编码既是 GA 理论中的基础，又是 GA 应用中的首要问题。编码方案将影响 GA 的收敛速度和搜索效率，在应用中选择或设计一种便于 GA 求解问题的编码方案常 常需要对问题有深入的理解。GA 从原理上要求使用者采用尽量简单的编码方式来表示 问题的解空间，这样可以使低阶、长度短的、适应度值高的基因模式能够产生更多的后 代从而加快收敛。因此 SGA 采用二进制数编码，而且在 SGA 运行过程中编码方法保持 不变。对于实变量优化问题的求解精度要求较高时，二进制数编码长度将很大，导致计 算量激增，并直接影响全局极值的求解。目前常用的改进方式之一是采用动态参数编码 [34] ，它先让 SGA 从低精度开始搜索，当发现最佳个体越过某个值后，起用变焦操作， 从而提高一倍精度，如此反复。与此类似，可利用在 SGA 运行过程中搜索到的优秀个 体子群体来逐步缩小 SGA 的搜索空间，以解决二进制数编码与解精度的矛盾[106]。

总之，编码须考虑优化问题的解空间特征，所采用的编码方式除了必须保证不丢失 全局最优解外，还应考虑 SGA 的求解效率，并尽量避免产生不可行解，编码方式也可 随着算法不同运行阶段而取不同的形式。

2.2.4.2 改进初始群体的生成方式

实际应用中初始群体的分布将影响 SGA 的搜索效率。由于 SGA 的杂交位置、变异 位置都是随机选取的，这使得 SGA 的收敛速度对初始群体的选择的依赖性较强，收敛 不稳定。用随机方法产生初始群体时《城市地下工程盖挖逆作法结构设计指南》宣贯培训材料（北京市规划和自然资源委员会），要求它们均匀分布于整个解空间，以便 SGA 搜

索全局最优解。若初始群体缺乏多样性，则选择算子和杂交算子的寻优作用不能发挥， 而依靠小变异概率的变异算子进行全局寻优搜索的效率也很低。为提高 SGA 求解的效 率和解的质量，避免早熟收敛，目前的主要改进方式， 一是尽可能使初始群体分布于整 个解空间的不同区域中[109]，二是增大群体规模，如取 300 以上来增强初始群体的多样性 [106]，三是根据应用问题的具体情况采用其它优化方法如 BP 算法[110]、启发式方法或人 工设定方式等来生成初始群体； 四是采用粗粒度、小生境等并行遗传算法方式[109，111]； 五是群体规模随着演化的推进而改变[63，71]。

2.2.4.3 改进适应度函数的定义方式

fi = e Ei / T / e Ej / T ，其中 Ei 为第 i 个个体的目标函数值，N 为群体规模，T 为类似

于模拟退火算法中温度参数，T 值随进化次数 g 的增加而减少[111]。

2.2.4.4 改进选择算子

选择算子主要模拟生物进化过程中的适者生存、优胜劣汰规则。通过选择，低适应 度函数值个体趋向于被淘汰，而高适应度函数值个体趋向于被复制，选择算子的作用是 提高群体的平均适应度值，同时也损失了群体的多样性，在总体上决定群体向着目标函 数值改善的方向进化。SGA 采用的转盘式比例选择算子或繁殖池比例选择算子， 是根据 某个体的适应度函数值占群体适应度函数值之和的比例来确定该个体的选择概率[33，34， 63]，当群体规模较小或群体最大适应度函数值与最小适应度函数值之比很大时， 这些比 例选择算子将使群体的多样性很快丧失，导致早熟收敛。目前的改进方式主要有： 一是 排序选择[63，67]，即个体的选择概率只决定于该个体适应度函数值在群体中的序号（按适 应度函数值从大到小排序），不受适应度函数值的分布和取值范围的直接影响，因此排序 选择不需对适应度函数值进行调整；二是竞争选择[63]，即每次选择就在群体中随机选取 的 k 个个体中选择适应度函数值最大的个体，竞争选择可避免超级个体（当前最大适应 度函数值个体）的影响，可在一定程度上克服早熟收敛；三是通过随着 SGA 的运行调 节适应度函数的形式，来调整个体的选择概率的表达式，如 Boltzmann 竞争选择等[63] ， 或个体选择概率的表达式直接与算法运行的进化代数建立函数关系；四是有条件选择， 如根据某个体与超级个体的距离是否大于给定值来决定该个体的取舍[80]；五是最优个体 保存策略也可视作一种改进的选择算子。

XJJ 075-2016 建筑消能减震应用技术规程.pdf2.2.4.5 改进杂交算子