2022年遗传算法综述 .pdf
1 遗传算法综述摘要：遗传算法是一种全局优化的随机搜索算法，是解决复杂优化问题的有力工具。近年来，由于遗传算法求解复杂优化问题的巨大潜力及其在工业工程领域的成功应用，这种算法受到了国内外学者的广泛关注。本文介绍了遗传算法的基本原理和主要特点，概述了遗传算法的常见应用领域，讨论了遗传算法的基本步骤和存在的问题。关键词 ：遗传算法适应度 随机搜索1.引言遗传算法 Genetic Algorithm，简称 GA 是由美国 Michigan 大学的Holland 教授于 1969年提出，后经 DeJong 、Goldberg等人归纳总结所形成的一类模拟进化算法。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说，是生命科学与工程科学互相交叉、互相渗透的产物，其本质是模拟生物进化过程的一种随机搜索与全局优化算法。目前，遗传算法广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科学等领域，适用于解决复杂的非线性和多维空间寻优问题，如TSP( 旅行商问题 ) 、背包问题、排课问题等。2.遗传算法理论遗传算法的基本术语由于遗传算法是模拟生物进化过程的，因此有必要了解下面几个关于生物学的基本术语。1染色体 chromosome ：生物细胞中含有的一种微小的丝状化合物，是遗传物质的主要载体，由多个基因组成。2基因 gene)：DNA 或RNA ，长链结构中占有一定位置的基本遗传单位。3个体 individual：指染色体带有特征的实体，在问题简化的情况下可代表染色体。4种群 population ：染色体带有特征的个体的集合称为种群，该集合内个体数称为群体的大小。有时个体的集合也称为个体群。5进化 evolution：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改进，这种生命现象称为进化。生物的进化是以种群的形式进行的。6适应度 fitness：在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。对生存精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 6 页2 环境适应度高的物种将获得更多的繁殖时机，而对生存环境适应程度较低的物种，其繁殖的时机就相对较少，甚至逐渐灭绝。遗传算法的基本原理遗传算法是从一组随机产生的初始解开始搜索，按照适者生存和优胜劣汰的原理，通过交叉、变异和选择运算来实现的。其中，选择是指从种群中选择生命力强的染色体来产生新种群的过程，选择的依据是每个染色体的适应度大小, 适应度越大 , 被选中的概率就越大；交叉运算是指两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体；变异就是以很小的概率, 随机改变染色体某个位置上的基因。根据适应度的大小，从上一代和后代中选择一定数量的个体作为下一代群体，再继续进化。这样经假设干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。遗传算法的主要特点遗传算法作为一种新型的、模拟生物进化过程的随机化搜索方法，不同于枚举法、启发式算法、搜索算法等传统的优化方法。它具有以下特点：1自组织、自适应和自学习性。2遗传算法的本质并行性。3遗传算法不要求导或其他辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数。4遗传算法强调概率转换规则，而不是确定的转换规则。5遗传算法可以更加直接地应用。6遗传算法对给定问题，可以产生许多的潜在解，最终选择可以由使用者确定。3.基本步骤遗传算法的基本步骤为：Step 1 ：随机产生一定数目的初始种群，每个个体表示为染色体的基因编码；Step 2 ：计算每个个体的适应度，并判断是否符合优化准则，假设符合，输出最正确个体及其代表的最优解并结束计算，否则转向第3步；Step 3 ：依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；Step 4 ：执行交叉和变异操作，生成新的个体；Step 5 ：得到新一代的种群，返回到第2步。在遗传算法的具体实现过程中，优化参数需要事先确定, 参数的选取对遗传算法的性能有重要影响。1) 种群数量。群体规模影响遗传优化的最终结果以及遗传算法的执行效精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 6 页3 率。当种群数量太小时，遗传算法的优化性能一般不会太好；种群数量较大则可减少遗传算法陷入局部最优解的机率，但也意味着计算复杂度变大，效率变低。一般取种群数量为 10到160之间。具体的的种群数量根据具体情况有所不同。2交叉概率交叉概率的选择决定了交叉操作的频率。频率越高，可以越快地收敛到最优解区域，但过高的频率也可能导致收敛于一个解；假设交叉概率太低，遗传算法搜索可能陷入迟钝状态。一般取交叉概率的值为至之间。3变异概率。变异概率通常只取较小的数值，通常为0.001 左右。一般而言，低频度的变异可防止群体中重要的、单一基因的可能丧失；假设取较高的变异概率将使遗传算法趋于纯粹的随机搜索，一方面会增加样本模式的多样性，另一方面也可能引起不稳定。4.应用领域遗传算法经过几十年的发展，逐渐被人们接受和运用，遗传算法的应用研究比理论研究更为丰富，下面是遗传算法的一些主要应用领域。优化问题优化问题包括函数优化和组合优化两种。函数优化是遗传算法的经典领域，也是对遗传算法进行性能评价的常用算例。对于组合优化，随着问题规模的扩大，搜索空间急剧扩大，这类复杂问题，人们已经意识到把精力放在寻找其满意解上。实践证明，遗传算法对于组合优化中的NP 完全问题非常有效。生产调度在很多情况下，用常规方法建立的数学模型难以精确求解生产调度问题，即使经过一些简化之后可以进行求解，有时也会因简化太多而使得求解结果与实际目标相差甚远。一般情况下，在现实生产中主要是靠经验来进行调度。研究发现，遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面，遗传算法都得到了有效的应用 。自动控制在自动控制领域中许多与优化相关的问题需要求解，遗传算法的应用日益增加，并显示了良好的效果。例如用遗传算法进行航空控制系统的优化、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习，都显示了遗传算法在这些领域中应用的可能性。机器学习学习能力是高级自适应系统所具备的能力之一，基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。遗传算法被用于学习模糊控制规则，可以更好地改进模糊系统的性能；基于遗传算法的机器学习不但可以用来调整人工：神经网络的连接权，也可用于人工神经网络结构的优化设计。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 6 页4 这一新的研究方向把遗传算法从历史离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。图像处理图像处理是电脑视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可防止地会存在一些误差，从而影响图像的效果。如何使这些误差最小化是电脑视觉到达实用化的重要要求。遗传算法可用于图像处理中的优化计算，目前已在模式识别(包括汉字识别 ) 、图像恢复、图像边缘特征提取等方面得到了应用。人工生命人工生命是用电脑、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的联系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于初期阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将会得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。数据挖掘数据挖掘能够从大规模数据库中提取隐含的、未知的、有潜在应用价值的知识和规则。许多数据挖掘问题可以看做是搜索问题。其中，数据库可看做是搜索空间，挖掘算法可看做是搜索策略。应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化，直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则 0 。Sunil 已成功地开发了一个基于遗传算法的数据挖掘工具 ，利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果说明遗传算法是进行数据挖掘的有效方法之一。5.存在的问题虽然遗传算法在许多领域中都有成功的应用，但其自身也存在不足，如局部搜索能力差、存在未成熟收敛和随机游走等现象，导致算法的收敛性能差，需要很长时间才能找到最优解等问题。这些不足阻碍了遗传算法的推广应用。如何改善遗传算法的搜索能力和提高算法的收敛速度，使其更好地应用于实际问题的解决中，是各国研究者一直探索的主要课题。6.结束语遗传算法作为一种非确定性的模拟自然演化的学习过程的求解问题方法，精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 6 页5 在很多领域具有广泛的应用价值，尽管它在实际应用中取得了巨大成功, 但其鲜明的生物特征 , 使得在数学基础方面相对不完善，有待于进一步研究、探讨和完善。可以预期，随着电脑技术的进步和生物学研究的深入，遗传算法在操作技术和方法上将更通用、更有效，遗传算法的前景值得期待。参考文献精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页6 1 马永, 贾俊芳 . 遗传算法研究综述 . 山西大同大学学报 ( 自然科学版 ),2007 年12月, 第23卷第3期. 2 高颖. 遗传算法综述 . 电脑光盘软件与应用 ,2010年第4期. 3 刘定理 . 遗传算法综述 . 中国西部科技 ,2009 年9月上旬第 08卷第25期总第186期. 4 葛继科 , 邱玉辉 , 吴春明 , 蒲国林 . 遗传算法综述 . 电脑应用研究 ,2008年10月第25卷第10期. 5 周瑛, 陈基漓 . 遗传算法综述 . 广州轻工业电脑与信息技术,2008 年1月第1期总第 110期. 6 王宏杰 , 魏先锋 , 薛周建 , 彭丹. 遗传算法综述 , 科技经济市场 ,2008年第6期. 7 赵宜鹏 , 孟磊, 彭承靖 . 遗传算法原理与发展方向综述. 黑龙江科技信息 . 8 常洪江 . 遗传算法综述 . 电脑学习， 2010年6月第3期. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页
