遗传算法原理

关于遗传算法原理报告提纲一、遗传算法概述二、遗传算法原理三、遗传算法的应用第2页,共97页，2024年2月25日，星期天一、遗传算法概述1、智能优化算法

2、基本遗传算法

3、遗传算法的特点

第3页,共97页，2024年2月25日，星期天1、智能优化算法智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。第4页,共97页，2024年2月25日，星期天常用的智能优化算法（1）遗传算法（GeneticAlgorithm，简称GA）（2）模拟退火算法（SimulatedAnnealing，简称SA）（3）禁忌搜索算法（TabuSearch，简称TS）

……第5页,共97页，2024年2月25日，星期天智能优化算法的特点它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。返回第6页,共97页，2024年2月25日，星期天遗传算法起源遗传算法是由美国的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。第7页,共97页，2024年2月25日，星期天遗传算法的搜索机制遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和突变)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

返回第8页,共97页，2024年2月25日，星期天2、基本遗传算法基本遗传算法（SimpleGeneticAlgorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。第9页,共97页，2024年2月25日，星期天基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、突变）（4）运行参数第10页,共97页，2024年2月25日，星期天编码GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。第11页,共97页，2024年2月25日，星期天函数优化示例求下列一元函数的最大值：

x∈[-1,2]，求解结果精确到6位小数。第12页,共97页，2024年2月25日，星期天SGA对于本例的编码由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3×106等份。又因为221<3×106<222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间[-1，2]内对应的实数值转化为一个二进制串（b21b20…b0）。第13页,共97页，2024年2月25日，星期天几个术语基因型：1000101110110101000111

表现型：0.637197编码解码个体（染色体）基因第14页,共97页，2024年2月25日，星期天初始种群SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。第15页,共97页，2024年2月25日，星期天适应度函数

遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。第16页,共97页，2024年2月25日，星期天选择算子遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。第17页,共97页，2024年2月25日，星期天轮盘赌选择方法轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：第18页,共97页，2024年2月25日，星期天轮盘赌选择方法的实现步骤（1）计算群体中所有个体的适应度函数值（需要解码）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。第19页,共97页，2024年2月25日，星期天交叉算子所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。第20页,共97页，2024年2月25日，星期天单点交叉运算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉点第21页,共97页，2024年2月25日，星期天突变算子所谓突变运算，是指依据突变概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的突变运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和突变运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中突变算子采用基本位突变算子。第22页,共97页，2024年2月25日，星期天基本位突变算子基本位突变算子是指对个体编码串随机指定的某一位或某几位基因作突变运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行突变操作的某一基因座上的原有基因值为0，则突变操作将其变为1；反之，若原有基因值为1，则突变操作将其变为0。第23页,共97页，2024年2月25日，星期天基本位突变算子的执行过程突变前：000001110000000010000突变后：000001110001000010000突变点第24页,共97页，2024年2月25日，星期天运行参数（1）M：种群规模（2）T：遗传运算的终止进化代数（3）Pc：交叉概率（4）Pm：突变概率第25页,共97页，2024年2月25日，星期天SGA的框图产生初始群体是否满足停止准则是输出结果并结束计算个体适应度值比例选择运算单点交叉运算基本位突变运算否产生新一代群体执行M/2次返回第26页,共97页，2024年2月25日，星期天3、遗传算法的特点（1）群体搜索，易于并行化处理；（2）不是盲目穷举，而是启发式搜索；（3）适应度函数不受连续、可微等条件的约束，适用范围很广。返回第27页,共97页，2024年2月25日，星期天二、遗传算法原理1、遗传算法的数学基础

2、遗传算法的收敛性分析

3、遗传算法的改进

返回第28页,共97页，2024年2月25日，星期天1、遗传算法的数学基础（1）模式定理（2）积木块假设返回第29页,共97页，2024年2月25日，星期天模式模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即0或者1。

