《遗传算法原理》PPT课件.ppt

《《遗传算法原理》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《遗传算法原理》PPT课件.ppt（96页珍藏版）》请在三一办公上搜索。

1、遗传算法,报告提纲,一、遗传算法概述 二、遗传算法原理三、遗传算法的应用,一、遗传算法概述,1、智能优化算法 2、基本遗传算法 3、遗传算法的特点,1、智能优化算法,智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。,常用的智能优化算法,（1）遗传算法（Genetic Algorithm，简称GA）（2）模拟退火算法（Simulated Annealing，简称SA）（3）禁忌搜索算法（Tabu Search，简称TS）,智能优化算法的特点,它们的共

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

3、2、基本遗传算法,基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。,基本遗传算法的组成,（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、突变）（4）运行参数,编码,GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。,函数优化示例,求下列一元函数的最大值：,x-1,2，求解结果精确到6位小数。,S

4、GA对于本例的编码,由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。又因为221 3106 222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b0）。,几个术语,基因型：,表现型：0.637197,编码,解码,个体（染色体）,基因,初始种群,SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。,适应度函数,遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然

5、选择的唯一标准，它的设计应结合求解问题本身的要求而定。,选择算子,遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。,轮盘赌选择方法,轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：,轮盘赌选择方法的实现步骤,（1）计算群体中所有个体的适应度函数值（需要解码）；（2

6、）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。,交叉算子,所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。,单点交叉运算,交叉前：交叉后：,交叉点,突变算子,所谓突变运算，是指依据突变概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个

7、新的个体。遗传算法中的突变运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和突变运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中突变算子采用基本位突变算子。,基本位突变算子,基本位突变算子是指对个体编码串随机指定的某一位或某几位基因作突变运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行突变操作的某一基因座上的原有基因值为0，则突变操作将其变为1；反之，若原有基因值为1，则突变操作将其变为0。,基本位突变算子的执行过程,突变前：0000010000突变后：1000010000,突变点,运行参数,（1）M：种群规模（2）T

8、：遗传运算的终止进化代数（3）Pc：交叉概率（4）Pm：突变概率,SGA的框图,返回,3、遗传算法的特点,（1）群体搜索，易于并行化处理；（2）不是盲目穷举，而是启发式搜索；（3）适应度函数不受连续、可微等条件的约束，适用范围很广。,返回,二、遗传算法原理,1、遗传算法的数学基础 2、遗传算法的收敛性分析 3、遗传算法的改进,返回,1、遗传算法的数学基础,（1）模式定理（2）积木块假设,返回,模式,模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即 0 或者 1。模式示例：10*1,两个

9、定义,定义1：模式 H 中确定位置的个数称为模式 H 的阶，记作O(H)。例如O(10*1)=3。定义2：模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式 H 的定义距，记作(H)。例如(10*1)=4。,模式的阶和定义距的含义,模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。,模式定理,模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算

10、法机理提供了数学基础。,模式定理,从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。,返回,积木块假设,积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。,返回,2、遗传算法的收敛性分析,遗传算法

11、要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和突变概率。,种群规模对收敛性的影响,通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。,选择操作对收敛性的影响,选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和突变操作，使之直接进入下一代，最终可使遗传算法以概率1收

12、敛于全局最优解。,交叉概率对收敛性的影响,交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。,突变概率对收敛性的影响,突变操作是对种群模式的扰动，有利于增加种群的多样性。但是，突变概率太小则很难产生新模式，突变概率太大则会使遗传算法成为随机搜索算法。,遗传算法的本质,遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用突变算子进行模式突变。通过这些遗传操作，

13、模式逐步向较好的方向进化，最终得到问题的最优解。,返回,3、遗传算法的改进,遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。,遗传算法的改进途径,（1）对编码方式的改进（2）对遗传算子 的改进（3）对控制参数的改进（4）对执行策略的改进,对编码方式的改进,二进制编码优点在于编码、解码操作简单，交叉、突变等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题，浮点数编码改善了遗传算法的计算复杂性。,对

