实数编码遗传算法中交叉算子的研究与改进
- 格式：pdf
- 大小：283.14 KB
- 文档页数：8
下载文档原格式
合集下载
如何在遗传算法中应用交叉和变异操作
如何在遗传算法中应用交叉和变异操作遗传算法是一种模拟生物进化过程的优化算法，它通过模拟自然选择、交叉和变异等操作，逐步优化问题的解。
在遗传算法中，交叉和变异操作是非常重要的步骤，它们能够增加算法的搜索空间，提高算法的收敛速度和解的质量。
本文将探讨如何在遗传算法中应用交叉和变异操作。
一、交叉操作的原理和应用交叉操作是遗传算法中的一种重要操作，它模拟了生物进化过程中的基因交换。
在交叉操作中，通过将两个个体的染色体进行交叉，产生新的个体。
交叉操作的主要目的是增加种群的多样性，避免算法陷入局部最优解。
在遗传算法中，交叉操作通常分为单点交叉和多点交叉两种。
单点交叉是指在染色体上选择一个交叉点，将两个个体的染色体在交叉点处进行切割，然后交换切割后的片段，形成新的个体。
多点交叉则是选择多个交叉点，将两个个体的染色体在这些交叉点处进行切割和交换。
交叉操作的应用非常广泛。
在求解函数优化问题时，通过交叉操作可以将两个个体的优良特征进行组合，产生更优的个体。
在求解组合优化问题时，交叉操作可以将两个个体的部分解进行组合，形成新的解。
此外，在求解机器学习问题时，交叉操作也可以用于模型参数的组合和优化。
二、变异操作的原理和应用变异操作是遗传算法中的另一种重要操作，它模拟了生物进化过程中的基因突变。
在变异操作中，通过对个体的染色体进行随机的变异，产生新的个体。
变异操作的主要目的是增加种群的多样性，引入新的解空间。
在遗传算法中，变异操作通常是对染色体中的基因进行随机的变动。
变异操作的方式有很多种，如基因值的随机变动、基因位置的随机交换等。
变异操作的概率通常设置为一个较小的值，以保证种群的多样性。
变异操作在遗传算法中有着广泛的应用。
在求解函数优化问题时，通过变异操作可以引入新的解，避免算法陷入局部最优解。
在求解组合优化问题时，变异操作可以对解的部分进行随机的变动，寻找更优的解。
在求解机器学习问题时，变异操作可以用于优化模型的参数。
实数编码遗传算法中交叉算子的研究与改进
实数编码遗传算法中交叉算子的研究与改进
王巍，彭力
江南大学通信与控制工程学院控制研究中心，江苏无锡（214122）
E-mail：wangwei8311@
摘 要：为了克服实数编码遗传算法进化过程易于停滞的缺点，从个体以及种群的平均适应
度两个方面，对常用的中间重组交叉算子进行了详细的分析。并在进一步思考了其他两种改
的个体在下一代的期望复制数为 1”这一事 实的证明，可以看出：这会导致比例选择操 作失去了效力，出现了对每一个个体都复制 一次的结果，即等概率复制。
综上所述，采用中间重组的交叉操作， 父代与子代的平均适应度几乎不发生变化， 并且种群中的个体会趋于相同，使进化过程 停滞。
基于这种观点，对上面图 1 加以分析。 分析如下：虽然中间重组的交叉操作从始至 终不会改变父代与子代的平均适应度，但在 进化开始时，由于初始种群个体的多样性， 选择算子会起到作用，使得种群的平均适应 度有所上升，随着进化的进行，种群中的个 体会趋于相同，导致个体的适应度都约等于 平均适应度，这就使得比例选择操作失去了 效力，而变异只能产生个别的新解，所以造 成了寻优过程的停滞不前。这也就是图 1 中 的曲线开始时上升，随后趋于平缓，而收敛 不到全局最优解的原因了。
f avg (t + 1) =
f (x(t)) + βf ( y(t) − x(t)) + 2
f ( y(t)) + αf (x(t) − y(t))
= f (x(t)) + f ( y(t)) + f (x(t) − y(t)) (α − β )
2
2
= f avg (t) + Δ
(8)
其中
Δ=
f (x(t) − y(t)) (α − β ) 。
评＂遗传算法交叉操作的改进＂
１ ２ 实数 编码 ．
子 。ｒ ｌ ｓ ｓ 、ｒ２为父 代 染色体 ，与 ２ １ 同 ， ｔ ｔ ．相
ｒｔ（）＝ ｚ ｔ（）＋（ （ ） ｔ（） ｓ （）Ｘｒ ｌ ｚ （）一 ）Ｘ ｓ ３ ｓ ｒ２
作者简介 ：杨 国军（ ９ ３一） １７ ，男，工程 师 ，硕 士。研 究方 向：仿 生优化 算法 ，伟 列天线 。陈丽娟 （ ９ １一） １７ ，女 ，硕 士。研 究方向 ：遗传算 法。机 械设 计及 其 自动化 。王 桂娟
（９ ０一） １８ ，女 ，助 理 工程 师。研 究方 向 ：雷 达数 据 处 理。
收稿 日期 ：２ｃ － － ０ｒ ０ １ ７５ ０
由于 Ｈ ｍ ｉｇ ａ ｍｎ 悬崖 的存在 ，二进制编码应用 于函数优 化问题 存在严重缺 陷 。Ｈ ｍ ｉ Ｊ ａ ｍｎ ｇ悬崖 是指表现型空间 中距 离很小 的个体对 可能有很大 的 Ｈ ｍ ｉ 距 离。 如 染 色 体 ０ １１１１ 和 ａｍｎ ｇ １１１１ １００００属于表现型空 间中的相邻点，但它们却 ００００ 在基 因型空 间具有最大 的 Ｈ ｍ ｉ 距离 ，为了翻 ａ ｍｎ ｇ 越 Ｈ ｍｎ 悬崖 ，染 色体 的所有位需要 同时进行 ｍ ａ ｉ ｇ 改变 ，由交叉和变异实 现翻越 的可能性很 小 ，所 以，在这种情况下 ，二进 制编码无法维 持表现型
程 洪凯（９ ２一） １８ ，男，助理 工程 师。研 究方 向：计算机 科
学与技术。
２ ２
维普资讯
评“ 遗传算 法交叉操作 的改进”
空 间 中点 的位 置 。 同时 ，当 函 数 的维 数 高 、优 化 要求 精度 高 时 ，二进 制 编 码 染 色 体 维 数 会 非 常庞 大 ，计 算 量将 十分可 观 。
要 从 算法的计算效率 、求解精度以及算法 的适应性 出发 ，详细分析 了交叉 算子对算 法搜 索能 力的影
子 。ｒ ｌ ｓ ｓ 、ｒ２为父 代 染色体 ，与 ２ １ 同 ， ｔ ｔ ．相
ｒｔ（）＝ ｚ ｔ（）＋（ （ ） ｔ（） ｓ （）Ｘｒ ｌ ｚ （）一 ）Ｘ ｓ ３ ｓ ｒ２
作者简介 ：杨 国军（ ９ ３一） １７ ，男，工程 师 ，硕 士。研 究方 向：仿 生优化 算法 ，伟 列天线 。陈丽娟 （ ９ １一） １７ ，女 ，硕 士。研 究方向 ：遗传算 法。机 械设 计及 其 自动化 。王 桂娟
（９ ０一） １８ ，女 ，助 理 工程 师。研 究方 向 ：雷 达数 据 处 理。
收稿 日期 ：２ｃ － － ０ｒ ０ １ ７５ ０
由于 Ｈ ｍ ｉｇ ａ ｍｎ 悬崖 的存在 ，二进制编码应用 于函数优 化问题 存在严重缺 陷 。Ｈ ｍ ｉ Ｊ ａ ｍｎ ｇ悬崖 是指表现型空间 中距 离很小 的个体对 可能有很大 的 Ｈ ｍ ｉ 距 离。 如 染 色 体 ０ １１１１ 和 ａｍｎ ｇ １１１１ １００００属于表现型空 间中的相邻点，但它们却 ００００ 在基 因型空 间具有最大 的 Ｈ ｍ ｉ 距离 ，为了翻 ａ ｍｎ ｇ 越 Ｈ ｍｎ 悬崖 ，染 色体 的所有位需要 同时进行 ｍ ａ ｉ ｇ 改变 ，由交叉和变异实 现翻越 的可能性很 小 ，所 以，在这种情况下 ，二进 制编码无法维 持表现型
程 洪凯（９ ２一） １８ ，男，助理 工程 师。研 究方 向：计算机 科
学与技术。
２ ２
维普资讯
评“ 遗传算 法交叉操作 的改进”
空 间 中点 的位 置 。 同时 ，当 函 数 的维 数 高 、优 化 要求 精度 高 时 ，二进 制 编 码 染 色 体 维 数 会 非 常庞 大 ，计 算 量将 十分可 观 。
要 从 算法的计算效率 、求解精度以及算法 的适应性 出发 ，详细分析 了交叉 算子对算 法搜 索能 力的影
遗传算法的变异和交叉操作研究
遗传算法的变异和交叉操作研究遗传算法的变异和交叉操作研究遗传算法是一种基于生物进化原理的优化算法，通过模拟生物进化过程中的遗传与适应性选择来寻找最优解。
其中，变异和交叉是遗传算法中两个重要的操作，它们在搜索空间中引入多样性和探索新解，从而提高算法的收敛性和搜索效率。
本文将对遗传算法的变异和交叉操作进行研究。
首先，我们来介绍变异操作。
变异是指在遗传算法中，通过对个体基因或染色体进行随机或有规律的改变，以产生新的个体。
变异操作的作用是维持种群的多样性，防止算法陷入局部最优解。
常用的变异操作包括位点变异、片段变异和基因重组等。
位点变异是指在染色体中的一个或多个位点上，随机或有规律地改变基因的取值。
例如，对于二进制编码的染色体，可以通过随机翻转某一位上的0或1来进行变异。
而对于实数编码的染色体，则可以通过增加或减小染色体上的某一基因值来进行变异。
位点变异操作可以在搜索空间中引入随机性，有助于遗传算法跳出局部最优解，从而更好地探索全局最优解。
片段变异是指对染色体中的一段基因进行改变。
这种变异操作可以在搜索空间中引入更大范围的变化，由此提高了算法的探索能力。
例如，在染色体中选择一个片段，然后将该片段进行翻转或交换位置，从而产生一个新的个体。
基因重组是指通过交叉操作将两个个体的染色体进行部分交叉，从而产生新的个体。
交叉操作的目的是将两个个体的优良特性进行组合，以产生具有更好适应性的后代。
常用的交叉操作包括单点交叉、多点交叉和均匀交叉等。
单点交叉是指在染色体中选择一个交叉点，然后将两个个体的染色体在该交叉点处切割，交换切割后的染色体片段，从而产生两个新的个体。
多点交叉和单点交叉类似，只是选择多个交叉点进行切割和交换。
而均匀交叉则是按照一定概率，随机选择两个个体的染色体上的基因进行交叉操作。
这种交叉操作可以更好地保持个体的多样性，有助于全局搜索。
总之，变异和交叉是遗传算法中两个重要的操作，它们通过引入随机性和多样性，提高了算法的搜索能力和全局优化能力。
遗传算法调试及改进策略
遗传算法调试及改进策略遗传算法是一种基于生物进化理论的搜索算法，能够在解决各种优化问题上取得不错的效果。
但是在实际应用中，遗传算法的调试和改进策略也十分重要，本文就此展开讨论。
一、遗传算法的调试策略1、选择算子的调试选择算子是遗传算法中最重要的一步，其作用是筛选出适应度高的个体并进行后代产生。
调试选择算子时，需要注意以下几点：（1）选择算子应具有“竞争性”，即适应度高的个体应该有更大概率被选中，同时不适应度高的个体也有一定的被选中概率，以保证算法具有全局搜索能力。
（2）选择算子应具有一定的随机性，避免算法陷入局部最优解。
（3）选择算子应该能够处理不同类型的编码方式，如二进制编码、实数编码等。
2、交叉算子的调试交叉算子是遗传算法中产生后代的重要步骤，其作用是将两个个体的染色体进行交叉，从而产生新的后代个体。
调试交叉算子时，需要注意以下几点：（1）交叉算子应该具有“多样性”，即不同类型的交叉方式应该有一定的概率被选中，以保证算法的全局搜索能力。
（2）交叉算子应该能够处理不同类型的编码方式，如二进制编码、实数编码等。
（3）交叉算子的位置和长度应该有一定的随机性，以保证算法不会陷入局部最优解。
3、变异算子的调试变异算子是遗传算法中保持种群多样性的重要步骤，其作用是对个体的染色体进行随机变异，从而产生新的后代个体。
调试变异算子时，需要注意以下几点：（1）变异算子应该具有一定的“可控性”，即变异概率应该适当，过高或过低都会影响算法的性能。
（2）变异算子应该能够处理不同类型的编码方式，如二进制编码、实数编码等。
（3）变异算子的位置和长度应该有一定的随机性，以保证算法不会陷入局部最优解。
二、遗传算法的改进策略1、自适应参数调整在遗传算法中，参数的选择对算法的性能至关重要，如种群大小、交叉概率、变异概率等。
为了更好地平衡全局搜索和局部搜索之间的关系，可以采用自适应参数调整策略，根据算法的实际运行情况，动态地调整参数值。
遗传算法实数编码交叉
遗传算法实数编码交叉引言随着人工智能领域的发展，遗传算法作为一种优化算法，逐渐在各领域得到广泛应用。
其中，实数编码交叉是遗传算法中的一个重要工具之一。
本文将介绍实数编码交叉的相关理论和实现方法。
一、实数编码基础知识实数编码是指将优化问题中的一组实数向量作为染色体，每个实数称为染色体的一个基因。
这种编码方式将连续优化问题离散化，转化成离散优化问题，便于应用遗传算法等离散优化方法求解。
实数编码把寻优参数的取值范围的精细度作为调节参数，以提高求解精度。
二、实数编码交叉1.单点交叉单点交叉是遗传算法中最基本的交叉方法之一，也适用于实数编码。
该方法随机选择染色体上的一个交叉点，然后分别将两个染色体在该点前后分成两部分进行交叉。
单点交叉方法相对简单，但由于仅考虑染色体的一个点，容易陷入局部最优解，随着维度的增加，交叉的效果逐渐减弱，收敛速度慢。
2.多点交叉多点交叉是单点交叉的扩展形式，它随机选择多个交叉点，然后按照交叉点的位置分别对两个染色体进行交叉。
多点交叉能够有效地避免陷入局部最优解和增强搜索空间的多样性，因此被广泛应用。
3.均匀交叉均匀交叉是另一种常用的实数编码交叉方法，其交叉方式如下：（1）设定某个交叉概率Pc，对两个染色体的每个基因进行独立随机抽样，在抽样点上进行交叉；（2）抽样第i个基因时，以Pc的概率执行交叉，否则直接从父代中继承对应基因。
均匀交叉方法考虑了连续优化问题的特性，保留了每个染色体中所有基因的信息，而不是仅考虑单个点的信息，相对于单点交叉，交叉能力得到了显著提高。
三、实数编码交叉的改进策略为了进一步提高遗传算法的求解效果和搜索速度，研究者们提出了一系列实数编码交叉的改进策略。
主要包括比例均匀交叉、指数分布交叉、正态分布交叉、分段线性交叉等。
其中，指数分布交叉是一种流行的交叉方式，其交叉概率如下：p_{ki}=\left\{\begin{aligned}\frac{1}{2}(1-\frac{2|x_{ki}-\frac{1}{2}|^\beta}{2^\beta-1}),\ if\ r_i<r_c\\ 1-\frac{1-p_c}{L-1}(L-|k-k_i|),\ if\ r_i\geq r_c\\\end{aligned}\right.其中，k表示染色体上的位置，i表示父代之一的染色体下标，r_i代表从[0,1]间均匀采样得到的随机数，r_c为指定交叉概率，L为染色体长度，x_{ki}表示染色体k中位置为i的基因值，β为指数参数。
自适应遗传算法交叉变异算子的改进
自适应遗传算法交叉变异算子的改进
自适应遗传算法交叉变异算子的改进是一种能够更好地适应复杂环境的遗传算法变异
算法。
传统的遗传算法变异算子需要在交叉变异的过程中设置固定的参数以及变异概率，
这一流程给实施遗传算法带来了很多困难，经常无法得到期望的结果。
为了解决这一问题，目前提出了自适应遗传算法交叉变异算子的改进思想。
自适应遗传算法交叉变异算子的改进，使用学习方法根据环境条件，动态调整变异参
数和变异概率。
这样能够有效地根据实际情况，调节算子的参数，获得最优的变异参数和
变异概率，从而提高遗传算法的求解效率。
最后，自适应遗传算法交叉变异算子的改进同时带来了另一个优势：可以更好地调整
遗传算法交叉变异算子参数和变异概率，帮助合理匹配算法参数，减少求解运行过程中的
误差和损失，从而提高遗传算法的求解质量。
遗传算法的研究与优化
遗传算法的研究与优化遗传算法的基本原理遗传算法是一种基于进化思想的优化算法，其基本原理包括个体编码、适应度评价、选择、交叉和变异等步骤。
个体编码是指将问题的解空间中的一个个体用编码的方式表示出来，一般使用二进制编码、实数编码或者排列编码等方式。
适应度评价是指对个体的解的质量进行评价，一般使用目标函数或评价函数来衡量个体的优劣。
选择是指根据个体的适应度值，以一定的概率选择出一部分优秀的个体作为下一代的种群。
交叉是指选取两个优秀个体，通过某种交叉操作来产生新的个体。
变异是指对种群中的个体进行随机的变化，以增加种群的多样性。
通过不断地迭代，种群中的个体将不断地进化，最终得到问题的最优解。
遗传算法的优点在于它能够快速有效地搜索解空间，且对问题的种类没有太强的限制，能够处理复杂的优化问题。
遗传算法的研究现状在遗传算法的研究领域，一些重要的进展正在不断涌现。
研究人员对遗传算法的基本原理和特性进行了深入的研究，提出了各种改进和优化的算法。
遗传算法已经被应用到了各种不同的领域，例如工程设计、机器学习、金融和生物信息学等。
由于遗传算法有着很强的并行化特性，研究人员也在不断地探索并行遗传算法的设计和实现方法。
对于特定问题的优化方法也是遗传算法研究的一个重要方向。
在工程设计领域，研究人员通过引入约束条件和多目标优化等手段，对遗传算法进行了改进，以适应不同的问题类型。
在机器学习领域，研究人员将遗传算法和其他优化方法相结合，提出了各种混合优化算法，取得了一些较好的实验结果。
遗传算法的研究正在不断地向着更高的效率、更广泛的应用场景和更好的解决方案方向发展。
遗传算法的优化方法在遗传算法的优化方法中，有一些常见的改进手段和优化技巧，它们可以使得遗传算法更加有效和高效地搜索解空间。
首先是种群的初始化策略。
在遗传算法中，种群的初始状态对算法的收敛速度和结果品质有着重要的影响。
研究人员对种群的初始化策略进行了深入的研究，提出了各种不同的初始化方法，包括随机初始化、局部优化初始化、自适应初始化等。
基于改进的选择算子和交叉算子的遗传算法
基于改进的选择算子和交叉算子的遗传算法
哎呀，各位朋友，今儿咱来摆摆龙门阵，说说这改进的选择算子和交叉算子的遗传算法。
这算法啊，就像咱们四川的火锅，得选好料，还得有技巧，才能整出那麻辣鲜香的味儿。
咱们先从选择算子说起。
这就好比咱们陕西人挑面，得选那筋道有嚼劲的面条子。
选择算子也得挑那些优质的基因，才能培育出更好的后代。
有时候，咱也得学学北京人那种精细劲儿，得看清楚、想明白，再下手。
这样选出来的基因，才能确保遗传算法的效率和准确性。
再来说说交叉算子。
这就好比咱们四川人做串串香，得把各种食材串在一起，才能烧出那独特的味道。
交叉算子也是这么回事，得把不同的基因片段交叉组合，才能产生新的可能性。
咱得借鉴陕西人的大胆创新，也得学学北京人的稳重务实，在交叉的过程中既要敢于尝试，又得确保稳定可靠。
总的来说啊，这改进的选择算子和交叉算子的遗传算法，就得咱们三地人结合起来，才能把事儿办得漂漂亮亮的。
四川人的灵活变通，陕西人的大胆创新，还有北京人的精细稳重，都得用上。
这样整出来的算法，才能像咱们三地的美食一样，让人回味无穷啊！。
改进的遗传算法求解TSP问题_5改进交叉算子求解TSP问题的研究_41_51
5 改进交叉算子求解TSP问题的研究5.1 引言用遗传算法求解TSP问题的关键就是交叉算子的设计。
通过大量的实践发现，一个好的算子往往能够使群体快速的向最优方向靠拢，反之，则不能达到比较好的效果。
虽然从理论上讲，通过采取一定的方法，譬如，选取初始种群数量足够大，迭代的代数接近无穷大时一定能获得最优解，但实际操作显然是不可能的。
因此，对遗传算法求解TSP问题的交叉算子进行研究和改进，快速地找到近似最优解，无论在学术上还是在应用上都具有十分重要的意义。
5.2 常用交叉算子分析本文的研究主要针对基于路径表示的交叉算子。
人们常用的基于路径表示的交叉算子主要有：部分匹配交叉(PMX)、顺序交叉(OX) 、循环交叉(CX) 、插入交叉(IX) 、两交换启发式(HGA)等算子。
部分匹配交叉(PMX)、顺序交叉(OX) 、循环交叉(CX)这三种算子是最基本的交叉算子，它们使用起来比较简单，而且不会产生非法的路径。
但是它们没有充分考虑TSP问题自身所具有的特点，忽视了父代中边的邻接状况，使得运算效果不理想。
许多的交叉算子都是在它们的基础上设计出来的。
例如：陈国良等在文献[22]中采用的类OX算子，梁艳春等在文献[23]中设计的单点交叉映射算子和单点顺序交叉算子。
这些算子虽然做了一些改进的工作，但效果仍不十分明显。
插入交叉(IX)和两交换启发式(HGA)算子虽然对邻接状况进行了考虑，在交叉的过程中每一步的结果都是在母体的范围内使用贪婪策略进行选择，得到的序列在母体的范围是一种局部最优点列，但是，最后一个城市都没有选择的余地，也就没有考虑染色体最后一个基因和第一个基因之间的距离，同时它们对邻接状况的评价也具有一定的局限性，因此难以保证其选择的优越性。
因此，为克服上述算子的局限性，通过进一步研究，本文提出了两种能够有效利用局部信息，并且能很好的继承父代优秀基因的交叉算子。
通过实例仿真，取得了令人满意的效果。
5.3 顺序插入交叉算子5.3.1 顺序插入交叉算子设计"染色体编码定义为推销员所经过的城市的顺序号，如假设有n个城市1,2,,n染色体12:(,,)n X x x x " ，将上述染色体看成一个环，染色体中n x 的下一个城市为1x 。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2.2.1 对解空间中个体的影响
f ( y(t) + α[x(t) − y(t)]) ，其平均适应度为：
设父代个体中第 i 维变量为 xi (t), yi (t) ， 则第一次交叉后的子代个体中第 i 维变量
为： xi (t + 1), yi (t + 1) ，第二次交叉后子代个
体中第 i 维变量为： xi (t + 2), yi (t + 2) ，如此 循环，第 n 次交叉后子代个体中第 i 维变量
后的平均适应度。
(a) 交叉操作前的平均适应度
(b) 交叉操作后的平均适应度
(c) 交叉操作前的平均适应度
(d) 交叉操作后的平均适应度
图 1 交叉操作前后的平均适应度变化曲线 Fig.1 Changing curves of average fitness using
crossover operator
从图(a)与(b)的对比和(c)与(d)的对比中 可以看出，种群的平均适应度在经过交叉操 作后是几乎不发生变化的。
2.3 小结
为了更好地说明中间重组交叉算子的
给寻优过程带来的影响，先对一事实加以证
明。
下面对“适应度等于平均适应度的个体
在下一代的期望复制数为 1”进行证明。
（3）
其中，α, β ∈ rand (0,1) 。
2.2 中间重组交叉算子的分析
目前，对于实数编码的遗传算法，很多 论文中都采用了这种交叉算子[2][3][4]。下面分 别从解个体的微观层次和整个种群平均适 应度的宏观层次对这种交叉算子进行分析。
-1-
的个体在下一代的期望复制数为 1”这一事 实的证明，可以看出：这会导致比例选择操 作失去了效力，出现了对每一个个体都复制 一次的结果，即等概率复制。
综上所述，采用中间重组的交叉操作， 父代与子代的平均适应度几乎不发生变化， 并且种群中的个体会趋于相同，使进化过程 停滞。
基于这种观点，对上面图 1 加以分析。 分析如下：虽然中间重组的交叉操作从始至 终不会改变父代与子代的平均适应度，但在 进化开始时，由于初始种群个体的多样性， 选择算子会起到作用，使得种群的平均适应 度有所上升，随着进化的进行，种群中的个 体会趋于相同，导致个体的适应度都约等于 平均适应度，这就使得比例选择操作失去了 效力，而变异只能产生个别的新解，所以造 成了寻优过程的停滞不前。这也就是图 1 中 的曲线开始时上升，随后趋于平缓，而收敛 不到全局最优解的原因了。
f avg (t + 1) =
f (x(t)) + βf ( y(t) − x(t)) + 2
f ( y(t)) + αf (x(t) − y(t))
= f (x(t)) + f ( y(t)) + f (x(t) − y(t)) (α − β )
2
2
= f avg (t) + Δ
(8)
其中
Δ=
f (x(t) − y(t)) (α − β ) 。
f (x(t)), f ( y(t)) ，其平均适应度为：
f avg (t) =
f (x(t)) + 2
f ( y(t))
(6)
子代两个体的适应度为：
f (x(t) + β[ y(t) − x(t)])
和
进行交叉后，都不会导致平均适应度的变
化，所以，解个体在进行交叉后，也不会使
整个种群的平均适应度发生变化。
则子代个体中的第 i 维变量的交叉算子
计算式为：
xi (t +1) = yi (t +1) = αxi (t) + (1 − α ) yi (t)
(14) 其中，α = f (x) 。
f (x) + f (y)
3.1.2 均匀算术交叉算子的分析
可以认为(14)式是一种加权操作，其实 质是对适应度大的个体加以较大的权重，使 得子代个体在适应度大的父代个体附近产 生。
中图分类号：TP301.6
文献标识码：A
1. 引言(Introduction)
遗传算法(Genetic Algorithm)是模拟达 尔文的遗传选择和自然淘汰的生物进化进 程 的 计 算 模 型 , 由 美 国 Michigan 大 学 的 J.Holland 教授创建的。是一种高度并行的随 机化搜索的自适应的组合优化算法。该算法 不需要求导或其他辅助知识，只是通过影响 搜索方向的目标函数和相应的适应度函数 来寻求最优解。在许多领域得到了应用。
2
当α = β 时， f avg (t + 1) = favg (t) ，说
明父代种群中的任意两个体在经过交叉操
作后，平均适应度不变。由上述 x(t), y(t) 选
取的任意性，可知整个种群的平均适应度也
是 不 变 的 ； 当 α≠β 时 ， 由 于
α, β ∈ rand (0,1) ， Δ 变化范围很小，所以
(5) 从上面的推导可以看出，中间重组的交 叉算子使得产生解的搜索空间不断缩小。
f avg (t + 1) =
f (x(t + 1)) + 2
f ( y(t + 1))
= f (x(t) + β[ y(t) − x(t)]) + f ( y(t) + α[x(t) − y(t)]) 2
(7)
由于线性组合满足齐次性和叠加性，所以：
交叉后的两子代个体分别为：
x(t + 1) = [x1 (t + 1), x2 (t + 1),Λ , xn (t + 1)] y(t + 1) = [ y1(t + 1), y2 (t +1),Λ , yn (t + 1)]
(2)
其中， xi (t), yi (t) 为父代解向量中对应的第 i 维变量，即第 i 个待优化参数； xi (t + 1), yi (t + 1) 为子代解向量中对应的第 i
f avg (t + 1) ≈ favg (t) 。
②再来考虑解个体有 n 维，即：待优化 参数只有 n 个，并且适应度函数仍为解的线 性组合的情况。在这种情况下，每一维的在
2.2.2 对种群平均适应度的影响
下面推导当采用中间重组的交叉算子
时，子代与父代的平均适应度的关系。
①为了简便，首先考虑解个体只有一
2. 中间重组交叉算子的描述与 分析(Description and analysis of crossover operator)
2.1 中间重组交叉算子的描述
设用于交叉的任意两父代个体分别为：
x(t) = [x1(t), x2 (t),Λ , xn (t)]
(1)
y(t) = [ y1(t), y2 (t),Λ , yn (t)]
③最后，考虑解个体有 n 维，并且适应 度函数为解的非线性组合的情况。在这种情
况下，可对非线性的适应度函数进行线性
化，因此猜想在进行中间重组交叉操作后，
整个种群的平均适应度是不变的，但有待证
明。
通过对非线性的 Shaffer’s F6 函数的仿 真试验，表明父代与子代的平均适应度是不
变的。
Shaffer’s F6 函数表达式为：
f
(
x,
y )= 0.5−
sin 2 x 2 + y 2 − 0 .5 (1 + 0 .001 ( x 2 + y 2 )) 2
分别对α = β 、α ≠ β 时进行仿真试
验。仿真结果如图 1。
图 1 中，(a)和(b)图是当α = β 时，各
-2-
代交叉操作之前和之后的平均适应度；(c)
和(d)是当α ≠ β 时，各代交叉操作之前和之
维变量。从父代到子代交叉变异的公式为：
xi (t + 1) = αxi (t) + (1 − α ) yi (t) = yi (t) + α[xi (t) − yi (t)] yi (t + 1) = βyi (t) + (1 − β )xi (t) = xi (t) + β[ yi (t) − xi (t)]
遗传算法常用的编码方式有两种，一种 是二进制编码，另一种是浮点数编码。这两 种编码方式各有所长，二进制编码方式与浮 点数编码方式相比，搜索能力强，但是浮点 数编码比二进制编码在变异操作上能够保 持更好的种群多样性[1]。
目前，对于实数编码的遗传算法，交叉 操作算子多采用传统的中间重组的方法 [2][3][4]。但是，这种交叉方法易于使寻优过程 停滞，不能得到满意解。因此，很多人也对 此进行了改进，提出了许多改进型的交叉算 子[5][6]，但是，在使用过程中，也出现了问 题。本文对传统的中间重组的方法以及两种 改进型交叉算子进行了分析，并在此基础 上，提出一种新的交叉算子，使得算法不论 在收敛的快速性还是正确性上都有很大的 提高。
为： xi (t + n), yi (t + n) 。
因为 α, β ∈ rand (0,1) ，所以，
xi (t +1), yi (t +1) ∈(min[xi (t), yi (t)],max[xi (t), yi (t)]) xi (t + 2), yi (t + 2)∈(min[xi (t +1), yi (t +1)],
f sum
f sum
f sum
f sum
(12)
其中 fi × n = [( f1 + f2 + Λ + fn ) n]× n = 1，即：
f sum
f sum
适应度等于平均适应度的个体在下一代的