模式示例：10**1第30页,共97页，2024年2月25日，星期天两个定义定义1：模式H中确定位置的个数称为模式H的阶，记作O(H)。例如O(10**1)=3。定义2：模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距，记作δ(H)。例如δ(10**1)=4。第31页,共97页，2024年2月25日，星期天模式的阶和定义距的含义模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。

第32页,共97页，2024年2月25日，星期天模式定理模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。第33页,共97页，2024年2月25日，星期天模式定理从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。返回第34页,共97页，2024年2月25日，星期天积木块假设积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。返回第35页,共97页，2024年2月25日，星期天2、遗传算法的收敛性分析遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和突变概率。第36页,共97页，2024年2月25日，星期天种群规模对收敛性的影响通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。第37页,共97页，2024年2月25日，星期天选择操作对收敛性的影响选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和突变操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。第38页,共97页，2024年2月25日，星期天交叉概率对收敛性的影响交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。第39页,共97页，2024年2月25日，星期天突变概率对收敛性的影响突变操作是对种群模式的扰动，有利于增加种群的多样性。但是，突变概率太小则很难产生新模式，突变概率太大则会使遗传算法成为随机搜索算法。第40页,共97页，2024年2月25日，星期天遗传算法的本质遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用突变算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。返回第41页,共97页，2024年2月25日，星期天3、遗传算法的改进遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。第42页,共97页，2024年2月25日，星期天遗传算法的改进途径（1）对编码方式的改进（2）对遗传算子的改进（3）对控制参数的改进（4）对执行策略的改进第43页,共97页，2024年2月25日，星期天对编码方式的改进二进制编码优点在于编码、解码操作简单，交叉、突变等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题，浮点数编码改善了遗传算法的计算复杂性。第44页,共97页，2024年2月25日，星期天对遗传算子的改进排序选择均匀交叉逆序突变（1）对群体中的所有个体按其适应度大小进行降序排序；（2）根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体；（3）以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。第45页,共97页，2024年2月25日，星期天对遗传算子的改进排序选择均匀交叉逆序突变（1）随机产生一个与个体编码长度相同的二进制屏蔽字P=W1W2…Wn

；（2）按下列规则从A、B两个父代个体中产生两个新个体X、Y：若Wi=0，则X的第i个基因继承A的对应基因，Y的第i个基因继承B的对应基因；若Wi=1，则A、B的第i个基因相互交换，从而生成X、Y的第i个基因。

第46页,共97页，2024年2月25日，星期天对遗传算子的改进排序选择均匀交叉逆序突变突变前：348|7965|21突变后：348|5697|21第47页,共97页，2024年2月25日，星期天对控制参数的改进Schaffer建议的最优参数范围是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。

第48页,共97页，2024年2月25日，星期天对控制参数的改进Srinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和Pm，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和Pm，使性能较差的个体被淘汰。第49页,共97页，2024年2月25日，星期天对执行策略的改进混合遗传算法免疫遗传算法小生境遗传算法单亲遗传算法并行遗传算法返回第50页,共97页，2024年2月25日，星期天三、遗传算法的应用1、遗传算法的应用领域

2、遗传算法的应用示例