14、遗传算子 的改进,排序选择 均匀交叉 逆序突变,（1）对群体中的所有个体按其适应度大小进行降序排序；（2）根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体；（3）以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。,对遗传算子 的改进,排序选择 均匀交叉 逆序突变,（1）随机产生一个与个体编码长度相同的二进制屏蔽字P=W1W2Wn；（2）按下列规则从A、B两个父代个体中产生两个新个体X、Y：若Wi=0，则X的第i个基因继承A的对应基因，Y的第i个基因继承B的对应基因；若Wi=1，则A、B的第i个基因相互交换，从而生成X、Y

15、的第i个基因。,对遗传算子 的改进,排序选择 均匀交叉 逆序突变,突变前：3 4 8|7 9 6 5|2 1突变后：3 4 8|5 6 9 7|2 1,对控制参数的改进,Schaffer建议的最优参数范围是：M=20-100，T=100-500，Pc，Pm。,对控制参数的改进,Srinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和Pm，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和Pm，使性能较差的个

16、体被淘汰。,对执行策略的改进,混合遗传算法免疫遗传算法小生境遗传算法单亲遗传算法并行遗传算法,返回,三、遗传算法的应用,1、遗传算法的应用领域 2、遗传算法的应用示例 3、我的研究,1、遗传算法的应用领域,（1）组合优化（2）函数优化（3）智能控制（4）图像处理（5）机器学习（6）人工生命,返回,遗传算法应用于组合优化,组合优化是指在给定约束条件下,求解目标函数的最优值。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能求出其最优解。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有NP难度的组合优化问题上取得了成功的应

17、用。如旅行商问题，我们给定一组n个城市和他们两两之间的直达距离，通过遗传算法我们可以寻找一条闭合的旅程，使得每个城市刚好经过一次且总的履行距离最短。再如车间作业调度问题，车间作业是指利用车间资源对某一对象进行生产的过程，作业调度实际上就是对车间作业进行有效排序，使某个目标函数最小。比方一台机床有多个工具，加工多种工件，各工件有确定的加工期限约束，需要制定一个月的加工计划保证完成所有的加工任务。由于JSP具有离散、动态、多变量耦合等属性，应用遗传算法具有一定难度，主要体现在遗传编码方法上。,返回,函数优化,工程上经常会遇到在多准则或多设计目标下设计和决策的问题，如果这些目标是相背的，需要找到满足

18、这些目标的最佳设计方案。通常的做法是根据某有效函数将多目标合成单一目标来进行优化。但大多数情况下，在优化之前这种效用函数是难以确切知道的。法国经济学V.Pareto(1848-1923)最早研究经济领域内的多目标优化问题，他的理论称为Pareto最优化理论。J.Horn和N.Nafpliotis提出了关于用遗传算法解决多目标问题的基本算法思想，遗传算法界称为NPGA。,返回,智能控制,许多控制领域问题，当考虑到系统优化、自适应、自组织和自学习等方面的要求时，一般存在许多常规方法难以凑效的困难。例如，当有非连续评价函数、缺少初始信息、模型参数和结构或控制过程中的随机性、不确定性等复杂因素出现时，

19、现有的控制理论和方法往往因需要求导信息、对初始条件的敏感性、对高品质的领域知识依赖性而难以得到很好的应用。1971年从研究自学习控制系统入手，将智能控制概括为自动控制与人工智能的交集；1977年，Saridis以智能机器人的控制为主要研究背景，从研究机器智能的角度提出了智能控制是自动控制、人工智能及运筹学的交集，并提出了分级递阶智能控制的结构和方法；Astrom提出的专家智能则是将专家对被控对象和控制过程的知识、经验等融入控制器的设计与控制决策中。早期的智能控制研究受到传统控制理论的影响，大部分着眼点仍然基于系统已有的先验知识来解决问题，而不是自动获取知识。模糊控制基于模糊集理论，模拟人的近似

