遗传算法概述
1遗传算法概述
遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的自适应概率性随机化迭代搜索算法。1975 年，美国Michigan 大学的J.H.Holland 教授在从事机器学习时注意到，学习不仅可以通过单个生物体的适应来完成，而且可以通过一个种的许多进化适应来加以实现，Kenneth De Jong 将这种算法用来解决优化问题。Holland 研究GA 是从设计和实现一种能应付变化的、不确定环境的鲁棒性好的自适应系统开始。他认为这种系统的自适应是从所处的环境中随时得到反馈的函数关系，因而形成了我们今天称之为简单遗传算法的再生计划(Reproductive Plan)。这种简单的GA 只是一类具有固定种(Population)规模、个体用固定长度的基因链的抽象模型。根据适应度(Fitness)来随机地选择双亲，并按交叉(Crossover)和变异(Mutation)算子来产生
新的种。遗传算法的特点是它的算法中不包含待解决问题所持有的形态。它是从改变基因的配置来实现问题的整体优化的，因而属于自下而上的优化方法。类似于生物的进化过程，遗传算法处理的是变量集合的编码而非变量本身。它直接对结构对象进行操作，不存在求导
和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些特点已被人们广泛地应用于组合优化、机器学习、信号理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。
2.进化计算
进化计算[19](Evolutionary Computation，简记为EC)是自60 年代开始发展的一门新兴学科。它是指以进化原理为仿真依据，按优胜劣汰的自然选择优化规律和方法，在计算机上解决科技领域中难以用传统优化方法解决的优化计算问题的算法和程序，因此有时也称之为进化算法(Evolutionary Algorithms，EA)。
进化计算最初具有三大分支：遗传算法(Gentic Algorithm ，GA)、进化规划(Evolutionary Programming，EP)和进化策略(Evolutionary Strategy，ES)。它们具有共同的本质，均来源于达尔文的进化论，分别强调了自然进行中的不同层面：遗传算法强调染体的操作，进化策略强调了体级的行为变化，而进化规划则强调种级上的行为变化。90 年代初，在遗传算法的基础上又形成了一个分支：遗传程序设计(GeneticProgramming，GP)。虽然这
几个分支在算法实现方面有一些差别，并且这些差别正逐渐缩小，它们一个共同的特点是借助生物进化的思想和原理来解决实际问题。作为进化计算理论体系的中心—遗传算法，其理论和方法不断地完善具有普遍的意义。现在进化算法EC 的研究主要集中于遗传算法GA、进化策略ES 和进行规划EP。国外在遗传编程GP 方面的研究已形成规模，在国内，这方面的研究还处于在探索阶段。
1)遗传算法GA 的基本思想
遗传算法[19](GA)是近几年发展起来的一种崭新的全局优化算法。1962 年霍兰德(Holland)教授首次提出了GA算法的思想，它的基本思想是基于Darwin 进化论和Mendel的遗传演说。Darwin 进化论最重要的是适者生存的原理，它认为每一代种总是向着前进方向发展，越来越适应环境。每一个个体都有继承前代的特性，但不是完全继承，会产生一些新特性。最终只有适应环境的特征才能被保留下来。Mendel 遗传学说最重要的是基因遗传原理，它认为遗传以密码方式存在细胞中，并以基因形式包含在染体内。一条染体中存在很多基因，每个基因有自己的位置并控制着外部特征；基因的产生和变异直接影响到个体的特性是否能适应环境。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
遗传算法正是借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。这一点体现了自然界中"物竞天择、适者生存"进化过程。与自然界相似，遗传算法对求解问题的本身一无所知，从代表问题可能潜在解集的一个种(population)开始，每一个种则由经过基因(gene)编码(coding)的一定数目的个体(individual)构成。每个个体实际上是染体(chromosome)带有特征的实体。把问题的解表示成染体，并基于适应值来选择染体，遗传算法所需要的仅是对算法所产生的每个染体进行评价，使适应性好的染体有更多的繁殖机会。在算法中也就是以二进制编码的串。并且，在执行遗传算法之前，给出一染体，也就是假设解。然后，把这些假设解置于问题的“环境”中，也即在一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染体进行复制, 淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染体。对这个新种进行下一轮进化，直到最适合环境的值。
2.3 遗传算法的基本概念
由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中要用到各种进化和遗传学的概念。这些概念如下：
1)染体(Chromosome) 生物细胞中含有的一种微小的丝状化合物。这是遗传物质
的主要载体，由多个遗传因子－基因组成。
2)个体(Individual) 指染体带有特征的实体。
3)串(String) 它是个体(Individual)的形式，在算法中为二进制，并且对应于遗传学中的染体(Chromosome)。
4)基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝81011，则其中的1，0，1，1 这4 个元素分别称为基因。其值称为等位基因(Alletes)。
5)种(Population) 染体带有特征的个体的集合称为种。该集合内个体数称为体的大小。有时个体的集合也称为个体。
6)体大小(Population Size) 在体中个体的数量称为体的大小。
7)表现型(Phenotype) 由染体决定性状的外部表现，或者说，根据遗传子型形成的个体。
8)基因位置(Gene Position) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101 中，0 的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
9)基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011 中，基因位置3 中的1，它的基因特征值为2；基因位置数学二进制的算法1 中的1，它的基因特征值为8。
10)串结构空间ss 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。
11)参数空间sr 这是串空间的物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。
12)非线性 它对应遗传学中的异位显性(Epistasis)。
13)适应度(Fitness) 表示某一个体对于环境的适应程度。
14)选择(Selection) 指决定以一定的概率从种中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。
15)复制(Reproduction) 细胞在分裂时，遗传物质DNA 通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。
16)交叉(Crossover) 有性生物在繁殖下一代时两个同源染体之间通过交叉而重组，亦即在两个染体的某一相同位置处DNA 被切断，其前后两串分别交叉组合形成两个新的染体。这个过程又称基因重组recombination，俗称“杂交”。
17)变异(Mutation) 在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA 发生某种变异，产生出新的染体，这些新的染体表现出新的性状。
18)编码(Coding) DNA 中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。
19)解码(Decoding) 从遗传子型到表现型的映射。
2.4 遗传算法的模式定理
模式定理是遗传算法的理论基础，它描述了遗传算法的搜索策略。
1) 模式
定义2.1 设GA 的个体p∈Bl ，记集合S={0,1,*}l ，则称∀S ∈S 为一个模式
(Schemata)，其中，“*”代表通配符，l 表示个体染体长度。由以上定义可见，所谓“模式”就是指编码的字符串中具有类似特征的子集。在二进9制编码的串中，模式是基于三个字符集(0,1,*)的字符串，字符“*”是通配符，它表示可以取“1”，又可以取“0”。对于一个模式s，我们至少可以到一个和它相匹配的个体q。
例如：s 为10**101*1010，个体q 可为：100110101010。2)模式阶和定义距
定义2.2 若一个个体q 的每一位与模式s 相配，则称q 是s 的一个表示。一个模式代表一个个体的集合，这个集合中的每一个个体都是这个模式的一个表示。所有的模式并不是以同等机会产生的。有些模式比起其他模式更确定，如模式011**1 与模式0*****相比，在相似性方面有明确的表示。有些模式的跨度要比其他的长，如与模式1*1***相比，1****1 要跨越整个串长更大的部分。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。