3、我的研究第51页,共97页，2024年2月25日，星期天1、遗传算法的应用领域（1）组合优化（2）函数优化（3）智能控制（4）图像处理（5）机器学习（6）人工生命返回第52页,共97页，2024年2月25日，星期天遗传算法应用于组合优化组合优化是指在给定约束条件下,求解目标函数的最优值。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能求出其最优解。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有NP难度的组合优化问题上取得了成功的应用。如旅行商问题，我们给定一组n个城市和他们两两之间的直达距离，通过遗传算法我们可以寻找一条闭合的旅程，使得每个城市刚好经过一次且总的履行距离最短。再如车间作业调度问题，车间作业是指利用车间资源对某一对象进行生产的过程，作业调度实际上就是对车间作业进行有效排序，使某个目标函数最小。比方一台机床有多个工具，加工多种工件，各工件有确定的加工期限约束，需要制定一个月的加工计划保证完成所有的加工任务。由于JSP具有离散、动态、多变量耦合等属性，应用遗传算法具有一定难度，主要体现在遗传编码方法上。返回第53页,共97页，2024年2月25日，星期天函数优化工程上经常会遇到在多准则或多设计目标下设计和决策的问题，如果这些目标是相背的，需要找到满足这些目标的最佳设计方案。通常的做法是根据某有效函数将多目标合成单一目标来进行优化。但大多数情况下，在优化之前这种效用函数是难以确切知道的。法国经济学V.Pareto(1848-1923)最早研究经济领域内的多目标优化问题，他的理论称为Pareto最优化理论。J.Horn和N.Nafpliotis提出了关于用遗传算法解决多目标问题的基本算法思想，遗传算法界称为NPGA。返回第54页,共97页，2024年2月25日，星期天智能控制许多控制领域问题，当考虑到系统优化、自适应、自组织和自学习等方面的要求时，一般存在许多常规方法难以凑效的困难。例如，当有非连续评价函数、缺少初始信息、模型参数和结构或控制过程中的随机性、不确定性等复杂因素出现时，现有的控制理论和方法往往因需要求导信息、对初始条件的敏感性、对高品质的领域知识依赖性而难以得到很好的应用。1971年K.S.Fu从研究自学习控制系统入手，将智能控制概括为自动控制与人工智能的交集；1977年，Saridis以智能机器人的控制为主要研究背景，从研究机器智能的角度提出了智能控制是自动控制、人工智能及运筹学的交集，并提出了分级递阶智能控制的结构和方法；Astrom提出的专家智能则是将专家对被控对象和控制过程的知识、经验等融入控制器的设计与控制决策中。早期的智能控制研究受到传统控制理论的影响，大部分着眼点仍然基于系统已有的先验知识来解决问题，而不是自动获取知识。模糊控制基于模糊集理论，模拟人的近似推理和决策过程。1974年Mamdani成功地将它应用于高炉和蒸汽机的控第55页,共97页，2024年2月25日，星期天智能控制制，随后获得了迅猛的发展。模糊控制的主要困难在于控制规则的获取以及控制系统的稳定性问题。20世纪80年代中期以来，神经网络得到重新重视和发展。它主要模拟人脑的形象思维以及学习获取知识的能力。神经网络应用于控制问题，由于其高度依赖于生产现场所提供的大量训练样本，且训练算法的可实现性、实时性要求等因素，影响了其实用性。此外，对复杂问题的神经网络结构最优设计一直缺乏有效的方法。90年代以来，模糊理论、神经网络、专家系统、遗传算法和混沌方法等在许多控制领域得到了应用和发展，并且更重视这些方法相互融合，形成所谓的混合软计算。遗传算法借助搜索机制的随机性，能够搜索问题域的全局最优解，并且对噪声和变化表现出很好的鲁棒性和自适应能力。遗传算法在控制领域的应用大致分为两大类：一类是离线设计和分析；另一类是在线自适应性调整。前者遗传算法作为优化器，对于已知的控制对象寻求合适的控制规则以满足控制品质方面的要求，或者对于特定的控制器结构搜索最优参数。后者遗传算法作为一种学习机制来确定未知的或非稳定系统的特征，或者对控制器进行自适应性调整。返回第56页,共97页，2024年2月25日，星期天图像处理图像处理和模式识别是计算机视觉中的一个重要领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会产生一些误差，这些误差会影响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在图像处理中的优化计算方面是完全可以胜任的，目前已在图像校准、图像分割、几何形状识别、图像压缩、三维重建优化以及图像检索等方面得到了应用。返回第57页,共97页，2024年2月25日，星期天机器学习机器学习以复杂系统为对象，研究机器如何获取新知识或改善已有知识的问题，属于人工智能研究中较年轻的分支。由于20世纪40年代计算机的产生，使机器学习的实现有了可能，并且在50年代中期到60年代中期成了机器学习的热烈时期，这一时期主要研究各类自适应系统，并已开始研究神经网络模型和人工进化系统。60年代中期到70年代中期转入低潮，主要研究侧重于基于概念的学习和基于归纳的学习；70年代中期到80年代中期又得到了迅速地发展，特别是专家系统的成功应用。不同的学习策略和各种学习方法相继问世，示例归约学习成为研究主流，如出现了影响很大的示例学习方法:ID系列和AQ系列。此外，自动知识获取成为机器学习的应用研究目标，遗传算法应用于机器学习的思想已经被提出。最近10多年机器学习的研究和发展又进入了一个暂新时期。1986年，神经网络重新兴起，基于连接机制的学习开始向传统的符号学习挑战。神经网络将知识的表达蕴涵于网络连接中，处理隐层和反向传播算法的发展，显示出很强的学习能力，因而，广泛应用于模式识别、自动控制、信号处理、语音识别等许多领域。随着各种改进型学习算法不断地被提出，显著地改善了机器学习系统的性能。而此前的符号学习试图将知识由一个知识库包含和解释，其学习能力非常局限，只能适用于知识表达相对简单的系统。第58页,共97页，2024年2月25日，星期天机器学习迄今，自然界只有人类才真正具有完善的学习能力，机器学习系统实际上是对人的学习机制的一种抽象和模拟，是一种理想的学习模型。基于符号学习和学习系统如监督型学习系统、条件反射型学习系统、类比式学习系统、推理学习系统等，只具备一些较初级的学习能力。近年来，由于遗传算法的发展，基于进化机制的遗传学习成为一种新机器学习方法，它将知识表达为另一种符号形式-----遗传基因，通过模拟生物的进化过程，实现专门领域知识的合理增长型学习，所以有的学者将之称为次符号学习方法。机器学习成为遗传算法的经典领域之一，归功于密歇根大学Holland等早期的工作。他们将基于遗传的机器学习方法发展成为CSI的分类系统学习方法，奠定了遗传算法重要的思想基础，后来被归纳为“密歇根方法”。1991年，DeJong等提出了“匹茨堡方法”。1994年，日本名古屋大学的市桥等结合两种方法的优点提出了“名古屋方法”，这些方法都分别在复杂机器学习系统获得了成功的应用。此外，遗传程序设计方法应用于机器发现系统的研究及结合不同学习方法交互作用的混合学习方法也开始受到重视。返回第59页,共97页，2024年2月25日，星期天人工生命生物的多种特性与功能已经给科学研究者很多启示，人工神经网络可以说是受到人的神经元的启发，而遗传算法、进化计算更是根据生物的遗传、进化机制演变而成的。近年来，一些学者对人工生成具有生命特征的产物进行了多方面的研究。在早期，冯.诺依曼根据许多小单元均只与附近小单元相互作用的原则构造了元胞自动机，这种自动机可以“自繁殖”。他又指出计算机程序可以在内存中进行自复制。现在出现的各种计算机病毒，它们在一定的条件下可以自繁殖，甚至“进化”。各种电子宠物如“电子鸡”、“电子鱼”等具有类似生物的特性，例如需要按时进食，对环境可以趋利避害，有发育、生长、会生病、死亡等生物特征。这些“人工生命”可以看成一种具有生命特性的信息系统，相当一部分的人工生命是在计算机上实现的。可以认为自然界产生的生物是以核酸分子作为信息载体的，而生命的特征是由生物体中的信息系统决定的，如果把表征生命特性的信息系统在其它媒体上实现，同样也会产生相应的特征。这就是人工生命的内涵。返回第60页,共97页，2024年2月25日，星期天2、遗传算法的应用示例弹药装载问题（AmmunitionLoadingProblem，简称ALP），就是在满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率达到最大值的问题。第61页,共97页，2024年2月25日，星期天AGSAA的基本原理