20、推理和决策过程。1974年Mamdani成功地将它应用于高炉和蒸汽机的控,智能控制,制，随后获得了迅猛的发展。模糊控制的主要困难在于控制规则的获取以及控制系统的稳定性问题。20世纪80年代中期以来，神经网络得到重新重视和发展。它主要模拟人脑的形象思维以及学习获取知识的能力。神经网络应用于控制问题，由于其高度依赖于生产现场所提供的大量训练样本，且训练算法的可实现性、实时性要求等因素，影响了其实用性。此外，对复杂问题的神经网络结构最优设计一直缺乏有效的方法。90年代以来，模糊理论、神经网络、专家系统、遗传算法和混沌方法等在许多控制领域得到了应用和发展，并且更重视这些方法相互融合，形成所谓的混合软计

21、算。遗传算法借助搜索机制的随机性，能够搜索问题域的全局最优解，并且对噪声和变化表现出很好的鲁棒性和自适应能力。遗传算法在控制领域的应用大致分为两大类：一类是离线设计和分析；另一类是在线自适应性调整。前者遗传算法作为优化器，对于已知的控制对象寻求合适的控制规则以满足控制品质方面的要求，或者对于特定的控制器结构搜索最优参数。后者遗传算法作为一种学习机制来确定未知的或非稳定系统的特征，或者对控制器进行自适应性调整。,返回,图像处理,图像处理和模式识别是计算机视觉中的一个重要领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会产生一些误差，这些误差会影响到图像处理和识别的效果。如何使这些误

22、差最小是使计算机视觉达到实用化的重要要求。遗传算法在图像处理中的优化计算方面是完全可以胜任的，目前已在图像校准、图像分割、几何形状识别、图像压缩、三维重建优化以及图像检索等方面得到了应用。,返回,机器学习,机器学习以复杂系统为对象，研究机器如何获取新知识或改善已有知识的问题，属于人工智能研究中较年轻的分支。由于20世纪40年代计算机的产生，使机器学习的实现有了可能，并且在50年代中期到60年代中期成了机器学习的热烈时期，这一时期主要研究各类自适应系统，并已开始研究神经网络模型和人工进化系统。60年代中期到70年代中期转入低潮，主要研究侧重于基于概念的学习和基于归纳的学习；70年代中期到80年代

23、中期又得到了迅速地发展，特别是专家系统的成功应用。不同的学习策略和各种学习方法相继问世，示例归约学习成为研究主流，如出现了影响很大的示例学习方法:ID系列和AQ系列。此外，自动知识获取成为机器学习的应用研究目标，遗传算法应用于机器学习的思想已经被提出。最近10多年机器学习的研究和发展又进入了一个暂新时期。1986年，神经网络重新兴起，基于连接机制的学习开始向传统的符号学习挑战。神经网络将知识的表达蕴涵于网络连接中，处理隐层和反向传播算法的发展，显示出很强的学习能力，因而，广泛应用于模式识别、自动控制、信号处理、语音识别等许多领域。随着各种改进型学习算法不断地被提出，显著地改善了机器学习系统的性

24、能。而此前的符号学习试图将知识由一个知识库包含和解释，其学习能力非常局限，只能适用于知识表达相对简单的系统。,机器学习,迄今，自然界只有人类才真正具有完善的学习能力，机器学习系统实际上是对人的学习机制的一种抽象和模拟，是一种理想的学习模型。基于符号学习和学习系统如监督型学习系统、条件反射型学习系统、类比式学习系统、推理学习系统等，只具备一些较初级的学习能力。近年来，由于遗传算法的发展，基于进化机制的遗传学习成为一种新机器学习方法，它将知识表达为另一种符号形式-遗传基因，通过模拟生物的进化过程，实现专门领域知识的合理增长型学习，所以有的学者将之称为次符号学习方法。机器学习成为遗传算法的经典领域之

