论文部分内容阅读
粒计算是研究如何在问题求解过程中使用人类“粒度”和“粒”的思想的一门新兴学科,致力于探索基于粒度的理论、技术和工具,在过去十年中,它得到了很多研究者的关注。粒计算三元论提倡将各个学科的粒化思想进行整理、抽象和整合,从而获得与具体领域无关的粒计算原理。粒计算三元论以粒结构为核心,对粒计算进行结构化思维、结构化问题求解和结构化信息处理三方面的研究。粒结构是由粒、层次、分层结构、多个分层结构组成的结构模型,它最主要的特点是多层次和多视角。对粒结构本身的特征、属性、构建和应用的研究试图从各个领域的结构中提取共性,将特定领域中隐含的结构明确化,探索领域通用的结构模型,是对粒计算研究的新尝试。 本文基于粒计算三元论,用图论的方法对粒结构展开研究。主要围绕粒结构组成成分的分析、粒结构模型的建立、利用粒结构模型进行问题求解和信息处理这条主线,提出了基于图的粒结构,讨论了图的粒化方法,并将基于图的粒结构推广到基于超图的粒计算模型,给出了利用粒结构进行问题求解的基本策略。最后,作为对前几部分内容的一个综合应用实例,本文将基于图的粒结构应用在城市交通问题当中,试图对城市交通拥堵的表示、分析和预警提供新的解决途径。 图论是在信息处理领域受到广泛使用的工具。很多现实问题由图表示非常形象直观,并且用图论的方法来处理十分有效,因此图已经成为一些问题的最佳抽象数学模型。以往将图与粒结构结合的研究并不多,本文用图论的方法构建粒结构为粒计算的研究增添了新方法和新途径。基于图的粒结构既是对粒结构的形式化表示和描述,也有利于探索图中隐藏的复杂结构,同时,它能够使粒计算中的集合方法与基于图的算法有效结合,为针对具体问题的粒结构构建以及应用粒结构进行信息处理和问题求解提供具体的方法和工具。 本文的创新工作主要有: 1)本文用图论的方法研究粒结构模型。针对基于图的粒结构构建问题,定义了图中的粒、层次、粒结构;给出了粒与粒之间、层次与层次间关系的衡量方法;讨论了粒结构的粒度测度和代数结构;并给出了对粒和层次的四种运算。通过层次问关系的定义,可以比较不同层次的粒度粗细;通过对粒和层次的四种运算,可以实现粗粒度与细粒度层次之间的转换。从粒计算三元论的角度考虑,本部分内容侧重于结构化的信息处理。 2)在粒结构的研究中,我们发现对边以及图中特定结构的粒化在很多实际问题中有重要作用。虽然有时候可以采用将边转换为点、点转换为边的方法来借用对点粒化的方法研究边,但很多时候这种转换并不方便。针对基于图的粒结构中单个层次的粒化问题,本文提出了对图中三种对象点、边和结构分别粒化的概念,并总结了面向点的粒化方法,提出了面向边的两种粒化方法。从粒计算三元论的角度看,本部分内容属于对结构化信息处理的研究。 3)针对基于粒结构的问题求解,本文将基于图的粒结构扩展为基于超图的粒计算模型。基于超图的模型表达能力和描述能力更强,并能够将超图特有的一些理论和算法作为工具来建立结构。本文探讨了利用粒计算模型进行多粒度问题求解的基本策略,提出了基于粒计算模型的逐层粗化与逐层细化渐进计算算法。从粒计算三元论的角度考虑,本部分内容强调的是结构化的问题求解。 4)粒计算的理论、技术和方法总的来说应用范围还不广,粒结构的研究也刚刚起步,还没有太多应用。针对粒结构的应用问题,本文将基于图的粒结构应用在城市交通拥堵问题中。作为粒结构应用的实例,探索对城市交通拥堵情况的多粒度分析、表示和预警,试图对应用粒结构解决实际问题,拓广粒结构的应用范围作出尝试,为应用粒结构解决其他问题提供启发。 总结以上创新工作,本文主要贡献可以归纳为: 1)建立了基于图的粒结构模型,给出了模型中粒、层、结构的定义、关系、度量和运算; 2)提出了对图的点、边、固定结构三种对象粒化的概念,总结了对点粒化的方法,给出了对边粒化的方法; 3)将基于图的模型扩展为基于超图的粒计算模型,并给出基于模型的多粒度问题求解方法; 4)将基于图的粒结构应用在城市交通拥堵问题中,给出了基于粒结构的多粒度拥堵分析、表示和预警方法。