在弹药装载中，考虑到模拟退火算法的基本思想是跳出局部最优解，将模拟退火思想引入遗传算法，应用改进型遗传算法和模拟退火算法相结合，构建自适应遗传模拟退火算法（AGSAA），从而综合了全局优化和局部搜索的特点，为解决弹药装载这一组合优化问题提供了新的思路。第62页,共97页，2024年2月25日，星期天AGSAA的编码方式

AGSAA采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为１，表示该弹药箱装入运输工具，为０则不装。第63页,共97页，2024年2月25日，星期天AGSAA的解码和适应度函数

AGSAA采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计算适应度函数值。第64页,共97页，2024年2月25日，星期天弹药装载的启发式算法

（1）定位规则（Locatingrule）定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。（2）定序规则（Orderingrule）定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。第65页,共97页，2024年2月25日，星期天遗传算子的选择AGSAA的选择算子采用轮盘赌选择算子，并结合最优保存策略；突变算子采用基本位突变算子；同时，在突变运算之后，增加退火算子，以增强算法的局部搜索能力；交叉概率和突变概率为自适应概率，以提高种群的进化效率。第66页,共97页，2024年2月25日，星期天交叉算子的选择由于AGSAA是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用传统方式进行，就有可能使个体的编码产生重复基因（即一个弹药箱编号在一个个体中出现两次以上），从而产生不符合条件的个体，因此，AGSAA采用的是部分映射交叉算子。