25、一，归功于密歇根大学Holland等早期的工作。他们将基于遗传的机器学习方法发展成为CSI的分类系统学习方法，奠定了遗传算法重要的思想基础，后来被归纳为“密歇根方法”。1991年，De Jong等提出了“匹茨堡方法”。1994年，日本名古屋大学的市桥等结合两种方法的优点提出了“名古屋方法”，这些方法都分别在复杂机器学习系统获得了成功的应用。此外，遗传程序设计方法应用于机器发现系统的研究及结合不同学习方法交互作用的混合学习方法也开始受到重视。,返回,人工生命,生物的多种特性与功能已经给科学研究者很多启示，人工神经网络可以说是受到人的神经元的启发，而遗传算法、进化计算更是根据生物的遗传、进化机制演

26、变而成的。近年来，一些学者对人工生成具有生命特征的产物进行了多方面的研究。在早期，冯.诺依曼根据许多小单元均只与附近小单元相互作用的原则构造了元胞自动机，这种自动机可以“自繁殖”。他又指出计算机程序可以在内存中进行自复制。现在出现的各种计算机病毒，它们在一定的条件下可以自繁殖，甚至“进化”。各种电子宠物如“电子鸡”、“电子鱼”等具有类似生物的特性，例如需要按时进食，对环境可以趋利避害，有发育、生长、会生病、死亡等生物特征。这些“人工生命”可以看成一种具有生命特性的信息系统，相当一部分的人工生命是在计算机上实现的。可以认为自然界产生的生物是以核酸分子作为信息载体的，而生命的特征是由生物体中的信息

27、系统决定的，如果把表征生命特性的信息系统在其它媒体上实现，同样也会产生相应的特征。这就是人工生命的内涵。,返回,2、遗传算法的应用示例,弹药装载问题（Ammunition Loading Problem，简称ALP），就是在满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率达到最大值的问题。,AGSAA的基本原理,在弹药装载中，考虑到模拟退火算法的基本思想是跳出局部最优解，将模拟退火思想引入遗传算法，应用改进型遗传算法和模拟退火算法相结合，构建自适应遗传模拟退火算法（AGSAA），从而综合了全局优化和局部搜索的特点，为解决弹药装载这一组合优化

28、问题提供了新的思路。,AGSAA的编码方式,AGSAA采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为，表示该弹药箱装入运输工具，为则不装。,AGSAA的解码和适应度函数,AGSAA采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计算适应度函数值。,弹药装载的启发式算法,（1）定位规则（Locating rule）定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。（2）定序规则（Ordering rule）定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。,遗传算

29、子的选择,AGSAA的选择算子采用轮盘赌选择算子，并结合最优保存策略；突变算子采用基本位突变算子；同时，在突变运算之后，增加退火算子，以增强算法的局部搜索能力；交叉概率和突变概率为自适应概率，以提高种群的进化效率。,交叉算子的选择,由于AGSAA是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用传统方式进行，就有可能使个体的编码产生重复基因（即一个弹药箱编号在一个个体中出现两次以上），从而产生不符合条件的个体，因此，AGSAA采用的是部分映射交叉算子。,部分映射交叉算子,交叉前：8 7|4 3|1 2 6 5 1 2|5 7|8 3 4 6交叉后：8 3|6 7|1 2 4 5 1 7

30、|6 2|8 3 4 5,返回,关于遗传算法应用方面我的研究,1、基于遗传算法的提高排课满意度的研究（计算机应用研究 中国计算机学会会刊 2007年增刊 电脑知识与技术.学术交流 2007/09）2、基于遗传算法的虚拟物体的变形研究(计算机应用与软件 中国计算机学会会刊 录用待发)3、计算机遗传病毒染毒机理分析(计算机应用与软件 中国计算机学会会刊 2008/08)4、倒立摆的混合控制（审稿阶段）5、基于GA和滑模控制的功率控制器的设计与仿真（审稿阶段）6、基于遗传算法的智能化动态分组的研究（2008年山西省教育厅研究课题）,返回,基于遗传算法的提高排课满意度的研究染色体结构,染色体结构如右图

