（电力系统及其自动化专业论文）变电运行软仿真培训系统研究.pdf

a b s t r a c t a b s t r a c t p e r s o nw h ow o r ko nt h ed e p a r t m e n to fs u b s t a t i o no p e r a t i o nm a n a g e m e n ta r e l a c ko ft r a i n i n ga n ds i m u l a t i n go p e r a t et o w a r d st h es t a t i o ne q u i p m e n t s t h u si th a s g r e a tf u n c t i o nt om a k eu s eo f t h el o c a t i n gt r a i n i n gs y s t e mt os t r e n g t h e nt h et e c h n i q u e l e v e lo f o p e r a t o ra n dr a i s et h es a f em o v e m e n tl e v e lo f t h ee l e c t r i cp o w e rs y s t e m t h e s y s t e mh a sh u g ea d v a n t a g ei ne c o n o m i ca n ds o c i a lp e r f o r m a n c ew h i c hc a nn o tb e s u b s t i t u t e db yo t h e rt r a i n i n g ，t h e r e f o r e ，t h eo p e r a t i o nt r a i n i n gs y s t e mo fs u b s t a t i o n c a nr a i s et h el e v e lo f t h e o r i e sa n do p e m t i o n t h et h e s i sf r o ma i l - k i n d so fa n g l ei n t r o d u c e st h ed e v e l o p m e n tc o u r s eo ft h e t r a n s f o r m i n gs o f to p e r a t i o nt r a i n i n gs y s t e mo fs u b s t a t i o n ，a n dd e v e l o p m e n to ft h e s y s t e m ，a n dt h et h e o r e t i c a lf o u n d a t i o n ，t e c h n o l o g ya n dr e l e v a n tn o r m si n v o l v e di nt h e d e v e l o pc o u r s eo ft h i ss y s t e mw a si n t r o d u c e d t h et h e s i si n t r o d u c e dt h et o t a ld e s i g no fs y s t e mf i r s t ，e l a b o r a t e dt h er e q u i r e m e n t a n a l y s i sa n dt h es t r u c t u r ed e s i g no fs y s t e m ；a n dd i s c u s s e dt h er e a l i z a t i o nf u n c t i o n m o l do ft h es y s t e m ，a n dt h ep r o b l e mt h a tl o we f f i c i e n c yo fp r o g r a mo fp r o g r a mw a s s o l v e da n dd a t a b a s ew e r ed e s c r i b e di nd e t a i l ，a n ds o m ed e v e l o p e di n t e r f a c e so f s y s t e mw e r ep r o v i d e d t h et h e s i sd i s c u s s e dt h ea p p l i c a t i o no ft h eg e n e t i ca l g o r i t h mi na u t ot e s tp a p e r m a k i n gi nd e t a i l t h es y s t e mi sn o tp e r f e c to ri d e a l se n o u g h ，a n di ti sn o ti n t e l l i g e n t ， w h i c hm a k e sd a t ac o l l e c t i o na n dd i s p o s a lb e c o m et i m e - c o n s u m i n ga n dd i f f i c u l t t h e g e n e t i ca l g o r i t h miu s e dm a k e st h er e s u l tt h a tt h ei m p r o v e dm e t h o di sc l o s e dt ot h e t a r g e to fe n a c t m e n tp a r a m e t e rc o m p a r e dt ot h et r a d i t i o ng e n e t i ca l g o r i t h m a tl a s t ，c o m b i n i n gt h et h e o r yo fo b j e c t o r i e n t e dt e c h n o l o g y ，t h ed e v e l o pc o u r s e o f e x a m i n a t i o no ns w i t c h i n go p e r a t i o nw e r ed i s c u s s e di nd e t a i l s t h ep r o d u c t i o no ft h er e s e a r c hh a sb e e na p p l i e dt ol i c h t m ns u b s t a t i o no fs t a t e p o w e rc o m p a n yi nf u z h o uj i a n g x in o w ，a n dt h es y s t e mh a sp a s s e dt h ea c c e p t a n c eo f s c i e n c ea n dt e c h n o l o g yh a l lo f p r o v i n c e2 0 0 7a n dm a d eas a t i s f i e da c h i e v e m e n t k e y w o r d s ：s u b s t a t i o no p e r a t i o nm a n a g e m e n t u n i f i e dm o d e ll a n g u a g e ；g e n e t i c a l g o r i t h m ；s w i t c h i n go p e r a t i o nt i c k e t i i 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导, ；i t i t h 导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：户耗琴 签字日期：砌年f 2 月乃日 学位论文版权使用授权书 本学位论文作者完全了解南昌大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权南昌大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：户艳琴 签字日期：堋年1 2 月2 3 日 导师签名：枸研4 艮 签字日期：堋年f 王月1 3h 第1 章绪论 第1 章绪论 1 1 选题背景及其意义 变电站是电力系统的重要组成部分，变电站的安全可靠运行对维持电力系 统的稳定运行和保证供电的可靠性具有十分重要的意义【1 】。随着计算机技术、现 代电子技术、通信技术和信号处理技术等先进技术在电力系统的应用，变电站 正朝着集保护、测量、控制和遥测、遥控、遥信、遥调于一体的综合自动化方 向发展，大大提高了电网的安全运行与管理水平。 由于变电站值班人员的技术、素质直接影响是否能减少事故发生和减轻事 故造成的影响，因此加强对他们的技术培训是极其必要的，为员工在运行值班、 倒闸操作、事故处理等方面提供技术支撑，建立一个能模拟实际变电站运行， 便于运行人员掌握现场实际情况的变电运行软仿真教学培训系统迫在眉睫。变 电运行软仿真教学培训系统能创造与实际变电站相符的环境，对变电站值班人 员进行运行值班、倒闸操作、事故处理等方面提供培训。在一线的变电运行人 员，虽然经常接触和了解运行设备，但是实际经常操作的机会并不多，缺乏经 常性的并且有针对本站设备的培训和模拟操作，因此，把大量的安规、运规知 识，现场模拟操作形成数据库，由运行人员经常性自我测试，数据库内容可随 机出现并进行判读，有利于运行人员，特别是文化程度较低的运行人员的现场 培训。 实验证明，利用现场培训系统对增强运行人员的运行技术素质，提高电力 系统安全运行水平起到了很好的作用，具有其它培训方式所不可能替代的独特 优点，其经济效益和社会效益是巨大的。因此，开发有针对变电站设备运行的 培训和模拟操作，可以提高运行人员的理论知识和实际操作水平。 本课题是2 0 0 6 年江西省电力局立项课题，该软件现运用于抚州运行公司， 使用情况良好。 本系统针对变电站的现场要求对专业知识进行合理分类，使变电站运行人 员可以有针对性地进行专项学习和训练，在短时间内熟悉一次、二次设备原理， 了解系统规章制度，该系统操作简便，学习形式多样化，趣味性强，有益于提 高阅读效率，达到较好的培训效果。 第1 章绪论 1 2 变电运行软仿真培训系统发展现状 1 2 1 国外变电运行软仿真培训系统应用现状 国内外电力系统的培训仿真从7 0 年代开始发展，开始主要集中在火电厂机 组，之后相继扩展到电网、变电站的仿真培训。国外7 0 年代就出现了实用的火 电仿真系统( 1 9 7 1 年美国、日本和英国分别安装了第一套大容量的火电培训仿 真机) ，电网仿真系统( 1 9 7 7 年美国c d c 公司开发出第一套调度员培训仿真系 统d t s ( d i s p a t c h e rt r a i n i n gs i m u l a t o r ) 装置) 和变电站的仿真系统( 7 0 年代日本 关西电力公司建立了变电站仿真系统) 2 1 1 3 1 1 4 1 1 5 6 1 。从现有资料看，电力系统调度、 火电厂人员培训，原子能电站设备培训仿真系统应用较多，但由于国外电网调 度员都直接用s c a d a 系统进行遥控、遥调操作，有关变电运行仿真系统的开发 和使用报导少之又少。 1 2 2 国内变电运行软仿真培训系统应用现状 我国于1 9 8 2 年研制成功了第一套火电仿真机组，期间电网调度仿真机和 变电站仿真机也在开发，并从8 0 年代末期开始陆续建立了电网和变电站的仿真 培训系统，1 9 9 0 年研制出了第一台d t s - - 东北电网仿真系统，到1 9 9 9 年，大 多数的网调、省调都使用了电网调度仿真器材【7 1 。由于早期电力容量不大，电力 系统中变电站的数目又多，自动化水平较低，其运行操作的要求不高，使得变 电站软仿真培训系统的作用没有得到充分的体现。但随着电力系统的发展，一 些采用先进自动化技术的高电压、大容量变电站的投运，对运行人员提出了比 较高的要求，因此5 0 0 k v 、2 2 0 k v 的变电站仿真培训系统相继建成，并取得了良 好的效果。目前我国国内从事变电站仿真的公司、科研机构和高校不少，并且 其开发研制的系统各有特点，在以下的论文中有体现： 文献【8 】介绍了大港油田变电站仿真培训系统，该系统包括模拟控制盘、模 拟继电器保护盘、配电装置、主接线模拟操作盘和计算机控制仿真系统几部分。 文献 9 】介绍了南昌5 0 0 k v 站的仿真培训系统，该系统只有计算机硬件、仿 真软件和网络组成。其计算机技术、网络技术和多媒体技术的发展和基于微机 平台和基于网络的变电站仿真系统使得学员的所有操作都能在计算机屏幕上完 成。 文献 1 0 】介绍了深圳供电局仿真培训系统，该系统仿真的对象包括深圳供电 2 第1 章绪论 局1l o k v 及以上的电网和主要厂站，模拟了5 0 0 k v 和2 2 0 k v 两个典型的虚拟变 电站，所有的一、二次设备均在计算机屏幕上显示，用鼠标对设备操作，一次 设备的巡视采用多媒体技术完成。该系统将电网仿真和变电站仿真结为一体。 文献 1 1 1 介绍了成都l l o k v 无人值班变电站及控制中心仿真培训系统。该系 统主要针对1 l o k v 集控站进行仿真培训，收集了有代表性的8 种变电站。系统 主要由仿真机、教练员台、学员台、开发工作站和物理模拟操作间组成，通过 以太网和i o 设备相联。学员可以与教练台和物理模拟变电站通信。 文献【1 2 1 介绍了川渝5 0 0 k v 变电站和电网仿真系统。该系统以5 0 0 k v 变电 站为全仿真对象，同时对川渝5 0 0 k v 电网进行了原理性仿真。该系统实现了仿 真的全软件化，即所有的显示和操作都在计算机屏幕上完成，并采用了实际的 系统结线、设备参数、调度系统监控画面及各种控制和保护的定值。 文献1 3 1 介绍了华中地区5 0 0 k v 变电站仿真系统，该系统采用了微机交互式 分时网络软硬件结合的体系结构，研制了建立在i 蘑n i ) ( 环境下的多用户仿真支 撑系统，仿真软硬相结合，控制盘和保护屏与现场一样，主控室设备的操作在 屏幕上进行。该系统实现了对微机继电保护装置、事件记录和微机录波装置及 静补装置及其调节系统的仿真。 文献 1 4 1 介绍了一种带盘台模式的仿真系统，并部分采用了软表盘、仿真系 统软件主要由计算机操作系统、支持软件、模型软件、诊断软件、就地操作软 件、虚拟盘台软件、动态二次系统软件、教练员台软件等组成。 文献 1 5 1 介绍了郑州工业大学开发的变电站仿真培训专家系统。该系统利用 多媒体技术实现了变电站电气主接线模拟盘及保护屏的全软仿真，主要由变电 站操作票仿真培训系统和变电站事故仿真培训系统组成。 文献 1 6 1 介绍了黑龙江5 0 0 k v 变电站仿真培训系统，该系统采用了带盘台模 式，具有监视、巡视、操作、故障现象和处理功能，保护由定值启动，并对微 机保护的液晶输出进行了仿真。 文献 1 7 1 介绍的变电站仿真培训装置也带有盘台，软件主要由计算机系统软 件、仿真支撑软件、仿真模型软件及算法库、工程师站软件、教练员站软件、 就地操作站软件和变电站监控系统仿真软件组成，采用多媒体技术实现户外设 备的巡视和就地操作。 3 第1 章绪论 1 3 课题来源 本课题是2 0 0 6 年江西省电力局的立项项目，是与江西抚州供电公司变电运 行分公司的合作项目，主要目标是开发出一套软件，使它能够将安规、运规等 有关变电运行方面的理论知识和与实际相关的操作形成数据库，随机形成试题 卷，并且要求在一定的时间内完成测试。其中，模拟操作在一次模拟图通过对 开关、刀闸的点合、点分，完成模拟操作，对模拟事故也可以进行模拟操作。 抚州供电公司变电运行分公司i g i ) l l 变电站位于i g s ) i i 区临川大道南路，离市区约 六公里处，占地2 3 9 8 8 6 平方米。于1 9 8 6 年6 月开始入建和设备安装调试；1 9 8 8 年1 2 月7 日正式投入运行。临川变是本地区有人值班的2 2 0 k v 枢纽变电站。 变电运行软仿真培训软件有好高的经济效益和社会效益，主要的经济指标 是每年可节省每人的培训费用2 0 0 0 元，社会效益的分析主要是为该培训系统可 以增强变电人员的运行技术素质，适应新技术的发展，提高电力系统安全运行 水平，真正实现无指化。 1 4 本文的主要工作及结构安排 1 4 1 本文主要研究的工作 本文针对抚州变电公司提出的要求，进行分析研究，并利用变电公司现有 的局域网，开发一套基于c s 运行模式的变电运行软仿真培训系统。主要工作 如下： ( 1 ) 采用u m l 建模技术，实现本系统的需求分析和系统分析设计。 ( 2 ) 完成数据库设计和软件编程。 ( 3 ) 遗传算法进行自动组卷。 ( 4 ) 采用面对对象技术完成操作票考试的初始化。 1 4 2 本文结构安排 第一章是绪论部分，主要介绍了变电运行软仿真系统的发展概况，分析了 现有系统的特点，提出了本文的研究重点和方向。 第二章介绍了系统开发过程中所涉及的理论基础，技术。 第三章是本系统的总体设计部分，通过江西抚州供电公司的要求，提出了 总体构思，并介绍了项目的需求分析。 4 第1 章绪论 第四章系统实现和功能模块。 第五、六章是本文的重点，也是作者开展的主要研究工作，作者首先介绍 了基于遗传算法来进行自动组卷，最后介绍了倒闸操作票生成的实现过程。 第七章为结束语，其中包括了对本工作的总结及对今后进一步工作提出的 展望。 5 第2 章理论与技术简述 第2 章理论与技术简述 2 1 u m l 介绍嫡m 。 统一建模语言( u m l ) 是一个通用的可视化建模语言，用于对软件进行描 述、可视化处理，并构造和建立软件系统制品的文档。它记录了对必须构造的 系统的决定和理解，用于对系统的理解、设计、配置、维护和信息控制。 u m l 描述了一个系统的静态结构和动态行为。静态结构定义了系统中的重 要对象的属性和操作以及这些对象之间的相互关系。动态行为定义了对象的时 间特性和对象，为完成目标而相互进行通信的机制。从不同但相互联系的角度 对形态建立的模型可用于不同的目的。 u m l 是个非常庞大的系统，它几乎无所不能，在项目需求中，主要用到用 例视图、交互视图；项目分析中主要用到动态行为模型和静态视图。 2 1 1 用例视图 用例视图是被称作参与者的外部用户所能观察倒的系统功能的模型图。用 例是系统中的一个功能单元，可以被描述为参与者与系统之间的一次交互作用。 用例视图的用途是列出系统单元中的用例和参与者，并显示了哪个参与者参与 了哪个用例的执行。 ( 1 ) 用例 用例是外部可见的一个系统功能单元，这些功能由系统单元提供，并通过 一系列系统单元和一个或多个参与者之间交换的消息所表达。一个用例描述了 系统的一个完整的功能需求：一个用例包含系统与参与者的交互；用例可以有 变体，组织用例时可以分解出其中公共、可复用的行为；一个用例要完成一些 确定的工作；用例可以应用于整个系统，也可以应用于系统的一部分。 ( 2 ) 参与者 参与者是与系统、子系统或类发生相互作用的外部用户、进程或其他系统 的理性化概念。参与者的特征是作为外部用户与系统发生交互作用。在系统的 实际运作中，一个实际用户可能对应系统的多个参与者，不同的用户也可以只 对应于一个参与者，从而代表同一参与者的不同实例。参与者可以是人、另一 6 第2 章理论与技术简述 个计算机系统或一些可运行的进程。 ( 3 ) 用例图描述 用例图描述的一般格式是： 用例名称 简要说明：简要描述该用例所要的目的 前置条件：执行该用例前必须满足的条件 后置条件：执行完该用例后要满足的条件 主事件流：参与者与系统之间的一次成功的交互过程，不包含异常情况 可选事件流：系统处理该用例时不同的可选方式或异常 错误流：表示系统本身的问题( 不是必须的) 相关用例：与该用例相关的其他用例 2 1 2 动态行为模型 动态行为模型描述对象之间的互相作用。互相作用是指通过一组协同的对 象、对象之间消息的有序的序列、参与对象的可见性定义等来定义系统运行时 的行为。系统的动态行为模型由活动图、状态图、交互图表示。在本文中此部 分内容将简单叙述。 ( 1 ) 活动图 活动图是一种特殊形式的状态机，用于对计算机流程和工作流程建模。活 动图包含活动状态。活动状态表示过程中命令的执行或工作流程中活动的进行。 与等待某一个事件发生的一般等待状态不同，活动状态等待计算处理工作的完 成。当活动完成时，执行流程转入到活动图中的下一个活动状态。当一个活动 的前导活动完成时，活动图中的完成转换被激发。活动状态通常没有明确表示 出引导活动转换的事件，当转换出现闭包循环时，活动状态会异常终止。 活动图显示了一组活动，从活动到活动的顺序或分支的流，以及发生动作 的对象或动作所施加的对象。活动图强调对象之间的控制流。 ( 2 ) 状态图 状态图通过对一个对象的可能生命历史进行建模，描述了对象在事件序列 上的动态行为。每个对象被认为是通过检测事件并对之响应来与外界进行通讯 的孤立实体。事件表达了对象可以检测的变动对象间的调用或显示信号、某个 值的改变或时间的推移。任何影响对象的事物可以被描述成事件。： 7 第2 章理论与技术简述 状态指就某个特定类而言，对于发生的事件具有相同性质响应的一系列对 象值。换言之，同一状态的所有对象以相同的方式响应某个事件，即对于给定 的所有对象在接收到同一事件时执行相同的动作。状态包含由事件连接的状态。 每个状态对对象生命期中的一段时间建模，该时间内对象满足一定的条件。当 事件发生时，它可能导致迁移的激发，使对象改变至新状态。当迁移激发时， 附属于迁移的动作可能被执行。 如果一个类有一些的重要的动态行为，则可以创建状态图。否则没有毕业 创建状态图。 ( 3 ) 交互图 交互图包括顺序图和协作图。顺序图是强调消息的时间次序的交互图，它 主要反映对象之间发送消息的先后次序，说明对象之间的交互过程，以及系统 执行过程中，在某一具体位置将会有什么事件发生；它有对象生命线并有控制 焦点。协作图是强调收发消息的对象的结构组织的交互图，它显示了一组对象、 对象的链以及这组对象收发的消息。顺序图与协作图可以互相转化。 2 1 3 静态结构模型 静态视图结构定义了系统中的重要对象的属性和操作以及这些对象之间的 相互关系。系统的静态结构模型主要由对象类图和对象图来表达。发现对象类， 确定他们静态结构和动态行为，是面对对象分析的最基本的任务。 ( 1 ) 对象类 类代表了被建模的应用领域中的离散概念；是有着相同结构、行为和关系 的一组对象的描述符号。所用的属性与操作都被附在类或其他类元上。类是面 对对象系统组织结构的核心。 ( 2 ) 类与类之问的关系 类与类之间的关系包括关联、依赖性、累积、实现关系和一般化。关联是 指一个类需要使用另外一个类的和操作，是双向的。依赖性关系也是连接两个 类，但是是单向的，一个类向另外一个类发送消息。累积关系是强关联，是整 体和个体的关系。实现关系显示类与接口、包与接口、用例与用例实现之间的 关系。寻找类与类的关系，可以检查前面创建的模型元素。 s 第2 章理论与技术简述 2 2 遗传算法 2 2 1 遗传算法定义及应用 遗传算法【1 8 1 19 】刚口1 l g a ( g e n e t i ea l g o r i t h m ) 是一种新型的、模拟自然界生物 进化过程的随机搜索、优化方法。 遗传算法是一种群体型操作该操作以群体中的所有个体为对象，选择、 交又和变异构成的遗传操作，使遗传算法有了其它传统方法所没有的特征。遗 传算法在计算机自动组卷中作为搜索最优条件算法，由以下基本元素构成： ( 1 ) 染色体编码 遗传算法不能直接处理问题空间的参数，它只能处理以基因链码形式表示 的个体。因而使用遗传算法来求解问题的时候，就必须把问题解的参数形式转 换成的由基因编码按一定结构组成的遗传染色体或个体。这一转换叫做编码， 也称为问题的表示。从生物学的角度来看，编码就相当于选择遗传物质，它是 研究遗传的基础。目前遗传算法的染色体编码方式有：二进制编码、动态编码、 实数编码、自然数编码、有序串编码、可变长编码等。 ( 2 ) 个体适应度评价 在遗传算法中，衡量个体优劣的尺度是适应度。根据适应度的大小来评价 群体中的每个个体对环境的适应能力，决定某些个体是繁殖还是消亡。因此， 适应度是驱动遗传算法不断寻优的动力。从生物学的角度来讲，适应度相当于 “生存竞争，适者生存”的生物生存能力，适应度在遗传过程中有重要意义。 因而，适应度函数的选取至关重要，它的设计直接影响到遗传算法的性能。一 般而言，适应度函数由目标函数变换而成。对目标函数值域的某个映射变换称 为适应度函数的尺度变换，又称为适应度定标( f i t n e s ss c a l i n g ) 。标准遗传算法 采用赌轮选择机制，即按个体适应度来决定当前群体中每个个体遗传到下一个 群体中的概率大小。由于要计算每个个体被复制的概率，所以个体的适应度必 须保证为非负数。 ( 3 ) 遗传操作 在遗传算法中，遗传操作就是对群体中的个体，按照它们对环境适应的程 度施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度来说， 遗传操作可以使问题的解一代又一代地优化，并逐渐逼近最优解。 遗传算法的遗传操作使用三个基本遗传操作算子：选择( s e l e c t i o n ) 、交叉 9 第2 章理论与技术简述 ( c r o s s o v e r ) 和变异( m u t a t i o n ) 。 选择算子 选择算子是为了从群体中按照一定的规律选择染色体。选择染色体的目的 是为了强调群体中适应性强的个体，并希望其后代也能具有较强的适应性。选 择算子选择强度应该适中，选择强度太大将会使局部最优个体在群体中占优势， 从而使群体的多样性减少，是群体陷入局部最优，影响群体进化；反之，选择 算子选择强度太小，将极大地缓解群体的进化过程。常用的选择方法有：适应 度成比例选择、q 选择、伯茨曼选择、次序选择( r a n ks e l e c t i o n ) 、竞争选择 ( t o u r n a m e n ts e l e c t i o n ) 。 交叉算子 遗传算法的主要特点就是使用交叉算子。一方面，它使得在原始群体中的 优良个体的特性能够在一定程度上保持；另一方面，它使得算法能够探索新的 基因空间，从而使新的群体中的个体具有多样性。常用的交叉算子有：单点交 叉、二点交又、多点交叉、均匀交叉等等。 变异算子 变异算子的基本内容是，对群体中的个体串的某些基因位置上的基因值作 变动。遗传算法中使用变异算子使得遗传算法具有局部的随机搜索能力，而且 可以使遗传算法维持群体的多样性。主要的变异算子有：基本变异算子、均匀 变异、正态变异、自适应变异。 一般认为，交叉是遗传算法具有搜索能力的主要算子，位于第一位。而变 异是保证位串中任一位的等位基因不会永久不变，位于第二位 2 2 1 。 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题 的具体领域，对问题的种类具有很强的鲁棒性，所以广泛应用于很多学科 2 3 - 2 6 1 。 下面简要介绍遗传算法的一些主要应用领域： ( 1 ) 函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进 行性能评价的常用算例。很多人构造出了各种各样复杂形式的测试函数，有连 续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确 定函数也有随机函数，有单峰值函数也有多峰值函数等。用这些几何特性各具 特色的函数来评价遗传算法的性能，更能反映算法的本质效果。而对一些非线 性、多模型、多目标的函数优化问题，用其他优化方法很难求解，而遗传算法 却能方便地得到较好的结果。 1 0 第2 章理论与技术简述 ( 2 ) 组合优化。随着问题规模的增大，组合优化问题的搜索空间也急剧增 大，有时在目前的计算机上用枚举法很难甚至不可能求出其精确最优解。对这 类复杂问题，人们已经意识到应把主要精力放在寻求其满意解上，而遗传算法 是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的 j = p 完全问题非常有效。例如，遗传算法已经在求解旅行商问题、背包问题、装箱 问题、图形划分问题等方面得到了成功的应用。 ( 3 ) 生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难 以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使求 解结果与实际相差太远。而目前在现实生产中也主要是依靠一些经验来进行调 度。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、 流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应 用。 ( 4 ) 自动控制。在自动控制领域中有很多与优化相关的问题需要求解，遗 传算法已在其中得到了初步的应用，并显示了良好的效果。例如用遗传算法进 行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的 参数辨识等，都显示出了遗传算法在这些领域中应用的可能性。 ( 5 ) 机器人学。机器人是一类复杂的难以精确建模的人工系统，而遗传算 法的起源就来自对人工自适应系统的研究，所以机器入学理所当然地成为遗传 算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节 机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协 调等方面得到应用和研究。 ( 6 ) 图像处理。图像处理是计算机视觉中的一个重要研究领域。在图像处 理的过程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这 些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用 化的重要要求。遗传算法在这些图像处理的优化计算方面找到了用武之地，目 前已在模式识别、图像恢复，图像边缘特征提取等方面得到了应用。 ( 7 ) 人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具 有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的 两大主要特征。人工生命和遗传算法有着密切的关系，基于遗传算法的进化模 型是研究人工生命现象的重要基础理论。虽然人工生命的研究仍处于启蒙阶段， 但遗传算法已在其进化模型、学习模型、自组织模型等方面显示出了初步的应 第2 章理论与技术简述 用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成， 遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促 进遗传算法的进一步发展。 ( 8 ) 遗传编程。k o z a 发展了遗传编程的概念，他使用了以l i s p 语言所表 示的编码方法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。 虽然遗传编程的理论尚未成熟，应用也有一些限制，但它已成功地应用于人工 智能、机器学习等领域。 ( 9 ) 机器学习。学习能力是高级自适应系统所应具备的能力之一。基于遗 传算法的机器学习，特别是分类系统，在很多领域中都得到了应用。例如，遗 传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好 地改进了模糊系统的性能。 2 2 2 基本遗传算法描述 遗传算法是一种开放式的算法，很容易与其它方法结合形成混合优化方法。 遗传算法的计算步骤也没有固定的模式，可以针对具体问题作适当的调整。以 下是遗传算法的基本步骤【2 7 】： ( 1 ) 确定问题的编码方式和定义适应度函数 根据所求解问题的特点，确定一种将问题的解表示成字符串的编码方式。 遗传算法最基本的编码方式是二进制编码。二进制编码方式将问题的解表示成 二进制位串。二进制编码遗传算法的遗传算子简单，遗传操作方便，但解码较 繁琐，难以在遗传操作过程中处理约束条件，计算精度和计算效率都不高。但 二进制编码遗传算法的理论研究较成熟，实际应用也很多。除二进制编码方式 以外，遗传算法还有实数编码( 又称浮点编码) 、自然数编码( 也称序号编码) 等编码方式。实数编码采取一个参数对应一个基因的编码方式，染色体中的基 因就是参数对应的实数值，无需解码，可方便地在遗传操作过程中处理约束条 件，但其理论研究尚不成熟，遗传算子的作用效率也有待提高：自然数编码方 式以事物序号作为染色体中的基因，在求解有序组合优化问题时比较方便，计 算效率较高。本文提出的计算机自动组卷系统中的搜索算法采用自然数编码， 该编码方案比传统遗传算法能更方便地在遗传操作过程中处理约束条件。 个体的适应度函数_ ，( 卅应能保证任何个体的适应度值都是非负的，且能反 映个体的优劣，或能反映个体对环境的适应能力。本文算法中，- r 【叫选取的是 1 2 第2 章理论与技术简述 各约束条件与目标值的误差值，所以_ ，l 叫越小的个体对环境的适应能力越强， 被选择用来繁殖后代的机会越大。 ( 2 ) 产生初始群体 随机产生n 个个体构成初始群体。n 为群体规模，是遗传算法的一个重要 参数，对算法的计算效率有重要影响。若n 取得太小，每一代处理的染色体数 量不多，搜索效率不高，且易陷入局部最优解；若n 取得太大，每一代的适应度 值计算量太大，计算效率不高。 ( 3 ) 个体评价 计算群体中每一个个体相应的适应度值，。本系统中厂( x ) 越小，表示个 体适应度值越高，对环境的适应能力越强，被选择繁殖后代的机会越大。 ( 4 ) 停机条件的判断 若群体中存在最优个体，或己满足预先设定的停机条件则输出最优解后停 机，否则转下一步。 ( 5 ) 选择 按照某种选择策略从群体中选择出若干个体进入交配池。交配池中的个体 通过遗传算子的作用产生新一代群体。选择策略应遵守的基本原则是：适应度 值越小的个体被选中的概率应该越大。常用的选择策略有赌轮选择、确定性选 择等。 ( 6 ) 繁殖 定义适当的遗传算子。通过遗传算子的作用，交配池中的个体产生新的个 体，构成新一代群体。传统遗传算法主要通过交换( 交叉) 算子繁殖后代。交换算 子的搜索不具有遍历性，仅仅使用交换算子无法保证算法的全局收敛性。可辅 以变异算子模拟生物进化过程中的基因突变现象；通过突变保持群体中个体的 多样性。突变算子的搜索具有遍历性，能保证算法的全局收敛性。 ( 6 ) 跳转第( 3 ) 步。 遗传算法就是这样不断地进行个体评价、选择、繁殖，如此循环反复，使 群体中的个体朝着最优解的方向不断移动，直到搜索到最优解或满意解。 遗传算法流程图如下图所示： 1 3 第2 章理论与技术简述 编码和初始群体生成 上 群体中个体适应度的检验 图2 1 遗传算法流程图 2 2 3 基于遗传算法的自动组卷方法 自动组卷( a u t o g e n e r a t i o n o f t e s t p a p e r ) 【2 司【捌口o 】【3 l 】是利用一定的组卷算法， 自动地从题库中抽取合适的试题，使它们组成的试卷能满足用户要求。组卷算 法的原理是首先将用户要求量化成试卷模型；然后基于试卷模式建立组卷的数 学模型，并对模型进行求解；然后根据求出的解在题库中找到和求出的解一致 的试题即完成了组卷。 组卷主要是根据给定的约束条件( 总时间、试卷分数、试卷难度系数、题 型比例、知识点、已选择次数等) 从大量的试题库中抽取出最优的试题组合。 要实现自动组卷算法必须首先建立自动组卷的数学模型，形成具体的试卷指标 和具体的试题。 ( 1 ) 试题指标 试题指标指建立组卷系统中的试题库，由于试题本身包含固定的特性，这 些特性可用一定的指标来描述，具体介绍如下： 1 ) 试题类型 2 ) 试题难度 1 4 第2 章理论与技术简述 在试题命题过程中，针对不同的考试对象，不同阶段的考试，命题难度也 不同，所以，应在试题库中增加难度系数，也就是每个试题库中都要考虑的结 构。 3 ) 解答值 4 ) 涉及内容 试题涉及的内容可以按课程的篇章细分，也可以按知识点划分，一道试题 可能涉及多个内容，涉及的程度可用一个关于这些内容的比例分布来表示。 5 ) 区分度 试题的区分度就是鉴别度，它是衡量试题对考生的知识能力水平鉴别和区 分程度的指标。区分度好的试题能够把不同水平的被试者有效的区别开来，计 算区分度的方法有多种，常用高低分分组分析法。 q = ( h - l ) f ( 2 1 ) 式中，h 为高分组学生在该题的平均分，l 为低分组学生在该题的平均分， f 为该题的满分。评测标准：0 9 以上，优秀题目：0 3 - - 0 9 ，良好题目；0 2 , , - 0 2 9 ， 勉强合格；0 1 9 以下，差的题目。 6 ) 分值 分值是每一道试题的满分值。对各种类型的题目可以设置不同的分值。为 了统一通用，且考虑其他综合因素，对题分应限定最低、最高分数档及最小的 分数档间隔，它一般受到考试时间及试题难度的影响。 一 7 ) 试题内容的相关性 试题内容的相关性主要是指在命题时避免相同的试题太多，而无法对学生 所学的知识进行全面的考核，要对题目的相关性进行定量，引入相关性系数t l ， 对每门课程其题目的”范围为o 1 0 。 建立题库的目的就是为了克服在命题中人为的主观性和片面性，提高试题 命题的客观性和科学性，以及命题的质量和效率。同样试卷指标也是控制计算 机自动命题质量的关键，因此对试卷指标有一个清晰的概念也是十分必要的。 根据用户对组卷系统的要求信息及课程教学专家经验，试卷指标主要表现在：难 易程度( 难度、方差或及格率) 、区分度、效度( 包括内容效度、结构效度、标准 相关效度) 、信度、考试目的和考试对象。 ( 2 ) 试卷模式的建立 当前试卷模式的具体描述如下： 1 5 第2 章理论与技术简述 1 ) 满分值s ：答对所有题目所获得的试卷总分，通常为1 0 0 分。 2 ) 试卷的预估时间：用于控制试卷的试题数量和试题的难度，默认为1 2 0 分钟。 3 ) 题型及分数：包括试题类型的数量、每种题型的总分值和每种题型下的 试题数量。 设有1 1 种题型的集合为：d ( _ ( 1 ，2 ，n ) ，在试卷中的第m 种题型的总分 值记为t m ( m = l ，2 ，n ) ，有： s - - - t i - i t 2 + + t ( 2 2 ) 通常给出在试卷中的第m 种题型的数量：a m ( k = l ，2 ，n ) ，这样可得第 m 种题型的每个试题的分数： 7+ 厶2 f 。，f f l 2 l ，2 ，卵 ( 2 3 ) 4 ) 难度分布 指不同等级的入选试题占试卷总分的百分比分布。设等级仁 l ，2 ，p ) ， 期望第i 种难度的总分值为：a i ( i - 1 ，2 ，p ) ，则得到： s 2 a l + a 2 + + a p ( 2 4 ) 5 ) 范围分布 指入选试题所测试的内容和具体的知识点范围占试卷总分中的分数百分 比。设范围集合为f = - 1 ，2 ，q ) ，期待第j 种范围的总分值b j ( j = l ，2 ， q ) ，则有： s - - 岛+ 6 2 + + 乞 ( 2 5 ) 6 ) 能力分布 指入选试题所测量考生的能力占试卷总分中的分数百分比，能力集合l = f 1 ， 2 ，r ) ，期望第k 种能力的总分值c k ( k - = - i ，2 ，r ) ，则有： s = e l + 乞+ + c r ( 2 6 ) 通过以上的分析，我们建立当前试卷模式，从而利用试卷中的题型、难易 度、题目的重复度等条件一一加以限制约束，将不确定型转化为确定型。 ( 3 ) 组卷数学模型的建立 卜1 1 a l h s = l ；i ( 2 7 ) l a , 1 。a m n j 矩阵s 的列元素的分布分别满足用户指定的试卷的总体要求，即各篇章所 1 6 第2 章理论与技术简述 占的分数、试卷中各种题型的题数、反映不同教学层次要求的试题所占的分数 比例、各种难度的试题所占的分数比例、各种区分度的试题所占的分数比例、 所有试题的估时总和、所有试题的分数总和这些指标都应等于用户指定的要求 或误差最小。在实际应用中，设定整卷指标f 来综合反映这些个指标与用户要求 的误差，由于它们的重要程度不同，因此整卷的指标就是这些个指标的加权和， 同时为了不至于各个误差相互抵消，这些指标与用户要求的误差都取绝对值。 设f 为整卷指标，用下式表示： f _ - ，嵋 ( 2 8 ) i - i 其中丘表示第i 个指标与用户要求的误差的绝对值，w i 表示第i 个指标的权 值。n 表示s 的控制指标的个数。 组卷就是从题库中抽取试题，使得整卷指标f 最小，且目标状态矩阵应满足 如下条件： s - - t l - it 2 + + t 。 ( 2 9 ) s 。q + a 2 + + a p ( 2 1 0 ) s 2 岛+ 屯+ + ( 2 1 1 ) s 2 q + c 2 + + c r ( 2 1 2 ) 厶2 0 ( 2 1 3 ) 公式( 2 9 ) 至公式( 2 1 3 ) 表明组卷问题是一个多重约束目标求解的问题。 我们可以把组卷要求看成是试卷目标，它是通过试卷模式中各个参数的取值来 体现的，因此把各个试卷参数取值的限定作为实现自动组卷的多个目标，则公 式( 2 9 ) 至公式( 2 1 3 ) 就可以看成是多个目标函数。 2 2 4 基于遗传算法组卷的优势 作为一种优化与搜索算法，遗传算法相比于其他算法应用于组卷系统所具 有的优势在于： ( 1 1 遗传算法的操作对象是一组可行解，而非单个可行解，搜索轨道有多条， 而非单条，因而具有良好的并行性。 ( 2 ) 遗传算法只需要利用目标的取值信息，而无需梯度等高价值信息，因而 适用于任何大规模、高度非线性的不