遗传算法 汇报人：吴钰.pptx

《遗传算法 汇报人：吴钰.pptx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、遗传算法汇报人：吴钰GeneticAlgorithmALGORITM目录CONTENTS1遗传算法定义Geneticalgorithmdefinition2遗传算法关键技术Biologicalterminology3遗传算法过程Problemimport4问题与代码实现Generalrealization5遗传算法Code11-1遗传算法的科学定义1-2生物遗传1-3遗传算法图解过程遗传算法定义123遗传算法（GeneticAlgorithm,GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可

2、能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现是某种基因组合，它决定了个体的形状的外部表现以编码空间代替问题参数空间，从代表问题可能有潜在解集的一个种群出发，按照生物进化过程中适者生存、优胜略汰的原理，以适应度作为评价个体优劣的依据，重复使用选择、交叉、变异算子作用于群体，使之不断进化，逐渐接近最优解GeneticAlgorithm遗传算法科学定义遗传算法TITLE01TITLE02Loremipsumdolorsitamet,consectetueradi

3、piscingelit,seddiamnonummynibheuismodtinciduntutlaoreetdoloremagnaaliquameratvolutpat.TITLE03生物遗传概念遗传算法生物遗传概念遗传算法的概念基因可行解的每一分量的特征染色体可行解的编码个体可行解种群通过适应度函数值选取的一组可行解交叉两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成产生一组新的可行解变异编码的某一分量发生变化的过程适应度度量某个物种对于生存环境的适应程度复制细胞分裂时，遗传物质通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。选择以一定概率从种群中选择

4、若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程2遗传算法关键技术2-1初始化2-2适应度函数2-3选择2-4交叉2-5变异遗传算法步骤遗传算法你准备要去野游1个月，但是你只能背一个限重30公斤的背包。现在你有不同的必需物品，它们每一个都有自己的「生存点数」。因此，你的目标是在有限的背包重量下，最大化你的「生存点数」。物件重量生存点数睡袋1515绳索37折叠刀210手电筒55瓶子98葡萄糖2017100110001110010100011001A1A2A3A4基因染色体种群遗传算法初始化染色体可表达为二进制数串，在这个问题中：1代表基因存在0代表基因丢失特定位置上的基因代表

5、了上方背包问题表格中的物品。第一个位置上是睡袋第二个位置上是绳索第三个位置上是折叠刀第四个位置上是手电筒第五个位置上是瓶子第六个位置上是葡萄糖例如：染色体A1表示：1、睡袋；4、手电筒、5、瓶子A1(100110)A1(001110)A1(010100)A1(011001)适应度函数遗传算法物件重量生存点睡袋1515手电筒55瓶子98总和2928物件重量生存点折叠刀210手电筒55瓶子98总和1623物件重量生存点绳索37手电筒55总和812物件重量生存点绳索37折叠刀210葡萄糖2017总和2534遗传算法选择----轮盘赌选择染色体生存点选择概率积累概率A1280.2890.28

6、9A2230.2370.526A3160.1240.650A4340.3511.000选择用来实施适者生存的原则，即把当前的群体中的个体按照一定方法，挑选出一部分个体，用于构建交配池选择算子的作用效果是提高了群体的平均适应度。由于选择算子没有产生新个体，所以群体中最好个体的适应值不会因为选择操作而有所改变轮盘赌选择算法如图所示：选择了俩个个体A1,A4个体00.2890.5260.6501.000第1轮第2轮遗传算法交叉在上一个步骤中，我们已经选择出了可以产生后代的亲本染色体。那么用生物学的话说，所谓「交叉」，其实就是指的繁殖。现在我们来对染色体A1和A4（在上一个步骤中选出来的）进

7、行「交叉」，见下图：100110011001011110100001ParentsOff-springs单点交叉100110011001101010100101多点交叉ParentsOff-springs遗传算法变异如果现在我们从生物学的角度来看这个问题，那么请问：由上述过程产生的后代是否有和其父母一样的性状呢？答案是否。在后代的生长过程中，它们体内的基因会发生一些变化，使得它们与父母不同。这个过程我们称为「变异」，它可以被定义为染色体上发生的随机变化，正