31、上所示。该染色体含有m个基因，m的个数即是参与授课教师的总人数，每一个基因代表每位教师的课表，每一染色体即表示一种可能的排课结果。每位教师课表可用一维字符阵列表示。如右图下所示。例如：某一教师星期2第3大节要配置“微机原理”课程，字符阵列即可表示为：demo(23)=”微机原理”结合所有的染色体及所有的教师人数和上述的一维字符阵列，可成为一个三维阵列，即（染色体编号、教师编号、教师课表）。例如：第染色体的第位教师，于星期二第大节课要配置“微机原理”课程，字符阵列可表示为demo(5,8,23)=”微机原理”以教师的课表为基因单位，两染色体经交叉操作后基因互换，不会影响到每位教师所教授的课程，也

32、不会造成教师课表内含有其他教师的教授课程，不会出现每代演化后课表染色体结构不合理的问题。,基于遗传算法的提高排课满意度的研究适应性函数,适应性函数是计算出每条染色体的适应值。在本研究中，染色体若其适应值较大者，表示该排课结果拥有较多较佳授课时段，将会被给予较大的生存概率于下一代演化中。首先建立每位教师的授课时段优先度，如表1所示，可由教师填入自己较喜欢的时段及其喜好程度，该表格将提供做适应性使用，其中3代表最喜欢的授课时段，2代表较喜欢的授课时段，1代表喜欢的授课时段，空白代表可以接受的授课时段，-1代表不喜欢的授课时段。在演化过程中，应尽量避免-1所代表的时段，以避免教师不愿授课。将染色体中

33、每个基因（教师课表）与教师时段喜好表比较，取相对应位置的值相加，如此累计计算出整条染色体的值。染色体函数计算所得的适应值也越大。,基于遗传算法的提高排课满意度的研究选择,选择就是将较大适应值的染色体复制到交叉池中。本文采用随机竞争法，即由上一代随机选取两条染色体来竞争，适应值较大的即可生存下来。此方法的优点是不影响竞争概率。,基于遗传算法的提高排课满意度的研究交叉,交叉是以每位教师课程表为基因单位，进行随机交换。方法是随机自交叉池里选取一对染色体作为进行交叉的双亲，并再取一乱数值（设为r），与系统预设的交叉率值（设为t）比较，若rt即进行交换基因。,基于遗传算法的提高排课满意度的研究突变,突变

34、是随机改变任一教师的一授课时段，将教师课表的时段以乱数方式决定是否要搬移与搬移到何处。当取出的乱数值小于系统预设的突变率时，即进行交叉，并随机决定新的位置，如图6所示。例如：将第5条染色体的第8位教师的星期2第3大节课的“微机原理”搬到星期3的第一大节课，可表示为：demo(5,8,31)=demo(5,8,23)demo(5,8,23)=”。,基于遗传算法的提高排课满意度的研究演化流程图,基于遗传算法的提高排课满意度的研究实验结果,在研究中，以数种不同交叉率及突变率来进行演化模型。我们设交叉率为0.5，突变率分别为0.01、0.03、0.05为例，每项各执行10次，再求取平均数，如下表所示。

35、其次，以突变率为0.01，交叉率分别为0.6、0.7、0.8为例，每项各执行10次，再求取其平均数，如下表所示。,基于遗传算法的提高排课满意度的研究实验结果,图是适应函数值在演化过程中的变化，演化100代，染色体50条，突变率0.5，交叉率为0.01。图中绿色代表可行染色体中的最佳值，红色代表世代最佳值，蓝色代表世代平均值，黑色代表世代最佳值。,返回,基于遗传算法的虚拟物体的变形研究虚拟物体的初始建构,为使虚拟物体能利用虚拟物体变形，首先需要进行初始建构。本系统初始建构的方法是：将虚拟物体依一定之次序切割成9个不同的截面。考虑到绘图面的弹性与控制点的密度，将控制每个截面外形的控制点数目设定为1

