网站建设涉及的内容,建网站哪家好,网站建设 意见征集,四川住房和城乡建设厅进不去网站该算法已被很多篇文章讲解#xff0c;本文将会去除很多较简单的内容#xff0c;挑选认为重点核心部分进行讲述#xff0c;内容中有属于信息的收集整理部分#xff0c;也有属于自己理解的部分。
1、遗传算法概述 遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方…该算法已被很多篇文章讲解本文将会去除很多较简单的内容挑选认为重点核心部分进行讲述内容中有属于信息的收集整理部分也有属于自己理解的部分。
1、遗传算法概述 遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出其主要特点是直接对结构对象进行操作不存在求导和函数连续性的限定具有内在的隐并行性和更好的全局寻优能力采用概率化的寻优方法能自动获取和指导优化的搜索空间自适应地调整搜索方向不需要确定的规则。遗传算法的这些性质已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。 2、遗传算法的基本操作 遗传算法有三个基本操作 选择 Selection 、 交叉 Crossover 和变异 Mutation • 选择。 从当前种群中选出优良的个体 使它们有机会作为父代种群为下一代种群进行更新迭代。 根据各个个体的适应度值 按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代种群中。 选择的依据是适应性强的个体为下一代贡献一个或多个后代的概率大。 • 交叉。 通过交叉操作可以得到新一代个体 新个体组合了父辈个体的特性。 将群体中的各个个体随机搭配成对 对每一个个体 以交叉概率交换它们之间的部分染色体。 • 变异。 对种群中的每一个个体 以变异概率改变某一个或多个基因座上的基因值为其他的等位基因。 同生物界中一样变异发生的概率很低 变异为新个体的产生提供了机会。 3、遗传算法的基本步骤 遗传算法的基本步骤包含了编码、解码、初始种群生成、适应度计算、选择、交叉、变异
1)编码 GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据 这些串结构数据的不同组合便构成了不同的点。 遗传算法的搜索核心是编码方式遗传算子的选择因此对于遗传算法的研究其中最常见的内容与方向是遗传算子遗传算子的选择多样性也导致了算法表现的多样性常见的选择方式如图所示 常见的编码方式有二进制编码、自然数编码、实数编码和树形编码等常见的编码有二进制编码与自然数编码很多实际问题如VRP调度问题更多采用自然数编码。编码方式不赘述根据模型需要自行选择即可
2初始群体的生成随机产生N个初始串结构数据 每个串结构数据称为一个个体 N个 个体构成了一个群体。
3)适应度评估适应度表明个体或解的优劣性。 不同的问题 适应性函数的定义不同。
4)选择选择的目的是为了从当前群体中选出优良的个体。 选择体现了达尔文的适者生存原则。
常见的选择方式有 轮盘赌法Roulette-wheel selection 轮盘赌选择法是依据个体的适应度值计算每个个体在子代中出现的概率并按照此概率随机选择个体构成子代种群。轮盘赌选择策略的出发点是适应度值越好的个体被选择的概率越大。 为了计算选择概率需要用到每个个体i的适应度值 从给定种群中选出M个个体就等价于旋转M次轮盘在选择个体前实际上不必对种群中的个体进行排序。 锦标赛选择Tournament selection 在锦标赛选择中从种群中随机采样s个个体注意采样是有放回的然后选择最优的个体进入下一代只有个体的适应度值优于其他s-1个竞争者时才能赢得锦标赛。注意最差的个体永远不会幸存而最优的个体在其参与的所有锦标赛中都能获胜。 可以通过改变锦标赛的大小s来改变对于较大的s值弱者被选中的机会较小常见的有二元锦标赛和三元锦标赛等。与适应度值比例选择相比锦标赛选择由于缺乏随机噪声同时锦标赛选择也和遗传算法适应度函数的尺度无关。 随机遍历选择Stochastic-universal selection 随机遍历选择SUS是一种根据给定概率以最小化波动概率的方式选择个体的方法。可以将其认为是一种轮盘赌游戏在轮盘上有p个等间距的点进行旋转。SUS使用一个随机值在等间隔的空间间隔内选择来选择个体。相比较于适应度比例选择法该方法中较劣个体也有很好的机会被选择从而奖励了不公平性。该选择方法是由James Baker提出的展示了其原理其中n为要选择的个体数量。随机遍历采样保证了选出的子代比轮盘赌法更加接近希望得到的结果。 精英选择Elite selection 精英选择将一小部分最优的候选解原封不动的复制到下一代中这会对性能产生巨大的影响因为这保证了GA不会浪费时间重新发现以前拒绝的部分解。通过精英主义被保留下来的个体仍然有资格被选为下一代的父代。精英主义也与记忆有关记住目前找到的最优解。不过精英主义的问题在于会导致GA收敛到局部最优所以纯粹的精英主义是一场通向最近局部最优的竞争。
5)交叉交叉操作是遗传算法中最主要的遗传操作。 通过交叉操作可以得到新一代个体 新个体组合了其父辈个体的特性。
常见的交叉方式有 单点交叉Single-point crossover 单点交叉通过选取两条染色体在随机选择的位置点上进行分割并交换右侧的部分从而得到两个不同的子染色体。 两点交叉Two-points crossover 两点交叉是指在个体染色体中随机设置了两个交叉点然后再进行部分基因交换。两点交叉的具体操作过程是
在相互配对的两个个体编码串中随机设置两个交叉点交换两个个体在所设定的两个交叉点之间的部分染色体。部分匹配交叉Partially-matched crossoverPMX 部分匹配交叉保证了每个染色体中的基因仅出现一次通过该交叉策略在一个染色体中不会出现重复的基因所以PMX经常用于旅行商TSP或其他排序问题编码。 PMX类似于两点交叉通过随机选择两个交叉点确定交叉区域。执行交叉后一般会得到两个无效的染色体个别基因会出现重复的情况为了修复染色体可以在交叉区域内建立每个染色体的匹配关系然后在交叉区域外对重复基因应用此匹配关系就可以消除冲突。
Step1随机选择一对染色体父代中几个基因的起止位置两染色体被选位置相同。 Step2交换这两组基因的位置。 Step3做冲突检测根据交换的两组基因建立一个映射关系如图所示以7-5-2这一映射关系为例可以看到第二步结果中子代1存在两个基因7这时将其通过映射关系转变为基因2以此类推至没有冲突为止。最后所有冲突的基因都会经过映射保证形成的新一对子代基因无冲突。 最终结果为 还有其他的交叉方法这里不一一举例说明。
6)变异变异首先在群体中随机选择一个个体 对于选中的个体以一定的概率随机地改变 串结构数据中某个串的值。
整体的流程如下 4、案例分析 案例后续讲述 TSP优化 遗传算法优化神经网络
5、遗传算法特点
相对于传统算法而言遗传算法有以下突出特点
优点 1. 可适用于灰箱甚至黑箱问题 2. 搜索从群体出发具有潜在的并行性 3. 搜索使用评价函数适应度函数启发过程简单 4. 收敛性较强。 5. 具有可扩展性容易与其他算法粒子群、模拟退火等结合。
不足: 1. 算法参数的选择严重影响解的品质,参数的选择大部分是依靠经验 2. 遗传算法的本质是随机性搜索不能保证所得解为全局最优解 3.在处理具有多个最优解的多峰问题时容易陷入局部最小值而停止搜索造成早熟问题无 法达到全局最优。