第67页,共97页，2024年2月25日，星期天部分映射交叉算子交叉前：87|43|126512|57|8346交叉后：83|67|124517|62|8345返回第68页,共97页，2024年2月25日，星期天关于遗传算法应用方面我的研究1、基于遗传算法的提高排课满意度的研究（计算机应用研究中国计算机学会会刊2007年增刊电脑知识与技术.学术交流2007/09）2、基于遗传算法的虚拟物体的变形研究(计算机应用与软件中国计算机学会会刊录用待发)3、计算机遗传病毒染毒机理分析(计算机应用与软件中国计算机学会会刊2008/08)4、倒立摆的混合控制（审稿阶段）5、基于GA和滑模控制的功率控制器的设计与仿真（审稿阶段）6、基于遗传算法的智能化动态分组的研究（2008年山西省教育厅研究课题）返回第69页,共97页，2024年2月25日，星期天基于遗传算法的提高排课满意度的研究

染色体结构染色体结构如右图上所示。该染色体含有m个基因，m的个数即是参与授课教师的总人数，每一个基因代表每位教师的课表，每一染色体即表示一种可能的排课结果。每位教师课表可用一维字符阵列表示。如右图下所示。例如：某一教师星期2第3大节要配置“微机原理”课程，字符阵列即可表示为：demo(23)=”微机原理”结合所有的染色体及所有的教师人数和上述的一维字符阵列，可成为一个三维阵列，即（染色体编号、教师编号、教师课表）。例如：第５染色体的第８位教师，于星期二第３大节课要配置“微机原理”课程，字符阵列可表示为demo(5,8,23)=”微机原理”以教师的课表为基因单位，两染色体经交叉操作后基因互换，不会影响到每位教师所教授的课程，也不会造成教师课表内含有其他教师的教授课程，不会出现每代演化后课表染色体结构不合理的问题。第70页,共97页，2024年2月25日，星期天基于遗传算法的提高排课满意度的研究

