《2022年遗传算法及其改进研究数学建模论文》由会员分享，可在线阅读，更多相关《2022年遗传算法及其改进研究数学建模论文（8页珍藏版）》请在金锄头文库上搜索。
1、遗传算法及其改良研究_数学建模论文论文导读:：遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。本文讲述了遗传算法的相关知识要点，通过对遗传算法特点的分析，提出遗传算法的缺点，然后针对遗传算法的缺点提出相应的一些改良方法。论文关键词：遗传算法1 引言“物竞天择，适者生存是达尔文生物进化论的根本原理，揭示了物种总是向着更适应自然界的方向进化的规律。可见，生物进化过程本质上是一种优化过程，在计算科学上具有直接的借鉴意义。在计算机技术迅猛开展的时代，生物进化过程不仅可以在计算机上模拟实现，而且还可以模拟进化过程，创立新的优化计算方法，并应用到复杂工程领域之中，这就
2、是遗传算法等一类进化计算方法的思想源泉。2 遗传算法概述遗传算法是将生物学中的遗传进化原理和随1优化理论相结合的产物，是一种随机性的全局优算法。遗传算法不但具有较强的全局搜索功能和求解问题的能力，还具有简单通用、鲁棒性强、适于并行处理等特点数学建模论文，是一种较好的全局优化搜索算法。在遗传算法的应用中，由于编码方式和遗传算子的不同，构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同点，Holland的遗传算法常被称为简单遗传算法简记SGA，简单遗传算法只使用选择算子、交叉算子和变异算子
3、这三种根本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和根底，这种改良的或变形的遗传算法，都是以其为根底1。2.1遗传算法几个根本概念个体(IndividualString)：个体是遗传算法中用来模拟生物染色体的一定数目的二进制串，该二进制串用来表示优化问题的满意解。种群(population)：包含一组个体的群体，是问题解的集合。基因模式(Sehemata)：基因模式是指二进制位串表示的个体中，某一个或某些位置上具有相似性的个体组成的集合，也称模式。适应度(Fitness)：适应度是以数值方式来描述个体优劣程度的指标，由评价函数F计算得到。F作为求解问题的目标函数，求
4、解的目标就是该函数的最大值或最小值。遗传算子(genetic operator)：产生新个体的操作，常用的遗传算子有选择、交叉和变异。选择(Reproduetion)：选择算子是指在上一代群体中按照某些指标挑选出的，参与繁殖下一代群体的一定数量的个体的一种机制龙源期刊。个体在下一代种群中出现的可能性由个体的适应度决定，适应度越高的个体，产生后代的概率就越高。交叉(erossover)：交叉是指对选择后的父代个体进行基因模式的重组而产生后代个体的繁殖机制。在个体繁殖过程中，交叉能引起基因模式的重组，从而有可能产生含优良性能的基因模式的个体。交叉可以发生在染色体的一段基因串或者多段基因串。交叉概率
5、Pc决定两个个体进行交叉操作的可能性数学建模论文，交叉概率太小时难以向前搜索，太大那么容易破坏高适应度的个体结构，一般Pc取0.250.75变异(Mutation)：变异是指模拟生物在自然的遗传环境中由于某种偶然因素引起的基因模式突变的个体繁殖方式。在变异算子中，常以一定的变异概率Pm在群体中选取个体，随机选择个体的二进制串中的某些位进行由概率控制的变换0与1互换从而产生新的个体2。如果变异概率太小，就难以产生新的基因结构，太大又会使遗传算法成了单纯的随机搜索，一般取Pm=0.10.2。在遗传算法中，变异算子增加了群体中基因模式的多样性，从而增加了群体进化过程中自然选择的作用，防止早熟现象的出
6、现。2.2根本遗传算法的算法描述用P(t)代表第t代种群，下面给出根本遗传算法的程序伪代码描述：根本操作：InitPop操作结果：产生初始种群，初始化种群中的个体，包括生成个体的染色体值、计算适应度、计算对象值。Selection初始条件：种群已存在。操作结果：对当前种群进行交叉操作。Crossover初始条件：种群已存在。操作结果：对当前种群进行交叉操作。Mutation初始条件：种群已存在。对当前种群进行变异操作。PerformEvolution初始条件：种群已存在且当前种群不是第一代种群。操作结果：如果当前种群的最优个体优于上一代的最优本，那么将其赋值给bestindi，否那么不进行任何
7、操作。Output初始条件：当前种群是最后一代种群。操作结果：输出bestindi的表现型以及对象值。3 遗传算法的缺点及改良遗传算法有两个明显的缺点：一个原因是出现早熟往往是由于种群中出现了某些超级个体，随着模拟生物演化过程的进行，这些个体的基因物质很快占据种群的统治地位，导致种群中由于缺乏新鲜的基因物质而不能找到全局最优值；另一个主要原因是由于遗传算法中选择及杂交变异等算子的作用，使得一些优秀的基因片段过早丧失，从而限制了搜索范围，使得搜索只能在局部范围内找到最优值，而不能得到满意的全局最优值3。为提高遗传算法的搜索效率并保证得到问题的最优解，从以下几个方面对简单遗传算法进行改良。3.1编
8、码方案因实数编码方案比二进制编码策略具有精度高、搜索范围大、表达自然直观等优点数学建模论文，并能够克服二进制编码自身特点所带来的不易求解高精度问题、不便于反响所求问题的特定知识等缺陷，所以确定实数编码方案替代SGA中采用二进制编码方案4。3.2 适应度函数采用基于顺序的适应度函数，基于顺序的适应度函数最大的优点是个体被选择的概率与目标函数的具体值无关，仅与顺序有关5。构造方法是先将种群中所有个体按目标函数值的好坏进行排序，设参数(0,1)，基于顺序的适应度函数为：13.3 选择交叉和变异在遗传算法中，交叉概率和变异概率的选取是影响算法行为和性能的关键所在，直接影响算法的收敛性。在SGA中，交叉
9、概率和变异概率能够随适应度自动调整，在保持群体多样性的同时保证了遗传算法的收敛性。在自适应根本遗传算法中，pc和pm按如下公式进行自动调整：23式中：fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f为待交叉的两个个体中较大的适应度值；f为待变异个体的适应度值；此处，只要设定k1、k2、k3、k4为0，1之间的调整系数，Pc及Pm即可进行自适应调整。本文对标准的遗传算法进行了改良，改良后的遗传算法对交叉概率采用与个体无关，变异概率与个体有关。交叉算子主要作用是产生新个体，实现了算法的全局搜索能力。从种群整体进化过程来看，交叉概率应该是一个稳定而逐渐变小，到最后趋于某一稳定值的
10、过程；而从产生新个体的角度来看，所有个体在交叉操作上应该具有同等地位，即相同的概率，从而使GA在搜索空间具有各个方向的均匀性。对公式2)和3进行分析说明，适应度与交叉率和变异率呈简单的线性映射关系。当适应度低于平均适应度时，说明该个体是性能不好的个体数学建模论文，对它就采用较大的交叉率和变异率；如果适应度高于平均适应度，说明该个体性能优良，对它就根据其适应度值取相应的交叉率和变异率龙源期刊。当个体适应度值越接近最大适应度值时，交叉概率和变异概率就越小；当等于最大适应度值时，交叉概率和变异概率为零。这种调整方法对于群体处于进化的后期比拟适宜，这是因为在进化后期，群体中每个个体根本上表现出较优的性
11、能，这时不宜对个体进行较大的变化以免破坏了个体的优良性能结构；但是这种根本遗传算法对于演化的初期却不利，使得进化过程略显缓慢6。因为在演化初期，群体中较优的个体几乎是处于一种不发生变化的状态，而此时的优良个体却不一定是全局最优的，这很容易导致演化趋向局部最优解。这容易使进化走向局部最优解的可能性增加。同时，由于对每个个体都要分别计算Pc和Pm，会影响程序的执行效率，不利于实现。对自适应遗传算法进行改良，使群体中具有最大适应度值的个体的交叉概率和变异概率不为零，改良后的交叉概率和变异概率的计算公式如式4和5所示。这样，经过改良后就相应地提高了群体中性能优良个体的交叉概率和变异概率，使它们不会处于
12、一种停滞不前的状态，从而使得算法能够从局部最优解中跳出来获得全局最优解7。(4)(5)其中：fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f为待交叉的两个个体中较大的适应度值；f为待变异个体的适应度值；pc1为最大交叉概率；pm1为最大变异概率。3.4 种群的进化与进化终止条件将初始种群和产生的子代种群放在一起，形成新的种群，然后计算新的种群各个体的适应度，将适应度排在前面的m个个体保存，将适应度排在后面m个个体淘汰数学建模论文，这样种群便得到了进化8。每进化一次计算一下各个个体的目标函数值，当相邻两次进化平均目标函数之差小于等于某一给定精度时，即满足如下条件：(6)式中，
13、为第t+1次进化后种群的平均目标函数值，为第t次进化后种群的平均目标函数值，此时，可终止进化。3.5 重要参数的选择GA的参数主要有群里规模n，交叉、变异概率等。由于这些参数对GA性能影响很大，因此参数设置的研究受到重视。对于交叉、变异概率的选择，传统选择方法是静态人工设置。现在有人提出动态参数设置方法，以减少人工选择参数的困难和盲目性。4 结束语遗传算法作为当前研究的热点，已经取得了很大的进展。由于遗传算法的并行性和全局搜索等特点，已在实际中广泛应用。本文针对传统遗传算法的早熟收敛、得到的结果可能为非全局最优收敛解以及在进化后期搜索效率较低等缺点进行了改良，改良后的遗传算法在全局收敛性和收敛
14、速度方面都有了很大的改善，得到了较好的优化结果。参考文献1邢文训,谢金星.现代优化计算方法M.北京:清华大学出版社,1999:66-68.2王小平,曹立明.遗传算法理论M.西安交通大学出版社,2002:1-50,76-79.3李敏强,寇纪淞,林丹,李书全.遗传算法的根本理论与应用M.科学出版社, 2002:1-16.4涂承媛,涂承宇.一种新的收敛于全局最优解的遗传算法J.信息与控制,2001,30(2):116-1385陈玮,周激,流程进,陈莉.一种改良的两代竞争遗传算法J.四川大学学报:自然科学版,2003.040(002):273-277.6王慧妮,彭其渊,张晓梅.基于种群相异度的改良遗传算法及应用J.计算机应用,2022,26(3):668-669.7金晶,苏勇.一种改良的自适应遗传算法J.计算机工程与应用,2022,41(18):64-69.8陆涛,王翰虎,张志明.遗传算法及改良J.计算机科学,2022,34(8):94-96
