第二章 基本遗传算法和改进.doc

第二章 基本遗传算法 Holland创建的遗传算法是一种概率搜索算法，它利用某种编码技术作用于称为染色体的数串，其基本思想是模拟由这些组成的进化过程。该算法通过有组织地然而是随机地信息交换重新组合那些适应性好的串在每一代中，利用上一代串结构中适应好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。 遗传算法是一类随机优化算法，但是它不是简单的随机走动，它可以有效地利用已经有的信息处理来搜索那些有希望改善解质量的串类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值来改变染色体，使适用性好的染色体比适应性差的染色体有更多的繁殖机会。 .1 遗传算法的运行过程 .1.1 完整的遗传算法运算流程 遗传算法的一般步骤如图所示。 完整的遗传算法运算流程可以用图2.2来描述。 由图可以看出，使用上述三种遗传算子(选择算子、交叉算子、变异算子) 的遗传算法的主要运算过程如下： 1) 编码：解空间中的解数据，作为遗传算法的表现型形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。 2) 初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数计数器t←0；设置最大进化代数T；随机生成M个个体作为初始群体P(0) 。 3) 适应度值评价检测：适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数的定义方式不同。根据具体问题，计算群体P(t) 中各个个体的适应度。 4) 选择：将选择算子作用于群体。 5) 交叉：将交叉算子作用于群体。 6) 变异：将变异算子作用于群体。群体P(t) 经过选择、交叉、变异运算后得到下一代群体P(t+1)。 7) 终止条件判断若tT，则t←t+1，转到步骤2）；若tT，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。 进化操作过程简单，容易理解，它给其他各种遗传算法提供了一个基本框架。 一个简单的遗传算法被Goldberg用来进行轮廓描述并用来举例说明遗传算法的基本组成。t代种群变量P()表示初始种群是随机设计的P(0)。简单遗传算法的伪代码描述如： .1.2 遗传算法的三个基本操作 ：(Selection)、(Crossover)和(Mutation)。 1) 选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择运算体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。体现了达尔文的适者生存原则。 (3) 变异。变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机改变串结构数据中某个串的值即，(称为变异概率，mutation rate) 基本遗传算法 基本遗传算法(标准遗传算法或简单遗传算法，Simple Genetic Algorithm，SGA) 是一种群体型操作，该操作以群体中的所有个体为对象，只使用基本遗传算子(Genetic perator)：选择算子(perator)、交叉算子(Crossover perator)和变异算子(Mutation perator)，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。选择、交叉和变异是遗传算法3个主要操作算子，它们构成了所谓的遗传操作，使遗传算法具有了其它传统方法没有的特点。 .2.1 基本遗传算法的数学模型 基本遗传算法可表示为： () 式中——个体的编码方法；——个体适应度评价函数； ——初始种群； ——种群大小；——选择算子； ——交叉算子； ——变异算子； ——遗传运算终止条件。 图为基本遗传算法的流程图。 .2.2 基本遗传算法的步骤 染色体编码与解码基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值{0，1}所组成。初始群体中各个个体的基因可用均匀分布的随机数来生成。例如：X=100111001000101101就可表示一个个体，该个体的染色体长度是n=18。 ) 编码：设某一参数的取值范围为[]，我们用长度为的二进制编码符号来表示该参数，则它总共产生不同的编码，可使参数编码时的对应关系为：其中，。 解码：假设某一个体的编码为，则对应的解码公式为：