适应性函数适应性函数是计算出每条染色体的适应值。在本研究中，染色体若其适应值较大者，表示该排课结果拥有较多较佳授课时段，将会被给予较大的生存概率于下一代演化中。首先建立每位教师的授课时段优先度，如表1所示，可由教师填入自己较喜欢的时段及其喜好程度，该表格将提供做适应性使用，其中3代表最喜欢的授课时段，2代表较喜欢的授课时段，1代表喜欢的授课时段，空白代表可以接受的授课时段，-1代表不喜欢的授课时段。在演化过程中，应尽量避免-1所代表的时段，以避免教师不愿授课。将染色体中每个基因（教师课表）与教师时段喜好表比较，取相对应位置的值相加，如此累计计算出整条染色体的值。染色体函数计算所得的适应值也越大。第71页,共97页，2024年2月25日，星期天基于遗传算法的提高排课满意度的研究

选择选择就是将较大适应值的染色体复制到交叉池中。本文采用随机竞争法，即由上一代随机选取两条染色体来竞争，适应值较大的即可生存下来。此方法的优点是不影响竞争概率。第72页,共97页，2024年2月25日，星期天基于遗传算法的提高排课满意度的研究

交叉交叉是以每位教师课程表为基因单位，进行随机交换。方法是随机自交叉池里选取一对染色体作为进行交叉的双亲，并再取一乱数值（设为r），与系统预设的交叉率值（设为t）比较，若r<t即进行交换基因。第73页,共97页，2024年2月25日，星期天基于遗传算法的提高排课满意度的研究

突变突变是随机改变任一教师的一授课时段，将教师课表的时段以乱数方式决定是否要搬移与搬移到何处。当取出的乱数值小于系统预设的突变率时，即进行交叉，并随机决定新的位置，如图6所示。例如：将第5条染色体的第8位教师的星期2第3大节课的“微机原理”搬到星期3的第一大节课，可表示为：demo(5,8,31)=demo(5,8,23)demo(5,8,23)=””。第74页,共97页，2024年2月25日，星期天基于遗传算法的提高排课满意度的研究

演化流程图

第75页,共97页，2024年2月25日，星期天基于遗传算法的提高排课满意度的研究

实验结果在研究中，以数种不同交叉率及突变率来进行演化模型。我们设交叉率为0.5，突变率分别为0.01、0.03、0.05为例，每项各执行10次，再求取平均数，如下表所示。其次，以突变率为0.01，交叉率分别为0.6、0.7、0.8为例，每项各执行10次，再求取其平均数，如下表所示。第76页,共97页，2024年2月25日，星期天基于遗传算法的提高排课满意度的研究

实验结果图是适应函数值在演化过程中的变化，演化100代，染色体50条，突变率0.5，交叉率为0.01。图中绿色代表可行染色体中的最佳值，红色代表世代最佳值，蓝色代表世代平均值，黑色代表世代最佳值。返回第77页,共97页，2024年2月25日，星期天基于遗传算法的虚拟物体的变形研究

虚拟物体的初始建构

为使虚拟物体能利用虚拟物体变形，首先需要进行初始建构。本系统初始建构的方法是：将虚拟物体依一定之次序切割成9个不同的截面。考虑到绘图面的弹性与控制点的密度，将控制每个截面外形的控制点数目设定为12点，并应用曲线配合方式使控制点位于截面线上。如图1。调整各截面的大小，再调整各截面的位置，如图2所示。再将各截面连接，完成演变前的初始状态。如图3：第78页,共97页，2024年2月25日，星期天基于遗传算法的虚拟物体的变形研究

虚拟物体形变的规则

