简谈遗传算法

题目（中）简谈遗传算法姓名与学号 刘成昊3071904023年级与专业 cs0703所在学院计算机学院简谈遗传算法及其改进3071904023 刘成昊摘 要：遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度有效的随机搜索算 法。本文介绍了遗传算法的基本工作原理，讨论了遗传算法的理论、技术、存在问题及改进 方法论了混合遗传算法和并行遗传算法，指出了遗传算法的研究方向.1 引言遗传算法是一类借鉴生物界的进化规律 ( 适者生存，优胜劣汰遗传机制 )演化而来 的随机搜索算法。利用基因变异、杂交，繁殖等手段 ，根据达尔文的适者生存，优胜劣汰 的理论选择最优点进行变异和杂交 ， 从而繁殖产生新的后代 ，这些都是建立在概率的基 础之上.它尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题.如著名的T S(巡回旅行商问题)背包问题、排课问题等.虽然遗传算法在许多领域中都有成功的应用， 但其自身也存在不足，如局部搜索能力差 、存在未成熟收敛和随机游走等现象，导致算 法的收敛性能差， 需要很长时间才能找到最优解等问题。这些不足阻碍了遗传算法的推广 应用。如何改善遗传算法的搜索能力和提高算法的收敛速度， 使其更好地应用于实际问题 的解决中， 是现在遗传算法研究者首要考虑的问题。2技术及改进2 .1 遗传算法的执行过程遗传算法的执行过程遗传算法作为一种自适应全局优化搜索算法，使用二进制遗传编 码，即等位基因厂= 0 , 1 ，个体空间H t = 0, 1 ，且繁殖分为交叉与变异两个独立的 步骤进行。其基本执行过程如下 ：A )初始化。确定种群规模W、交叉概率P、变异概率p和置终止进化准则；随机生成， v个个体作为初始种群X( 0 )；置进化代数计数器t _ 0。B) 个体评价。计算或估价 t ) 中各个体的适应度。C ) 种群进化 。(a )选择(母体)。从X( t )中运用选择算子选择出M/ 2对母体(三W)。( b ) 交叉。对所选择的 M2 对母体， 依概率 P ， 执行交叉 形成 M 个中间个体。( c) 变异。对 个中间个体分别独立依概率 P 执行变 异， 形成 个候选个体。(d )选择从上述候选个体中依适应度选择出，v个个体组成新一代种群(t +1 )。D )终止检验。如已满足终止准则，则输出X( t +1 )中具有最大适应度的个体作为最优解， 终止计算否则置 f f +1并转 C ) 。2 .2 混合遗传算法简单的遗传算法在许多情况下不是十分有效，局部寻优能力较差，于是提出了多种混合算法。 例如， A c l d e y 推荐的遗传爬山法； Ma t h e f o u d 提出的遗传模拟退火算法； Mi l l e r 等提出的对于NP难问题的优化问题，采用遗传算法中增加局部改善运算等等。混合遗传 算法的基本思想是： 对于每个新产生的后代在其进入下一代群体之前应用局部优化技术 ( 如爬山法、 模拟退火算法等) ， 使之移动到最近的局部最优点。在混合遗传算法中， 用 启发式方法作局部优化 ， 采用遗传算法作全局最优点的探索。由于遗传算法与传统优化方 法的互补性， 混合遗传算法通常比单一算法优越。并行遗传算法可通过不同种群的加入打破平衡状态，促使各种群向更高层次的平衡状态进 化，从而得到最优个体。当算法运行一定代数后，即使是处于两个不同种群中的个体，其结 构也会类似，故通过采用不同种群的个体打破彼此内部平衡的作用有限。2. 3 编码方式 编码是遗传算法中首要解决的问题， 二进制编码是遗传算法中最常用的一种编码方法， 它 采用最小字符编码原则 ，编解码操作简单易行， 利于交叉、 变异操作的实现， 也可以 采用模式定理对算法进行理论分析 。但二进制编码用于多维 、 高精度数值问题优化时， 不能很好地克服连续函数离散化时的映射误差；不能直接反映问题的固有结构，精度不高， 并且个体长度大、占用内存多。针对二进制编码存在的不足，人们提出了多种改进方法 ， 比较典型的有以下几种：a ) 格雷码编码。为了克服二进制编码在连续函数离散化时存在的不足， 人们提出了用格雷 码进行编码的方法，它是二进制编码的变形 。格雷码不仅具有二进制编码的一些优点，而 且能够提高遗传算法的局部搜索能力。格雷码有这样一个特点： 任意两个整数的差是这两 个整数所对应的格雷码之间的海明距离。这个特点是遗传算法中使用 格雷码来进行个体编 码的主要原因。b ) 实数编码。该方法适合于遗传算法中表示范围较大的数 ， 使遗传算法更接近问题空间， 避免了编码和解码的过程。它便于较大空间的遗传搜索， 提高了遗传算法的精度要求便于 设计专门问题的遗传算子；便于算法与经典优化方法的混合作用，改善了遗传算法的计算 复杂性，提高了运算效率。c ) 十进制编码。该方法利用十进制编码控制参数， 缓解了“ 组合爆炸” 和遗传算法的 早熟收敛问题 。d ) 非数值编码。染色体编码串中的基因值取一个仅有代 码含义而无数值含义的符号集， 这些符号可以是数字也可以是字符 。非数值编码的优点是在遗传算法中可以利用所求问 题的专门知识及相关算法。对于非数值编码，问题的解和染色体的编码要注意染色体的可行 性 、 染色体的合法性和映射的惟一性 。24 遗传算子1 ) 选择( S e l e c t i o n ) 算子又称复制繁殖算子 选择是从种群中选择生命力强的染色体， 产生新种群的过程 选择的依据是每个染色体的适应度大小， 适应度越大， 被选中的概 率就越大，其子孙在下一代产生的个数就越多选择操作的主要目的是为了避免基因缺失 、 提高全局收敛性和计算效率 选择的方法根据不同的问题， 采用不同的方案 最常 见的方法有随机遍历抽样、 局部选择和截断选择等2 ) 交叉 ( C r o s s o v e r ) 算子又称重组配对( b r e e d i n g ) 算子 当许多染色体相同或后 代的染 色体与上一代没有多大差别时，可通过染色体重组来产生新一代染色体 染色体重 组分两个步骤进行： 首先，在新复制的群体中随机选取两个染色体，每个染色体由多个位 ( 基因) 组成； 然后， 沿着这两个染色体的基因随机取一个位置，二者互换从该位置起的 末尾部分基因3 ) 变异( Mu t a t i o n ) 算子 选择和交叉算子基本上完成了遗传算法的大部分搜索功能， 而变异则增加了遗传算法找到接近最优解的能力，即决定了遗传算法的局部搜索能力 变 异就是以很小的概率， 随机改变字符串某个位置上的值 在二进制编码中， 就 是将 0 变成 l ，将1变成 0它本身是一种随机搜索，但与选择、 交叉算子结合在一起，就能 避免由复制和交叉算子引起的某些信息的永久性丢失，从而保证了遗传算法的有效性3 遗传算法的应用3 1 函数优化 函数优化是遗传算法的经典应用领域 ， 也是对遗传算法进 行性能评价的常用算例。不同研究者构造出了各种各样的复杂形式的测试函数， 有连续函 数也有离散函数， 有凸函数也有凹函数， 有低维函数也有高维函数，有确定函数也有随机 函数， 有单峰值函数也有多峰值函数等。用这些几何特性各具特色的函数来评价遗传算法 的性能， 更能反映算法的本质效果。对于一些非线性、 多模型、 多目标的函数优化问题， 用其他优化方法较难求解， 遗传算法却可以方便地得到较好的结果 。3.2 组合优化 随着问题规模的增大， 组合优化问题的搜索空间也急剧扩大， 有时在 目前的计算机上用枚举法很难或甚至不可能求出其精确最优解 。对这类复杂 问题 ，人 们 已意识 到应把主要精力放在寻求其满意解上， 而遗传算法是寻求这种满意解的最佳工具 之一。实践证明，遗传算法已经在求解旅行商问题 、背包问题、 装箱问题、布局优化、 图形划分问题等各种具有 N P 难度的问题得到成功的应用。33生产调度问题生产调度问题在很多情况下建立起来 的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差 甚远。目前在现实生产中主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度 问题 的有效工具 ，在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面 遗传算法都得到了有效的应用 。3 .4 自动控制在自动控制领域中有很多与优化相关的问题需要求解， 遗传算法已在其中得到了初步的应用， 并显示出良好的效果。例 如用遗传算法进行航空控制系统的优 化、 使用遗传算法设计空间交会控制器、 基于遗传算法的模糊控制器的优化设计、 基于 遗传算法的参数辨识、 基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经 网络的结构优化设计和权值学习等， 都显示出了遗传算法在这些领域中应用的可能性 。3 .5 机器学习 学习能力是高级 自适应系统所具备的能力之一，基于遗传算法的机 器学习， 特别是分类器系统， 在很多领域中都得到了应用。遗传算法被用于学习模糊控制 规则，可以更好地改进模糊系统的性能；基于遗传算法的机器学习不但可以用来调整人工： 神经网络的连接权， 也可用于人工神经网络结构的优化设计 。3.1 0 数据挖掘 数据挖掘能够从大规模数据库中提取隐含的、未知的、有潜在应用 价值的知识和规则。许多数据挖掘问题可以看做是搜索问题。其中， 数据库可看做是搜索 空间， 挖掘算法可看做是搜索策略。应用遗传算法在数据库中进行搜索 ， 对随机产生的 一组规则进行进化， 直到数据库能被该组规则覆盖， 从而挖掘出隐含在数据库中的规则。 S u n i l已成功地开发了一个基于遗传算法的数据挖掘工具，利用该工具对两个飞机失事 的真实数据库进行了数据挖掘实验， 结果表明遗传算法是进行数据挖掘的有效方法之一。4 遗传算法的研究方向1 ) 基础理论 、 数学模型 遗传算法的理论基础 、数学模型主要集中于对算法的收 敛性、 复杂性、 收敛速度的研究上 在遗传算法中， 群体规模和遗传算子的控制参数的 选取非常困难， 但它们又是必不可少的试验参数遗传算法还有一个过早收敛的问题，怎 样阻止过早收敛也是正在研究的问题之一2 ) 分布并行遗传算法 遗传算法在操作上的突 出特点是具有高度的并行性， 许多 研究人员都在探索在并行机和分布式系统上高效执行遗传算法的策略 对分布并行遗传算 法的研究表明，只要通过保持多个群体和恰当控制群体间的相互作用来模拟并行执行过程， 即使不使用并行计算机， 也能提高算法的执行效率3 ) 分类系统 分类系统属于基于遗传算法的机器学习中的一类。包括基于串规则的 并行生成子系统、规则评价子系统和遗传算法子系统 分类系统越来越多地应用在科学、 工程和经济领域中， 是目前遗传算法研究中一个十分活跃的领域4 ) 遗传神经网络遗传算法与神经网络相结合正成功地被用于从时间序列分析来进行 财政预算在这些系统中， 信号是模糊的，数据是有噪声的，一般很难正确给出每个执行的 定量评价 如果采用遗传算法， 就能克服这些困难，显著提高系统性能5 ) 借鉴自然现象提出新的算法模型 从生物进化或自然界的各种现象中获得新的启 发， 提出新的方法， 或对现有的算法进行改进 如二倍体显性技术等5结束语遗传算法作为一种非确定性的拟自然算法， 为复杂系统的优化提供了一种新的方法， 遗传算法是一个十分活跃的研究领域， 遗传算法的研究正在从理论的深度、技术的多样化 以及应用的广度不断地探索， 朝着计算机拥有甚至超过人类智能的方向努力。