第1章绪论
自20世纪40年代电子计算机问世以来，机器能否思维一直是人们关注的问题，人工智能的研究经历了曲折的发展过程，作为其主要内容的智能优化算法成为学者和工程师们研究的热点。受生物分子特性和分子操作启发的RNA遗传算法是智能优化算法的重要分支。
1975年，美国Michigan大学的Holland教授，基于达尔文的生物进化论和孟德尔的遗传变异理论，提出了遗传算法[1]（GA）。遗传算法在求解各种复杂优化问题上取得了令人鼓舞的结果[2，3]。自1985年在卡耐基 梅隆大学召开的第一届遗传算法国际会议（International　Conference　on　Genetic　Algorithms）到1997年IEEETransactions　on　Evolutionary　Computation创刊，遗传算法作为一类高性能的智能优化算法渐趋成熟。1989年，Goldberg出版了遗传算法领域的一部重要著作Genetic　Algorithms　in　Search，Optimization　and　Machine　Learning.Michalewicz则在其著作Genetic　Algorithms+Data　Structures=Evolution　Programs中详细介绍了一些实数遗传算子及其典型应用[5]。此后，遗传算法进入了蓬勃发展的时期。
然而，遗传算法并不总是优于专门处理某一领域问题的传统优化算法，围绕进一步改善或提高遗传算法的搜索效率、局部搜索能力以及克服早熟收敛等核心问题，仍需要进行深入的基础研究和理论创新。此外，遗传算法解的不确定性不能保证解的最优性和可行性。要解决复杂问题或难题需要开放性的计算体系和创造性的计算思想，融合RNA分子操作是遗传算法发展的一条蹊径。
下面从基本理论、研究热点问题等方面对遗传算法的研究状况进行简要的回顾。
1.1基本遗传算法
基本遗传算法的框架如图1.1所示。图中，待优化问题的每个变量都用长度为/的二进制染色体串描述，搜索范围的下限对应于编码0，而其上限对应于编码11-1。若包含n个变量，则由长度为L=nxl的二进制染色体串编码表示。通过对随机生成的染色体群体进行选择、交叉和变异操作使整个种群向着最优群体方向进化。
图1.1的基本遗传算法框架中包含了四个参数:交叉概率Pc和变异概率Pm，以及群体规模N和编码长度L。Schaffer等建议的算法参数范围是[6]：Ne[20，200]，Pce[0.5，1.0]，Pme[0，0.05]。图1.1描述的是基本遗传算法，称为SGA或CGA。本书的研究工作是以基本遗传算法为基础展开的。
1.2遗传算法的特点
遗传算法是进化计算中产生最早、影响最大、应用最广的一个重要的研究领域，它包含了进化算法的基本形式和几乎全部优点，如下所示。
（1）直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受所求问题连续性的约束，也没有要求所求问题的导数必须存在。
（2）每一代对群体规模为N的个体进行操作，实际上处理了大约个模式，具有很高的并行性，因而具有显著的搜索效率。
（3）在所求问题为非连续、多峰以及有噪声的情况下，能够以大概率收敛到最优解或满意解，因而具有很好的全局寻优能力。
（4）算法的基本思想简单，运行方式和实现步骤规范，便于使用。
但是，传统的遗传算法还存在如下有待进一步研究的问题。
（1）由于GA需要进行遗传操作，其最优解是群体进化的结果，算法需要的搜索时间较长，因而限制了GA在在线优化问题求解方面的应用。
（2）采用二进制编码的GA，虽然编码和解码操作简单而且交叉、变异等遗传操作易于实现并可用模式定理进行理论分析；但是对连续函数的优化问题，其局部搜索能力较差。对多维、要求高精度的连续函数优化问题，如果个体编码串较短，则可能达不到精度要求；而个体编码串较长时，虽然能提高精度，但是会使算法的搜索空间急剧扩大，从而降低了遗传算法的性能。
（3）传统的遗传算法虽然具有较强的全局搜索能力，能较快地确定全局最优点的大概位置，但是其局部搜索能力较弱，进一步精确求解要耗费较长时间，而且当算法搜索到一定的程度后，所有解收敛到某一局部最优解，不能对搜索空间做进一步的探索。
（4）大多数的实际问题是具有约束条件和多目标的问题，求解具有约束的优化问题是遗传算法面临的一大挑战。能否处理好约束，是能否成功应用遗传算法的一个关键的问题。此外，多目标优化问题的求解也是当前的一个研究热点。
（5）相对遗传算法在应用方面取得的丰硕成就，其理论研究则显得薄弱。由于运行机理非常复杂，遗传算法的理论基础尤其是多目标遗传算法的理论研究还处在进一步的发展和完善过程中。
问题（1）是由遗传算法本身决定的，很难有本质上的改进，但是可通过遗传算法的设计减少寻优迭代次数或进化代数从而使总体的时间复杂度降低，如引入RNA编码和RNA分子操作等，提出RNA遗传算法；针对遗传算法的其他问题，已经有了许多改进方法及研究成果。下面将对遗传算法取得的成果进行简要介绍。本书是在前人工作的基础上，结合DNA计算、RNA计算和生物分子操作，进行RNA遗传算法的研究。
1.3遗传算法的研究进展
1.3.1遗传算法的理论研究
虽然GA求解过程和形式简单，但是其运行机理非常复杂。随着GA在复杂优化问题求解和实际工程中的应用，人们对GA的理论基础给予了越来越多的关注，主要的研究成果如下。
（1）模式定理:设GA的交叉和变异概率分别和，模式的定义距为，阶为，第代种群含有元素的个数期望值记为。
该定理说明那些低阶、短定义距、超过群体平均适应度的模式的数量将随迭代次数的增加而以指数级增长。Holland用其与隐并行性原理来解释GA的作用，是从进化动力学的角度提供了能较好地解释遗传算法机理的一种数学工具，同时也是编码策略、遗传策略等分析的基础。
（2）积木块假设[7]:通过选择、交叉、变异等遗传操作算子的作用，个体的基因链能够相互拼接在一起，形成适应度更高的个体编码串。积木块假设阐述了用遗传算法求解各类问题的基本思想，即通过基因块之间的相互拼接能够产生出问题更好的解。
基于模式定理和积木块假设，使得人们能够在很多应用问题中广泛地使用遗传算法。但是一些研究者们后来相继发现了模式定理、隐并行性原理的不足和不严格之处，而积木块假说又没有给予过证明，遗传算法早期的收敛性理论是不完善的。
（3）遗传算法的新模型。
为了弄清楚遗传算法的机理，近些年来人们建立了各种形式的新模型，如马氏链模型、公理化模型[8]、积分算子模型以及鞅论[9]，其中最为典型的是马氏链模型。遗传算法的马氏链模型主要有三种：种群马氏链模型[叫、Vose模型[11]和Cerf扰动马氏链模型[12]。
种群马氏链模型将遗传算法的种群迭代序列视为一个有限状态马氏链来加以研究，运用模型转移概率矩阵的某些性质来分析遗传算法的极限行为。Vose模型是在无限种群假设下，利用相对频率导出表示种群概率向量的迭代方程，
通过对这一迭代方程的研究，可以讨论种群概率的不动点及其稳定性，从而得出对遗传算法的极限行为的刻画，但是对解释有限种群遗传算法行为的能力相对差一些。Cerf扰动马氏链模型将遗传算法看成一种特殊形式的广义模拟退火模型，并利用动力学系统的随机扰动理论对遗传算法的极限行为及收敛速度进行了研究。
从近期有关遗传算法的收敛性和收敛速度估计的研究结果[13]来看，无论遗传算法的某一特定实现，还是在某一较弱的意义下讨论算法的收敛性，以及在某一特定度量下研究算法的收敛速度，都具有一定的局限性。遗传算法的基础理论还处在进一步的发展和完善过程当中。利用马氏链模型进行遗传算法收敛性分析时，因转移概率的具体形式难以表达，妨碍了对遗传算法的有限时间行为的研究。然而，从随机过程和数理统计角度探讨遗传算法的一般规律，有助于较好地把握遗传算法的特性，以提高求解效率和改善求解效果。
1.3.2遗传算法的编码问题
编码是遗传算法要解决的重要问题，为克服二进制编码存在的缺陷以及其海明悬崖问题，例如，15和16的二进制表示为01111和10000，算法从15变到16必须改变所有的位。为此，研究者们对遗传算法的编码进行了研究，采用了如下的编码。
（1）格雷编码[14]:它是二进制编码方法的一种变形，其连续的两个整数所对应的编码值之间仅有一个码位是不同的，并且任意两个整数的差是所对应的格雷码之间的海明距离，它克服了二进制编码的海明悬崖问题，提高了遗传算法的局部搜索能力。
（2）实数编码:对于一些多维、精度要求高的连续函数优化问题，使用二进制编码来表示个体将会带来一些不利因素，例如，二进制编码存在着连续函数离散化时的映射误差，而且不便于反映所求问题的特定知识。为了克服这些缺点，人们提出了实数编码方法，即个体的每个基因值用实数表示，降低了遗传算法的计算复杂性，提高了运算效率。
（3）符号编码[16]:是指染色体编码串中的基因值取自一个无数值含义、只有代码含义的符号集，这些符号可以是字符，也可以是数字。符号编码的主要优点是便于在遗传算法中利用所求问题的专门知识及相关算法。
此外还有十进制编码、多值编码、动态参数编码、Delta编码、混合编码、RNA编码、DNA编码、氨基酸编码等多种编码形式，这些编码形式各有优缺点。
1.3.3求解约束问题的遗传算法
求解具有约束的优化问题对遗传算法来说是一种挑战，与处理无约束优化问题的大量文献相比，用GA求解约束优化问题的文献比较少。目前尚无GA专属的约束处理方法，用于GA处理约束的方法分为以下4类。
（1）罚函数法。
罚函数法是最常见的一种约束处理方法，尤其是针对不等式约束。该方法最早由Courant提出[17]，并有不少研究者进行了扩充和改进，出现了各种罚函数法。静态罚函数法指罚参数在遗传算法的整个进化过程中保持不变[18]，其不足是罚参数的选择缺乏通用性，需根据特定的问题来确定。动态罚函数法[19]与静态罚函数法相比，具有更好的寻优性能，然而，实际上很难设计较好的动态罚函数，而静态罚函数法存在的问题在动态罚函数法中同样存在。自适应罚函数法[2。]中的罚函数取决于搜索过程的反馈信息，该方法需要事先定义一些参数值，并限定罚参数的变化范围，以避免罚参数的跳变。为避免罚参数的经验整定，又有学者提出了一些方法选择罚参数来有效处理约束问题。
（2）特定的编码和操作算子。
由于传统二进制编码存在缺陷，一些学者针对特定的具有约束的优化问题，提出了特定的编码策略。由于编码的改变，需要设计特定的操作算子以适合于求解优化问题。编码改变的目的在于简化搜索空间形态，以及利用特定的操作算子来保证解的可行性[21]。这种约束处理方法主要用于可行解很难获取的具有约束的优化问题，虽然对特定的问题可以获得较好的效果，但是这种方法的推广性不强。
（3）修复法。
修复法是通过某种程序修复进化过程所出现的不可行染色体，使其变为可行的染色体[22]。该方法多见于求解组合优化问题，其原因在于求解组合优化问题时修复程序相对容易产生。修复法的优点是对个体编码、遗传算子等没有其他的附加要求，并可期望遗传搜索能够从可行解和不可行解的两侧最终趋近最优解。修复法的缺点是对问题本身有依赖性，以扩大搜索空间为代价。但是对于某些问题，修复过程甚至比原问题的求解更复杂[23]。
（4）目标和约束分离法。
采用目标和约束进行分离的方法有很多种，例如，协作进化方法使用两个种群进行约束和适应度函数值的同时进化，并保留同属于两个种群的个体[24]。

目录
前言
外文缩写对照列表
第1章 绪论 1
1.1 基本遗传算法 1
1.2 遗传算法的特点 2
1.3 遗传算法的研究进展 4
1.3.1 遗传算法的理论研究 4
1.3.2 遗传算法的编码问题 5
1.3.3 求解约束问题的遗传算法 6
1.3.4 混合遗传算法 7
1.3.5 融合分子操作的遗传算法 7
1.3.6 多目标遗传算法 8
1.4 遗传算法的系统建模 10
1.5 本书的主要内容 11
参考文献 12
第2章 RNA遗传算法 17
2.1 引言 17
2.2 RNA-GA 18
2.2.1 RNA编码和解码 18
2.2.2 RNA序列基本操作算子 19
2.2.3 基本遗传算法 20
2.2.4 RNA遗传算法及操作算子 20
2.2.5 RNA-GA算法实现步骤 23
2.3 RNA-GA全局收敛性分析 23
2.4 RNA-GA性能分析 26
2.4.1 测试函数 26
2.4.2 RNA-GA参数适应性分析 29
2.4.3 RNA-GA与SGA寻优对比研究 31
2.5 小结 37
参考文献 38
第3章 具有茎环操作的RNA遗传算法 40
3.1 引言 40
3.2 srRNA-GA 41
3.2.1 编码和解码 41
3.2.2 选择操作 41
3.2.3 相似剔除操作 42
3.2.4 交叉操作 42
3.2.5 变异操作 44
3.2.6 简单局部搜索 44
3.2.7 srRNA-GA的实现步骤 45
3.3 测试函数寻优实验 46
3.3.1 测试函数 46
3.3.2 实验结果和分析 46
3.4 小结 50
参考文献 50
第4章 受蛋白质启发的RNA遗传算法 52
4.1 引言 52
4.2 PIRNA-GA 52
4.2.1 编码和解码 52
4.2.2 选择操作 54
4.2.3 交叉操作 55
4.2.4 变异操作 57
4.2.5 PIRNA-GA算法的实现 59
4.3 测试函数寻优实验 60
4.3.1 测试函数 60
4.3.2 计算结果与分析 61
4.4 小结 66
参考文献 67
第5章 信息熵动态变异概率的RNA遗传算法 69
5.1 引言 69
5.2 edmpRNA-GA 70
5.2.1 编码方式 70
5.2.2 选择操作 70
5.2.3 交叉操作 70
5.2.4 变异操作 70
5.2.5 edmpRNA-GA算法实现过程 72
5.3 约束处理 74
5.4 测试函数寻优实验 75
5.4.1 测试函数 75
5.4.2 寻优结果与分析 77
5.5 小结 79
参考文献 80
第6章 自适应策略的RNA遗传算法 82
6.1 引言 82
6.2 ARNA-GA 83
6.2.1 编码方式 83
6.2.2 遗传操作自适应策略 83
6.2.3 选择算子 85
6.2.4 交叉算子 85
6.2.5 变异算子 85
6.2.6 终止条件 87
6.2.7 ARNA-GA算法的实施步骤 87
6.3 测试函数寻优实验与结果分析 88
6.3.1 测试函数 88
6.3.2 参数设置 89
6.3.3 实验结果与分析 89
6.4 小结 93
参考文献 93
第7章 发夹交叉操作RNA遗传算法的桥式吊车支持向量机建模 95
7.1 引言 95
智能优化算法：RNA遗传算法

viii
7.2 *小二乘支持向量机 96
7.3 发夹交叉操作RNA遗传算法 97
7.3.1 编码和解码 97
7.3.2 交叉算子 97
7.3.3 变异算子 99
7.3.4 选择算子 99
7.3.5 算法的实现步骤 99
7.4 桥式吊车支持向量机建模方法和仿真实验结果 101
7.5 小结 104
参考文献 104
第8章 发夹变异操作RNA遗传算法的桥式吊车神经网络建模 106
8.1 引言 106
8.2 RBF 神经网络 107
8.3 发夹变异操作的RNA遗传算法 108
8.3.1 编码和解码 108
8.3.2 交叉算子 108
8.3.3 变异算子 108
8.3.4 选择算子 109
8.3.5 算法的实现步骤 109
8.4 神经网络桥式吊车建模方法与仿真实验结果 111
8.5 小结 115
参考文献 115