本系统以各截面为形变的基础，采用数列这种数学模型进行形变。2．1等差数列以其项数为横轴，各项的值为纵轴。2．2等差级数以其项数为横轴，各项的和为纵轴。本系统是对欲形变的截面做缩放或空间位置的变化，而各截面的缩放或位移，则透过等差数列或等差级数来进行造型变化。开始形变截面的大小与空间位置为“首项”，而开始形变到终止形变之间n个截面的缩放比例与位移距离为数列中的各项值，形变方式即透过等差数列或等差级数的计算，将第n个截面（即数列中的第n项）的缩放值与位移距离计算出，得到该截面在空间上的大小与应位移的距离，以此类推，将其他各截面的大小与空间位置推出，建构变形后的造型。2．3数列计算运用于造型形变分别对造型中的主截面进行x、y轴项的比例缩放或x、y轴向的位置变化，再进行主截面与主截面间的形体渐变，分大小与位移渐变，大小渐变，是指两个主要截面之间有大小的差异，渐变时，会由一个主截面的大小渐变到另一个主截面的大小。而位移渐变，是指两个主要截面与z轴距离值的差异，渐变时，会由一个主截面与z轴的x、y距离值增减到另一个主截面与z轴的x、y距离。第79页,共97页，2024年2月25日，星期天基于遗传算法的虚拟物体的变形研究

遗传算法的应用染色体本系统采用实数型方式，各截面的位移和缩放采用等差数列或等差级数。以（ABCDEFGH）代表染色体的各个基因。编码如表1：第80页,共97页，2024年2月25日，星期天基于遗传算法的虚拟物体的变形研究

遗传算法的应用适应函数本系统采用符合虚拟物体功能需求为评判机制，以虚拟物体变形后空间大小接近原虚拟物体内部体积为选择方式，建立适应函数，以使虚拟物体变形后有足够体积容纳内部物质。适应函数为：F1=|(AP+AQ)×h/2-S|（１）其中F1：适应函数AP：虚拟物体前端的面积AQ：虚拟物体后端的面积h：P、Q截面的距离3．3选择随机的从空间座标中挑选2条染色体，然后各计算两条染色体的适应函数值，比较计算结果若都比前一代演算结果佳(适应值高)，就进行下一个步骤，若有一条染色体没有前一代佳就再选取，直到两条染色体的适应值都比前一代高就进行下一个步骤。第81页,共97页，2024年2月25日，星期天基于遗传算法的虚拟物体的变形研究

遗传算法的应用3．4交叉交叉是将选取出的两条染色体依交叉点做基因交换，若比系统所定的交叉率低的可进行交叉。本系统采用成功率较高的交叉率80%来进行。而交叉方式，则采用单一交叉的方式进行。若染色体之交叉率低于80%，且随机选取基因1与基因2之间作为交叉点，交叉方式如图4。第82页,共97页，2024年2月25日，星期天基于遗传算法的虚拟物体的变形研究

遗传算法的应用突变突变是随机选择出染色体基因，做基因数值上的增减，突变的发生根据染色体的突变率而定。本系统设定为20%，只要染色体所产生的突变率小于20%就会突变。而突变方式，采用单点突变的方式进行，先随机选取基因3为突变点，并随机产生增减值1。原则上，增减后不超过基因规定的范围，超过后以最接近的基因规定范围内的值代替。如图5。第83页,共97页，2024年2月25日，星期天基于遗传算法的虚拟物体的变形研究

遗传算法的应用3．6适应度比较选择、交叉或突变完后，计算各子代的适应函数值，将适应函数值较优且比前一代适应值优良的子代留下，作为下一次运算选取步骤中，染色体选择的比较基准。3．7替换、再循环留下子代中适应值最大且前一代适应值优良的子代，并进行下一次的选择、交叉、突变。3．8演变完成的条件当前一代的适应值与本代的适应值的差距很小，几乎不改变时，表示前一代与本代相差不大，演变完成。演变完成的条件：E=|fl-1-fl|/fl<ε（２）E：适应函数的最终判断函数

S：虚拟物体体积大小fl：第l代适应函数的值fl-1：第l-1代适应函数的值第84页,共97页，2024年2月25日，星期天基于遗传算法的虚拟物体的变形研究