36、2点，并应用曲线配合方式使控制点位于截面线上。如图1。调整各截面的大小，再调整各截面的位置，如图2所示。再将各截面连接，完成演变前的初始状态。如图3：,基于遗传算法的虚拟物体的变形研究虚拟物体形变的规则,本系统以各截面为形变的基础，采用数列这种数学模型进行形变。21 等差数列以其项数为横轴，各项的值为纵轴。22 等差级数以其项数为横轴，各项的和为纵轴。本系统是对欲形变的截面做缩放或空间位置的变化，而各截面的缩放或位移，则透过等差数列或等差级数来进行造型变化。开始形变截面的大小与空间位置为“首项”，而开始形变到终止形变之间n个截面的缩放比例与位移距离为数列中的各项值，形变方式即透过等差数列或等差

37、级数的计算，将第n个截面（即数列中的第n项）的缩放值与位移距离计算出，得到该截面在空间上的大小与应位移的距离，以此类推，将其他各截面的大小与空间位置推出，建构变形后的造型。23 数列计算运用于造型形变分别对造型中的主截面进行 x、y轴项的比例缩放或x、y轴向的位置变化，再进行主截面与主截面间的形体渐变，分大小与位移渐变，大小渐变，是指两个主要截面之间有大小的差异，渐变时，会由一个主截面的大小渐变到另一个主截面的大小。而位移渐变，是指两个主要截面与z轴距离值的差异，渐变时，会由一个主截面与z轴的x、y距离值增减到另一个主截面与z轴的x、y距离。,基于遗传算法的虚拟物体的变形研究遗传算法的应用,染

38、色体本系统采用实数型方式，各截面的位移和缩放采用等差数列或等差级数。以（A B C D E F G H）代表染色体的各个基因。编码如表1：,基于遗传算法的虚拟物体的变形研究遗传算法的应用,适应函数 本系统采用符合虚拟物体功能需求为评判机制，以虚拟物体变形后空间大小接近原虚拟物体内部体积为选择方式，建立适应函数，以使虚拟物体变形后有足够体积容纳内部物质。适应函数为：F1=|(AP+AQ)h/2-S|（）其中F1：适应函数AP：虚拟物体前端的面积AQ：虚拟物体后端的面积h：P、Q截面的距离33 选择随机的从空间座标中挑选2条染色体，然后各计算两条染色体的适应函数值，比较计算结果若都比前一代演算结果

39、佳(适应值高)，就进行下一个步骤，若有一条染色体没有前一代佳就再选取，直到两条染色体的适应值都比前一代高就进行下一个步骤。,基于遗传算法的虚拟物体的变形研究遗传算法的应用,34 交叉交叉是将选取出的两条染色体依交叉点做基因交换，若比系统所定的交叉率低的可进行交叉。本系统采用成功率较高的交叉率80%来进行。而交叉方式，则采用单一交叉的方式进行。若染色体之交叉率低于80%，且随机选取基因1与基因2之间作为交叉点，交叉方式如图4。,基于遗传算法的虚拟物体的变形研究遗传算法的应用,突变突变是随机选择出染色体基因，做基因数值上的增减，突变的发生根据染色体的突变率而定。本系统设定为20%，只要染色体所产生

40、的突变率小于20%就会突变。而突变方式，采用单点突变的方式进行，先随机选取基因3为突变点，并随机产生增减值1。原则上，增减后不超过基因规定的范围，超过后以最接近的基因规定范围内的值代替。如图5。,基于遗传算法的虚拟物体的变形研究遗传算法的应用,36 适应度比较选择、交叉或突变完后，计算各子代的适应函数值，将适应函数值较优且比前一代适应值优良的子代留下，作为下一次运算选取步骤中，染色体选择的比较基准。37 替换、再循环留下子代中适应值最大且前一代适应值优良的子代，并进行下一次的选择、交叉、突变。38 演变完成的条件当前一代的适应值与本代的适应值的差距很小，几乎不改变时，表示前一代与本代相差不大，

