24小时热门版块排行榜

返回列表

当前主题已经存档。

allbeauty

银虫 (正式写手)

应助: 0 (幼儿园)
金币: 448
红花: 1
帖子: 509
在线: 63.7小时
虫号: 475422
注册: 2007-12-07
性别: MM
专业: 电化学分析

[交流] 【讨论】接上面的

3.2.2 遗传算法基本原理
遗传算法的原理比较简单，传统遗传算法常常用一个二进制线性数字串表示一个个体（individual）,若干个体构成一个种群（population）.一般我们用随机的办法产生初始种群。初始种群产生以后，就用定义的“适应性函数”（fitness function）去评价种群中的每个个体。然后通过个体的得分选择部分个体并通过交叉和变异去繁衍它们的后代。当然得分高的被选中的可能性会大些，同时那些未选中的个体就自然消亡。留下来的个体和它们新产生的子代就形成了新的种群。经过一些列交叉和变异过程后，就可以得到总体得分比较高的种群，这就是我们所要寻找的具有特殊性能的构型。
我们习惯上把Holland 1975年提出的GA称为传统的GA。其主要步骤如下：1编码. GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点；2 产生初始种群。随机产生初始串结构数据。每个串结构数据称为一个个体，多个个体构成一个种群。GA以这个串结构数据作为初始点开始迭代优化过程；3 进行适应性指评估检测。适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同；4 选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。选择实现了达尔文的适者生存原则；5 交叉。交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性，交叉体现了信息交换的意思；6 变异。变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中的某个串的值。同生物界一样，变异为新个体的产生提供机会。

3.2.3 遗传算法基本特点
遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的优势。与传统搜索方法相比，遗传算法具有以下特点：1 搜索过程不直接作用在变量上，而是作用在参数集进行了编码的个体上。此编码操作使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作；2 搜索过程是从一组迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部优化的可能性，并易于优化；3 采用概率变迁的规则来指导搜索方向，而不采用确定性搜索规则；4对搜索空间没有任何特殊的要求（如连通性、凸性等），只利用适应性信息，不需要导数等其他辅助信息，适用范围更广。

3.2.4 遗传算法的工作原理
遗传算法是一个以适应度函数（或目标函数）为依据，通过对群体中个体施加遗传操作实现群体内个体结构重组的迭代优化过程。它的理论主要有模式定理、积木块假设、最小欺骗问题和隐并行性问题等。我们主要介绍模式理论和最小欺骗问题。
模式理论是研究较广、影响较大的GA理论。它将GA的运算过程理解为模式操作过程并从模式运算的角度解释GA的性能特点。GA的计算过程是从一个个体组成的初始群体出发，循环的执行选择、交叉、变异过程。表面上看运算过程直接作用于群体，但其中隐含了模式集合中的操作过程。模式定理从模式操作的角度论证了在选择、交换和变异因子作用下某一模式量的变化。模式定理揭示出具有低阶、短定义矩以及平均适应度高于群体平均适应度的模式在子代中将以指数级增长，由于重组、变异的作用，并非低阶优于平均的模式都是有效模式，但在规模为N的群体中，有多个模式是有效的，即每一代GA处理个体的同时，获得了对多个模式的并行处理，并且无须额外的存储量，这一性质称为隐并行性。也就是GA在群体中搜索的过程可看作是隐含的对模式的抽样过程，然后通过遗传算子的作用将短的低阶模式的信息组合起来，形成高阶模式，直至搜索到最优解，这说明同传统的优化算法相比，GA有很强的处理能力。
研究欺骗是为了预测给定问题用GA求解的难易程度，这是我们所关注的问题。由模式理论，一个问题能否用遗传算法有效地求解，取决于问题编码是否能满足积木块假设，满足者用遗传算法求解率高，不满足者求解率较低，甚至找不到满意解，这一现象称为欺骗。最小欺骗问题旨在尽可能使问题的编码违背积木块假设，使高阶积木块不能生成最优解。但实验结果表明，对包含欺骗的问题，用GA求解时得到最优解和得不到最优解的情况都有可能发生。这说明欺骗不是衡量用GA解决问题难易程度的唯一标准。目前我们还无法判断一个问题包含欺骗的多少和问题相对于GA难易程度间的关系。

3.2.5 遗传算法的一个计算实例
遗传算法在程序上实现并不复杂，我们可以通过考虑如下简单的非线性优化问题来具体讨论遗传算法的实现过程。
函数定义如下：f(x)=x*sin(10Л* x)+1.0 (-1≤x≤2)
我们要用遗传算法得到上面这个函数的最大值。已知方程的极值为f(1.85)=2.85。整个实现过程可分为以下几个步骤：
1 编码：我们使用二进制的字符串表示方程的自变量x。字符串的长度取决于所需要的精度。定义域的范围是3。精度要求小数点后取6位有效数字，也即是要把这个定义域范围分为3×1000000个相等的区域。这样就需要22位的二进制字符串来表示每个个体，因为2的21次方小于3×1000000，所以要取到3×1000000格点[也就是前面所说的区域]，至少要取到2的22次方。
把一个二进制字符串转化为x的实数解需要两个步骤：首先把二进制字符串转化为十进制的整数；然后把得到的整数化为实数解。
2 产生初始种群：这一步比较简单，所有的个体构成初始种群[个体就是我们所说的方程的解]，为每个个体产生一个22位二进制字符串，需要强调每个字符串对应着方程的一个解。
3 适应性函数：在这里每个个体的适应性函数就是方程f(x)的值，由于我们在这里求的是极值，所以每个个体所对应f(x)的值越大，就表明个体的适应性就越好，则被选出的几率就越大。适应性函数相当于自然进化中的环境，它会直接控制种群的演化过程。
4 遗传操作：在遗传算法中有两个主要的遗传操作：突变和交叉。突变是在群体中随机选择一个个体，然后以一定的概率随机地改变串结构中某个串的值[这相当于改变了x的值，也就改变了f(x)的值，最终导致适应性函数值的变化。交叉操作的结果类似也是改变了个体的适应性函数值，这个步骤可以加快寻找最大值的速度。
5 参数的选择：在整个迭代优化过程中种群大小、交叉几率和突变几率对计算过程会产生较大的影响。
6 计算结果：经过上面的编码操作产生初始种群，然后带入每个个体值算出f(x)的值根据适应性函数[也就是我们的要求，在这里我们的要求是取极大值，所以值越大表明个体值的适应性就越好]判断个体值的好坏，这一过程辅之以遗传操作也确保更快更好的找到所需的值。循环这一过程，直到找到使f(x)最大的值，任务完成。
当然对不同的问题在实际操作上会有一定的差别，比如可能会对种群中的个体采用不同的数据结构，会采用其他的遗传操作。但总体上来讲，其基本流程是类似的，最大的差别就是根据不同的问题采用不同的适应性函数。

回复此楼