结论返回第85页,共97页，2024年2月25日，星期天算机遗传病毒染毒机理分析第86页,共97页，2024年2月25日，星期天防毒与解毒方法2.1防毒（1）扫描对比法扫描对比法是依据先前建立好的病毒特征码去判断病毒,依照病毒某些固定不变的特征,制作成病毒特征码。这种方法的优点是可以准确判断出已知的病毒,准确率很高。缺点是需要时刻更新病毒特征码,否则无法对抗新病毒。（2）加总查核法加总查核法是根据档案本身的特征属性（如档名、档案大小、存档日期时间,或档案内容依照特定演算法产生识别）,利用这些特征属性来产生检查码。此种方法的优点是可以确保此档案不遭到病毒的更改,保持其完整性。缺点是档案只要一经正常使用修改后,都需重新制作检查码,不利于经常更新的档案，且制作检查码前须确定档案未遭受病毒感染。（3）行为模式侦测法行为模式侦测法是依照程式的行为模式,来辨别该程式是否为病毒。从而分析计算机系统中一些不正常的行为指令,来防治一些危险性的行为,此种方法常用来对付多形病毒和会自我编码的病毒。此种方法的优点是可预防行为模式类似的变种病毒或未知病毒。缺点是很难定义出绝对危险或绝对安全的行为模式,也有可能拦截下具特殊功能的正常程式。第87页,共97页，2024年2月25日，星期天防毒与解毒方法（4）虚拟机器模拟法除了上述的行为模式侦测法可以用于对付多形病毒和会自我编码的病毒外,另一种方法就是使用虚拟机器模拟法。此种方法主要通过虚拟机器来模拟产生执行环境,再使用假执行将已加密过的病毒解密后,配合使用扫描对比病毒特征码等其他方法来发现病毒。此方法的优点是可以完全解开多形和会编码的病毒保护功能,使其无所遁形。缺点是会严重地耗用系统资源,将许多时间花费在虚拟执行上。2.2解毒工作原理解毒最主要的功能就是清除病毒,将磁道或档案恢复成未受病毒感染的状态。以引导区病毒为例,原始引导区的信息被搬移至别处,而病毒写入该引导区。此种病毒的解毒原理即是将被搬移的原始引导区信息,重新搬回引导区内并覆盖病毒。档案型病毒是在原始文件中加入有毒宏指令,从而感染文件,而此种病毒的解毒原理则为将有毒宏从中毒文件中移除,回复原始文件。第88页,共97页，2024年2月25日，星期天研究方法和研究模型从过去计算机病毒与防毒软件的发展史来说,早期传统的防毒软件要正确地找出病毒,都是通过扫描对比固定的病毒特征码,从病毒特征去判断程式是否已被感染。但是传统的防毒方法对于多形病毒和病毒产生器则无所适从。因为多形病毒有赋予病毒改变外貌的能力,以躲避防毒软件的扫描对比,通过不同的编码技术或参数,让被感染的档案里找不到相同的病毒特征码。病毒产生器则是根据病毒作者的需求,在功能选单上以勾选的方式选择,依乱数选取模组来产生病毒。这种产生病毒的方式,可造就出与众不同的病毒,并且能很容易产生出许多不同功能类型的新病毒。因此我们试图探讨是否存在一种方式,能够结合前述的多形病毒与病毒产生器的优点,让病毒在数字世界里,提高其生存机率,而遗传算法似乎正好具备有此种能力,在未来病毒的演进中,若结合遗传算法来遂行其永续存活的理想,将可能造成防毒或是消毒的工作负担。第89页,共97页，2024年2月25日，星期天遗传算法根据遗传算法的原理我们让原本一成不变的病毒能够改变自己。这种改变不是某种外貌或编码方式的改变,而是进行病毒本体的实质更新。本文试图建立一组新的病毒核心,让这个核心采用遗传算法的原则,实现演变工程。当然要特别强调的是,本文是对这个核心提出设计概念,并非要将固定的指令码一陈不变式地写入核心内。在遗传算法的选择、交叉、变异的操作步骤下,病毒的演变将会很类似自然界的行为法则。病毒的最主要目的,