（计算机应用技术专业论文）基于商空间的粒度计算在启发式搜索中的应用与研究.pdf

摘要 摘要 搜索技术是人工智能中的一个基本而重要的研究领域。人工智能所处理的信息通常是 不确定的、模糊的、不完整的、海量的，因此一般不能明确地知道问题求解的途径，需要 通过搜索求解的空间才能找到正确的答案。 当缺少相关的邻域知识，问题的规模又不是很大时，可以采用盲目穷举的搜索策略， 如广度优先和深度优先搜索策略。这种情况下，计算时间的耗费通常是可以接受的，因此 在小规模的专家系统中被广泛采用。 一个实际的人工智能系统，它的求解空间一般很大，空间中的每一个结点代表一个求 解的子目标，对于每个子目标，又有多种可供选择的求解方案。因此，在许多情况下采用 盲目搜索策略并不能解决问题，而启发式搜索使用经验的、直观的启发式知识来控制搜索 的方向和路径，在一定程度上克服了搜索的盲目性，求解效率也有了较大的提高。但是目 前基于启发式的各种搜索方法基本上都未能克服计算量的指数爆炸问题。 粒度计算是软计算科学的一个分支，是信息处理的一种新的概念和范式，覆盖了所有 有关粒度的理论、方法、技术和工具的研究。它是词计算理论、粗糙集理论、商空间理论、 区间计算等的超集，目前已成为模糊的、不完整的、不精确的及海量的信息处理的重要工 具和人工智能研究领域的热点之一。 本文提出了一种基于商空间粒度的启发式搜索算法，对启发式搜索过程的粒度原理进 行了深入的讨论与研究。该算法利用商空间的分层思想对问题的求解空间先进行较粗粒度 的划分，根据启发式信息对各个划分进行判断，若某个划分包含问题的解，则对该划分进 行更细粒度的划分，否则放弃对该划分解空间的任何处理，重复上述过程直至找到问题的解 为止。基于这种分层的思想，减少了很多不必要的搜索，从而提高问题求解的效率。这种 算法思想很好地模拟了人类分析和解决问题的过程，即能够从不同的粒度去观察和分析同 一问题，最后综合各个粒度的信息而得到问题的解。在文章的最后，对本文提出的粒启发 式搜索算法进行了验证，实验将其应用于一些边缘信息相对分散的图像进行边缘信息的提 取，获得了比经典算法更好的边缘提取效果。 关键词：商空间；粒度计算；启发式搜索；粒启发式搜索；图像边缘提取； 广东工业大学t 学硕士学位论文 a b s t r a c t s e a r c h i n gt e c h n o l o g yi sab a s i ca n di m p o r t a n tr e s e a r c hf i e l do fa r t i f i c i a li n t e l l i g e n c e ( a i ) a i d e a l s 、析也t h ei n f o r m a t i o nw h i c hi s a l w a y sn o n c o n f i r m e d 、f u z z y 、n o n c o m p l e t e da n d m a s s i v e s og e n e r a l l yi ti sn o ts u r ef o ru st ok n o wt h ew a yf o rp r o b l e ms o l v i n g i n s t e a d ，w e s h o u l ds e a r c ht h ep r o b l e ms p a c et of i n dt h er i g h ta n s w e r s w h e ni ti ss h o r to fn e i g h b o r h o o dk n o w l e d g ea n dt h es c a l eo fp r o b l e mi sn o ts og r e a t ，w ec a n m a k eu s eo fb l i n ds e a r c hs t r a t e g i e ss u c ha sb r e a d t h f u s ts e a r c h 、d e p t h - f i r s ts e a r c he t c i nt h e s e c a s e s ，t h ec o s to ft i m ei sa l w a y sa c c e p t a b l e ，s ob l i n ds e a r c ht e c h n o l o g yi sw i d e l ya d o p t e di n s m a l l - s c a l ee x p e r ts y s t e m s a sar e a la r t i f i c i a li n t e l l i g e n ts y s t e m ，i t sp r o b l e m s o l v i n gs p a c ei sv e r yl a r g e ，a n de v e r yn o d e i nt h es p a c ed e n o t e sa s u b g o a lo fs o l u t i o n s f o re v e r ys u b g o a l ，t h e r ea r es o m es o l v i n gm e t h o d st o s e l e c t s ow ec a n tp r a c t i c a l l ys o l v et h o s ep r o b l e m si fw eu s et h eb l i n ds e a r c hs t r a t e g yi nm a n y c a s e s h e u r i s t i cs e a r c hu s et h ee x p e r i e n c e da n di n t u i t i v ek n o w l e d g et oc o n t r o lt h ed i r e c t i o na n d p a t ho fs e a r c h ，w h i c ho v e r c o m e st h eb l i n d n e s so fs e a r c h i n gt oac e r t a i ne x t e n ta n de n h a n c e st h e s o l v i n ge f f i c i e n c yal o t b u tt h ep r e s e n tv a r i o u sh e u r i s t i c b a s e ds e a r c ha l g o r i t h mh a sb a s i c a l l y n o to v e r c o m et h ec a l c u l a t i o no ft h ei n d e xe x p l o s i v ei s s u e g r a n u l a rc o m p u t i n gi sab r a n c ho fs o f tc o m p u t i n ga n di ti sa l s oae m e r g i n gc o n c e p t u a la n d c o m p u t i n gn o r m a lf o r mo fi n f o r m a t i o np r o c e s s i n g j u s ta sag r e a tu m b r e l l a i tm a yb er e g a r d e da s al a b e lo ft h e o r i e s 、m e t h o d o l o g i e s 、t e c h n i q u e sa n dt o o l st h a tm a k eu s eo fg r a n u l e s g r a n u l a r c o m p u t i n gi sas u p e rs e to ft h et h e o r yo ff u z z yi n f o r m a t i o ng r a n u l a t i o n ，r o u g hs e tt h e o r y , t h e t h e o r yo ft h eq u o t i e n ts p a c ea n di n t e r v a lc o m p u t i n ge t c i tp l a y sa ni m p o r t a n tr o l ei ni n f o r m a t i o n p r o c e s s i n gf o rf u z z y ，u n c e r t a i n t y ，p a r t i a lt r u t h ，m a s sa n dg r a n u l a rc o m p u t i n gi sb e c o m i n go n e o f t h em a i ns t u d ys t r e a mi nai t h i sp a p e rp r o p o s e dah e u r i s t i cs e a r c ha l g o r i t h mb a s e do nq u o t i e n ts p a c e i na d d i t i o n a l ，i t d i s c u s s e da n dr e s e a r c h e dt h eg r a n u l a rp r i n c i p l e so ft h ep r o c e s so fh e u r i s t i cs e a r c hi nd e p t h t h i s a l g o r i t h mm a k e s u s eo fh i e r a r c h i c a lm e t h o dt od i v i d et h es o l v i n gs p a c ei nac o a r s eg r a n u l ef i r s t l y , a n dt h e nj u d g ew h i c hg r a n u l ec o n t a i n st h es o l u t i o nb yh e u r i s t i ci n f o r m a t i o n i fs o ，d i v i d et h e g r a n u l ei nas m a l l e rg r a n u l e ，o t h e r w i s eg i v eu pt od e a lw i t ht h eg r a n u l e r e p e a tt h i sp r o c e s su n t i l f i n d i n gt h er i g h ts o l u t i o n b a s e do nt h i sh i e r a r c h i c a lt h i n k i n g ，t h ea l g o r i t h mr e d u c e dal o to f i i a b s t r a c t u n n e c e s s a r ys e a r c ha n di m p r o v e dt h ee f f i c i e n c yo fp r o b l e ms o l v i n gw h i c hw e l ls i m u l a t e dt h e h u m a na n a l y s i sa n dp r o b l e m s o l v i n gp r o c e s s i no t h e rw o r d s ，i ti sa b l et oo b s e r v ea n da n a l y z e t h es a m ei s s u ei nd i f f e r e n tg r a n u l e sa n ds y n t h e s i sv a r i o u si n f o r m a t i o no fe a c hg r a n u l e so f d i f f e r e n ts i z et og e tt h es o l u t i o n i nt h ee n do ft h i sp a p e r , i tv e r i f i e dt h ea l g o r i t h mb a s e do n g r a n u l a rc o m p u t i n g ，t h ee x p e r i m e n tp r o v e si t sv a l i d i t yi ne d g ei n f o r m a t i o ne x t r a c t i o no ft h e p i c t u r e s i to b t a i n e db e t t e re x t r a c t i o ne f f e c tt h a nt h et r a d i t i o n a lm e t h o d k e yw o r d s ：q u o t i e n ts p a c e ；g r a n u l a rc o m p u t i n g ；h e u r i s t i cs e a r c h ；g r a n u l eh e u r i s t i c a l l y s e a r c h ；e d g ee x t r a c t i o n i i i 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在导师的指 导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，不包含本人或其他用途使用过的 成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明，并表 示了谢意。 本学位论文成果是本入在广东工业大学读书期间在导师的指导下取得的，论文成果妇 广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 5 8 指导教师签 论文作者签 矽蟛年歹月万日 学位论文版权使用授权书 学位论文版权使用授权书 本学位论文作者完全了解有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印、或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适应本授权书) 学位论文作者签名： 签字日期：年月日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期：年月 日 电话： 邮编： 第一章绪论 第一章绪论 粒度计算g r c ( g r a n u l a rc o m p u t i n g ) 是继人工神经网络、模糊集理论、遗传算法、进化算 法等软计算方法的又一种人工智能问题求解方法。它是信息处理的一种新的概念和计算范 式，覆盖了所有有关粒度的理论、方法、技术和工具的研究。它是词计算理论、粗糙集理 论、商空间理论、区间计算等的超集，已成为模糊的、不完整的、不精确的及海量信息处 理的重要工具和人工智能研究领域的热点之一。 本章作为绪论，前面四节介绍本文研究所涉及的内容的概述及研究现状，后两节给出 了本文的主要研究内容及创新之处。 1 1 引言 搜索是人工智能中的一种重要推理技术，也是人工智能问题求解的基本方法之一i l j 。 人工智能所处理的信息通常是不确定的、模糊的、不完整的、海量的，因此一般不能明确 地知道问题求解的途径，需要通过搜索求解的空间才能找到正确的答案。 随着人工智能技术的快速发展，这些年在启发式搜索技术的理论及应用研究方面也取 得了不少进步和成果【2 5 】。经典的启发式搜索算法如最好优先搜索算法和a 算法在八数码等 n p 难题及组合优化等方面等有了一些实际应用，相对于盲目搜索算法在一定程度上提高了 问题的求解效率。张提出的统计启发式搜索算法( 简记为s a ) j 是在p e r l 概率模型的基础上， 利用启发式搜索与统计推断的相似性，将搜索过程看成是一个随机取样的过程，将搜索过 程中搜索方向的选择看成是进行一次统计推断，于是就可以将统计推断中较成熟的理论与 方法移植到启发式搜索中来，提供了一种新的研究工具。该算法在搜索过程中加上一个全 局判断的步骤，而全局判断又是基于统计推断方法，也就是利用搜索空间中不同部分之间 统计量的差异，而不是利用统计量的绝对值，这样就在一定假设下使s a 避免指数爆炸问题。 从某种意义上说，s a 算法是那些经典的启发式搜索算法的改进算法。但是在实际应用中， 很难满足s a 算法所有的约束条件，也就是说s a 算法在实际应用中有很大的局限性。 一个实际的人工智能系统，它的求解空间一般很大，许多情况下采用盲目搜索策略并 不能解决问题，而启发式搜索使用经验的、直观的启发式知识来控制搜索的方向和路径， 广东工业人学t 学硕士学位论文 在一定程度上克服了搜索的盲目性，求解效率也有了较大的提高。但是目前基于启发式的 各种搜索方法基本上都未能克服计算量的指数爆炸问题。因此，研究新的启发式搜索算法 有着重要的理论和现实意义。 粒度计算方法是对人类智能的一种模拟，也是人工智能领域的研究热点之一。它主要 用于处理不确定的、模糊的、不完整的、海量的信息。分层递阶( h i e r a r c h y ) 这一概念正是粒 度计算这一种思维和方法的重要体现，它很早就已经广泛应用到电子信息，自动控制以及 管理决策等学科领域当中。最近，人工智能也开始使用相关的知识，提出了一些新的概念， 例如分层学习( h i e r a r c h i c a ll e a r n i n g ) 、分层规划( h i e r a r c h i c a lp l a n n i n g ) 等等。由于观察问题的 角度和获取对象的特征信息的不同，对复杂对象可按分析问题的需要，将对象简练成若干 个保留重要特征和性能的点，从而便于分析，这种观点就是不同粒度世界的代表。 本课题尝试对商空间粒度原理应用于启发式搜索策略进行研究，生成一种效率较高的 启发式搜索算法，并将其应用于问题求解的相关领域中。 1 2 粒度计算的发展及研究现状 粒度计算是对人类智能的一种模拟，体现了人类从同一问题的不同层次去分析和求解 的特性，现已成为人工智能领域研究的热点之一。2 0 世纪6 0 年代，美国著名数学家z a d e h 提出模糊集合论，在此基础上，于1 9 7 9 年首次提出并讨论了模糊信息粒度化问题，推动 了模糊逻辑理论及其应用的发展，但在当时未引起足够的重视。1 9 9 6 年，z a d e h 又提出 了“词计算理论 【7 】，标志着模糊粒度化理论的诞生。词计算理论的研究主要是为了在利 用自然语言时，进行模糊推理和判断，以实现模糊智能控制。1 9 9 8 年，美国多特蒙德大 学的h e l m u tt h i e l e 教授提出了“词计算理论的语义模型 【8 】，促进了词计算理论的发展。 词计算理论对因特网上的海量信息资源的高效利用有着深远的影响。基于z a d e h 的模糊集 论，进行粒度计算理论和方法的研究，已成为“粒度计算”的重要研究方向之一。 波兰学者p a w l a k 于1 9 8 2 年提出了粗糙集理论【9 】。由于粗糙集理论具有很强的定性分析 能力，能够有效地表达不确定的或不精确的知识，善于从数据中获取知识，并能利用不确 定、不完整的经验知识进行推理等，因此在知识获取、机器学习、规则生成、决策分析、 智能控制等领域获得了广泛应用，特别是在数据挖掘领域，获得了巨大成功，业已成为粒 2 第一章绪论 度计算研究领域的主要方向之一。加拿大r e g i n a 大学教授yy y a o 在研究粗糙集理论的 基础上，提出了基于邻域系统的粒度计算模型【l o 】，并成功应用于知识发现领域。粒度计算 作为专门的术语，首次出现在z a d e h 的文献【1 1 】中。后来，t yl 证、y y y r a 0 和z a d e h 又 在文献【1 2 】中着重描述了粒度计算的重要性，这激发了人们对它的研究兴趣。 在国内，张钹院士和张铃教授提出了基于商空间的粒度计算模型【1 3 1 。在该模型中，用 子集来表示概念，不同粒度的概念就体现为不同粒度的子集，一簇概念就构成空间的一个 划分商空间( 知识基) ，不同的概念簇就构成不同的商空间。而粒度计算问题，也就等 价于研究在给定知识基上的各种子集合之间的关系和转换。对同一问题，可以采取不同的 粒度，通过对不同的粒度的分析，综合获取对原问题的求解。在此基础上，张钹院士和张 铃教授于提出了模糊商空间理论【1 4 】，并将商空间粒度原理应用于运动规划、时间规划等方 面，取得了较大的成功。 随着更多的学者对粒度计算进行深入研究，目前该理论己经成功应用于人工智能研究 领域，并取得了相当显著的成果。目前，在国际上已形成了专门的研究群体，并定期召开 关于粒度计算的国际研讨会。1 9 9 8 年1 0 月在美国n o r t hc a r o l i a n 召开的第六界粗糙集、数 据挖掘及粒度计算国际研讨会“t h es i x t hi n t e r n a t i o n a lw o r k s h o po nr o u g hs e t s ，d a t am i m n g a n dg r a n u l a rc o m p u t i n g ，r s d m g r c 9 8 ”成为首次以粒度计算为主题的国际会议。2 0 0 5 年7 月，在我国的清华大学召开了第一届粒度计算国际研讨会“i n t e r n a t i o n a lc o n f e r e n c eo n g r a n u l a rc o m p u t i n g ，g r c 2 0 0 5 ”，会上分别就什么是粒度计算、粒度计算需要解决的问题、 粒度计算的应用和发展等基本问题展开了研讨。由此可见，粒度计算己成为当前人工智能 领域的研究热点之一。 1 3 粒度计算的研究意义 粒度计算研究的基本问题来源于两个方面：粒度的结构及如何利用粒度来作计算。前 者处理的是粒度的构成、表示和解释，后者处理的是解决问题过程中如何来利用粒度。 关于粒度的计算可以从语义和算法两个角度来进行研究。一方面，人们需要解释粒度之间 不同的关系，如封闭性、依赖性等，并且定义和解释粒度上的操作；另一方面，需要为粒 度计算设计方法和工具，如近似、推理等。 广东工业人学工学硕士学位论文 在人工智能的研究领域中，粒度计算的研究对复杂的人工智能系统的设计和实现有着 深远的影响。自1 9 6 5 年人工智能a i 问世以来，它在知识表示、推理方法、机器学习和专家 系统等领域取得了一些进展，但是面对复杂的智能系统的设计和模糊的、不精确的、不完 整的和海量的信息的处理，人工智能的传统理论和方法遇到了前所未有的困难。众所周知， 智能模拟是获得人工智能、实现智能控制的重要途径。人工智能的发展还有待于进一步理 解人类智能的机制。人类智能的一个公认特点，就是人们能从极不相同的粒度( g r a n u l a r i t y ) 上观察和分析同一问题。人们不仅能在不同粒度的世界上进行问题求解，而且能够很快地 从一个粒度世界跳到另一个粒度世界，往返自如，毫无困难。这种处理不同粒度世界的能 力，正是人类问题求解的强有力的表现。如何根据问题求解的需要选择合适的粒度，不同 粒度世界之间又如何转换等问题对于现有的问题描述方法，诸如状态空间法、问题归约法 以及其它表达方法都难以奏效，我们缺少描述不同粒度世界的手段。如果能够把人类的这 种能力形式化，并使计算机也具备类似的能力，这对于机器智能的开发意义重大。 从优化论的角度来看，优化论是软计算科学的核心内容，虽然经典的优化理论在生产 计划与调度、交通运输、商业运作、金融管理等领域的应用有数不清的成功实例，但随着 信息科学的迅猛发展，现代系统越来越复杂、信息系统常常包含着海量的、不完整、模糊 及不精确的数据或对象，常常使得传统的数学优化方法显得无能为力，例如，运筹学。这 是因为传统的优化方法往往要求目标函数是凸的、高阶连续可微的及可行域是凸集，这大 大限制了其应用范围，而且其处理非确定性信息的能力很差。因此，探寻能够有效处理模 糊的、不完整的、不精确的及海量的信息，且具有智能特征的优化方法成为优化理论的发 展趋势。粒度计算的理论与方法在观念上突破了传统优化思想的束缚，不再以数学上的精 确解为目标，即：需要的是很好地理解和刻画一个问题，而不是沉溺于那些用处不大的细 节信息上，这是观念上的创新，非常有价值。粒度计算的方法不要求目标函数和约束函数 的连续性与凸性，甚至有时连有没有解析表达式都不要求，而且对计算中数据的不确定性 也有很强的适应能力，计算速度也快，这些优点使粒度计算具有更广泛的应用前景，所以， 粒度计算理论的研究对推动优化理论的发展极其重要。 从问题求解的角度看，现实世界的许多复杂问题的求解过程中，常常需要将问题分解 为更小、更易处理的一系列子任务。在这里，粒度计算能够作为处理上述任务的有效工具 ( 或模型) 。 4 第一章绪论 从应用技术的角度看，图像处理、语音与字符识别等，是计算机多媒体的核心技术。 这些信息处理质量的好坏直接依赖于分割的方法和技术，基于聚类算法、小波分析、分形 分维、灰度等分割技术的方法在静态数据的处理方面取得了丰硕的成果。但随着应用的发 展，迫切需要能够快速实现、处理动态数据的分割方法与技术，粒度计算的研究或许能够 解决这一问题。总之，信息科学的发展需求是研究粒度计算的最根本的动机。 1 4 粒度计算的研究模型 人们在处理问题或描述问题时，都是在大量的信息中进行的。所谓信息粒度( i n f o r m a t i o n g r a n u l e ) 就是人类在处理问题时把信息按其各自的特征进行划分成若干块，这些块被看成 一个信息粒度。对粒度的研究，就是取不同大小的块，也就是说，将原来“粗粒度”的大 块分割为若干“细粒度”的小块，或者把若干小块合并成一个大的块进行研究。 模糊粒度计算是一种在不精确和部分真值的环境中做出合理决策的方法。粒度计算目 前有三个主要的模型和方法：一是z a d e h 的“词计算理论 ( t h e o r yo fw 6 r d sc o m p u t i n g ) ， 一是p a w l a k 的“粗糙集理论”( t h e o r yo f r o u g hs e t ) ，一是张铃教授与其合作者提出的“商 空间理论 ( t h e o r yo f q u o t i e n ts p a c e ) 。张铃教授1 6 1 和张燕平博士【1 刀对三者的关系进行了比 较和讨论。 1 4 1z a d e h 的模糊集理论模型 z a d e h 于1 9 6 5 年提出了模糊集合论【1 8 】，创造了“隶属度”这一概念来描述事物的模糊性， 提出用f u z z y 集及其运算来描写、刻画和表达f u z z y 事物及其模糊性，并在其一系列文献i l 她副 中讨论模糊信息粒度理论时，提出人类认知的三个主要概念：粒度( g r a n u l a t i o n ) 、组织 ( o r g a n i z a t i o n ) 和因果( c a u s a t i o n ) ，并认为模糊数学是粒度计算的主要工具之一。粒度包括将 全体分解为部分，组织包括从部分集成为全体，因果包括因果的关联。他认为粒度计算是 模糊信息粒度理论的超集，而粗糙集理论和区间计算是粒度数学的子集，指出粒度计算是 一把大伞它覆盖了所有有关粒度的理论、方法论、技术和工具的研究。z a d e h 的工作激起 了学术界对粒度计算研究的兴趣，yy y a o 和他的合作者对粒度计算进行了一系列的研究 1 2 3 - 2 6 ，并将其应用于数据挖掘等领域，其工作的要点是用决策逻辑语言( d l 语言) 来描述集 广东t 业大学工学硕士学位论文 合的粒度( 用满足公式元素的集合来定义等价类聊( ) ) ，建立概念之间的矿一k e n 关系与 粒度集合之间的包含关系的联系，并提出利用由所有划分构成的格来求解一致分类问题。 这些研究为知识挖掘提供了一些新的方法和思路。 z a d e h 的词计算理论认为人类在进行思考、判断、推理时主要是用语言进行的，而语言 是一个很粗的“粒度 ，即无法用精确的分类标准做出明确肯定的断言，比如说“这个人 很年轻”，其中“很年轻 这个词就比较“笼统”，就把这种“笼统”称为模糊i 生( f u z z y n e s s ) ， 模糊集理论正是这样描述模糊性的，他利用语言进行推理判断，这就是“词计算”的雏型。 沿模糊集论的方向，用模糊数学的方法进行有关粒度计算的方法和理论的研究，就构成“粒 度计算 的一个非常重要的方法和方向，这也是人们比较熟悉的一个方法。 其模型为：设x 为论域u 的可变值，x 值上的一个普遍约束可以被表示为x 衙r ， 这里尺是一个约束关系，衙是一个可变的连接词，r 是个具体的变量，它的值确定了尺用 什么方法来约束x 。约束的例子有相等约束、可能性约束、模糊约束等。例如，一个相等 约束：，= e ，若xd ea ，即表示x = 口。 1 4 2r o u g h 集 为了识别事物，人们总是依据一定的标准对他们进行分类，分类是人类认识世界的基 本能力。波兰学者p a w l a k 在粗糙集理论中提出一个假设【9 】：人的智能( 知识) 就是一种分类的 能力。这个假设可能不是很完备，但却非常精练。在此基础上，他用论域中的子集来表示 概念，于是在论域中给定一组子集族，或说给定一个划分( 所谓划分，是指将x 分成两两 不相交的子集之并) 。在数学中，每个个体与某种块的族结合在一起构成了一个邻域系统， 如果一个邻域系统的所有块都是非空的，则这个邻域系统是一个覆盖；如果全体块族形成 一个划分，则这个邻域系统便规约到r o u 曲集系统。 从数学上知道，给定x 上的一个划分，等价于在z 上给定一个等价关系r 。p a w l a k 称 之为在论域上给定了一个知识基( x ，r ) 。然后讨论一个一般的概念x ( x 中的一个子集) ， 如何用知识基中的知识来表示，就是用知识基中的集合的并来表示。对那些无法用( x ，r ) 中的集合的并来表示的集合，他借用拓扑中的内核和闭包的概念，引入r 一下近似r 一( x ) ( 相 当于x 的内核) 和r 一上近似r 一( x ) ( 相当于x 的闭包) ，当r 一( x ) r 一( x ) 时，就称x 为粗糙集， 即把那些无法确认的个体都归属于边界区域，而这个边界区域被定义为r 一( x ) 一r 一( x ) ，从 6 第一章绪论 而创立了“粗糙集理论 。r 一( x ) 和r 一( x ) 都可以通过等价关系给出的数学公式确切地计算， 因而，边界区域的模糊元素数目也就可以确切地计算。 粗糙集理论是一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法， 目前粗糙集理论在理论模型、算法研究、工程应用等领域取得了较好的成果和应用，尤其 是机器学习、模式识别、模糊控制、数据挖掘和知识获取等领域取得较大的成功，文献1 2 7 与粗糙集理论应用专集【2 8 】较好地总结了这一时期的研究成果，现已成为学习和应用模糊集 理论的重要文献，国内的一些学者在这方面也有一些研究工作【2 9 11 3 0 。运用粗糙集理论求解 问题的一个特点是不需要预先给定某些特征或属性的数量描述，如统计学中的概率分布、 模糊集理论中的隶属度或隶属函数等，而是直接从给定问题的描述集合出发，通过不可分 辨关系和不可分辨类确定给定问题的近似域，从而找出该问题中的内在规律【3 。 1 4 3 商空间理论 基于商空间理论【3 2 】的粒度计算认为概念可以用子集来表示，不同粒度的概念就体现为 不同粒度的子集，一簇概念就构成空间的一个划分商空间( 知识基) ，不同的概念簇就 构成不同的商空间。故粒度计算，就是研究在给定知识基上的各种子集合之间的关系和转 换，以及对同一问题，取不同的适当的粒度，从对不同的粒度的研究中，综合获取原问题 的解。它将原来的空间分成粒度粗细不同的空间，这与数学中的“划分( p a r t i t i o n ) 概念完 全吻合，而数学上“划分”与“等价关系”是等价的，故“等价关系就成为建立商空间 理论的一个基本概念。这种对粒度的理解与模糊集对粒度的理解不完全一样。 按照z a d e h 粒度计算的定义，商空间理论和粗糙集理论都属于“粒度计算 范畴，粗糙 集和商空间讨论的粒度是“清晰的粒度”，而他自己讨论的是“模糊粒度”。在模型上，三 者都是描述人类能按不同粒度来处理事物的能力的模型。商空间理论、粗糙集理论、模糊 集理论都将所讨论的对象的集合构成论域，但讨论对象之间的关系时，却各有不同。 商空间理论、粗糙集理论认为概念可以用子集来表示，不同粒度的概念可以用不同大 小的子集来表示，所有这些表示可以用等价关系来描述。模糊集理论认为概念是用“词 来表示，而描述“词”的有效的方法就是模糊集理论。 总之，从以上简单的比较商空间理论、模糊集、粗糙集等粒度计算方法之间的关系， 可以看出这三个不同的粒度计算理论，从思考问题的出发点和解决问题的任务，不是互相 7 广东工业大学工学硕一l ：学位论文 冲突，而是互相补充的，他们对于模糊信息的处理有各自独立的方法。三者都有一个共同 的特点，那就是都考虑到人类智能中，有从不同粒度思考问题的这一特点。如何将三者的 优点结合起来，形成更强有力的粒度计算的方法和理论，是今后一个重要的研究课题。 1 5 本文研究的主要内容 1 5 1 本文的主要研究内容 本文的主要研究内容包括： 1 建立基于商空间的粒度计算的启发式搜索模型； 2 基于商空间的启发式搜索算法的研究； 3 粒启发式搜索算法在实际应用中的效果验证。 1 5 2 预期目标 1 提出基于商空间的启发式搜索算法； 2 对本文提出豹新算法进行验证，并证明该算法的有效性。 1 5 3 关键技术 1 基于商空间的粒度计算模型及相关理论； 2 将粒度计算的思想应用于启发式搜索技术。 1 6 本课题的创新之处 1 本课题建立在粒度计算的理论基础上，从模拟人类智能的机制的角度出发，是一种 人工智能中求解问题的全新的研究方法。 2 本课题和传统的启发式搜索方法不同，基于商空间粒度原理的启发式搜索算法首先 对问题空间先进行较粗的分层( 粒度化) ，从划分的等价类中获取对问题求解有用的等价 类( 即包含问题的解的等价类) ，再把有用的等价类进行更细粒度的划分，直至找到问题的 解，这种搜索算法避免了经典的搜索算法中基于遍历所有可能解的思想，降低了搜索量。 8 第二章人工智能问题求解技术 2 1 引言 第二章人工智能问题求解技术 “a ii sb a s i c a l l yp r o b l e ms o l v i n gu s i n gc o m p u t e r sa n di n t e l l i g e n tm e t h o d s 。a tt h eh e a r to f m a n ya is o l u t i o n si st h ec o n c e p to fas t a t e - s p a c ea n do p e r a t o r sw h i c ht r a n s f o r mo n es t a t ei n t o a n o t h e r t h ef u n d a m e n t a la p p r o a c ho fs t a t e s p a c ep r o b l e ms o l v i n gi st or e p r e s e n tt h ep r o b l e ma s ag r a p ho rt r e es t r u c t u r e ( t h es t a t e s p a c e 、a n dp e r f o r ma ni n t e l l i g e n ts e a r c ho fs t a t e s t h et w ok e yi n g r e d i e n t st oa u t o m a t dp r o b l e ms o l v i n ga r er e p r e s e n t i n ga n d s e a r c hm a n y p r a c t i c a lp r o b l e m sc a nb ef o r m u l a t e do rr e p r e s e n t e di ns t a t e s p a c eo rg r a p hf o r m ”【3 3 】 上面这两段话清楚地说明了状态空间和搜索算法在人工智能中的重要地位，人工智能 问题求解的过程，简单来说就是：把实际问题表示成计算机能处理的形式，然后在此形式 上进行搜集，最后给出解。 2 2 状态空间 问题求解( p r o b l e m s o l v i n g ) 是个大课题，它涉及归约、推断、决策、规划、常识推理、 定理证明和相关过程的核心概念。在分析了人工智能研究中运用的问题求解方法之后，就 会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能 的解空间内寻找一个解来求解问题的。这种基于解空间的问题表示和求解方法就是状态空 间法。它是以状态和算符为基础来表示和求解问题的。其中，“状态用以描述问题求解 过程中不同时刻的状况：“算符”表示对状态的操作，“算符”的每一次使用就使问题由一 种状态变换为另一种状态。当到达目标状态时，由初始状态到目标状态所用算符的序列就 是问题的一个求解路径。 状态空间搜索的基本思想是：首先把问题的初始状态( g o 初始结点) 作为当前状态，选择 适用的“算符 对其进行操作，生成一组子状态( 或称后继状态、后继结点、子结点) ，然 9 后检查目标状态是否在其中出现。若出现，则搜索成功，找到了一个状态作为当前状态。 重复上述过程，直到目标状态出现或不再有可供操作的状态及“算符时为止。状态空间 的搜索示意图如下图2 1 所示： 铆 c f 置卷啦 状卷中n d 搜嚷申i j j 【j b ：状急m r 一一 匕j 於 - l 一 解挥路径 图2 - 1 状态空间搜索示意图 f i g 2 1s t a t e s p a c es e a r c hs k e t c h 在图2 1 中，矩形内是问题所涉及到的所有可能的状态集。矩形的上边是初始状态集， 矩形的下边是目标状态集。由初始状态到目标状态要找到一条解答路径，需采用搜索技术。 在搜索中所涉及到的状态集( 图中的画斜线部分) 称为搜索空间。我们的目标是在能保证找 到最优的解答路径的同时，尽可能的减小搜索空间，从而减少搜索代价。 2 3 一般搜索原理 搜索的方法有很多【1 1 ，比如宽度优先搜索、深度优用搜索等，它们均属于盲目搜索方 法，或者叫做无信息搜索，一般适用于求解比较简单的问题。盲目搜索是按规定的控制策 略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。由于搜索总是按照规定 的路线进行，没有考虑到问题本身的特性，所以具有盲目性，效率低，耗费过多的计算空 间与时间，不便于复杂问题求解。在盲目搜索中找到一个解，所需要扩展的结点数目可能 是很大的，这些结点的扩展次序完全是随意的，没有利用已解决问题的任何特性，因此除 了那些最简单的问题之外，一般都要占用很多时间或空间( 或者两者均有) 。 1 0 第二章人工智能问题求解技术 一种更有效率的搜索方法是启发式搜索( h e u r i s t i cs e a r c h ) 或有信息搜索( i n f o r m e d s e a r c h ) 。有关具体问题领域的信息常常可以用来简化搜索，我们假设，初始状态，目标状 态、动作都是完全确定的，然后决定了一个状态搜索空间，剩下的问题就是如何有效地搜 索这个给定的状态空间。 2 4 启发式搜索理论 要在盲目搜索中找到一个解，所需要扩展的结点数目可能是很大的。因为这些结点的 扩展次序完全是随意的，而且没有利用已解决问题的任何特性。因此，除了那些最简单的 问题之外，一般都要占用很多时间或空间( 或者两者均有) 。这种结果是组合爆炸的一种表 现形式。 启发式搜索是在搜索中加入了与问题相关的启发性信息，用以指导搜索沿着最有希望 的方向前进，加速问题的求解过程并找到最优解。这种搜索针对性强，因而原则上只需要 搜索问题的部分状态空间，效率高。 2 4 1 启发式信息和估价函数的设计 用于指导搜索过程，且与具体问题求解有关的控制性信息称为启发性信息。在启发式 搜索技术中，启发信息按其用途可以分为下列3 种： ( 1 ) 用于决定要扩展的下一个结点，以免像在宽度优先或深度优先搜索中那样盲目地扩 展。 ( 2 ) 在扩展一个结点的过程中，用于决定要生成哪一个或哪几个后继结点，以免盲目地 同时生成所有可能的结点。 ( 3 ) 用于决定某些应该从搜索树中抛弃或修剪的结点。 在搜索过程中，关键的一步是如何确定下一个要考察的结点，确定的方法不同就形成 了不同的搜索策略。如果在确定结点时能充分利用与问题求解有关的特性信息，估计出结 点的重要性，就能在搜索时选择重要性较高的结点，以利于求得最优解。用于估价结点重 要性的函数称为估价函数( 评价函数) ，其一般形式为：f ( x ) = g ( x ) + h ( x ) ，其中g ( x ) 为从 初始结点& 到结点x 已经实际付出的代价：h c x ) 是从结点x 到目标结点瓯的最优路径的估 广东丁业大学t 学硕士学位论文 计代价，它体现了问题的启发性信息，其形式要根据问题的特性确定。例如，它可以是结 点x 到目标结点的距离，也可以是结点x 处于最优路径上的概率等。h ( x ) 称为启发函数。 设计评价函数是使用搜索技术的关键，我们应充分利用启发式知识，设计比较优秀的 评价函数，尽可能的减少搜索代价，找出最优解( 最小路径代价) 。但是，由于我们要解决 的是难题，就是专家也会头痛的问题，一般没有算法解，想找到优秀的评价函数谈何容易。 如果因为找不