（计算机应用技术专业论文）改进的并行遗传算法在知识库中的应用研究.pdf

摘要 摘要 生产调度问题属于组合优化问题。将优化方法的理论研究引入到车间生产调度领域 中，改进算法性能、拓宽算法应用领域、完善算法体系，是一个同时具有理论意义和应 用价值的课题，具有重要的意义。 并行遗传算法一直是遗传算法领域中的研究热点。本文在传统的粗粒度并行遗传算 法的基础上，提出了一种改进的并行遗传算法。新算法主要在两个方面对传统的粗粒度 并行遗传算法做出了改进：改进后的算法采用了一种根据各个岛屿平均适应度的大小动 态的调整该岛屿的迁移率，使得当某个岛屿的平均适应度较高时通过调高其它岛屿到该 岛屿的迁移率来增加它的多样性，从而避免了该岛屿发生早熟现象：改进后的算法对参 加迁移的染色体引入了存活期的思想，不但确保了适应度较高的染色体拥有较长的存活 期，而且避免了某个岛屿的种群规模过度膨胀。这些改进措施对避免算法出现早熟、提 高算法的收敛速度和全局搜索能力有重要意义。应用标准测试集中的测试用例和实际调 度中的问题对改进后的算法进行了测试，仿真程序表明，该算法能以较快速度完成给定 范围的搜索和全局优化任务。 同时，针对制造企业的实际情况，本文设计了一种新的适用于实际车间调度问题的 种群初始化方法，相较与传统并行遗传算法只是随机划分初始种群的缺点，本文提出的 划分方法使种群具有了更高的多样性。 针对某工厂的实际问题，运用上述技术，本文设计并实现了一个车间调度知识库系 统平台，并将改进后的算法嵌入至知识库系统平台中，运用改进后的算法，针对实际问 题进行求解，得到的结果是可行的和有效的。 关键词：遗传算法；迁移率；知识库；车间调度 大连交通人学1 ：学硕十学佗论文 a b s t r a c t s c h e d u l i n gt h e o r yb e l o n g st o c o m b i n a t i o no p t i m i z a t i o n p r o b l e m i n t r o d u c i n gt h e o p t i m i z a t i o nt h e o r yt ot h ef i e l do f j o bs c h e d u l i n gi nw o r k s h o pc a l li m p r o v et h ep e r f o r m a n c e o fa l g o r i t h m ，m a k et h ea l g o r i t h ma p p l yt ob r o a d e rf i e l d sa n dc o m p l e t et h ew h o l es y s t e mo f t h ea l g o r i t h m ，w h i c hi sas u b j e c ti n c l u d i n gb o t ht h e o r e t i c a lm e a n i n ga n d p r a c t i c a lv a l u e s t h ep a r a l l e lg e n e t i ca l g o r i t h mh a sa l w a y sb e e nt h eh o ts p o to ft h er e s e a r c ho ng e n e t i c a l g o r i t h m t h i sa r t i c l ep r o p o s e sa l li m p r o v e dp a r a l l e lg e n e t i ca l g o r i t h mb a s e du p o nt h e t r a d i t i o n a lc o a r s eg r a i ng e n e t i ca l g o r i t h m t h ep r o p o s e da l g o r i t h mi m p r o v e dt h et r a d i t i o n a l o n em a i n l yi nt w oa s p e c t s ：o no n eh a n d ，i te m p l o y sam e c h a n i s mw h i c hc a nd y n a m i c a l l y a d j u s te a c hi s l a n d sm i g r a t i o nr a t ea c c o r d i n gt oi t sa v e r a g ef i t n e s s t h e r e f o r e ，i fo n ei s l a n d s a v e r a g ef i t n e s si sh i g h ，i t sd i v e r s i 黟w i l lb ei n c r e a s e db yi n c r e a s i n go t h e ri s l a n d s m i g r a t i o n r a t et ot h i si s l a n di no r d e rt oa v o i dp r e m a t u r i t y ；t h ei m p r o v e da l g o r i t h ma l s oc a l c u l a t e st h e s u r v i v i n gp e r i o d f o re a c hc h r o m o s o m ei n v o l v e di n m i g r a t i o n ，n o t o n l ye n a b l e t h e c h r o m o s o m ew i t hh i g hf i t n e s st os u r v i v el o n g e rb u ta l s oa v o i dt h ee x p l o s i o no ft h ep o p u l a t i o n o fs o m ei s l a n d t h e s ei m p r o v e dm e a s u r e sa r eo fg r e a ts i g n i f i c a n c eo na v o i d i n gp r e m a t u r i t y o ft h ea l g o r i t h m ，a sw e l la si n c r e a s i n gg l o b a ls e a r c h i n ga b i l i t yo ft h ea l g o r i t h m t h ei m p r o v e d a l g o r i t h mi st e s t e dt h r o u g hu s i n ge x a m p l e si nt h es t a n d a r dt e s ts e ta n dt h ea c t u a lp r o b l e mi n s c h e d u l i n g t h es i m u l a t i o nr e s u l t so ft h et e s ts h o wt h a tt h i sa l g o r i t h mc a nc o m p l e t et h et a s k o ft h ef a s ts e a r c hi nt h eg i v e nr a n g ea n dg l o b a lo p t i m i z a t i o n i nt h em e a n t i m e ，a c c o r d i n gt ot h ep r a c t i c a ls i t u a t i o no ft h em a n u f a c t u r i n gb u s i n e s s ，t h i s a r t i c l ed e s i g n san e wm e t h o dt oi n i t i a l i z et h ep o p u l m i o nw h i c hc a na p p l yt op r a c t i c a lj o bs h o p p r o b l e m i fc o m p a r e dw i t ht h ec o n v e n t i o n a lp o p u l a t i o ni n i t i a l i z i n ga l g o r i t h mw h i c ho n l y r a n d o m l yd i v i d e st h ei n i t i a lp o p u l m i o nt om a n ys m a l l e rg r o u p s ，t h en e wa l g o r i t h mi sm u c h m o r ee f f e c t i v ei nt h ea s p e c to fi n c r e a s i n gt h ed i v e r s i t yo ft h ep o p u l a t i o n t h i sa r t i c l ed e s i g n e da n di m p l e m e n t e da ni n t e l l i g e n ts c h e d u l i n gk n o w l e d g eb a s es y s t e m p l a t f o r mf o rw o r k s h o p ，w h i c hi st a r g e t i n ga ts o m ef a c t o r y sp r a c t i c a lp r o b l e m f u r t h e r m o r e ， t h ei m p r o v e da l g o r i t h mh a sb e e ne m b e d d e di n t ot h ek n o w l e d g eb a s es y s t e m i fw eu s et h i s n e wm e t h o dt os o l v et h ep r a c t i c a lp r o b l e m t h er e s u l ts h o w st h es o l u t i o ni sb o t l lf e a s i b l ea n d e f f e c t i v e k e y w o r d s ：g e n e t i ca l g o r i t h m ：m i g r a t i o nr a t e ；k n o w l e d g eb a s e ；w o r k s h o ps c h e d u l i n g i i 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解太羹塞通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太连塞通太堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太整交通态堂。学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 本人授权太整塞通太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 、 叉。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：触导师签名： 日期：2 0 0 8 年1o月2 5日 日期：2 0 0 8 年1 0 月2 5 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电子信箱： 电话： 邮编： 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太整銮通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力；申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名：赵芪 日期：上o d 占年o 月) 角 绪论 绪论 一、课题研究学术背景及意义 车间调度问题( j o bs h o ps c h e d u l i n g ) 问题具有很强的应用背景，许多实际应用问 题都可以与之相转化，在制造业、计算机行业等从多领域都有重在应用价值。有关资料 表明，制造过程中大多时间都消耗非切削过程环节上，有效的调度方法与优化技术可以 更好地解决工件在机器上的调度和资源分配，实现车间调度的合理化、自动化、集成化； 可以实现对生产过程中的物流和信息流的综合管理，使前后工序紧密衔接，保持物流的 一贯性：可以提高设备的生产效率，减少工序等待时间，降低物料的消耗，减少库存， 缩短交货期，降低成本，提高产品竞争力。所以在制造业中，车间调度是实现制造系统 的运筹技术、管理技术与优化发展的核心。同时随着科学技术的发展，各种先进的制造 技术和制造理念在实际制造中得到越来越多的应用，对于这些具有较高自动化水平的系 统，生产过程中的合理、高效运行的调度问题变得非常复杂，往往会超出人的正常决策 能力，单纯依靠人力指挥生产过程的传统管理模式已经不适应新的环境需要，因而迫切 需要研究与之相适应的生产调度和管理方法，在这样的生产要求背景下，调度问题的研 究具有重要的现实意义。从理论上讲，由于大量的调度问题都是n p 难问题，目f j i 尚无 有效的求解技术，因此从理论上研究调度问题，寻找有效的求解策略并探求其理论基础， 具有重大的研究意义，将丰富的调度理论成果应用于实际问题，具有很大的实践价值和 经济效益。 二、课题研究的主要内容及工作 知识库( k n o w l e d g eb a s e ) 是知识工程中结构化，易操作，易利用，全面有组织的知 识集群，是针对某一( 或某一些) 领域问题求解的需要，采用某种( 或若干) 知识表示方式 在计算机存储器中存储、组织、管理和使用的互相联系的知识片集合。这些知识片包括 与领域相关的理论知识、事实数据，由专家经验得到的启发式知识，如某领域内有关的 定义、定理和运算法则以及常识性知识等。 目前国内外在知识库系统方面的研究都不是太多，而且一般都是针对具体的应用领 域而开发的系统，这种系统一般只适用于其针对的领域。当面对其它应用领域的问题时， 又必须对系统进行较大的修改甚至需要重新开发。而从头开始建造一个知识库系统是一 个复杂、很费时间的工作，建立一个特定领域的系统则相对要容易一些，但这样的系统 仅能用于特定的问题和领域，一种更经济和更灵活的方式是开发一个知识库系统的开发 环境，以便各个领域的专家来利用它来有效地快速建立特定领域的知识库。基于以上思 大连交通人学i ：学硕十学伊论文 想，应当开发一个知识库系统的通用开发工具，或知识库系统平台，以方便用户快速建 立其具体领域的知识库，尽量减少和避免不必要的重复开发。 本论文通过对传统粗粒度并行遗传算法的研究、分析，提出在传统的粗粒度并行遗 传算法的基础上改进的并行遗传算法来解决作业车间生产调度平台中出现的问题，采用 这种改进后的算法寻优更容易求得全局最优解和搜索效率高的优点，明显提高生产效 率，这种改进后的算法的思想对企业的机械行业车间生产调度管理具有极其重要的意 义。论文理论密切联系实际，并采用标准测试数据对新算法进行测试；并对新算法从理 论和实际方面进行评价，结果表明该算法在作业车间调度中能有效地提高调度的效率， 加快了进化速度，算法在解决中小规模调度问题上非常有效。 本课题的主要工作为： 1 研究传统的并行遗传算法的基本原理、方法、优化操作与步骤实现； 2 针对作业车间调度问题，提出基于改进后的并行遗传算法的加工调度的求解算 法并将其实现； 3 运用标准测试集对新算法进行测试，从理论和实际上证明改进后的算法的有效 性，并进一步对其性能优化； 4 设计并开发机械制造行业车间调度知识库系统，并将新的混合算法应用到知识 库系统中。 2 第一章调度问题1 j 知识晖研究 第一章调度问题与知识库研究 1 1 调度理论的研究与发展 到目前为止，研究调度问题的主要理论仍然是产生于上世纪五十年代的经典调度理 论( c l a s s i c a ls c h e d u l i n gt h e o r y ) 。一般认为，j o h n s o n 于1 9 5 4 年对两台机器下作业排 序问题的求解是经典调度理论产生的重要理论。他首先在文献中提出了n m f c m a x 问 题的优化算法，并且在此基础上给出了针对n 3 f c m a x 中的一些特殊情况的算法。 j a c k s o n 在他的一个研究报告里首先提出了e d d 规则【2 j ；s m i t h 也提出了单机( s i n g l e m a c h i n e ) 问题的几个优化规则【3 1 。这段时期的研究成果主要是提出了针对特殊的和规模 较小问题的解析优化方法，一般仅适用于单机和简单的流水车间( f l o w s h o p ) 问题， 研究范围较窄，但这些早期的工作为经典调度理论后来的发展奠定了基础。 由于企业车i 、日j 的生产计划与控制问题在所有调度问题中最具典型性，所以对车间调 度问题的研究一直在调度理论中占据主导地位。特别是近几年，更多领域的研究人员都 对车间调度问题产生了浓厚的兴趣，他们各自用不同的技术和方法对这个问题进行了更 为广泛、深入、细致的研究，取得了丰硕的成果。所以到目前为止，调度理论仍然以制 造业的生产车间为主要研究对象，所用到的基本术语和问题描述方式大部分都来自于对 生产车间各要素的描述。 1 2 调度问题的描述 1 2 1 单双机调度问题 1 单机求解平均流程时间最短的调度问题( 采用s p t 原则，s h o r t e gp r o c e s s i n gt i m e ) 按工件加工时间的长短，按不减的顺序从小到大安排各项作业。 例：一个车间有一台加工中心，现有5 个工件需要该机器加工。相关的加工时间和 要求完成时间( 交货期) 如表1 1 所示，求平均流程时间最短的作业顺序。 表1 1 工艺约束表 t a b l e1 1t e c h n i c sc o n s t r a i n t j 1j 2j 3j 4j 5 加j ：时间 1 12 93 112 交货期 6 14 53 13 33 2 解：根据s p t 原则，得出： j 4 - j 5 一jl - j 2 _ j 3 大连交通火学r 1 学硕十学伊论文 有关项目的计算如表1 2 所示： 表1 2 调度结果表 t a b l ei 2r e s u l to fs c h e d u li n g 加j ：时间完成时间交货期 五正迟 j 4113 30 j 5233 20 j 11 11 4 6 10 j 22 94 34 50 j 33 17 43 14 3 平均流程时间：p = 兰yf ：= 1 3 5 5 = 2 7 0 n 二_ 一 平均延迟；石= 4 3 5 = 8 6 最大延迟：d 一4 3 2 单机求最大延期量最小的调度问题( 采用e d d 原则，e a r l i e s td u ed a t e ) 按工件交货期的长短，按不减的顺序从小到大安排各项作业。 解：根据e d d 原则，得出： j 3 - j 5 j 4 j 2 - j1 有关项目的计算如表1 3 所示： 表1 3 调度结果表 t a b l e1 3r e s u l to fs c h e d u l i n g 加i ：时间完成时间交货期延迟 j 33 13 13 1o j 523 3 3 21 j 413 43 31 j 22 96 34 51 8 j 11 17 46 11 3 平均流程时间；f = 三yf ：= 2 3 5 5 = 4 7 o n 厶 平均延迟。6 = 3 3 5 = 6 6 4 第一章凋度问题j 知识库研究 最大延迟：d 一= 1 8 3 单机调度综合原则( 多目标调度) 例：在一台设备上安排6 个工件的加工任务，每项任务的作业时问和交货期如表1 4 所示。求在满足t m a x 最小的情况下，使平均流程时间最小。 表1 4 工艺约束表 t a b l e l 4t e c h n i c sc o n s t r a i n t j 1 j 2j 3j 4j 5j 6 作业要求 3248 65 交货期要求 631 02 02 83 0 1 ) 首先使用e d d 规则调度 j 2 - j1 - j 3 - j 4 j 5 - j 6 2 ) 求出所有作业的总操作时间t t = 2 8 3 ) 求出交货期不小于t 的任务项，然后按其加工时间的大小调整，将加工时问长 的任务调整到后面。 如本例，j 5 ，j 6 满足要求，因为t 5 t 6 ，所以： j 2 _ j1 - j 3 - j 4 - j 6 _ j 5 4 ) 去掉己调整的任务，重复2 卜4 ) 步。 最后得最优解： j 2 - j1 - j 3 - - j 4 a j 6 _ j 5 平均流程时间：p = 1 3 6 7 4 双机调度问题 n 种零件在两台机器上加工，它们的工艺顺序相同，即为流水型调度问题。j o h n s o n 给出了m - - - 2 情形的调度问题的解法，揭开了调度问题研究的序幕，下面简单介绍一下 这种算法。 对于以最大流程时间为目标的两台机器流水车间调度问题称为j o h n s o n 问题，其最 优调度由著名的j o h n s o n 规则确定，j o h n s o n 算法为后来的m 台机器问题的启发式算法 提供了基础，几乎所有的试探性算法都以此为基础。 j o h n s o n 算法通过下列简单的规则给出了两台机器流水车间的最短生产周期的产品 序列。 人连交通人学7 ：学硕十学位论文 假设有n 个工件，在第一台机器和第二台机器上的加工时间分别t i j 、t i 2 ，i = 1 2 ，n ， 其最优调度由下列j o h n s o n 规则确定。 j o h n s o n 规则：如果m i n t i l , t i 2 t i 2 , t j l ，则将工件i 排在工件j 之前。 可以直接利用这个规则构造最优调度，具体步骤为： 将n 中产品分成p 和q 两组。分组的原则是，p 组工件在第二台机器上比在第一 台机器上加工时间长，其余的产品归q 组。 将p 组工件按它们在第一台机器上加工的时问递增顺序排列，将q 组工件按它们在 第二台机器上加工的时间递减顺序排列。 将p 组工件顺序和q 组工件顺序连接在一起，构成的就是生产周期最短的最优产品 顺序。 需要指出的是，当我们从应用j o h n s o n 算法求得的最优顺序中任意去掉一些工件时， 余下的工件仍然构成最优顺序。同时，j o h n s o n 只是一个充分条件，不是必要条件，不 符合这个法则的加工顺序，也可能是最优调度。 例：某一班组有a 、b 两台设备，要完成5 个工件的加工任务。每个工件在设备上 的加工时间如表1 5 所示。求解总的加工周期最短的作业顺序。 表1 5 调度结果表。 t a b l e1 5r e s u l to fs c h e d u l i n g ：i ：件编号 j 1j 2j 3j 4j 5 设备a 3 t6 t7 tt5 t 设备b 2 t8 t6 t4 t3 t 解：由上面算法步骤，得出最优调度如下 j 4 一j 2 一j 3 一j 5 一j1 1 2 2 调度问题的分类 调度问题的描述方法与其分类有关，最常见的是根据任务在机床上的流动形式来分 类，下面引用的是m a c c a r t h y 等( 1 9 9 3 ) 的分类【4 】： 6 第一章调度问题与矢j 1 识库研究 图调度问题分类图 f i g 】1k i n d so fs c h e d u l i n gp r o b l e m 1 多任务车间( j o bs h o p ) ：每一个任务都有其个别的流动形式或者具体的加工路 线，它们与一定的机床相联系。 2 流水车间( f l o ws h o p ) ：每一个任务都有相同的流动次序。 3 开放车间( o p e ns h o p ) ：任何任务没有指定的流动形式。 4 置换流水车间( p e r m u t a t i o nf l o ws h o p ) ：不仅对于每一台机床每一个任务都有 相同的流动次序，而且对于每一个任务所有机床的次序都一致。 5 单机车间( s i n g l em a c h i n es h o p ) ：一个车间只有一台机床。 6 并行机床车间( p a r a l l e lm a c h i n e ) ：在一道工序中提供了m 个相同的机床，每 一个任务需要且仅需要这些机床当中的一个。 7 多任务并行机床车间( j o bs h o pw i t hd u p l i c a t em a c h i n e s ) ：指这样的加工车间， 每一加工阶段有1 ( i 个相同的机床( i = l ，2 ，m ) ，并且任何任务都要求 其每一阶段只能在这些机床中的一个加工。 c o n w a y 等于1 9 6 7 年提出了调度问题的描述系统，用a b c d 的形式来表示，这种 办法一直被后来的大部分研究者采用，m a c c a r t h y 等( 1 9 9 3 ) 对其作了一些扩展： a 任务数，其可能值为任何j 下值，经常用n 来表示。 b 机床数，可能值为任何j 下值，经常用m 来表示。 c 任务流动形式和技术与管理上的约束，一般的可能值如下： ：即空值，表示单机车间。 7 人连交通入学l ：学硕十学伊论文 j ：表示多任务车间。 f ：流水车间。 f ，p e r m 置换流水车f 日j 。 k - p a r a l l e l ：k 个机床并行。 j ，k - p a r a l l e l ：每个加工阶段都有k 个机床并行的多任务车间。 d 执行目标，一般指最大完成时间c m a x 和最大流动时间f m a x 等调度的目标函数。 1 3 车间调度问题的研究现状 。 在过去的几十年罩，车间调度问题吸引了无数研究者的兴趣，大量的研究成果相继 问世，但其中大多数的研究集中在经典的作业调度问题。即：给定一个工件的集合和一 个工序的集合，每个工件包含多道工序，每道工序需要在一台给定的机床上非间断的加 工某一段时间：每台机器一次最多只能加工一道工序；调度就是把工序分配给机器上某 个时间段。问题的目标是找到最小时间长度的调度。从上面的问题模型可以看出，经典 的调度问题对真实的环境进行了大量的简化，忽略了很多重要的因数，离应用尚有不少 的差距【12 1 。 调度问题是一种典型的组合优化问题，求解调度问题的算法很多，到目前为止，主 要形成了三大类：精确算法、启发式方法和智能搜索算法。其中比较典型的算法有：调 度规则、数学规划方法、人工神经网络、模拟退火算法、遗传算法、禁忌搜索算法和启 发式搜索算法等，这些算法各有不同的特点，它们在各种条件下的性能也各不相同，因 此对它们的比较分析非常重要。在研究新算法时，常同以前的算法进行比较，特别是分 枝定界法经常被用来作为参考，但是这些比较都是小规模和局部的。m a c c a r t h y 等( 1 9 9 3 ) 曾认为，同丰富的调度算法研究文献相比，比较性的研究成果显得十分贫乏。直到今天， 较大规模的比较研究工作仍然很少，这是因为还没有人提出成熟的算法比较理论，算法 比较只能通过实验的方式，而目自i f 出现的调度算法，包括各种算法的组合，至少达上百 种，如果对它们都进行直接比较，即使不是两两进行，其工作量也会是个组合爆炸问题。 所以我们用三个衡量准则，对尽可能多的算法研究成果进行了间接的比较分析。这三个 准则是：有效性、适应性和计算复杂性i 辑矧。 1 算法的有效性：有效性指的是算法的最优解逼近程度，也可以用达到最优解的 概率来表示，其中还包括同问题规模的关系。 2 算法的适应性：指的是某种算法的适用范围，也可以说是算法的通用程度。对 于各具体的问题，适用的算法往往不一样，有时候，同样类型的问题，由于追 求的目标函数不同，应该采用的算法也不一致。 8 第一章调度问题1 - j 矢, w 识痒研究 3 算法的复杂性：由于大多数调度问题都是组合优化的问题，所以计算效率问题 显得特别重要。对于一些简单的问题，可以用数学手段来表达算法的复杂性， 然后再进行比较；而对一些较复杂的算法，可能需要计算实验。算法的复杂性 经常同前两个指标发生冲突，即有效性和适用性较好的算法可能计算复杂性较 差。 1 4 遗传算法在车间调度问题中的应用现状 车间调度问题是生产调度领域的典型代表，g a 则是智能优化技术的代表，因此基 于g a 的j s p 具有重要的理论意义和工程价值。首先，结合研究j s p 的特性及其局部极 小拓扑结构的分析，有助于更好利用g a 解决j s p 问题，而这方面的研究目前还很少， 很不深入，因此对于具有很强工程背景的j s p 这个代表性问题，这无疑是一个很重要的 研究方向。其次，虽然近年来g a 应用于j s p 的研究很多，但大都局限于少数几个问题， 因此所得到的关于g a 求解这类问题的优化性能的结论是否具有普遍性昵? h a r t 等为了 深入调查g a 对j s p 这类问题的优化性能，进而分析了g a 的优势和弱点，设计了一个 可调整难度的可配置问题发生器，其研究表明g a 具有相当好的鲁棒性，即g a 能够在 绝大多数情况下得到大部分问题的理想情况下的解 6 1 。其次，将j s p 的数学模型更加现 实化，动态调度的研究尤其值得重视，并将已有的理论成果推广到实际工程领域，用实 践来检验技术的潜力，这不仅能够推动先进生产的发展，而且将促使优化技术的进一步 完善。同时，鉴于g a 对生产技术人员较为陌生，开发相关的实用化集成化调度平台和 优化技术，无疑具有很强的工程意义。再则，鉴于国际学术界对混合系统与算法的日益 重视，混合优化策略以及相应仿真环境的开发无疑是一个值得关注的研究方向，尤其是 将已有各种调度算法的优点与g a 有效的融合1 7 4 引。 一般来讲，调度方法的搜索效率和搜索效果是相互矛盾、相互制约的，通常根据实 际情况，需要在两者之间做出折衷的选择。总之，对车问调度领域这一具有n p h a r d 特 性的问题的研究，随着应用数学理论的进一步发展，必然朝着集成化、多目标化、动态 实用化、高度次优化方向深入进行。 总之，随着计算技术，优化技术，数学理论和计算机硬件的发展，g a 和j s p 本身 以及它们的结合研究将得到更完善的解决，研究与应用领域将更宽广，理论研究将更系 统化，更接近于实际，并朝着集成化、实用化、最优化、多目标化、动态化、规模化发 展。 9 人连交通人学1 ：学硕十学伊论文 1 5 知识库系统 知识库系统( k n o w l e d g eb a s es y s t e m k b s ) 是人工智能领域的研究热点问题之一。 1 5 1 知识库的概念 知识库是将众多的知识按一定的结构形式组织起来，通过知识库管理系统对各种知 识进行有效的管理和使用。 知识库象数据库一样是一个共享资源。知识库中的知识可以重复使用，即可以被不 同系统所调用，避免了冗余。通过知识库可以将多个简单的个体组合起来构成更大的较 复杂的知识。这样知识库就比将知识隐含的编码在程序中的一般应用程序具有更强的使 用能力。 知识库使基于知识的系统( 或专家系统) 具有智能性。并不是所还将含有数据处理具有 智能的程序都拥有知识库，只有基于知识的系统才拥有知识库。现在许多应用程序都利 用知识，其中有的还达到了很高的水平，但是，这些应用程序可能并不是基于知识的系 统，它们也不拥有知识库1 2 2 。 1 5 2 知识库系统的研究现状 近年来，发展知识库系统不仅要采用各种定性的模型，而且要将各种模型综合运用。 以及运用人工智能和计算机技术的一些新思想和新技术，如分布式和协同式。这些都是 知识库系统的研究热点1 1 9 j ： 1 通用性知识库系统。知识库系统的开发是需要领域专家和知识工程师共同努力 的，领域专家绝大多数只对自己领域范围的知识了解，这就导致现阶段开发的 知识库系统只适用于某一特定问题领域。用户越来越希望有一种以用户为中心 的通用性知识库系统。这就需要通用性知识库系统具有各种不同的并行算法和 知识获取模块，能够采用多种推理策略。通用性知识库系统为一种新型知识库 系统，其特点如下：集成多种模型的知识库系统，根据用户需要，可以选择其 中的任何一种或多种，形成某一类型的知识库系统；通过多种模型的综合运用， 提高了知识库系统的准确率和效率；经过长期的使用，可以探索出针对某一问 题的最佳模式( 多种模型的综合运用) ，获得最优的知识库系统。 2 分布式知识库系统具有分布处理的特征，其主要目的在于把二个知识库系统的 功能经分解后分布到多个处理器上去并行工作，从而在整体上提高知识库系统 的处理效率。这种知识库系统比常规的知识库系统具有较强的可扩张性和灵活 性，将各个子系统联系起来，即使不同的丌发者针对同一研究对象也可以有效 l o 第一章调度问题j 知识库研究 地进行交流和共享。随着i i l t e m e t 的发展与普及，建立远程分布式知识库系统 可以实现异地多专家对同一对象进行控制或诊断，极大提高了准确率和效率。 3 协同式知识库系统。协同式知识库系统的概念目前尚无一个明确的定义。一般 认为，协同式知识库系统是能综合若干相关领域( 或一个领域) 多个方面的单 一知识库系统互相协作共同解决一个更广领域问题的知识库系统，这样的系统 亦可称之为“群专家系统”。在系统中，多个知识库系统协同合作，各知识库 系统间可以互相通信，一个或多个知识库系统的输出可能成为另一个知识库系 统的输入，有些知识库系统的输出还可以作为反馈信息输入到自身或其先辈系 统中去，经过迭代求得某种“稳定”状念。 1 5 3 知识库系统的功能 知识库系统主要功能有三个方面： 1 演绎功能：能从现有的数据中演绎和推导出一些新的数据。 2 归纳功能：能将数据库中的数据归纳成规则存入知识库。 3 知识管理功能：管理事实与规则的功能即管理知识的能力。 本章小结 在本章中，主要论述了调度问题的基本理论。介绍了调度问题的研究与发展，而且 还阐述了调度问题的分类及对简单调度问题的分析。同时，本章还简单介绍了知识问题 的概念及它的分类，对知识库系统也做了简要的说明。 大连交通i 学 ：学硕十学伊论文 第二章并行遗传算法的研究 2 1 并行遗传算法概述 遗传算法在解决实际问题时，其内含并行性时其保持较高计算和搜索效率的主要原 因之一，但当问题的规模和计算量很大时，遗传算法仍然需要消耗大量的时间。一般来 说，遗传算法的各组成部分中，适应度的计算消耗时间最多。由于遗传算法的进化过程 是不断产生新个体和新种群，然后再进行适应度计算的测试，这种过程使得算法并行处 理要求显得越来越突出1 2 。 对于并行遗传算法( p a r a l l e lg e n e t i ca l g o r i t h m ) 的研究已有较多成果，主要的并行实 现方案有主从式、粗粒度和细粒度和混合式并行遗传算法三种。 1 ) 主从式模型是遗传算法并行化的一种最直接方式。主从式并行遗传算法系统分 为一个主处理器和若干从处理器，主处理器监控整个种群，并基于全局统计执行的 选择操作，各从处理器接受来自主处理器的个体进行重组交叉和变异，产生新一代 个体，并计算适应度并把结果传给从处理器。主从式并行遗传算法比较直观，并且 针对适应度评价计算量大的问题主从模式可以得到接近线性的加速比。 2 ) 粗粒度模型又称为分布式模型或孤岛模型，是目i j 最流行的一种并行遗传算法。 它将整个种群划分为多个子种群，每个子种群独立的运行一个串行遗传算法。在每 个种群内部进行选择、交叉、变异等遗传操作，且每经过一定遗传代数再在个子种 群间交换优秀个体来丰富各子种群的多样性，减少了未成熟收敛的可能性。粗粒度 并行模型是目前应用最为广泛的并行遗传算法主要是基于两个方面：一方面是由于 它容易实现，只需要在串行遗传算法中增加个体迁移子例程，在并行计算机的节点 上各自运行一个算法的副本，定期交换最佳个体即可；另一方面是它容易模拟，即 使在没有并行计算机的情况下，也可在网络或者单机上执行【2 6 j 。 3 ) 细粒度模型也叫做邻域模型，这种模型与粗粒度模型的区别在于，粗粒度模型 在每个处理器上运行一个种群，而细粒度模型则在每个处理器上运行一个个体。这 是一种更为细致的划分，当然，当原种群规模较大时就需要大量的处理器协同工作。 在这种并行模型下，每个处理器进行适应度的计算，而选择、交叉和变异操作仅在 与之相邻的一个处理器之问相互传递个体中进行1 2 。 4 ) 基于混合模型的并行遗传算法主要是通过将粗粒度、细粒度和主从式三种模型 混合形成层次结构。在下层的并行模型中，子群体的规模是真实的，即为一个处理 进程所处理的个体数量。而对于上层模型，将每个下层的并行结构都视为一个“集 合子群体”，而“集合子群体”之间按上层的并行模型协调运行。无论是从下层还 1 2 第二章并行遗传算法的研究 是上层角度看，都是予群体( 集合予群体) 内部信息交互量大，子群体( 集合子群 体) 之间信息交互量小。上下层模型的组合关系主要有三种：卡h 粒度主从式、粗 粒度粗粒度、粗粒度细粒度。实际中应用较多的是粗粒度- 主从式模型。 2 2 粗粒度并行遗传算法 粗粒度模型又称为分布式模型或孤岛模型，是目前最流行的一种并行遗传算法。它 将整个种群划分为多个子种群，每个子种群独立的运行一个串行遗传算法。在每个种群 内部进行选择、交叉、变异等遗传操作，且每经过一定遗传代数再在各个子种群间交换 优秀个体来丰富各子种群的多样性，减少了未成熟收敛的可能性。粗粒度并行模型是目 前应用最为广泛的并行遗传算法主要是基于两个方面：一方面是由于它容易实现，只需 要在串行遗传算法中增加个体迁移子例程，在并行计算机的节点上各自运行一个算法的 副本，定期交换最佳个体即可；另一方面是它容易模拟，即使在没有并行计算机的情况 下，也可在网络或者单机上执行1 37 1 。粗粒度并行遗传算法的流程如图3 2 所示： 初始种群划分 一l 标准遗传算 法( s g a ) 的遗传操作 标准遗传算 法( s g a ) 的遗传操作 一一+ 一 - 迁移算子 一l 一 产生子代 图2 1 粗粒度并行遗传算法的流程图 f i g 2 1s t r u c t u r eo f c o a r s eg r a i np a r a l l e lg e n e t i ca l g o r i t h m 1 初始种群建立：有两种方法产生初始种群，一种方法是通过先验知识来产生初 始种群，另一种是完全随机的产生初始种群。 2 子种群的划分：一般来说划分子种群的方式有两种，一种是将整个初始种群随 机的划分为若干个包含相同个体数的子种群，另一种是结合问题本身的特征划 分初始种群。 大连交通人学t 学硕十学位论文 3 适应度评价：遗传算法的一个特点是它仅使用所求问题的目标函数值就可得到 下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体 现的，适应度函数通常是在目标函数的基础上构造的。 4 选择：选择操作主要是用来避免有效基因的损失，使高性能的个体得以更大的 概率生存。常用三种方法：比例选择、排序选择、锦标赛选择。 5 交叉和变异：交叉运算是指两个相互配对的染色体按某种方式交换其部分基因， 从而形成两个新的个体。当交叉操作产生的后代的适应值不再提高且没达到最 优时需要采用变异操作，主要的变异方式有：互换、逆序、和插入变异。 6 迁移：以一定的迁移率在各个子种群间互相交换个体，迁移的目的是提高各个 子种群的多样性。 2 3 主从式并行遗传算法 主从式模型是遗传算法并行化的一种最直接方式。主从式并行遗传算法系统分为一 个主处理器和若干从处理器，主处理器监控整个种群，并基于全局统计执行的选择操作， 各从处理器接受来自主处理器的个体进行重组交叉和变异，产生新一代个体，并计算适 应度并把结果传给从处理器。主从式并行遗传算法比较直观，并且针对适应度评价计算 量大的问题主从模式可以得到接近线性的加速比。主从式遗传算法的框架结构如图3 3 所示： w 终止 ， 图2 2 主从式遗传算法框架结构 f i g 2 2s t r u c t u r eo fm a s t e r s l a v em o d e l 1 4 器 第l 二章并行遗传算法的研究 主从式并行遗传算法，对串行程序所作的主要改动是，在适应度的计算阶段，由主 处理器将适应度的计算分配到各个处理器上去进行，计算完毕后再由主处理器收集结 果。然后由主处理器进行选择、交叉、变异等操作，并由此产生新一代种群，从而完成 次循环。主从式遗传算法框架结构如图3 3 所示。 主从式p g a 采用单一进化群体，个体的适应度的计算分配到一组处理器上完成， 如图3 4 所示。在主从式p g a 中，选择、交叉、变异等操作均以全部个体为基础实施， 因此也成为全局p g a 。主从式p g a 与s g a 的运行机理完全一样。 主从式p g a 是一种最典型的全局并行g a ，主处理器负责存储群体和完成选择、交 叉、变异等遗传操作，从处理器负责个体适应度的计算，从而实现g a 处理流程上的最 大程度并行化。 由于个个体的适应度的计算与其他个体无关，当个体适应度计算比较复杂和费时 时，主从式p g a 可以取得良好的加速比( s p e e d u p s ) 。一般来讲，从处理器的数量远 远小于群体规模。主从处理器之间的一次通信是一个或一组染色体位串，返回的是一个 个或一组适应度的数据，为喘解码工作在