41、演变完成。演变完成的条件：E=|fl-1-fl|/fl（）E：适应函数的最终判断函数S：虚拟物体体积大小fl：第l代适应函数的值f l-1：第l-1代适应函数的值,基于遗传算法的虚拟物体的变形研究结论,返回,算机遗传病毒染毒机理分析,防毒与解毒方法,2.1防毒（1）扫描对比法 扫描对比法是依据先前建立好的病毒特征码去判断病毒,依照病毒某些固定不变的特征,制作成病毒特征码。这种方法的优点是可以准确判断出已知的病毒,准确率很高。缺点是需要时刻更新病毒特征码,否则无法对抗新病毒。（2）加总查核法加总查核法是根据档案本身的特征属性（如档名、档案大小、存档日期时间,或档案内容依照特定演算法产生识别）,利

42、用这些特征属性来产生检查码。此种方法的优点是可以确保此档案不遭到病毒的更改,保持其完整性。缺点是档案只要一经正常使用修改后,都需重新制作检查码,不利于经常更新的档案，且制作检查码前须确定档案未遭受病毒感染。（3）行为模式侦测法行为模式侦测法是依照程式的行为模式,来辨别该程式是否为病毒。从而分析计算机系统中一些不正常的行为指令,来防治一些危险性的行为,此种方法常用来对付多形病毒和会自我编码的病毒。此种方法的优点是可预防行为模式类似的变种病毒或未知病毒。缺点是很难定义出绝对危险或绝对安全的行为模式,也有可能拦截下具特殊功能的正常程式。,防毒与解毒方法,（4）虚拟机器模拟法 除了上述的行为模式侦测法

43、可以用于对付多形病毒和会自我编码的病毒外,另一种方法就是使用虚拟机器模拟法。此种方法主要通过虚拟机器来模拟产生执行环境,再使用假执行将已加密过的病毒解密后,配合使用扫描对比病毒特征码等其他方法来发现病毒。此方法的优点是可以完全解开多形和会编码的病毒保护功能,使其无所遁形。缺点是会严重地耗用系统资源,将许多时间花费在虚拟执行上。2.2解毒工作原理解毒最主要的功能就是清除病毒,将磁道或档案恢复成未受病毒感染的状态。以引导区病毒为例,原始引导区的信息被搬移至别处,而病毒写入该引导区。此种病毒的解毒原理即是将被搬移的原始引导区信息,重新搬回引导区内并覆盖病毒。档案型病毒是在原始文件中加入有毒宏指令,从

44、而感染文件,而此种病毒的解毒原理则为将有毒宏从中毒文件中移除,回复原始文件。,研究方法和研究模型,从过去计算机病毒与防毒软件的发展史来说,早期传统的防毒软件要正确地找出病毒,都是通过扫描对比固定的病毒特征码,从病毒特征去判断程式是否已被感染。但是传统的防毒方法对于多形病毒和病毒产生器则无所适从。因为多形病毒有赋予病毒改变外貌的能力,以躲避防毒软件的扫描对比,通过不同的编码技术或参数,让被感染的档案里找不到相同的病毒特征码。病毒产生器则是根据病毒作者的需求,在功能选单上以勾选的方式选择,依乱数选取模组来产生病毒。这种产生病毒的方式,可造就出与众不同的病毒,并且能很容易产生出许多不同功能类型的新病

45、毒。因此我们试图探讨是否存在一种方式,能够结合前述的多形病毒与病毒产生器的优点,让病毒在数字世界里,提高其生存机率,而遗传算法似乎正好具备有此种能力,在未来病毒的演进中,若结合遗传算法来遂行其永续存活的理想,将可能造成防毒或是消毒的工作负担。,遗传算法,根据遗传算法的原理我们让原本一成不变的病毒能够改变自己。这种改变不是某种外貌或编码方式的改变,而是进行病毒本体的实质更新。本文试图建立一组新的病毒核心,让这个核心采用遗传算法的原则,实现演变工程。当然要特别强调的是,本文是对这个核心提出设计概念,并非要将固定的指令码一陈不变式地写入核心内。在遗传算法的选择、交叉、变异的操作步骤下,病毒的演变将会

