论文部分内容阅读
[摘 要] 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。采用简单的编码技术来表示各种复杂的结构，进行简单的遗传操作和优胜劣汰的自然选择来确定搜索方向。采用种群的方式组织搜索，使得它可以同时搜索解空间内的多个区域且适合大规模并行搜索。全局优化中的函数优化问题是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。
[关键词] 生物进化 遗传算法 全局优化
遗传算法是模拟生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种重要形式。同时，遗传算法是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制条件的约束，不需要有先验条件。其搜索过程是从问题解的一个随机产生的集合开始的，而不是从单个个体开始的，具有隐含并行搜索特性，也就大大减少可陷入局部极小值的可能。
1.基本遗传算法
Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质，所以每个基因产生的个体对环境具有某种适应性。基因突变和基因交叉可产生更适应于环境的后代。经过优胜劣汰的自然选择，适应性高的基因结构得以保存下来。
在基本遗传算法的运行过程中，控制参数的选择对搜索性能产生非常大的影响。因此对参数的合理选择与控制是十分重要的，以使 GA 呈现最佳搜索轨迹最终得到最优解。主要的控制参数包括染色体的长度L,种群规模M，交叉概率pc，变异概率pm。
作为一个优化算法，基本遗传算法也具有一些缺点，主要体现在以下几个方面。
首先，基本遗传算法是一类随机搜索型算法，而非确定性迭代过程描述。这种广种薄收的算法计算效率较低。
其次，对基本遗传算法的数值试验表明，算法经常出现过早收敛的现象。
第三，基本遗传算法的遗传和变异的完全随机性虽然保证了进化的搜索功能，但是这种随机变化也使得一些好的优良个体的形态被过早破坏，降低了各代的平均适应值。
第四，Rudolph通过 Markov 链方法证明了基本遗传算法是不收敛到最优解的。
第五，基本遗传算法中常采用伪随机函数(rand)产生的“随机数”来生成初始种群和控制遗传算子的操作，这些“随机数”不具备真正的随机性和遍历性，很大程度上影响到最优解的出现。
基于这些局限性，本设计在下文中提出了一种改进的遗传算法，针对这些问题提出了几种有效的解决方案。
2.改进遗传算法的设计
2.1 遗传算法的收敛性的定义
Rudolph 给出了一种针对个体的收敛性定义：
设 Zt为 t 时刻种群 X(t)中所包含的个体的适应度值的最大值，f*为适应度值函数 f(x)在所有可能的个体所组成的集合中所取的最大值，若 Zt满足:
（2.1）
则称算法收敛到最优解。
2.2 精英保留策略
针对基本遗传算法不能收敛到全局最优解的问题，本设计提出，在进行选择前用保留最优解的策略，使算法最终能以100%的概率收敛到最优解。
精英保留策略是改进的遗传算法收敛性的保证。
2.3 引入混沌的遗传算子
⑴Logistic映射在交叉操作中的应用
用混沌序列来控制交叉点的选择的思想为:设染色体有L位长，先产生一个混沌序列，然后把序列。映射到染色体的基因位空间，并在相应的位置进行交叉操作。
⑵Logistic映射在变异操作中的应用
用混沌序列来控制变异位置的选择的思想为:设染色体有L位长，先产生一个混沌序列，然后把序列映射到染色体的基因位空间，并在相应的位置进行变异操作。
本设计中，采用Logistic映射产生混沌序列来控制遗传算子操作的策略称为混沌控制策略，它的优点在于在遗传进化的过程中充分利用了混沌所具有的随机性，尤其是混沌的遍历性，使交叉和变异操作具有内在的规律性，克服了简单遗传算法中伪随机所带来的缺点，充分发挥了遗传算法和混沌的各自优点。
2.4 自适应交叉和变异率算子
本设计中提出自适应交叉和变异率算子：当适应度低于平均适应度值时对它就采用较大的交叉率和变异率；如果适应度高于平均适应度值，对它就根据其适应度值取相对应的交叉率和变异率。当适应度值接近最大适应度值时，交叉率和变异率就越小；当等于最大适应度值时，交叉率和变异率的值为零。为了保证每一代的优良个体不被破坏，采用精英选择策略，使它们直接复制到下一代中。
经过上述改进，pc和pm计算表达式如下：
（2.2）
（2.3）
上式中pc1，pc2，pm1，pm2的取值需要根据实际问题的规模，通过多数实验验证得到。
2.5 灾变算子设计
设计中引用了灾变的思想：在种群适应值保持在一个稳定值一段时间后，发生灾变，杀掉最优秀的个体，这样才可能产生更优秀的物种。
3.实验环境
实验测试的环境和工具:
⑴ 硬件环境:Intel Pentium® T4200@2.00GHz+ 2G RAM;
⑵ 操作系统:Mierosoft Windows xp Professional;
⑶ 编译环境: microsoft visual c++ 6.0;
⑷ 测试函数:
4.结论
⑴知道遗传算法的设计要从大体五个方面来设计：编码，初始种群的设定，适应度函数的设计，遗传操作的设计和控制参数的设定。在很好地设计一种遗传算法，且将其进行具体实际的应用，怎样去很好地选择、平衡这五个方面使算法得到更加理想的效果，这还需要继续进行试验研究，探讨。
⑵在进行遗传算法理论分析研究时，发现相关理论分析比较少。每一种设计的遗传算法都是将其进行具体的应用，所以算法的灵活性比较大，这样去寻求一种概括性的理论分析就存在一定的难度，且本设计提出的自适应遗传算法，从理论上分析研究其收敛到全局最优，仍然需要进一步的研究。
⑶关于遗传算法的定量分析和数学证明，仍需要进一步的研究。
参考文献:
[1]王小平，曹立明.遗传算法—理论应用与软件实现[M].西安：西安交通大学出版社，2002：21-22.
[2]张明辉，王尚锦.自适应遗传算法及其应用[J].机械工程学院学报，2002，20(1)：23-25.
[3]雷德明.多目标智能优化算法及其应用[M].北京：科学出版社，2009：67-78.
[4]李敏强，寇纪淞，林丹等.遗传算法的基本理论与应用[M].北京：科学出版社，2004：55-57.
作者简介：
周嘉：（1988—），男，湖南城市学院计算机应用专业2007级学生，从事优化算法研究。
[关键词] 生物进化 遗传算法 全局优化
遗传算法是模拟生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种重要形式。同时，遗传算法是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制条件的约束，不需要有先验条件。其搜索过程是从问题解的一个随机产生的集合开始的，而不是从单个个体开始的，具有隐含并行搜索特性，也就大大减少可陷入局部极小值的可能。
1.基本遗传算法
Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质，所以每个基因产生的个体对环境具有某种适应性。基因突变和基因交叉可产生更适应于环境的后代。经过优胜劣汰的自然选择，适应性高的基因结构得以保存下来。
在基本遗传算法的运行过程中，控制参数的选择对搜索性能产生非常大的影响。因此对参数的合理选择与控制是十分重要的，以使 GA 呈现最佳搜索轨迹最终得到最优解。主要的控制参数包括染色体的长度L,种群规模M，交叉概率pc，变异概率pm。
作为一个优化算法，基本遗传算法也具有一些缺点，主要体现在以下几个方面。
首先，基本遗传算法是一类随机搜索型算法，而非确定性迭代过程描述。这种广种薄收的算法计算效率较低。
其次，对基本遗传算法的数值试验表明，算法经常出现过早收敛的现象。
第三，基本遗传算法的遗传和变异的完全随机性虽然保证了进化的搜索功能，但是这种随机变化也使得一些好的优良个体的形态被过早破坏，降低了各代的平均适应值。
第四，Rudolph通过 Markov 链方法证明了基本遗传算法是不收敛到最优解的。
第五，基本遗传算法中常采用伪随机函数(rand)产生的“随机数”来生成初始种群和控制遗传算子的操作，这些“随机数”不具备真正的随机性和遍历性，很大程度上影响到最优解的出现。
基于这些局限性，本设计在下文中提出了一种改进的遗传算法，针对这些问题提出了几种有效的解决方案。
2.改进遗传算法的设计
2.1 遗传算法的收敛性的定义
Rudolph 给出了一种针对个体的收敛性定义：
设 Zt为 t 时刻种群 X(t)中所包含的个体的适应度值的最大值，f*为适应度值函数 f(x)在所有可能的个体所组成的集合中所取的最大值，若 Zt满足:
（2.1）
则称算法收敛到最优解。
2.2 精英保留策略
针对基本遗传算法不能收敛到全局最优解的问题，本设计提出，在进行选择前用保留最优解的策略，使算法最终能以100%的概率收敛到最优解。
精英保留策略是改进的遗传算法收敛性的保证。
2.3 引入混沌的遗传算子
⑴Logistic映射在交叉操作中的应用
用混沌序列来控制交叉点的选择的思想为:设染色体有L位长，先产生一个混沌序列，然后把序列。映射到染色体的基因位空间，并在相应的位置进行交叉操作。
⑵Logistic映射在变异操作中的应用
用混沌序列来控制变异位置的选择的思想为:设染色体有L位长，先产生一个混沌序列，然后把序列映射到染色体的基因位空间，并在相应的位置进行变异操作。
本设计中，采用Logistic映射产生混沌序列来控制遗传算子操作的策略称为混沌控制策略，它的优点在于在遗传进化的过程中充分利用了混沌所具有的随机性，尤其是混沌的遍历性，使交叉和变异操作具有内在的规律性，克服了简单遗传算法中伪随机所带来的缺点，充分发挥了遗传算法和混沌的各自优点。
2.4 自适应交叉和变异率算子
本设计中提出自适应交叉和变异率算子：当适应度低于平均适应度值时对它就采用较大的交叉率和变异率；如果适应度高于平均适应度值，对它就根据其适应度值取相对应的交叉率和变异率。当适应度值接近最大适应度值时，交叉率和变异率就越小；当等于最大适应度值时，交叉率和变异率的值为零。为了保证每一代的优良个体不被破坏，采用精英选择策略，使它们直接复制到下一代中。
经过上述改进，pc和pm计算表达式如下：
（2.2）
（2.3）
上式中pc1，pc2，pm1，pm2的取值需要根据实际问题的规模，通过多数实验验证得到。
2.5 灾变算子设计
设计中引用了灾变的思想：在种群适应值保持在一个稳定值一段时间后，发生灾变，杀掉最优秀的个体，这样才可能产生更优秀的物种。
3.实验环境
实验测试的环境和工具:
⑴ 硬件环境:Intel Pentium® T4200@2.00GHz+ 2G RAM;
⑵ 操作系统:Mierosoft Windows xp Professional;
⑶ 编译环境: microsoft visual c++ 6.0;
⑷ 测试函数:
4.结论
⑴知道遗传算法的设计要从大体五个方面来设计：编码，初始种群的设定，适应度函数的设计，遗传操作的设计和控制参数的设定。在很好地设计一种遗传算法，且将其进行具体实际的应用，怎样去很好地选择、平衡这五个方面使算法得到更加理想的效果，这还需要继续进行试验研究，探讨。
⑵在进行遗传算法理论分析研究时，发现相关理论分析比较少。每一种设计的遗传算法都是将其进行具体的应用，所以算法的灵活性比较大，这样去寻求一种概括性的理论分析就存在一定的难度，且本设计提出的自适应遗传算法，从理论上分析研究其收敛到全局最优，仍然需要进一步的研究。
⑶关于遗传算法的定量分析和数学证明，仍需要进一步的研究。
参考文献:
[1]王小平，曹立明.遗传算法—理论应用与软件实现[M].西安：西安交通大学出版社，2002：21-22.
[2]张明辉，王尚锦.自适应遗传算法及其应用[J].机械工程学院学报，2002，20(1)：23-25.
[3]雷德明.多目标智能优化算法及其应用[M].北京：科学出版社，2009：67-78.
[4]李敏强，寇纪淞，林丹等.遗传算法的基本理论与应用[M].北京：科学出版社，2004：55-57.
作者简介：
周嘉：（1988—），男，湖南城市学院计算机应用专业2007级学生，从事优化算法研究。