（计算机软件与理论专业论文）多目标优化遗传算法在建筑协同设计冲突消解中的应用.pdf

山东师范人学硕i ：学位论文 摘要 计算机支持协同工作( c o m p u t e rs u p p o r t e dc o o p e r a t i v ew o r k ，c s c w ) 是一种将人类 合作行为模式与计算机支持技术融合为一体的新兴技术，即在计算机技术支持的环境 下，一个群体协同完成一项共同的任务。计算机支持的协同设计( c s c d ) 是计算机支持 的协同工作中的一个重要领域，将协同工作的理论应用于设计系统就是计算机支持的协 同设计。c s c d 主要研究如何利用计算机网络对多人参与的协同设计工作、所涉及的数 据和设计过程进行组织、管理和协调。 在协同设计过程中，各小组或领域设计人员的知识背景互不相同，设计目标互不相 同，不同设计对象与其之间的属性也是相互依赖的，因而难免发生冲突。为使协同设计 能够顺利进行，提高协同设计小组的工作效率和效果，必须有一种有效的冲突消解策略， 来解决协同设计中的设计冲突，协调产品开发过程。 多目标优化遗传算法是近年来针对多目标优化问题发展起来的一种新的优化算法。 由于其具有高效、实用的特点，因此越来越受到学术界的重视。本文在充分分析研究协 同设计的冲突和多目标优化问题的基础上，将协同设计的冲突理解为一个多目标优化问 题，因此多目标优化遗传算法是冲突消解的有效途径。本文提出了基于多目标优化遗传 算法的冲突消解策略，通过对协同设计过程进行检测，及时发现冲突，然后在定性分析 的基础上，采用多目标优化遗传算法协调各领域设计人员设计目标达到整体最优，从而 达到冲突消解的目的。 建筑协同设计是网络环境下一种新兴的建筑设计方式。在该方式下，分布在不同地 理位置上的设计人员通过网络在各种计算机辅助工具的支持下协同地进行建筑的设计 工作。传统的建筑设计中解决冲突的方式是采用人工方式协调而非计算机智能解决。本 文设计并开发了建筑协同设计系统，并且将基于多目标优化遗传算法的冲突消解策略应 用于建筑协同设计系统中，自动发现建筑协同设计中的冲突并且进行消解，使传统的人 工协调由计算机协调取代，取得了较为满意的效果，保证了建筑协同设计能够顺利进行。 本文利用多目标优化遗传算法解决冲突，所得的多个非支配解为决策者提供了多样性的 选择，更有利于决策者做出正确的决策，为研究协同设计冲突消解提供了一种新的途径 与方法。 本文所做的主要工作如下： 1 、对多目标优化遗传算法n s g a i i 的优良性能进行了验证。总结了建筑协同设计 特点和过程、建筑协同设计的冲突并且对建筑协同设计的冲突进行了数学描述。 2 、构建了协同设计冲突的多目标优化模型。 山东师范人学顺l ：学位论文 在对协同设计的冲突和多目标优化问题深入研究的基础上，本论文将协同漫计中的 冲突描述为多目标优化问题，构建了协同设计冲突的多目标优化模型，在此模型的基础 上，可以根据实际出现的协同设计系统的冲突，建立具体冲突的多目标优化模型。 3 、提出了基于多目标优化遗传算法的冲突消解策略。 提出了基于多目标优化遗传算法的冲突消解策略，利用国际上先进的多目标优化遗 传算法n s g a i i 进行冲突求解。并给出了冲突检测的有效方法，给出了整个策略的流 程和具体的实现方法。 4 、将基于多目标优化遗传算法的冲突消解策略应用于建筑协同设计中。 设计并实现了一个建筑协同设计系统。系统以h o o p s n e t 作为整体架构、三维引擎 a c i s 为造型内核，采用s q ls e r v e r2 0 0 0 数据库系统，利用v c + + n e t2 0 0 3 在w i n d o w s x p 平台上开发完成。重点介绍了如何进行冲突消解，并且给出了采用多目标优化遗传 算法对建筑协同设计进行冲突消解的实例，对冲突消解的结果进行了实例展示，证明了 该策略的有效性。同时所得的多个非支配解也可以使决策者对整个问题非劣解集的分布 具有更加全面的了解，这有利于决策者作出更好的决策。 关键词：建筑协同设计；冲突消解；多目标优化问题；遗传算法 分类号：t p 3 1 1 山东师范人学硕i j 学位论文 a p p l i c a t i o no fm o g a i nc o n f l i c tr e s o l u t i o nf o ra r c h i t e c t u r e c o o p e r a t i v ed e s i g n a b s t r a c t c o m p u t e rs u p p o r t e dc o o p e r a t i v ew o r k ( c s c w ) i sa n e wt e c h n o l o g y , w h i c hs y n c r e t i z e s h u m a n sc o o p e r a t i o nb e h a v i o rm o d ea n dc o m p u t e rt e c h n o l o g y i tm a k e sa l lm e m b e r so fa t e a mc o m p l e t eac o m m o nw o r kb a s e do nc o m p u t e rt e c h n o l o g i e s w h e nc s c wi si n t r o d u c e d t od e s i g na r e a ，i ti sc o m p u t e rs u p p o r t e dc o o p e r a t i v ed e s i g n ( c s c d ) c s c di sa l li m p o r t a n t d o m a i no fc s c w c s c di sa l li m p o r t a n td o m a i no fc s c w i ts t u d i e sh o wt oo r g a n i z ea n d m a n a g et h ew o r k ，t h ed a t aa n dt h ed e s i g np r o c e s s e s i nt h ep r o c e s so ft h ec o o p e r a t i v ed e s i g n ，d i f f e r e n td e s i g ng r o u p sa n de x p e r t sh a v et h e d i f f e r e n ti d e a sa n dd e s i g no b j e c t sa b o u tt h ep r o d u c t sa n dt h ed i f f e r e n tk n o w l e d g e b a c k g r o u n d a n dam a s so fr e c i p r o c a lr e s t r i c t sa n di n f l u e n c i n gr e l a t i o n sc o n s i s ti nv a r i o u sp r o d u c tp a r t s ， s ot h ec o n f l i c t su n a v o i d a b l yo c c u ri nt h ep r o c e s so ft h ec o o p e r a t i v ed e s i g n i no r d e rt om a k e c s c dg oo nw h e e l sa n de n h a n c et h ee f f i c i e n c ya n dt h eq u a l i t yo ft h ed e s i g n ，w en e e dav a l i d t a c t i ct or e s o l v ec o n f l i c t sa n dc o o r d i n a t et h ep r o c e s s e so fp r o d u c td e v e l o p m e n t m u l t i - o b j e c t i v eo p t i m i z a t i o ng e n e t i ca l g o r i t h m ( m o g a ) i san e wp o w e r f u lt o o lf o r m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m s ，a n di tc a nd i r e c t l yw e i g ht h eb a l a n c ea m o n gm u l t i p l e o b j e c t i v e s i ti sb e i n gr a p i d l yd e v e l o p e di n r e c e n ty e a r s b e c a u s eo fh i 曲e f f i c i e n c ya n d p r a c t i c a b i l i t y , m o g aa t t a c h e sm o r ea n dm o r ei m p o r t a n c et ot h ea c a d e m e o nt h eb a s i so f s t u d y i n gt h ec o n f l i c t si nc o o p e r a t i v ed e s i g na n dm u l t i - o b j e c t i v eo p t i m i z a t i o np r o b l e m ，w e c a nr e g a r dt h ec o n f l i c t sa sm u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m s om o g ai sa ne f f e c t i v e m e t h o dt or e s o l v ec o n f l i c t s m o g ai sa p p l i e dt or e s o l v ec o n f l i c t sw h i c hi sp r o p o s e di nt h i s p a p e r c o n f l i c td e t e c t i o nc a nh e l pt h ed e s i g n e rt od i s c o v e rt h ee x i s t e n c eo ft h ec o n f l i c t ，a n d m o g ac a nc o o r d i n a t et h eo b j e c t so fd e s i g n e r si nl o t so fd o m a i n st oa c h i e v ei n t e g r a l o p t i m i z a t i o n a r c h i t e c t u r e c o o p e r a t i v ed e s i g n i san e w f a s h i o n e da r c h i t e c t u r ed e s i g nm o d e a r c h i t e c t u r ec o o p e r a t i v ed e s i g nm e a n st h a ta l lm e m b e r so fag r o u pw o r kc o o p e r a t i v e l yb y u s i n gc o m p u t e r - a i d e dt o o li nas h a r i n ge n v i r o n m e n tt oa c h i e v ea r c h i t e c t u r ed e s i g no nt h e i n t e r a c t o nt h eb a s i so fs t u d y i n gt h ea r c h i t e c t u r ec o o p e r a t i v ed e s i g n ，w ed e v e l o pa n a r c h i t e c t u r ec o o p e r a t i v ed e s i g ns y s t e m c o n v e n t i o n a la r c h i t e c t u r ed e s i g na d o p t sn e g o t i a t i o n t or e s o l v ec o n f l i c t s w ea p p l ym o g at or e s o l v ec o n f l i c t si n s t e a do fc o n v e n t i o n a ln e g o t i a t i o n m o d e ，a n di tc a nd i s c o v e rt h ec o n f l i c tp r o m p t l ya n ds o l v ei t e x p e r i m e n ts h o w st h a tt h e r e s u l t sa r eq u i t es a t i s f i e d ，a n dt h i sm e t h o dc a ne n s u r ea r c h i t e c t u r ec o o p e r a t i v ed e s i g ng oo n w h e e l s t h er e s o l v i n gr e s u l t sa r em a n yn o n - d o m i n a t e ds o l u t i o n s ，w h i c ha r ep r o p i t i o u sf o r d e c i s i o nm a k e rt om a k eac o r r e c td e c i s i o n t h et a c t i cp r o v i d e san e ww a yo fr e s o l v i n g c o n f l i c t s t h em a i nc o n t e n to ft h i sp a p e ri sa sf o l l o w s ： 1 t h ee x c e l l e n tp e r f o r m a n c eo fn s g a - i ii sd e m o n s t r a t e di nr e s o l v i n gat y p i c a le x a m p l e a b o u tm u l t i o b j e c t i v eo p t i m i z a t i o ni n t h i sp a p e f t h ea u t h o rs u m m a r i z e st h ec h a r a c t e r i s t i c ， t h ep r o c e s sa n dt h ec o n f l i c t so fa r c h i t e c t u r ec o o p e r a t i v ed e s i g n ，a n dm a k e st h em a t h e m a t i c a l d e s c r i p t i o nf o rt h ec o n f l i c t si na r c h i t e c t u r ec o o p e r a t i v ed e s i g n 2 c o n s t r u c tam u l t i o b j e c t i v eo p t i m i z a t i o nm o d e lf o r t h ec o n f l i c t si nt h ec o o p e r a t i v e d e s i g n o nt h eb a s i so fs t u d y i n gt h ec o n f l i c t si nc o o p e r a t i v ed e s i g na n dm u l t i - o b j e c t i v e o p t i m i z a t i o np r o b l e m ，t h i sp a p e r d e s c r i b e st h ec o n f l i c t si nc o o p e r a t i v ed e s i g n a s m u l t i o b j | e c t i v eo p t i m i z a t i o np r o b l e m s o nt h e b a s i s o ft h i sm o d e l ，w ec a nc o n s t r u c t m u l t i o b j e c t i v eo p t i m i z a t i o nm o d e lf o rac o n c r e t ec o n f l i c tw h e nw ed i s c o v e rac o n f l i c ti n a c t u a lc o o p e r a t i v ed e s i g ns y s t e m 3 b r i n gf o r w a r dat a c t i cf o rr e s o l v i n gc o n f l i c t s b a s e do nm o g a b r i n gf o r w a r dat a c t i cf o rr e s o l v i n gc o n f l i c t sb a s e do nm o g ai n t h i sp a p e r , a n d n s g a 1 1w h i c hi sa na d v a n c e dm u l t i o b j e c t i v eo p t i m i z a t i o ng e n e t i ca l g o r i t h m s o na n i n t e r n a t i o n a ls c a l ei sa p p l i e dt or e s o l v ec o n f l i c t s w ec a nd e t e c tc o n f l i c t se f f e c t i v e l yb yu s i n g t h i st a c t i c ，a n dt h ef l o wa n dc o n c r e t er e a l i z a t i o nm e t h o d o l o g y o ft h i st a c t i ci sg i v e n 4 t h et a c t i cf o rr e s o l v i n gc o n f l i c t sb a s e do nm o g a i sa p p l i e dt oc o n f l i c tr e s o l u t i o nf o r a r c h i t e c t u r ec o o p e r a t i v ed e s i g n i m p l e m e n ta na r c h i t e c t u r a lc o o p e r a t i v ed e s i g ns y s t e m w i t hh o o p s n e ta d o p t e da s t h e m a i ns k e l e t o n ，a n de n t i t ym o d e l i n ge n g i n ea c i su t i l i z e da st h es c u l p tk e r n e l ，t h es y s t e mi s d e s i g n e do nw i n d o w sx pp l a t f o r mw i t hv c + + n e t2 0 0 3 i na d d i t i o n ，s q ls e r v e r2 0 0 0i s u s e da sd a t a b a s es y s t e m t h ee m p h a s i si sp l a c e do nr e s o l v i n gc o n f l i c t s t h ee x a m p l ew h i c h s h o w sh o wt oa p p l yt h em o g at or e s o l v ec o n f l i c t si sg i v e i l t h er e s o l v i n gr e s u l t sa leq u i t e s a t i s f i e dw h i c hp r o v e st h et a c t i ci se f f e c t i v e n o n d o m i n a t e ds o l u t i o n sc a l lm a k et h ed e c i s i o n m a k e rh a v eat h o r o u g hk n o w l e d g eo ft h ed i s t r i b u t i o no fn o n - d o m i n a t e ds e t , a n d i t h e l p st h e d e c i s i o nm a k e rm a k eab e t t e rd e c i s i o n k e y w o r d s ：a r c h i t e c t u r ec o o p e r a t i v e d e s i g n ；c o n f l i c tr e s o l u t i o n ；m u l t i o b j e c t i v e o p t i m i z a t i o np r o b l e m ；g e n e t i ca l g o r i t h m c l a s s i f i c a t i o n ：t p 31 l 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：导师签字： 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：碱毒 l 签字胁卅年5 月舀日 导师签字：舞| 彩 r l i 70 芎 签字日期：口7 年玉厅g 同 山东师范人学硕l j 学位论文 1 1 引言 1 1 1 协同设计冲突消解 第一章绪论 设计是个将人的某种目的或需要转换为一个具体的产品的过程，是把种计划、规 划、设想通过具体的载体，以美好的形式表达出来的一种创造性活动的过程。由于设计阶 段要全面确定整个产品的外观、结构、规格等等，从而确定后面整个生产过程的走向，因 而，产品设计具有“牵一发而动全局”的重要意义。近年来，为了进一步缩短产品开发周 期，降低成本，提高企业的竞争力，人们提出了许多先进的设计理念。其中，计算机支持 的协同设计研究是国内外计算机应用研究中最为活跃的前沿方向之一【l 】。 计算机支持的协同设计( c o m p u t e rs u p p o r t e dc o o p e r a t i v ed e s i g n ，c s c u ) 技术给人们带 来了协作方式的变革 2 1 ，全球化计算机网络使得实时交互协同设计成为可能。不同领域的 设计人员、不同的设计组织、不同的工作部门人员之间，均可实现资源共享，实时交互协 同参与、合作设计【3 l ，避免不必要的重复工作，提高人们协同工作的整体效率，有助于发 挥人们的创造精神和主动参与意识，从而提高设计的质量，缩短设计开发周期，降低设计 开发成本，进而达到提高企业核心竞争力的目的。 协同设计包含着许多学科的知识、技术和理念，因此具有复杂性、多样性和不确定性 等特点。各学科领域的设计人员，在并行设计中由于客观的因素( 物理位置分布不同，工作 时间不一致，工作进度不协调等) 和主观的因素( 掌握的领域知识不同，考虑问题的角度不 一致和对对象的评判标准存在差异等) ，从而使得协同设计过程中存在着冲突与矛盾。冲突 是协同设计的内在特征，在产品开发过程中，冲突可能发生在设计的各个环节，是不可避 免。 冲突问题在协同设计过程中起着重要的作用，它的存在有利有弊，一方面冲突的存在 势必造成设计的不协调，甚至搁浅，导致设计成本增加等；另一方面，冲突是一个良好或 革新的设计的开始，冲突的产生促使设计人员及早发现问题并解决问题，最终实现提高产 品各项性能指标的目的，最大限度地满足各领域专家的要求。随着冲突的不断解决，一个 更优的设计也随之产生【4 1 。从某种意义上说，协同设计的过程就是一个冲突产生和消解的 过程，因此，冲突消解成为协同设计中至关重要的支撑技术，它可以协调各方的结果得以 达到全局最优结果。本论文主要研究的就是冲突消解技术。 建筑设计是- - f 综合性的学科，集实用性、经济性、艺术性于一体。建筑设计要综合 考虑建筑功能、空问、造型、及工程预算等诸多问题【5 】，涉及到多学科、多工种的交叉和 山东帅范人学硕i j 学位沦文 协凋。建筑设计的特点决定了建筑设计需要密切的配合和协作。随着中国建筑市场的开放， 外国建筑企业逐步进入中国市场，国内设计单位将面临国际化挑战，将面临愈加激烈的国 际竞争，而企业的竞争的关键在于核心实力的竞争，对于设计单位来况，设计产品质量和 设计效率和成本是其核心竞争力的体现。在这种市场环境下，迫切需要一种缩短设计周期、 提高产品质量、降低产品成本的设计方式。将协同设计理论应用到建筑设计中受到越来越 多的设计单位和学术界的广泛关注，并且建设部2 0 0 3 年- 2 0 0 8 年全国建筑信息化发展规 划纲要中把协同设计能力作为建筑单位评定其资质的一个条件p 1 。可以预见协同设计将 是未来建筑设计领域的变革方向，越早利用协同设计最新成果的设计单位将越能在未来竞 争中掌握主动权。 传统的建筑设计中解决冲突的方式是采用人工方式协调而非计算机智能解决。通过协 同设计中的冲突消解技术自动发现建筑设计中的冲突并且进行消解，使传统的人工协调由 计算机协调取代，可以大大提高设计效率，缩短设计时间，节省设计成本，保障建筑协同 设计的顺利进行。因此，先进的冲突消解技术对建筑协同设计有着重大意义。 1 1 2 多目标优化遗传算法 多目标优化问题( m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m ，m o p ) 起源于许多实际复杂系统 的设计、建模和规划问题，这些系统所在的领域包括工业制造、城市运输、资本预算、森 林管理、水库管理、新城市的布局和美化、能量分配等等。几乎每个重要的现实生活中的 决策问题都要在考虑不同的约束的同时处理若干相互冲突的目标，这些问题都涉及多个目 标的优化，这些目标并不是独立存在的，它们往往是耦合在一起的互相竞争的目标，每个 目标具有不同的物理意义和量纲。它们的竞争性和复杂性使得对其优化变得困难。 近年来，随着优化技术的不断发展，在处理多目标优化问题上已逐渐形成了一整套系 统有效的解决方案。比较常用的多目标处理方法有：多目标加权法、层次分析法、f 一约束 法、目标规划法等。而遗传算法通过代表整个解集的种群进化，以内在并行的方式搜索多 个非劣解，决策者可以在多个解中选择决策方案，这对于解决m o p 是非常诱人的。 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是模拟生物在自然环境中的遗传和进化过程形成的 一种自适应全局优化概率搜索算法。遗传算法的思想在多目标优化问题中的首次应用可以 追溯到1 9 6 7 年，在r o s e n b e r g 的研究中提出了模拟单细胞有机物的化学遗传特性中采用多 属性研究方法【7 】。虽然在他的研究中最终只应用了单一属性方法，正是他的研究开创了这 个领域的研究，遗传算法真正应用于多目标优化问题领域是在9 0 年代初期最早出现的。 近几年来，将遗传算法应用于多目标优化问题成为研究热点，这种算法通常称作多目标优 化遗传算法或多目标优化进化算法。由于遗传算法的基本特点是多方向和全局搜索，这使 得带有潜在解的种群能够一代一代地维持下来。从种群到种群的方法对于搜索p a r e t o 解来 说是十分有益的。 目前，多目标优化遗传算法已应用于燃气涡轮泵控制器没计、航空器结构设计以及汽 2 山东师范人学倾i j 学位论文 车发动机优化设计等。无论在科学或工程上，多目标优化问题都是非常重要的研究课题， 因而多目标优化遗传算法能引起了许多研究学者的兴趣。 本文将协同设计中产生的冲突看作一个多目标优化问题，冲突消解就是使得所求的变 量向量满足所有约束并且使得所有的参与协同设计的设计人员目标达到全局最优。本文建 立了一种全新的基于多目标优化遗传算法的协同设计冲突消解策略并且详细阐述了其具 体流程与实现方式。最后，设计并实现了建筑协同设计系统，应用国际上比较先进的多目 标优化遗传算法n s g a i i 进行冲突消解，取得了比较满意的结果，证明了该策略的有效性。 1 2 冲突消解的研究现状 近些年来，国内外专家学者对协同设计中的冲突已经作了比较深入的研究，并且逐渐 摸索出了一些可行的冲突消解的策略方法。 1 2 1 国外冲突消解研究现状 国外在协同设计的冲突消解问题上有着一定的理论基础，并采用了两种类型的方法8 1 来解决工程实践中出现的各种冲突。 1 、人工智能方法：采用人工智能领域的思想，利用设计型专家系统，通过神经网络、 基于知识的表示和推理等人工智能技术解决协同设计中的冲突问题。 2 、数学模型方法：对协同设计中出现的冲突，通过分析了解其产生的原因，利用决 策论理论、模糊理论、运筹学等数学方法，建立相应的数学模型，并分析和计算数学模型 来处理冲突。 m k l e i n 【9 】等指出各种类型的冲突可以归纳为不同的冲突“类，每一个冲突类都对应 适用的冲突消解策略。这些冲突类由低到高被组织成多个层次。越靠近顶层的是通用性越 强的冲突类，对应领域无关的冲突和相应的冲突解决策略，越接近底层的是特殊性越强的 冲突类，适用于特定领域的冲突。当一个冲突发生时，找到包含这个冲突的最特殊的冲突 类，尝试这个冲突类对应的冲突消解策略。如果这些冲突消解策略都不成功，向上找到上 一层的对应冲突类，使用这个冲突类对应的通用性更强的冲突消解策略。利用这种将冲突 分层的方法可以快速地找到解决一个冲突的策略。 z l o t k i n 和r o s e n s t e i n t l 0 】提出一个理论协商模型和协商协议，该模型适合于非协作领域 理l 生( r a t i o n a l ) 主体，即使在冲突情况下，主体仍然能部分地协调它们的行为。但模型施加 的限定条件过于严格，比如主体的目标是固定不变的( f i x e dg o a l s ) 以及每一主体知道所有 相关的信息( c o m p l e t ek n o w l e d g e ) 等，而这些前提条件在d a i ( d i s t r i b u t e da r t i f i c i a l i n t e l l i g e n c e ) 实际应用中很难得到满足。后来，z l o t k i n 和r o s e n s c h e i n t l l l 对他们先前的研究 成果进行了改进，提出了一种新的协商方法，使得主体可以放宽它们的初始目标，并且可 以部分地实现它们的目标，这种方法的一个关键成份是代价的概念，用代价值定义整个或 3 山东师范人学硕i ：学位论文 部分实现目标。 r o l l e r 1 2 j 等提出了一种支持产品协同设计的共享数据库的协作事物模型，探讨了冲突 解决方案。p o l a t t ”1 建立了基于多a g e n t 的冲突检测和解决的模型。b a h l e r 1 4 1 提出了一种基 于经济效用的协议，在设计初始阶段允许多功能小组提出自己的最大或最小期望，采取适 当评判工具，对期望进行折衷，避免设计初期产生冲突。r i c a r d o t ”】将冲突按轻重缓急分别 进行先后处理。 1 2 2 国内冲突消解研究现状 国内对冲突消解作了大量的研究，也取得了一定的成果，产生了一些可行的思路和算 法，构建了一些冲突消解的模块，初步成型了一些系统。 赵慧设，田凌，童秉枢等1 1 6 1 在研究协同设计中基于约束的冲突检测与协商技术时提出： 可以从约束满足的角度，对协同设计中的冲突检测与协商问题进行了探讨。给出了基于约 束验证和区问传播算法的冲突检测方法，提出了几个基于回溯策略和约束松弛策略的冲突 协商建议算法，并在此基础上，构建了基于w e b 的协同设计冲突检测与协商系统，支持设 计专家检测与协调冲突。 马海波，熊光楞，徐文胜等【1 7 垮f 对并行工程的复杂性，分析了采用实例法解决冲突的 优越性，并且构造了实际的应用系统。该系统具有冲突检测、实例匹配、实例优化和冲突 解决等功能，通过完善的实例库可以给出并行工程团队成员相似实例的冲突解决方案，用 来指导解决冲突。同时借助于对实例的更改，可以进一步扩展实例库，实现领域冲突的全 面解决。 李涛等( 1 8 1 提出了一种基于优化算法的冲突仲裁策略。在约束网络支持的并行设计过程 中，建立了冲突仲裁的数学模型，设计了反映冲突严重程度的指标，并针对该指标利用基 因算法进行优化求解。与以往的冲突解决方法不同，该方法利用设计参数区间的可扩展性， 找到了制约设计问题的瓶颈，以最小的设计区间损失争取到最佳设计指标，从而达到有效 解决冲突的目的。 孟秀丽、易红、倪中华等t 饽】采用协商方法解决协同设计中因目标差异而产生的冲突， 给出了协同设计冲突起因的数学描述，研究了基于对策论的目标冲突协商方法，建立了协 同设计冲突协商模型，并给出该模型的n a s h 协商解和基于满意度的解。 傅宜生，岳丽华，蔡荣峰等 2 0 l 针对目前基于本体的x m l 数据集成系统中，仅仅通过 映射到全局模式来进行冲突消解的不足，提出了一种可扩展的映射规则模型。基于该模型， 给出了一个冲突消解算法，可以较好地解决由于局部数据源间的冲突引起的局部数据源查 询结果整合不j 下确和数据源间的连接操作失败等局部数据源互操作中出现的问题。 4 山东师范人学硕l 坞。位论文 1 3 本文的主要内容安排 本文共分为六章，各章的内容简单概括如下： 第一章为绪论。 第二章主要阐述了多目标优化的理论基础，遗传算法的基本思想、基本操作以及应用 关键和优化流程。鉴于遗传算法在多目标优化工作中的不足，进一步引出多目标优化遗传 算法，介绍了多目标优化遗传算法的研究概况。并着重介绍和分析了多目标优化遗传算法 n s g a o l i ，并给出了n s g a i i 的优化实例，证明n s g a i i 解决多目标问题的有效性。 第三章介绍了计算机支持的协同设计，并且分析了协同设计冲突的定义、产生的原因、 冲突分类和特点。最后分析了建筑协同设计及其冲突，并且对建筑协同设计中的冲突进行 了数学描述。 第四章介绍并分析了一些常用的冲突消解策略，将协同设计的冲突看作多目标优化问 题，对冲突的消解是对多目标问题的求解，从而提出了一种全新的基于多目标优化遗传算 法的冲突消解策略。将多目标优化遗传算法n s g a i i 应用于协同设计冲突消解。对出现的 冲突能够进行及时的检测并建立了冲突的多目标优化模型，给出了该策略流程以及具体的 实现方法。 第五章将多目标优化遗传算法应用于建筑协同设计冲突消解中，设计并实现了一个建 筑协同设计系统。给出了该系统的体系结构、系统框架和关键技术，最后给出了具体实例， 实现了多目标优化遗传算法在建筑协同设计冲突消解中的应用，并展示了试验结果，实例 表明该策略对于解决冲突较为有效。 第六章对全文做的研究工作进行了总结和对进一步的研究方向进行了展望。 5 山东师范人学顾i ：学位论文 第二章多目标优化遗传算法的相关理论 2 1 多目标优化问题及p a r e t o 相关概念 一般说来，科学研究与工程实践中许多优化问题大都是多目标优化问题。多目标优化 问题中各目标之间通过决策变量相互制约，对其中一个目标优化必须以牺牲其它目标作为 代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。多 目标优化问题和单目标优化问题是有本质的区别的：前者一般是一组或几组连续解的集 合，而后者只是单个解或一组连续的解。 与遗传算法不同，多目标优化遗传算法必须对解的每个目标上的值进行综合评价，而 往往这些目标有时相互冲突，很难找到在每个目标上的值都是最优的解。所以引入了p a r e t o 概念，用基于p a r e t o 的概念来求解问题的最优解。 2 1 1 多目标优化问题( m o p ) 法国经济学家v i l f r e d op a r e t o ( 1 8 4 8 1 9 2 3 ) 最早研究经济领域内的多目标优化问题，他的 理论称为p a r e t o 最优化理论。多目标优化问题( m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m ，m o p ) 也称作向量优化问题或多准则优化问题。多目标优化问题可以描述为：求一个决策变量向 量，它满足所有约束并且使得由目标函数组成的向量最优化。而这些组成向量的目标函数 通常彼此之间都是互相矛盾的，因此，这里的“优化 意味着求一个解向量使目标向量中 的所有目标函数值满足设计者的要求。通常，多目标优化问题是由一组目标函数和相关的 一些等式和不等式约束组成： 设有k 个优化目标，目标函数向量可以表示为： ( j ) = 【z ( i ) 】，以( 贾) ，名( 元) 】7( 2 1 ) 满足的约束条件如下： g ，何) o ，( f = 1 , 2 ，聊) ( 2 - 2 ) h ，( 夏) = 0 ，( 汪1 , 2 ，p ) ( 2 3 ) 寻求孑= i x ，x ；，x ：】r ，在它满足约束( 2 - 2 ) 和( 2 3 ) 时，使目标函数向量厂 ) 达到最 优。因为向量函数中的k 个目标函数之间可能是彼此冲突的，所以求解多目标优化问题的 意思是，寻找这样的一个解向量，它使得所有的目标函数值对决策者来说都是可以接受的。 7 山东师范人学顾i j 学位论文 2 1 2 最优解的定义 我们这里所讲的最优( p a r e t oo p t i m u m ) ，是由v i l f r e d op a r e t o 在18 9 6 年提出的，故称之 为p a r e t o 最优解( p a r e t oo p t i m u ms o l u t i o n ) ，定义如下1 ： 设q 是可行解的集合，i = 1 ，2 ，k ) 。若对于每一个元q ，或者v 划( f 【元) = f 【j + ) ) ， 或者存在一个i ，使得厂( 元) 厂( i ) ，则称贾为p a r e t o 最优解。 2 1 3p a r e t o 相关概念 l 、p a r e t o 支配：对于向量厅= ( “i ，u t ) 和向量哥= ( y l ，1 ，女) ，我们称厅p a r e t o 支配哥( 表 示为u - 夕 ) ) 。 6 、p a r e t o 边界：对于给定的多目标优化问题m o p ( i ) 和p a r e t o 最优解集p ，p a r e t o 边界( p f + ) 被定义为：+ = 仁= 歹= ( 六( 石) ，以( x ) ) 卜p + ) 。 2 2 遗传算法 2 2 1 遗传算法概述 生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产 生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算 法。早在2 0 世纪4 0 年代就有学者开始研究如何利用计算机进行生物模拟技术。2 0 世纪 6 0 年代由美国密执安大学h o l l a n d 【2 2 1 教授提出，在研究和设计人工自适应系统时，可以借 鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到交叉、变异等运算策 略在自适应系统中的重要性。2 0 世纪7 0 年代初，h o l l a n d 教授提出了遗传算法的基本定理 模式