遗传算法 课外参阅资料

《遗传算法 课外参阅资料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、遗传算法简介遗传算法（GeneticAlgorithm）起始于20世纪60年代，主要由美国Michigan大学的JohnHolland与其同事和学生研究形成了一个较完整的理论和方法。从1985年在美国卡耐基梅隆大学召开的第5届目标遗传算法会议（IntertionalConferenceonGeneticAlgorithms:ICGA’85）到1997年5月IEEE的TransactiononEvolutionaryComputation创刊，遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究逐渐成熟。1.1遗传算法的产生与发展（

2、略）1.2遗传算法概要1.2.1生物进化理论和遗传算法的知识遗传：变异：亲代和子代之间，子代和子代的不同个体之间总有些差异，这种现象称为变异，变异是随即发生的，变异的选择和积累是生命多样性的根源生存斗争和适者生存：下面给出生物学的几个基本概念知识，这对于理解遗传算法很重要。染色体：是生物细胞中含有的一种微小的丝状化合物，是遗传物质的主要载体，由多个遗传因子—基因组成。遗传因子（gene）:DNA长链结构中占有一定位置的基本遗传单位，也称基因。生物的基因根据物种的不同而多少不一。个体（individual）:指染色体带有特征的实体种群（popu

3、lation）:染色体带有特征的个体的集合进化（evolution）;生物在其延续生命的过程中，逐渐适应其生存环境使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。适应度（fitness）:度量某个物种对于生存环境的适应程度选择（selection）:指以一定的概率从种群中选择若干个体的操作复制(reproduction)交叉(crossorer)变异（musation）：复制时很小的概率产生的某些复制差错编码（coding）:DNA中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看成是从表

4、现型到遗传子型的映射。解码（decoding）：从遗传子型到表现型的映射1.2.2遗传算法的基本思想遗传算法是从代表问题可能潜在解集的一个种群开始的。该种群是由经过基因编码的一定数目的个体组成，这需要实现从表现型到基因型的映射即编码。初代种群产生之后，按照适者生存、优胜略汰的原理，逐代进化产生出越来越好的近似种，即在每一代中，根据问题域中个体适应度大小挑选个体，并借助自然遗传学的遗传算子进行组合交叉和变异，产生出代表解的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码可以作为问题近似最

5、优解。采用多种群即有子种群的算法往往会获得更好的结果。每个子种群像单种群遗传算法一样独立地演算若干代后，在子种群之间进行个体交换。这种多种群遗传算法更加贴近于自然界中种族的进化，称为并行遗传算法。1.2.3遗传算法的特点*自组织，自学习，自适应性*本质并行性*不需要求导或其他辅助知识，而只要影响搜索方向的目标函数和相应的适应度函数*强调概率转换规则，而不是确定的转换规则*对给定问题可产生许多的潜存种，最终选择可以由使用者确定，因此对于确认可替代解集而言是特别适合的。（如多目标优化问题）1.3遗传算法的基本操作遗传算法包括三个基本操作：选择，交

6、叉（基因重组），变异这些基本操又有许多不同的地方。1.选择按比例的适应度算法（proportionalfitnessassigment）基于排序的适应度算法（rank-basedfitnessassignment）轮盘赌选择（roulettewheelselection）随机遍历抽样（stochasticuniversalsampling）局部选择（lacalselection）截断选择（tournamentselection）1.交叉或基因重组（crossorer/recombination）*实值重组（realvaluerecombina

7、tion）离散重组（discrete）、中间(intermediate)重组、线性(linear)重组、扩展线性(extendedlinear)重组*二进制交叉（binaryvaluelcrossorer）单点交叉、多点（multiple-poinrt）交叉、均匀(uniform)交叉、洗牌(shuffle)交叉、缩小代理(crossoverwithreducedsurrogate)2.变异（mutation）变异实质上是子代基因按小概率扰动产生的变化，有两种算法，分别为实值变异和二进制变异第二章基本遗传算法2.1一个简单的遗传算法实例本节介

8、绍一个简单的实例，来考察一下二进制算法的轮盘赌选择、多点交叉和变异操作，以便对遗传算法的基本过程和基本操作有所了解。表1是一组二进制基因构成的个体组成的初始种群，个