（计算机应用技术专业论文）交互式多目标遗传算法在调度知识库中的研究.pdf

摘要 摘要 在企业的日常运作过程中，会经常遇到各种各样复杂的调度问题，而车间生产调度 问题解决的好坏直接影响着企业的运作效率和客户满意程度，最终影响企业对市场的反 应力和竞争力。因此，调度问题已经成为机械制造行业运营管理领域的一大研究热点。 本文针对交互式多目标遗传算法应用中出现的决策者偏好信息难以预先确定以及 用户容易疲劳的问题，提出一种改进的交互式多目标遗传算法。通过对多目标进行权衡 分析，由精英逐步诱导出决策者目标权重偏好。把权重偏好与p a r c t o 秩相结合，引导遗 传搜索，从而解决人机交互困难的问题。设计一种交互代数间隔递减的方式，即：运算 初期交互间隔代数较多，越到后期，间隔越小，交互越密集，减轻用户疲劳，提高运算 速度。将改进的交互式多目标遗传算法运用于实际车间调度问题可证明其有效性。 针对以往先进车间调度系统只能适应某个具体车间环境，可重构性和通用性差的缺 点，设计并实现通用的车间调度智能优化算法知识库系统。通过知识获取、知识发现、 统计与聚类分析的方法，抽取调度规则，并作为知识加以存储。这样，在将来的生产中， 可对相近的任务采取直接规则查找的方式，提高运算效率。可根据生产类别、车间、调 度目标的性质以及问题的规模运用知识库系统选择出一个合适的算法来计算优化调度 方案。 将改进的交互式多目标遗传算法应用于车间调度知识库系统，可更高效的为各种不 同的生产企业、不同的问题规模提供一个统一的求解方案。使用该系统后，可以缩减原 来的计划编制人员，而且计划编制更加合理、科学、细致，可以提高设备的利用率。在 避免设备空闲时间和尽量缩短生产周期的原则下，根据每个设备的负荷进行任务分配， 提高企业的经济效益。这对于车间作业调度问题的研究和将理论研究成果推广到实际工 程领域具有一定的意义。 关键词：交互式多目标遗传算法；车间调度；知识库系统 人连交通人学i ：学硕十学位论文 a b s t r a c t a tp r e s e n t ，t h em a n u f a c t u r i n gs e c t o r ，i n c r e a s i n gc o m p e t i t i o n ，i nt h eo r d i n a r yc o u r s eo f b u s i n e s s ，w o u l do f t e n e n c o u n t e raw i d ev a r i e t yo fc o m p l e xs c h e d u l i n gp r o b l e m s ，s h o p s c h e d u l i n gp r o b l e m - s o l v i n gw i l lh a v ead i r e c ti m p a c to nt h eo p e r a t i o n a le f f i c i e n c yo f e n t e r p r i s e sa n de n d c u s t o m e r ss a t i s f a c t i o na n du l t i m a t e l ya f f e c tt h eb u s i n e s s t o m a r k e t r e s p o n s ea b i l i t ya n dc o m p e t i t i v e n e s s t h e r e f o r e ，t h es c h e d u l i n gp r o b l e mh a sb e c o m eam a j o r f i e l do fo p e r a t i o n sm a n a g e m e n tr e s e a r c hf o c u s t h ep o l i c y m a k e ri n f o r m a t i o nw h i c ha p p e a r si nv i e wo ft h ei n t e r a c t i v em u l t i o b j e c t i v e g e n e t i ca l g o r i t h ma p p l i c a t i o ni nd e t e r m i n e sa n dt h ee x p r e s s i o na sw e l la st h eu s e re a s yw e a r y q u e s t i o ni na d v a n c ew i t hd i f f i c u l t yb yc h a n c e ，p r o p o s e so n ek i n do fi m p r o v e m e n ti n t e r a c t i v e m u l t i - o b j e c t i v eg e n e t i ca l g o r i t h m t h r o u g hm u l t i o b j e c t i v e t r a d e o f f a n a l y s i s a n d d e c i s i o n - m a k e r sf r o mt h ee l i t et og r a d u a l l yi n d u c eg o a lw e i g h tp r e f e r e n c e s ，t h ep a r e t or a n ko f t h ew e i g h tc o m b i n a t i o no fp r e f e r e n c e sa n dt og u i d et h eg e n e t i cs e a r c h ，i no r d e rt oa d d r e s s h u m a n - c o m p u t e ri n t e r a c t i o nd i f f i c u l tp r o b l e m d e s i g na l li n t e r a c t i v ew a yo fd e c r e a s i n g i n t e r v a la l g e b r a ，n a m e l y ：c o m p u t i n gt h ei n i t i a li n t e r v a la l g e b r aa r em o r ei n t e r a c t i v e ，m o r et o t h ep o s t - i n t e r v a lt h es m a l l e rt h em o r ei n t e n s i v ei n t e r a c t i o n ，r e d u c i n gu s e rf a t i g u ea n di n c r e a s e s p e e do fo p e r a t i o n w i l li m p r o v et h ei n t e r a c t i v em u l t i - o b j e c t i v eg e n e t i ca l g o r i t h mf o rj o b s h o ps c h e d u l i n gp r o b l e mc a nb ea p p l i e dt ot h er e a lp r o o fo fi t se f f e c t i v e n e s s a tt h es a m et i m ef o r t h ep a s t ，a d v a n c e ds h o pf l o o rs c h e d u l i n gs y s t e mc a n o n l ya d a p tt oa s p e c i f i cs h o pe n v i r o n m e n t ，r e c o n f i g n r a b l ea n dg e n e r a ls h o r t c o m i n g so fp o o rd e s i g na n d r e a l i z a t i o no fu n i v e r s a li n t e l l i g e n to p t i m i z a t i o na l g o r i t h m ss h o ps c h e d u l i n gk n o w l e d g eb a s e s y s t e m t h r o u g hk n o w l e d g ea c q u i s i t i o n ，k n o w l e d g ed i s c o v e r y ，s t a t i s t i c sa n dc l u s t e ra n a l y s i s m e t h o d s ，e x t r a c t i o ns c h e d u l i n gr u l e s ，a n da sk n o w l e d g et ob es t o r e d ，s ot h a t i nf u t u r e p r o d u c t i o n ，c a nt a k ed i r e c tr u l es i m i l a rt ot h et a s ko fl o o k i n gf o rw a y st oi n c r e a s eo p e r a t i o n a l e f f i c i e n c y c a t e g o r i e sa c c o r d i n gt ot h ep r o d u c t i o n ，w o r k s h o pa n ds c h e d u l i n go b j e c t i v ea n d t h es c a l eo ft h ep r o b l e mo ft h en a t u r eo ft h eu s eo fk n o w l e d g eb a s es y s t e ms e l e c t sa n a p p r o p r i a t ea l g o r i t h mt oc a l c u l a t et h eo p t i m a ls c h e d u l i n gs o l u t i o n w i l li m p r o v et h ei n t e r a c t i v em u l t i o b j e c t i v eg e n e t i ca l g o r i t h mi sa p p l i e dt oj o bs h o p s 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 c a nb em o r ee f f i c i e n tf o rav a r i e t yo fd i f f e r e n t m a n u f a c t u r e r s ，d i f f e r e n ts c a l eo ft h ep r o b l e ms o l v i n gt op r o v i d eau n i f i e dp r o g r a m u s i n gt h e s y s t e m ，c a nr e d u c et h eo r i g i n a lp l a np r e p a r e r s ，b u ta l s op l a n n i n gam o r er a t i o n a l ，s c i e n t i f i c ， m e t i c u l o u s ，y o uc a ni m p r o v ee q u i p m e n tu t i l i z a t i o n t oa v o i de q u i p m e n ti d l et i m ea n ds h o r t e n t h ep r o d u c t i o nc y c l ea sf a ra sp o s s i b l eu n d e rt h ep r i n c i p l eo ft h el o a do fe a c hd e v i c ea c c o r d i n g t ot a s ka l l o c a t i o n ，a n dt oc o n s i d e rt h ei n s e r t i o no fn o n u r g e n tt a s k st o i m p r o v ee c o n o m i c 摘要 e f f i c i e n c yo fe n t e r p r i s e s t h i sj o b - s h o ps c h e d u l i n gp r o b l e mi nr e s e a r c h a n dt h e o r e t i c a l r e s e a r c hr e s u l t sw i l lb ee x t e n d e dt ot h ep r a c t i c a le n g i n e e r i n gf i e l do fc e r t a i ns i g n i f i c a n c e k e y w o r d s ：i n t e r a c t i v e m u l t i - o b j e c t i v eg e n e t i ca l g o r i t h m ；s h o ps c h e d u l i n g ； k n o w l e d g e - b a s e ds y s t e m s i 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太蓬交通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名： 斗0 ， 鸯旖 日期：2 0 0 9 年11 月5 日 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解太蓬塞通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太整塞通太堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太整銮通太堂。学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 本人授权太整塞通太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：7 耄二迪 日期：口。( 7 年i 月岁日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电。子信箱： 导师签名： 培泖 日期：沥7 年，月箩日 电话： 邮编： 绪论 绪论 一、课题研究学术背景及意义 生产调度是c i m s 生产管理研究领域的核心内容和关键技术，将丰富的调度理论成 果应用于实际问题，具有很大的实践价值和经济效益。目前，对调度理论的研究已经受 到广泛的关注，并取得了较大的进展，但还很不成熟。人们认识到调度问题的约束性、 非线性、多极小性、不确定性、多目标性等复杂性，研究和发展了统计式全局搜索技术 和人工智能的方法，如模拟退火、遗传算法、禁忌搜索、进化规划、进化策略、神经网 络方法、i a g r a n g i a n 松弛方法和混沌优化等。 2 0 世纪8 0 年代以来，数据库系统和人工智能的研究，包括形式语言、自然语言处 理方面的概念和技术的进步，汇聚到一点就是知识库系统的研究、开发与应用。目前， 知识库系统已在决策支持系统、智能控制系统、智能机器人、专家系统、c a d ，办公室 自动化等方面取得了很好的应用，可以预见其旺盛的生命力和美好前景。在车间作业调 度决策过程中运用知识库系统，可将作业车间调度模型更加现实化，可获取最优的控制 规律，提高系统的可重构性和通用性，提高运算效率，尽量减少和避免不必要的重复开 发。随着科技的发展，目前人们己开发出大量车间调度智能优化算法，这些算法具有各 自的优缺点和适用环境，但设计、开发、运用车间调度智能优化算法知识库的却并不多。 特别是将交互式多目标遗传算法引入车间调度知识库系统的更是少之甚少。 交互式多目标遗传算法的求解比较符合设计者的偏好，同时由于多目标遗传算法具 有处理大的问题空间的能力，已应用于桥梁、滤波器等多目标工程问题，取得了显著的 效果。生产调度领域大量实际问题正属于多目标优化问题，因此，针对实际调度过程中 的一些难点对交互式多目标遗传算法进行深入的研究，将现有的交互式多目标遗传算法 进行改进，提高效率，同时针对以往先进车间调度系统只能适应某个具体车间环境，可 重构性和通用性差的缺点，设计并实现通用的车间调度智能优化算法知识库系统具有极 其重要的现实意义。 二、课题研究的主要内容及工作 本文的课题来源为大连市科技计划项目“机械制造行业车间调度知识库系统研究”， 本课题的主要工作为： ( 1 ) 研究现有的交互式多目标遗传算法的基本原理、方法、优化操作与步骤实现。 ( 2 ) 针对交互式多目标遗传算法应用中出现的决策者偏好信息难以预先确定和表达 以及用户容易疲劳的问题，提出一种改进的交互式多目标遗传算法。通过对多目标进行 大连交通人学l ：学硕+ 学位论丈 权衡分析，由精英逐步诱导出决策者目标权重偏好，解决人机交互困难的问题。设计一 种交互代数l 日j 隔递减的方式减轻用户疲劳，提高运算速度。 ( 3 ) 将提出的改进算法运用于作业车间调度问题，与无偏好多目标优化的小生境 p a r e t o 遗传算法( n p g a ) 和固定间隔代数的算法进行了对比，从理论和实际上证明改 进后的算法的有效性，并进一步对其性能优化。 ( 4 ) 设计并开发机械制造行业车问调度智能优化算法知识库系统，使车间调度模型 更加现实化，提高系统的可重构性和通用性，抽取调度规则并作为知识加以存储，这样， 在将来的生产中，可对相近的任务采取直接规则查找的方式，提高运算效率。 2 第一章车间调度问题j 知识库研究 第一章车间调度问题与知识库研究 1 1 调度问题的发展 2 0 世纪初，由于g a n t t 和其他先驱者的工作，调度问题在制造业得到了重视。1 9 5 4 年，j o h n s o n 对两台机床的f l o ws h o p 型调度问题进行了研究，这标志着车间调度理论研 究的开始。 六十年代，人们开始用一些普通的优化方法来解决调度问题，s t o r y 1 j 和i g n a l l l 2 1 等采用一些数学规划方法进行研究，g e r e 3 1 和g a v e t t 4 】也开始将启发式算法应用到调度 问题的研究中去。1 9 6 7 年c o n w a y 5 】等提出了调度问题的描述系统，一个完整的经典调度 理论体系开始初步形成。七十年代，人们开始了问题复杂性方面的理论工作。p a n w a l k a r 等回顾了二十年来调度理论的研究情况，总结和归纳出1 1 3 条调度规则，并对其进行分 类。我国学者越民义等开始对调度问题进行研究。八十年代初期，s t e p h e n l 7 】等认为调度 理论与实际的结合已经成为调度研究的首要问题，许多跨学科领域的技术和方法被应用 到调度问题研究中。1 9 8 8 年，r o d a m n e r l 8 1 等总结了生产调度的理论和实践方面的最新研 究进展，认为生产调度无论在理论还是实践上都已经开始打破传统的界限。 九十年代后，基于生物学、物理学、人工智能、神经网络、计算机技术及仿真技术 的迅速发展，为调度问题的研究开辟了新的思路。特别是近几年来，对调度的研究向更 加实用的方向发展，如多目标调度、动态随机调度、批量调度等越来越吸引更多学者的 关注【引。2 0 0 5 年，a l v a r e zv a l d c s 等人提出了一个启发式规则，建模玻璃生产企业的生 产调度【1 0oa n g e l 等人研究了用拉氏松弛法近似求解单机环境下双目标调度问题，这种方 法对于小规模问题尚可求解，一旦问题规模增加则很难求解，即使能求解也需要花费大 量的计算时剐1 1 】。t o r a b i 等人建立了批量调度模型，并用枚举的方法进行求解【1 2 j 。2 0 0 6 年g u t o w s k i 对铝和钢两种不同材料在不同机床上进行加工的能量消耗进行了对比分析， 指出同一材料加工过程的能量消耗受机床类型的影响，通过选择合适的加工机床，可以 显著减少加工过程的能量消耗【1 3 】。同年赵良辉结合车间调度问题的特点阐述了模拟退火 算法在解决车间调度问题上的应用，提出了基于模拟退火算法的车间调度问题模型，并 以m a t l a b 为工具进行了仿真实验1 1 4 】。2 0 0 7 年，杨帆等描述了基于可变机器约束的多目标 柔性j o b - s h o p 调度问题模型，并应用种改进的遗传算法进行求解。采用了表示工序 先后顺序及机器选择的二维编码方式，以多目标优化函数为度量，通过三种遗传操作扩 展后代的多样性和算法的搜索空间，结果验证了该算法能有效解决多目标优化问题l l 5 。 3 大连交通大学1 1 j 学硕十学佗论文 2 0 0 8 年7 月，吴秀丽提出了一个基于多目标免疫遗传算法的动态调度优化算法，设计了 面向交货期性能最优的柔性作业车间调度算法，并讨论了影响算法复杂度的因素1 1 6 1 。 由此可见，调度问题的解决还存在的以下的问题与不足： ( 1 ) 调度的优化准则中，基于性能的指标研究较多，基于代价指标的研究很少，然 而这类指标对企业的管理决策又是至关重要的。 ( 2 ) 对于多目标优化方法的理论分析没有系统研究，如何保证优化方法的收敛性和 p a r e t o 解的多样性是多目标优化方法亟待解决的问题。 ( 3 ) 多目标调度问题的讨论仅仅局限在所有工件的目标均相同情况下的多目标调度 问题中，关于体现决策者目标偏好的研究特别的少。 ( 4 ) 多数企业的车间生产作业计划与调度软件都是针对某生产车间定制的，它只适 合特定的环境，而当前无论是开发者还是使用者，都迫切需要实现通用性好、适用面广、 智能化程度高的生产作业智能支撑系统。 1 2 车间调度问题概述 1 2 1 调度问题描述 调度问题通常是指对生产过程中作业计划的划分，即对工件在机器上的加工顺序、 生产批量等的划分。一般的调度问题可以这样描述【1 7 】：n ( j 1j 2 j n ) 个任务被加工， m ( m 1m 2 m n ) 个机器可用，这些机器要完成每一个任务的加工，j i 在m i 上作业称为 一个操作，用o “表示，其相应生产时间记为p 咿通常，工件加工特性可用六元组b = b 1 ， b 2 ，b 3 ，b 4 ，b 5 ，b 6 ) 来表示，其中b 1 用来表示加工方式，b 2 表示工件间的加工优先关系， b 3 表示工件的准备a n t 时间，b 4 表示加工时间或操作数量的限制，b 5 用来表示交货期信 息，b 6 表示批量信息。工艺约束要求每一个作业按照一定的顺序在这些机器上加工，所 以车间调度问题就是寻找一个任务在机器上的生产序列。生产作业调度问题的目标是对 企业资源进行优化配置，提高企业的经济效益和社会效益。具体在评价调度方案好坏时， 评价指标的确定可以根据影响企业成本费用的主要因素、对社会的贡献以及决策者的目 标偏好来确定。车间调度问题的典型性性能指标如下1 1 8 1 ： ( 1 ) 基于加工完成时间的性能指标： 最大流经时间，总流经时间罗e ，加权流经时间m e ，平均流经时间i 。 筒 筒 最大完成时间c 。( m a k e s p a n ) ，平均完成时间c 。 ( 2 ) 基于交货期的性能指标： 4 第一章车间调度问题与知识库研究 平均推迟完成时间l ，最大推迟完成时间一。 平均拖后时间亍，最大拖后时问瓦。，总拖后完成时间l 。 口 ( 3 ) 基于库存的性能指标： 平均待加工工件数虬。 平均未完成工件数帆。 平均已完成工件数m 。 平均正在加工工件数。 平均机器空闲时间，。 最大机器空闲时间，咄。 ( 4 ) 多目标综合性能指标： 流经时间与总拖后时间的综合，如i + a yl ，其中a 为权重。 钎 m a k e s p a n 与总拖后时间的综合，即：c 一+ a 罗五 罚 e t 指标，即罗q 巨+ 屈巧，其中q 和为屈权重。 1 2 2 调度问题分类和特点 车间调度问题可以分为很多类型：根据加工特点分为单机调度、f l o ws h o p 调度和 j o bs h o p 调度；根据生产任务特点可以分为确定性调度和随机性调度；根据调度方案的 生成方式分为静态调度和动态调度。 车间调度问题具有如下特点： ( 1 ) 复杂性。车间中的作业、加工设备、搬运系统之间往往是相互作用的，同时每 个作业又要考虑它的到达时间、加工时间、安装时间、操作顺序以及交货日期等，由于 车间调度问题是在等式或不等式约束下求性能指标的优化，在计算量上往往是n p 完全问 题，即随着问题规模的增大，对于求解最优化的计算量呈指数增长，因而使得一些常规 的最优化方法往往无能为力。 ( 2 ) 动态随机性。动态随机性首先表现在由于一些临时、突发事件，如急件的加入 或者交货日期的提前，所以加工任务携带着动态、随机等特点；其次设备以及其它资源 的临时故障等会迫使对原有的调度结果进行修改或者重新分配。 ( 3 ) 多约束。在研究调度问题时，不仅要考虑机器约束和加工过程的时间约束，同 5 大迮交通大学t 学硕十学位论文 时还要考虑其它约束条件，如人员、工具、物流系统等。 ( 4 ) 多目标。调度的目标多种多样，在实际的调度中需要综合考虑各种目标。一次 调度往往具有多个目标，如加工时间最短、利润最大、生产成本最低等，而且这多个目 标之间有时互相冲突，需要对不同目标加以协调。 1 3 知识库系统概述 1 3 1 知识库系统的概念 知识库是合理组织的关于某一特定领域的知识的集合【1 9 j ，一般包含知识以及存储知 识的场所这两个内容。知识库中的知识一般建立在某种论域之上，所以，这就限制了知 识库的变化范围。知识库中的知识由事实、规则和概念组成。事实在库中是短期信息。 规则是从专家们的经验中抽出来的知识，是长期信息，它能指导专家系统如何由已知的 或新产生的事实中推导出假设来。规则的质量直接影响到专家系统性能的优劣。概念包 含信念和常识。未来的计算机应用将是以大规模知识为基础的应用，即新一代计算机将 以知识库为核心来组织。所以，知识库的研究具有重要的地位和作用。 随着知识库的大型化。知识数量达数干条乃至上万条。知识的层次也丰富起来，包 括常识性知识、原理性知识、经验知识和元知识等。知识的管理成为突出的问题，随之 产生了知识库系统。 知识库系统是基于知识对实际问题进行求解的系统，他的核心部分是知识库和手隹- 理 机。知识库系统的性能取决于知识库中的知识质量( 结构、完备性、有效性、一致性) 以 及使用知识的方式( 推理) 。知识库系统是一般包括硬件、软件、知识以及有关的人员。 在软件方面，一般由知识库、知识库管理系统、用户接口、知识获取接口等基本部件组 成。知识库系统的体系结构如图1 1 所示。 人机交互 知识获取接口 j 3 e 知识库管理系统 知识库 推理机 图1 1 知识库系统的体系结构 f i g 1 1k n o w l e d g eb a s es y s t e ma r c h i t e c t u r e 6 第一章车间调度问题! j 知识库研究 在车间作业调度决策过程中运用知识库系统，可将作业车间调度模型更加现实化， 获取最优的控制规律，提高系统的可重构性和通用性，提高运算效率【2 0 1 。随着科技的发 展，目前人们已开发出大量车间调度智能优化算法，这些算法具有各自的优缺点和适用 环境，但设计、开发、运用车间调度智能优化算法知识库的却并不多。 1 3 2 知识库系统的功能 知识库系统的功能大体上包括以下几个方面【2 1 l ： ( 1 ) 知识表示功能。向用户提供一种或多种知识表示方法。知识表示是利用计算机 能够接受的符号和方式来表示人类改造客观世界中所获得的知识。对知识进行表示的过 程，就是变换、编码成为数据结构的过程。 ( 2 ) 知识获取功能。知识获取是指知识从外部知识源到知识系统的转换过程。知识 库中的知识有两个来源，一个是原始知识，由外界直接进入知识库；另一个是再生知识， 是由推理机生成追加加入知识库。知识获取是建立知识库的关键环节之一，是知识库系 统的“瓶颈”问题。 ( 3 ) 对知识进行快速有效的查询和检索。向用户提供行之有效的查询与检索工具， 是知识库及其管理系统的最基本功能。 ( 4 ) 对知识库进行增、删、改操作。知识库的建立过程就是知识的获取和更新过程， 所以，对知识进行增、删、改的操作是不可避免的。 ( 5 ) 对知识进行一致性检查。因为在对知识库进行增、删、改等操作的过程中可能 会发生矛盾，出现不一致问题。目前已有多种冲突消解策略，其基本思想都是对知识进 行排序。 ( 6 ) 知识库的日常管理与维护。包括对知识库使用权限的确认、修改知识库内容的 权限的确认、知识库的定期安全检查、文件管理等工作，以防止不合法的操作而损坏知 识库。 本章小结 在本章中，主要论述了调度问题的基本理论。介绍了调度问题的研究与发展，阐述 了调度问题的分类及特点。同时，本章还简单介绍了知识库系统问题的概念和功能。 7 火迕交通大学t 学硕+ 学位论文 2 1 遗传算法 第二章交互式多目标遗传算法研究 2 1 1 遗传算法概述 近代科学技术发展的显著特点之一是生命科学与工程科学的相互交叉、相互渗透和 相互促进，而遗传算法g a ( g e n e t i ca l g o r i t h m s ) 等智能化计算的蓬勃发展体现了科学发 展的这一特点和趋势。近年来对这些人工智能理论和方法的研究不断深入，研究的成果 得到了广泛的应用，也取得了显著的成果。遗传算法的实质是一种求解问题的高效并行 搜索方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索 过程以求得最优解或较优解。遗传算法的两大主要特点是群体搜索策略和群体中个体之 间的信息交换，它实际上是模拟由个体组成群体的整体学习过程，其中每个个体都是给 定问题搜索空间的一个解。 遗传算法是从一组随机产生的初始解，称为“种群( p o p u l a t i o n ) 一，开始搜索过 程。种群中的每个个体是问题的一个解，称为“染色体( c h r o m o s o m e ) 。染色体是 一串符号，比如一个二进制字符串。这些染色体在后续迭代中通过相关的遗传操作一代 一代进化，最终找到最优解。评估这些染色体好坏的函数称之为“适值( f i t n e s s ) 。 遗传算法一般包含三个基本的遗传操作，即选择、交叉和变异。选择体现了适者生存的 自然法则，是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。交叉操 作是通过基因重组来结合来自父代交配种群中的信息产生新的个体。变异操作是将个体 染色体编码串中的某些基因座上的基因值用该基因的其它等位基因来替换，形成一个新 的个体。 2 1 2 遗传算法步骤 标准遗传算法的主要步骤可描述如下： ( 1 ) 随机产生一组初始个体构成初始种群，并评价每一个体的适配值。 ( 2 ) 判断算法收敛准则是否满足。若满足则输出搜索结果；否则执行以下步骤。 ( 3 ) 根据适配值大小以一定方式执行复制操作。 ( 4 ) 按交叉概率执行交叉操作。 ( 5 ) 按变异概率执行变异操作。 ( 6 ) 返回步骤( 2 ) 。 8 第。j 幸交q ：式多日标遗传算法研究 2 2 多目标遗传算法 图2 1 遗传算法流程图 f i g 2 1t h ef l o wo fg e n e t i ca l g o r i t h m 2 2 1 多目标优化问题 7 0 年代以来，多目标优化的研究在国内和国际上都引起了人们极大的关注和重视， 而在车间调度实际问题中，大部分也属于多目标问题。8 0 年代中期，人们开始应用人工 智能的进化算法求解多目标优化问题【2 2 1 。 多目标优化问题一般可以表述为下面的形式： m a x z ( x ) = 【z l = f 1 ( x ) ，z 2 = f a x ) ，z q = f q ( x ，y ) 】 s t & ( x ) = 0 ，i = l ，2 m ( 2 1 ) ( 2 2 ) 优化的目标是寻找满足式( 2 2 ) 并使式( 2 1 ) 达到最优的解集。 多目标优化问题与单目标优化问题的差异非常大，在有单个目标时，人们寻找最好 的解，这个解比其它所有的解都要好。在有多个目标时，由于存在目标之间的无法比较 和冲突现象，不一定有在所有目标上都是最优的解。一个解可能在某个目标上是最好的， 但在其他目标上是最差的。因此在有多个目标时，通常存在一系列无法简单进行相互比 较的解，即非支配解( n o n d o m i n a t e ds o l u t i o n s ) 或p a r e t o 最优解( p a r e t oo p t i m a ls o l u t i o n s ) ， 它们的特点是：无法在改进任何目标函数的同时不削弱至少一个其他目标函数。 2 2 2 多目标遗传算法概述 由于现实问题往往呈现为多目标属性，并且需要优化的多个目标之间有时是相互冲 突的，研究表明基于人工生命的遗传进化模型非常适合求解这类多目标优化问题，这 算法即为多目标遗传算法i z 3 j 。1 9 8 9 年，d a v i dg o l d b e r g 在其著作g e n e t i ca l g o r i t h mf o r 9 大连交通人学t 学硕十学位论文 s e a r c ho p t i m i z a t i o na n dm a c h i n el e a r n i n g ) ) 中，提出用遗传算法实现多目标问题的优化 技术，多目标遗传算法的研究引起了许多学者的广泛关注，并涌现出了大量的研究成果。 多目标遗传算法具有处理大的问题空间的能力，在一次进化过程中可以得到多个可 行解曲面，对问题域的先验知识没有要求，对函数定义域的凸性不敏感，这正是经典算 法所不具备的。所以，应用遗传算法求解车间调度多目标优化问题，是这一领域的发展 趋势。基本上，多目标遗传算法的基本结构与求解单目标优化的遗传算法的基本结构相 类似，皆是经由评价、选择、交叉和变异等几个功能单元的交互作用，而达到求最优解 的目的。另一方面，在利用遗传算法进行多目标优化问题求解时，需要考虑如何评价 p a r e t o 最优解，如何设计适合于多目标优化问题的选择算子、交叉算子、变异算子等问 题，所以多目标遗传算法在实现时也有其独特的地方。 早期的多目标遗传算法一般都是遗传算法和一些经典的多目标优化技术的产物，它 们普遍效率不高、局限性大、鲁棒性差。之后出现了基于多种群的向量评估遗传算法、 基于字典序的方法、基于博弈论的方法等等，这些方法的特点是实用性差、解的精度不 高、不能保证求得最优解。目前多目标遗传算法的研究热点是采用p a r e t o 机制的多目标 优化技术，包括：多目标遗传算法m o g a ( m u l t i o b j e c t i v eg e n e t i ca l g o r i t h m ) ，改进的非 劣分层遗传算法n s g a - i i ( n o n d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h mi i ) ，小组决胜遗传算 法n p g a ( n i c h e dp a r e t og e n e t i ca l g o r i t h m ) 等等。m o g a 的主要优点是运行效率高，同 时比较易于实现，它的不足在于过于依赖共享参数的选择。n s g a - i i 的优点在于算法 无参数，容易实现；算法的运行效率高，解集有良好的分布性，特别是在低维问题的优 化上有很好的表现。缺点在于在高维问题上，因为聚集过程的缺陷，解集的多样性不如 s p e a 2 。n p g a 由于不需要对整个种群进行p a r e t o 排序，所以运行效率比较高，且能获 得较好的p a r e t o 最优边界。它的不足是共享参数的选择以及比较集大小的选择没有一 个通用的法则。 2 3 交互式多目标遗传算法 2 3 1 交互式决策方法 交互式决策方法能够实现决策者与优化模型之间的信息交换，并能充分体现决策者 的主观愿望，是上世纪8 0 年代以来多目标优化模型求解的主流方法。8 0 年代后，b e n a y o u n 等人【2 4 】首先提出了多目标交互决策法，通过对优化过程的人为控制，可以得出更符合问 题本身的解，这类方法不要求对问题域的先验认识，但它要求决策者必须始终参与优化 过程，对优化进行控制。由于其在工程系统和社会、经济、管理等各个领域的普遍存在 1 0 第：章交瓦式多目标遗传算法研究 性，因而越来越受到人们的重视。 交互设计过程的三个关键特征是：以用户为中心，特定的可用性标准和迭代。以用 户为中心这是关于交互设计的一个核心观点，让用户参与整个设计和评估，有助于及时 得到反馈。在项目开始时，就应该表示出特定的可用性和用户体验目标，并作明确说明， 而且也应就需求达成一致，这有助于设计人员选择不同的候选方案，并在产品丌发过程 中随时检查。通过迭代，就能利用反馈来改进设计，迭代是不可避免的，因为设计人员 不可能一次就找出正确地解决方案。 2 3 2 交互式多目标遗传算法概述 交互式多目标遗传算法是解决隐式多性能指标优化问题的有效方法算法，它将传统 的进化机制与人的智能评价相结合，通过人的个体给出适应值，代替难以( 或无法) 显 示表示的适应度函数，以充分体现用户的偏好和情感【瑚。由于交互式多目标遗传算法不 需要被优化问题的性能指标的数学表示，大大扩充了遗传算法的应用范围。因此该算法 自2 0 世纪8 0 年代末被提出以来，已成功地应用到人脸识别、服装设计、乐曲创作、语言 处理与韵律控制、知识获取与数据挖掘等众多领域。 交互式多目标遗传算法对进化过程中的隐含知识具有较强的依赖性，利用进化过程 中的进化信息可以进一步引导进化。当进化代数较多时，由于人直接参与种群进化过 程，而人具有易疲劳的特点，这将导致交互式多目标遗传算法的进化种群规模较小、进 化代数较少。对复杂优化问题而言，小的种群规模和少的进化代数往往难以找到其优化 解。这已经成为限制交互式多目标遗传算法进一步扩大应用范围的瓶颈。因此如何减轻 人的疲劳，从而提高进化个体的评价质量是改进交互式遗传算法性能的关键，也是国内 外众多学者近年来研究的热点之一。此外，由于人本身的认知局限性和表达有限性，要 求决策人一开始就定量而准确地描述出其偏好关系显然是不现实的，随着决策过程的进 行以及对中间结果的观察，决策者对各目标的偏好才能逐渐明确。因此不可避免地要涉 及到对决策人偏好关系的诱导、表示、处理以及利用。 2 3 3 交互式多目标遗传算法步骤 将交互式多目标遗传算法运用于车间调度问题的基本思路如下： ( 1 ) 针对车间调度的问题初始化参数，提供原始依据，为后面的优化设计打下基础。 ( 2 ) 将个体的目标值按式作规范化处理。 ( 3 ) 随机产生若干个可行解的初始种群。 ( 4 ) 挑选几个有差异的个体，由决策者判别其优劣性，产生一组非精确偏好包含。 若不能进行有差异的挑选，就可认为已经获得一组满意解，立即停止。 人连交通入学t 学硕十学付论文 ( 5 ) 对建立线性规划模型的个体进行比较后排序。 ( 6 ) 依据个体的p a r e t o 秩，计算适应度值，并进行分享操作。 ( 7 ) 选择个体，进行遗传操作，产生新一代个体。 ( 8 ) 世代更迭，每隔一定代数，需要产生非精确偏好包含，转第( 4 ) 步。 ( 9 ) 若代数超过一定数目，则停止，否则转向第( 5 ) 步。 图2 2 多目标遗传算法流程图 f i g 2 2t h ef l o wo fi n t e r a c t i v em u l t i - o b j e c t i v eg e n e t i ca l g o r i t h m 如图2 2 所述，交互式多目标遗传算法的基本思想是在基本的多目标遗传算法流程 的基础上，将人机交互引入到迭代中，通过人的判断进行适应值估计及评价和提取认知 信息引导进化操作。 2 4 交互式多目标遗传算法研究现状 2 0 0 1 年，胡毓、杨雷达发表了多目标随机规划的交互遗传算法1 2 8 l ，他们利用 遗传算法在处理过程中不依赖问题的种类、并具有较强鲁棒性等特点，提出了一种基于 交互式的求解多目标随机规划的遗传算法。算法的思想是，结合小生境技巧和构造p a r e t o 选优过滤器的手段，通过与决策者的反复交互对话，最后得到使决策者满意的问题的 1 2 第：审交旺式彩目标遗传算法研究 p a r e t o 有效解集。2 0 0 2 年1 月，王小平、曹立明在文献遗传算法一理论、应用与软件 实现 2 9 j 中对结合非精确目标权莺偏好信息与p a r e t o 秩的交互式多目标遗传算法进行 了详细的讨论。2 0 0 3 年，董朝阳、孙树栋等在网络化制造资源优化配置d s s 的优化 模型研究1 3 0 l 中采用结合非精确目标权重偏好信息与p a r e t o 秩的交互式多目标遗传算法 进行e m p 优化化模型算法设计。2 0 0 3 年1 0 月，朱英浩、李圣清等在基于交互式多 目标遗传算法的无源滤波器优化设计1