遗传算法原理与应用.ppt

《遗传算法原理与应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、遗传算法原理与应用组员：余静芝许冰孙纯轶杨美艳厉云丹提纲一、遗传算法概述二、遗传算法原理三、遗传算法的应用生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法(GeneticAlgorithms，简称GAs)就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就

2、是生物的遗传和进化。遗传与变异遗传(Heredity)——世间的生物从其父代继承特性或性状，这种生命现象就称为遗传(Heredity)，由于遗传的作用，使得人们可以种瓜得瓜、种豆得豆，也使得鸟仍然是在天空中飞翔，鱼仍然是在水中游。变异（variation）——虽然说子代遗传了父代的各种特性，但是总会出现与父代不一样的性状，这就可以说是变异。由于变异的存在，没有两个同种生物是完全一样的，或者说，没有两片叶子是一样的。遗传算法与生物进化之间的对应关系遗传算法生物进化适应函数环境适应值函数适应性适应性函

3、数值最大的解被保留的概率最大选择问题的一个解个体解的编码染色体编码的元素基因被选定的一组解群体根据适应函数选择的一组解（以编码形式表示）种群以一定的方式由双亲产生后代的过程交配编码的某些分量发生变化的过程变异遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNatu

4、ralandArtificialSystems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。遗传算法的定义染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头

5、发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新

6、的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。遗传算法计算优化的过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或算子）：选择（Selection）交叉（Crossover）变异（Mutation）选择(复制)：根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中；交叉：将群体P(t)内的各个个体随机搭配成对，对每一对

7、个体，以某个概率(称为交叉概率）交换它们之间的部分染色体；变异：对群体P(t)中的每一个个体，以某一概率(称为变异概率)改变某一个或某一些基因座上的基因值为其他基因值。依据适应函数值的大小，选择操作从规模为N的群体中随机地选择若干染色体构成种群，种群的规模可以与原来群体的规模一致，也可以不一致。若假设二者规模一致，但二者并不完全相同，因为适应函数值大的染色体可能会多次被从群体选出，而适应值小的染色体可能会失去被选中的机会。因此，一些适应函数值大的染色体可能会重复出现在种群中，而一些适应函数值小的染

8、色体则可能被淘汰。一、遗传算法概述1、智能优化算法2、基本遗传算法3、遗传算法的特点1、智能优化算法智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。常用的智能优化算法（1）遗传算法（GeneticAlgorithm，简称GA）（2）模拟退火算法（SimulatedAnnealing，简称SA）（3）禁忌搜索算法（TabuSearch，简