遗传算法原理

nullnull遗传算法null报告提纲一、遗传算法概述 二、遗传算法原理 三、遗传算法的应用一、遗传算法概述一、遗传算法概述1、智能优化算法 2、基本遗传算法 3、遗传算法的特点 1、智能优化算法 1、智能优化算法 智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。 常用的智能优化算法 常用的智能优化算法 （1）遗传算法 （Genetic Algorithm， 简称GA） （2）模拟退火算法 （Simulated Annealing， 简称SA） （3）禁忌搜索算法 （Tabu Search， 简称TS） ……智能优化算法的特点智能优化算法的特点 它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 空间，因而具有全局优化性能。返回遗传算法起源 遗传算法起源 遗传算法是由美国的J. Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法 。 遗传算法的搜索机制 遗传算法的搜索机制 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和突变)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 返回2、基本遗传算法2、基本遗传算法 基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。 基本遗传算法的组成 基本遗传算法的组成 （1）编码（产生初始种群） （2）适应度函数 （3）遗传算子（选择、交叉、突变） （4）运行参数 编码 编码 GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。 函数优化示例 函数优化示例 求下列一元函数的最大值： x∈[-1,2] ，求解结果精确到6位小数。SGA对于本例的编码 SGA对于本例的编码 由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3×106等份。又因为221 < 3×106 < 222 ，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间[-1，2]内对应的实数值转化为一个二进制串（b21b20…b0）。几个术语 几个术语 基因型：1000101110110101000111 表现型：0.637197 编码解码个体（染色体）基因初始种群 初始种群 SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。 适应度函数 适应度函数 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。 选择算子选择算子 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。 轮盘赌选择方法轮盘赌选择方法 轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为： 轮盘赌选择方法的实现步骤轮盘赌选择方法的实现步骤（1） 计算群体中所有个体的适应度函数值（需要解码）； （2） 利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率； （3） 采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。交叉算子 交叉算子 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。 SGA中交叉算子采用单点交叉算子。 单点交叉运算 单点交叉运算 交叉前： 00000|01110000000010000 11100|00000111111000101 交叉后： 00000|00000111111000101 11100|01110000000010000交叉点突变算子 突变算子 所谓突变运算，是指依据突变概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的突变运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和突变运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。 SGA中突变算子采用基本位突变算子。 基本位突变算子 基本位突变算子 基本位突变算子是指对个体编码串随机指定的某一位或某几位基因作突变运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行突变操作的某一基因座上的原有基因值为0，则突变操作将其变为1；反之，若原有基因值为1，则突变操作将其变为0 。 基本位突变算子的执行过程 基本位突变算子的执行过程 突变前： 000001110000000010000 突变后： 000001110001000010000 突变点运行参数 运行参数 （1）M ： 种群规模 （2）T ： 遗传运算的终止进化代数 （3）Pc ： 交叉概率 （4）Pm ： 突变概率 SGA的框图 SGA的框图 返回3、遗传算法的特点 3、遗传算法的特点 （1）群体搜索，易于并行化处理； （2）不是盲目穷举，而是启发式搜索； （3）适应度函数不受连续、可微等条件的约束，适用范围很广。返回二、遗传算法原理二、遗传算法原理1、遗传算法的数学基础 2、遗传算法的收敛性分析 3、遗传算法的改进 返回1、遗传算法的数学基础1、遗传算法的数学基础（1）模式定理 （2）积木块假设 返回模式模式 模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即 0 或者 1。 模式示例：10**1两个定义两个定义定义1：模式 H 中确定位置的个数称为模式 H 的阶，记作O(H)。例如O(10**1)=3 。 定义2：模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式 H 的定义距，记作δ(H)。例如δ(10**1)=4 。 模式的阶和定义距的含义模式的阶和定义距的含义 模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。 模式定理模式定理 模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。 模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。 模式定理模式定理 从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。 返回积木块假设 积木块假设 积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。 模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。 返回2、遗传算法的收敛性分析2、遗传算法的收敛性分析 遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和突变概率。 种群规模对收敛性的影响种群规模对收敛性的影响 通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。选择操作对收敛性的影响选择操作对收敛性的影响 选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和突变操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。交叉概率对收敛性的影响交叉概率对收敛性的影响 交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。 突变概率对收敛性的影响突变概率对收敛性的影响 突变操作是对种群模式的扰动，有利于增加种群的多样性 。但是，突变概率太小则很难产生新模式，突变概率太大则会使遗传算法成为随机搜索算法。 遗传算法的本质 遗传算法的本质 遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用突变算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。 返回3、遗传算法的改进3、遗传算法的改进 遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。 遗传算法的改进途径遗传算法的改进途径（1）对编码方式的改进 （2）对遗传算子 的改进 （3）对控制参数的改进 （4）对执行策略的改进 对编码方式的改进对编码方式的改进 二进制编码优点在于编码、解码操作简单，交叉、突变等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题 ，浮点数编码改善了遗传算法的计算复杂性 。 对遗传算子 的改进对遗传算子 的改进排序选择 均匀交叉 逆序突变（1） 对群体中的所有个体按其适应度大小进行降序排序； （2） 根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体； （3） 以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。 对遗传算子 的改进对遗传算子 的改进排序选择 均匀交叉 逆序突变（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个基因。 对遗传算子 的改进对遗传算子 的改进排序选择 均匀交叉 逆序突变突变前： 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 = 0.4-0.9， Pm = 0.001-0.01。 对控制参数的改进对控制参数的改进 Srinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和Pm，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和Pm，使性能较差的个体被淘汰 。对执行策略的改进对执行策略的改进混合遗传算法 免疫遗传算法 小生境遗传算法 单亲遗传算法 并行遗传算法返回三、遗传算法的应用三、遗传算法的应用1、遗传算法的应用领域 2、遗传算法的应用示例 3、我的研究1、遗传算法的应用领域1、遗传算法的应用领域（1）组合优化 （2）函数优化 （3）智能控制 （4）图像处理 （5）机器学习 （6）人工生命 返回遗传算法应用于组合优化遗传算法应用于组合优化组合优化是指在给定约束条件下,求解目标函数的最优值。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能求出其最优解。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有NP难度的组合优化问题上取得了成功的应用。 如旅行商问题，我们给定一组n个城市和他们两两之间的直达距离，通过遗传算法我们可以寻找一条闭合的旅程，使得每个城市刚好经过一次且总的履行距离最短。再如车间作业调度问题，车间作业是指利用车间资源对某一对象进行生产的过程，作业调度实际上就是对车间作业进行有效排序，使某个目标函数最小。比方一台机床有多个工具，加工多种工件，各工件有确定的加工期限约束，需要制定一个月的加工 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 保证完成所有的加工任务。由于JSP具有离散、动态、多变量耦合等属性，应用遗传算法具有一定难度，主要体现在遗传编码方法上。返回函数优化函数优化工程上经常会遇到在多准则或多设计目标下设计和决策的问题，如果这些目标是相背的，需要找到满足这些目标的最佳设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。通常的做法是根据某有效函数将多目标合成单一目标来进行优化。但大多数情况下，在优化之前这种效用函数是难以确切知道的。法国经济学V.Pareto(1848-1923)最早研究经济领域内的多目标优化问题，他的理论称为Pareto最优化理论。J.Horn和N.Nafpliotis提出了关于用遗传算法解决多目标问题的基本算法思想，遗传算法界称为NPGA。返回智能控制智能控制许多控制领域问题，当考虑到系统优化、自适应、自组织和自学习等方面的要求时，一般存在许多常规方法难以凑效的困难。例如，当有非连续评价函数、缺少初始信息、模型参数和结构或控制过程中的随机性、不确定性等复杂因素出现时，现有的控制理论和方法往往因需要求导信息、对初始条件的敏感性、对高品质的领域知识依赖性而难以得到很好的应用。1971年K.S.Fu从研究自学习控制系统入手，将智能控制概括为自动控制与人工智能的交集；1977年，Saridis以智能机器人的控制为主要研究背景，从研究机器智能的角度提出了智能控制是自动控制、人工智能及运筹学的交集，并提出了分级递阶智能控制的结构和方法；Astrom提出的专家智能则是将专家对被控对象和控制过程的知识、经验等融入控制器的设计与控制决策中。早期的智能控制研究受到传统控制理论的影响，大部分着眼点仍然基于系统已有的先验知识来解决问题，而不是自动获取知识。模糊控制基于模糊集理论，模拟人的近似推理和决策过程。1974年Mamdani成功地将它应用于高炉和蒸汽机的控智能控制智能控制制，随后获得了迅猛的发展。模糊控制的主要困难在于控制规则的获取以及控制系统的稳定性问题。20世纪80年代中期以来，神经网络得到重新重视和发展。它主要模拟人脑的形象思维以及学习获取知识的能力。神经网络应用于控制问题，由于其高度依赖于生产现场所提供的大量训练样本，且训练算法的可实现性、实时性要求等因素，影响了其实用性。此外，对复杂问题的神经网络结构最优设计一直缺乏有效的方法。90年代以来，模糊理论、神经网络、专家系统、遗传算法和混沌方法等在许多控制领域得到了应用和发展，并且更重视这些方法相互融合，形成所谓的混合软计算。 遗传算法借助搜索机制的随机性，能够搜索问题域的全局最优解，并且对噪声和变化表现出很好的鲁棒性和自适应能力。遗传算法在控制领域的应用大致分为两大类：一类是离线设计和分析；另一类是在线自适应性调整。前者遗传算法作为优化器，对于已知的控制对象寻求合适的控制规则以满足控制品质方面的要求，或者对于特定的控制器结构搜索最优参数。后者遗传算法作为一种学习机制来确定未知的或非稳定系统的特征，或者对控制器进行自适应性调整。返回图像处理图像处理图像处理和模式识别是计算机视觉中的一个重要领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会产生一些误差，这些误差会影响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在图像处理中的优化计算方面是完全可以胜任的，目前已在图像校准、图像分割、几何形状识别、图像压缩、三维重建优化以及图像检索等方面得到了应用。返回机器学习机器学习机器学习以复杂系统为对象，研究机器如何获取新知识或改善已有知识的问题，属于人工智能研究中较年轻的分支。由于20世纪40年代计算机的产生，使机器学习的实现有了可能，并且在50年代中期到60年代中期成了机器学习的热烈时期，这一时期主要研究各类自适应系统，并已开始研究神经网络模型和人工进化系统。60年代中期到70年代中期转入低潮，主要研究侧重于基于概念的学习和基于归纳的学习；70年代中期到80年代中期又得到了迅速地发展，特别是专家系统的成功应用。不同的学习策略和各种学习方法相继问世，示例归约学习成为研究主流，如出现了影响很大的示例学习方法:ID系列和AQ系列。此外，自动知识获取成为机器学习的应用研究目标，遗传算法应用于机器学习的思想已经被提出。最近10多年机器学习的研究和发展又进入了一个暂新时期。1986年，神经网络重新兴起，基于连接机制的学习开始向传统的符号学习挑战。神经网络将知识的表达蕴涵于网络连接中，处理隐层和反向传播算法的发展，显示出很强的学习能力，因而，广泛应用于模式识别、自动控制、信号处理、语音识别等许多领域。随着各种改进型学习算法不断地被提出，显著地改善了机器学习系统的性能。而此前的符号学习试图将知识由一个知识库包含和解释，其学习能力非常局限，只能适用于知识表达相对简单的系统。机器学习机器学习迄今，自然界只有人类才真正具有完善的学习能力，机器学习系统实际上是对人的学习机制的一种抽象和模拟，是一种理想的学习模型。基于符号学习和学习系统如监督型学习系统、条件反射型学习系统、类比式学习系统、推理学习系统等，只具备一些较初级的学习能力。近年来，由于遗传算法的发展，基于进化机制的遗传学习成为一种新机器学习方法，它将知识表达为另一种符号形式-----遗传基因，通过模拟生物的进化过程，实现专门领域知识的合理增长型学习，所以有的学者将之称为次符号学习方法。机器学习成为遗传算法的经典领域之一，归功于密歇根大学Holland等早期的工作。他们将基于遗传的机器学习方法发展成为CSI的分类系统学习方法，奠定了遗传算法重要的思想基础，后来被归纳为“密歇根方法”。1991年，De Jong等提出了“匹茨堡方法”。1994年，日本名古屋大学的市桥等结合两种方法的优点提出了“名古屋方法”，这些方法都分别在复杂机器学习系统获得了成功的应用。此外，遗传程序设计方法应用于机器发现系统的研究及结合不同学习方法交互作用的混合学习方法也开始受到重视。返回人工生命人工生命生物的多种特性与功能已经给科学研究者很多启示，人工神经网络可以说是受到人的神经元的启发，而遗传算法、进化计算更是根据生物的遗传、进化机制演变而成的。近年来，一些学者对人工生成具有生命特征的产物进行了多方面的研究。在早期，冯.诺依曼根据许多小单元均只与附近小单元相互作用的原则构造了元胞自动机，这种自动机可以“自繁殖”。他又指出计算机程序可以在内存中进行自复制。现在出现的各种计算机病毒，它们在一定的条件下可以自繁殖，甚至“进化”。各种电子宠物如“电子鸡”、“电子鱼”等具有类似生物的特性，例如需要按时进食，对环境可以趋利避害，有发育、生长、会生病、死亡等生物特征。这些“人工生命”可以看成一种具有生命特性的信息系统，相当一部分的人工生命是在计算机上实现的。可以认为自然界产生的生物是以核酸分子作为信息载体的，而生命的特征是由生物体中的信息系统决定的，如果把表征生命特性的信息系统在其它媒体上实现，同样也会产生相应的特征。这就是人工生命的内涵。返回2、遗传算法的应用示例2、遗传算法的应用示例 弹药装载问题（Ammunition Loading Problem，简称ALP），就是在满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率达到最大值的问题。AGSAA的基本原理AGSAA的基本原理 在弹药装载中，考虑到模拟退火算法的基本思想是跳出局部最优解，将模拟退火思想引入遗传算法，应用改进型遗传算法和模拟退火算法相结合，构建自适应遗传模拟退火算法（AGSAA），从而综合了全局优化和局部搜索的特点，为解决弹药装载这一组合优化问题提供了新的思路。AGSAA的编码方式AGSAA的编码方式 AGSAA采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为１，表示该弹药箱装入运输工具，为０则不装。AGSAA的解码和适应度函数AGSAA的解码和适应度函数 AGSAA采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计算适应度函数值。弹药装载的启发式算法弹药装载的启发式算法 　　（1）定位规则（Locating rule） 　　 定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。 　　 （2）定序规则（Ordering rule） 定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。遗传算子的选择遗传算子的选择　　　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 | 6 2 | 8 3 4 5返回关于遗传算法应用方面我的研究关于遗传算法应用方面我的研究1、基于遗传算法的提高排课满意度的研究（计算机应用研究 中国计算机学会会刊 2007年增刊 电脑知识与技术.学术交流 2007/09） 2、基于遗传算法的虚拟物体的变形研究(计算机应用与软件 中国计算机学会会刊 录用待发) 3、计算机遗传病毒染毒机理分析(计算机应用与软件 中国计算机学会会刊 2008/08) 4、倒立摆的混合控制（审稿阶段） 5、基于GA和滑模控制的功率控制器的设计与仿真（审稿阶段） 6、基于遗传算法的智能化动态分组的研究（2008年山西省教育厅研究课题）返回基于遗传算法的提高排课满意度的研究 染色体结构基于遗传算法的提高排课满意度的研究 染色体结构染色体结构如右图上所示。该染色体含有m个基因，m的个数即是参与授课教师的总人数，每一个基因代表每位教师的课表，每一染色体即表示一种可能的排课结果。每位教师课表可用一维字符阵列表示。如右图下所示。例如：某一教师星期2第3大节要配置“微机原理”课程，字符阵列即可表示为：demo(23)=”微机原理” 结合所有的染色体及所有的教师人数和上述的一维字符阵列，可成为一个三维阵列，即（染色体编号、教师编号、教师课表）。例如：第５染色体的第８位教师，于星期二第３大节课要配置“微机原理”课程，字符阵列可表示为demo(5,8,23)=”微机原理” 以教师的课表为基因单位，两染色体经交叉操作后基因互换，不会影响到每位教师所教授的课程，也不会造成教师课表内含有其他教师的教授课程，不会出现每代演化后课表染色体结构不合理的问题。基于遗传算法的提高排课满意度的研究 适应性函数基于遗传算法的提高排课满意度的研究 适应性函数适应性函数是计算出每条染色体的适应值。在本研究中，染色体若其适应值较大者，表示该排课结果拥有较多较佳授课时段，将会被给予较大的生存概率于下一代演化中。 首先建立每位教师的授课时段优先度，如表1所示，可由教师填入自己较喜欢的时段及其喜好程度，该表格将提供做适应性使用，其中3代表最喜欢的授课时段，2代表较喜欢的授课时段，1代表喜欢的授课时段，空白代表可以接受的授课时段，-1代表不喜欢的授课时段。在演化过程中，应尽量避免-1所代表的时段，以避免教师不愿授课。 将染色体中每个基因（教师课表）与教师时段喜好表比较，取相对应位置的值相加，如此累计计算出整条染色体的值。染色体函数计算所得的适应值也越大。基于遗传算法的提高排课满意度的研究 选择基于遗传算法的提高排课满意度的研究 选择选择就是将较大适应值的染色体复制到交叉池中。本文采用随机竞争法，即由上一代随机选取两条染色体来竞争，适应值较大的即可生存下来。此方法的优点是不影响竞争概率。 基于遗传算法的提高排课满意度的研究 交叉基于遗传算法的提高排课满意度的研究 交叉交叉是以每位教师课程表为基因单位，进行随机交换。方法是随机自交叉池里选取一对染色体作为进行交叉的双亲，并再取一乱数值（设为r），与系统预设的交叉率值（设为t）比较，若r 架构 酒店人事架构图下载公司架构图下载企业应用架构模式pdf监理组织架构图免费下载银行管理与it架构pdf ,其中,GV核心负责执行遗传算法,而各类别集合相同类型功能的程式码。分类的方法是,若不先将病毒的特征码依照功能分类,而直接用乱数将特征码进行替换或交叉,则创造出来的病毒,可能会产生特征逻辑有误或无法执行的问题,就如同将眼睛器官移植到鼻子上去,将导致无法生存。换句话说,毫无章法地任意取样乱配,会导致演变工程产生许多“畸形”病毒。简言之,分类的主要目的是要让GV在同一类的不同病毒元件中,选取可以替换或交叉到满足该类功能需求的特征。GV模型里的初始化工作,是要替病毒做染色体取样,并决定基因大小,以做为遗传基因操作的元素。在基因内的参数值,我们要找出相对应的编码与解码方式,并且我们可以用乱数方式改变参数值,获得变异的效果。 在GV模型中,除了功能分类很重要外,另一个重点是要如何制定演变终止条件。这个条件建议可视系统的可用资源来弹性调整,或依其CPU的处理能力来当参考值,或者使用防毒软件的病毒特征码去判断,直到演变出有一定数量不会被病毒特征码认出的新病毒为止。病毒演变过程如图4所示。病毒演变过程病毒演变过程3．4新病毒的复杂度3．4新病毒的复杂度3．4新病毒的复杂度 GV除了在创造下一代时,会做演变产生改变外,本身也可在一定时间内触发演变,使病毒的特征码会随时间而改变,以图4为例,在时间t与t+1的病毒特征码就不相同。其中,C’01与E’01分别为C01与E01的变异代号。在GV模型里,只要提供新元件,就有机会创造出数倍的病毒数量,累积演变出的病毒数也会呈指数倍数方式成长。 对于过去已经产生出的约六万只病毒,若能建立起病毒体信息库,则可取出大量的病毒元件。假设我们从这六万只病毒中,每只仅提取两个元件来使用,则可以产生使得病毒总变化量高达260000种可能（这还尚未包含自行变异产生的部分）,这个数量的确是相当惊人,让人不能低估GV的发展潜力。3.5 新病毒产生的冲击3.5 新病毒产生的冲击3.5.1防毒方法 （1）扫描对比法 若使用病毒特征码来对比病毒,将无法有效地找出所有GV演变出来的病毒。以图4为例,时间t和t+1的病毒特征经演变后已经不同,难以对比,并且GV可能演变出来的病毒数目过多,将很难对GV所有可能演变出来的病毒或变异种类做对比判断。虽然少部分病毒,有可能因演变不全而保有太多原病毒的特征而被对比法找出来,但这不影响整体族群,因为这部分病毒本来就在GV模型下的淘汰名单中。 （2）加总查核法 对于会自我检查的档案,最好的方式是不去更动档案,透过类似伴随型病毒的感染方式去感染,以避免使加总查核值被改变。GV模型主要在提供更多的生存机会,而非解决自我检查档案的方法。除非,刚好演变出某种病毒,其感染后恰巧与原始档案的加总查核结果相同,但这种的机率很低。 （3）行为模式侦测法 从图4中可以看出,在时间t与t+1,病毒的行为能力与行为规则都不尽相同,无法保证一定能以某一特定的行为模式来掌握病毒。由另一方面来看,GV最主要的特点就是可以组合并创造出多种新行为,用以躲避行为模式侦测法,这正是GV比一般传统病毒具有优势的地方。 （4）虚拟机器模拟法 此方法主要是针对多形病毒而设计的,对于GV模型病毒并没有什么影响,即使再经由假执行解密,因GV经演变后已改变实体,所以很难辨识出来其是否为病毒,故此方法对GV模型病毒并不会造成威胁。3.5.2解毒方法3.5.2解毒方法要写出某一只已知病毒的解毒方法并非难事,但要写出GV病毒的解毒方法,可能不是那么容易。主要原因是,在图4中,针对时间t写出来解毒方法,在时间t+1已不适用,也不可能针对所有GV可能的变化,甚至包含变异的可能变化,都能够制作出解毒方法来。这也就是在自然界中,由于生物病毒的不断演变,医药界仍然找不到,可以解决各种病菌的唯一疫苗的道理。返回