46、很类似自然界的行为法则。病毒的最主要目的,就是希望“存活”,而本模型的最主要目的,就是要创造更多能“存活”的病毒。,病毒新模型,本文所提出的模型,是以遗传算法为病毒核心,并且将病毒原本应有的功能予以建立类别,为简化说明,我们假设病毒基因依据其功能分为常驻、编码、感染、破坏与散播等五种,如图3所示。我们将此类具有遗传算法为核心的病毒,定义为遗传病毒。,病毒新模型,此模型仅是一般性的概念式架构,其中,GV核心负责执行遗传算法,而各类别集合相同类型功能的程式码。分类的方法是,若不先将病毒的特征码依照功能分类,而直接用乱数将特征码进行替换或交叉,则创造出来的病毒,可能会产生特征逻辑有误或无法执行的问题

47、,就如同将眼睛器官移植到鼻子上去,将导致无法生存。换句话说,毫无章法地任意取样乱配,会导致演变工程产生许多“畸形”病毒。简言之,分类的主要目的是要让GV在同一类的不同病毒元件中,选取可以替换或交叉到满足该类功能需求的特征。GV模型里的初始化工作,是要替病毒做染色体取样,并决定基因大小,以做为遗传基因操作的元素。在基因内的参数值,我们要找出相对应的编码与解码方式,并且我们可以用乱数方式改变参数值,获得变异的效果。在GV模型中,除了功能分类很重要外,另一个重点是要如何制定演变终止条件。这个条件建议可视系统的可用资源来弹性调整,或依其CPU的处理能力来当参考值,或者使用防毒软件的病毒特征码去判断,直

48、到演变出有一定数量不会被病毒特征码认出的新病毒为止。病毒演变过程如图4所示。,病毒演变过程,34新病毒的复杂度,34新病毒的复杂度GV除了在创造下一代时,会做演变产生改变外,本身也可在一定时间内触发演变,使病毒的特征码会随时间而改变,以图4为例,在时间t与t+1的病毒特征码就不相同。其中,C01与E01分别为C01与E01的变异代号。在GV模型里,只要提供新元件,就有机会创造出数倍的病毒数量,累积演变出的病毒数也会呈指数倍数方式成长。对于过去已经产生出的约六万只病毒,若能建立起病毒体信息库,则可取出大量的病毒元件。假设我们从这六万只病毒中,每只仅提取两个元件来使用,则可以产生使得病毒总变化量高

49、达260000种可能（这还尚未包含自行变异产生的部分）,这个数量的确是相当惊人,让人不能低估GV的发展潜力。,3.5 新病毒产生的冲击,防毒方法（1）扫描对比法若使用病毒特征码来对比病毒,将无法有效地找出所有GV演变出来的病毒。以图4为例,时间t和t+1的病毒特征经演变后已经不同,难以对比,并且GV可能演变出来的病毒数目过多,将很难对GV所有可能演变出来的病毒或变异种类做对比判断。虽然少部分病毒,有可能因演变不全而保有太多原病毒的特征而被对比法找出来,但这不影响整体族群,因为这部分病毒本来就在GV模型下的淘汰名单中。（2）加总查核法对于会自我检查的档案,最好的方式是不去更动档案,透过类似伴随型

50、病毒的感染方式去感染,以避免使加总查核值被改变。GV模型主要在提供更多的生存机会,而非解决自我检查档案的方法。除非,刚好演变出某种病毒,其感染后恰巧与原始档案的加总查核结果相同,但这种的机率很低。（3）行为模式侦测法从图4中可以看出,在时间t与t+1,病毒的行为能力与行为规则都不尽相同,无法保证一定能以某一特定的行为模式来掌握病毒。由另一方面来看,GV最主要的特点就是可以组合并创造出多种新行为,用以躲避行为模式侦测法,这正是GV比一般传统病毒具有优势的地方。（4）虚拟机器模拟法此方法主要是针对多形病毒而设计的,对于GV模型病毒并没有什么影响,即使再经由假执行解密,因GV经演变后已改变实体,所以