—个求解层次图边交叉数最小化问题的遗传算法

最小化边交叉数是层次图绘制过程中的一个关键步骤，直接影响着层次图的可读性。提出了一个基于遗传算法的层次图边交叉数最小化算法，详细地给出了编码表示方法以及遗传算子的设计。与常用的启发算法相比，该算法得到了更好的计算结果，此外算法简单且易于实现。     

关系图文法及其应用

字符串文法不适于描述二维以上事物的特征，无法定义事物之间的复杂关系．本文提出了关系图的概念，对关系图的性质进行了研究．在此基础上提出了一种新的文法——关系图文法．该文法能够方便地抽象和概括二维以上复杂对象的特征，为分析和识别这些对象提供工具和方法，可以广泛应用于模式识别、高维文本分析和描述图示语言的语法等领域．为了使关系图文法实用化，本文还提出了相应的识别和匹配算法.     

一个求解层次图边交叉数最小化问题的遗传算法

最小化边交叉数是层次图绘制过程中的一个关键步骤,直接影响着层次图的可读性。提出了一个基于 遗传算法的层次图边交叉数最小化算法,详细地给出了编码表示方法以及遗传算子的设计。与常用的启发算法 相比,该算法得到了更好的计算结果,此外算法简单且易于实现。     

地理实体概念及其位置关系的获取和验证

文本知识获取（Knowledge acquisition from text，简称KAT）是知识工程中的一个重要研究课题。重点研究如何从大规模Web网页文本中获取地理实体概念及其位置关系知识，本文首先介绍了如何自动和半自动地获取这些地理实体概念及其位置关系的文法模式，建立文法模式库；然后基于文法模式库获取例句来抽取候选概念并进行概念验证；最后利用基于图论的方法构造位置关系图，利用地理领域特定规则进行分析验证。作为统一概念图管理下概念空间的一个重要组成部分，地理实体概念及其位置关系本身不仅是知识库的一个重要部分，还可为知识库中其它领域的知识提供支持。     

图文法EGG在设计模式中的应用

对图变换和可视化语言的研究激发并促进了图文法的研究和发展。作为一维字符文法的扩展,图文法可以形式化描述二维空间中的对象,如图像、图形和表格等,为它们的定义、生成、变换及分析提供理论和技术上的支持。设计模式是可复用面向对象软件的基础,通常以二维图的形式来表示。为了与用户多样化的需求相适应,设计模式经常需要在不改变系统基本结构的情况下进行演化。本文讨论了图文法EGG及其形式化方法在设计模式的演化中的应用,聚焦在图变换和图解析两方面。前者用EGG格式的产生式作为图重写式来指导图的每一次变换,以确保相应设计模式演化每一步的正确性;后者用EGG文法机制来对图进行归约,以检查随意演化后的设计模式是否合法。     

上下文相关图文法分析及其应用初探

图文法是一种对可视化语言进行形式化定义的元语言，具有表达自然、能力强大的特点.随着使用可视化语言的最终用户编程技术的广泛应用，图文法分析尤其是上下文相关图文法分析在工程应用中的重要性日益突出.国内外相关文献或着重于纯理论探讨，或局限于特定语法类的特定应用，不利于工程应用人员参考.本文选取简洁明了的符号体系，介绍上下文相关图文法分析的一般性过程，并将其中规则选取关键步骤描述为CSP问题，利用已有的针对CSP问题的优化方法来优化算法，介绍了现有的优化方法并给出实现算法;同时，结合自身实践，讨论其在一个面向体系结构的Web服务集成系统中的应用.     

软件图语言的形式描述

本文从语言学和形式化角度对软件领域中广泛使用的软件图进行了研究，提出了软件图语言这一概念。本文首先提出了关于软件图语言的一组基本概念，其次研究软件图语言的同态和同构，以构成软件图形式描述的基础；最后讨论了软件图语言的形式表示法，并提出了基于图符网的文法，使图文法更适合于表示软件图语言。本文工作可以作为设计面向软件图语言的软件工具的基础。     

可视化语言技术在软件开发中的应用

可视化语言技术比一维文本语言在描述软件组成方面具有优越性.由于图表和图形概念在系统建模中的广泛使用,可视化语言可以应用于需求分析、设计、测试和维护等软件开发的各个阶段.除了具有直观易见的特点之外,图文法在计算机上的精确建模和验证能力,为设计可视化语言提供了一个坚实的理论基础.讨论了可视化语言的形式理论基础,回顾了相关的可视化图形编程环境.特别提出了一种空间图文法,并且用该图文法定义了统一建模语言的行为语义.基于空间图文法,开发了一种基于模式驱动的框架,以帮助软件架构与设计.     

遗传算法机理的研究及应用

在介绍遗传算法的基本理论及主要特点的基础上，针对遗传算法的设计机理和步骤，从设计遗传算法的基本原则、设计遗传算法的基本步骤、常用的编码表示方案、适应性的度量、选择策略及控制参数的选取等诸方面进行了阐述和分析，并结合计算机布局问题，提出了一个基于模拟退火算法的混合遗传算法，结合实例进行了计算机仿真，验证了该算法的有效性。     

vCGG:一种基于虚结点的空间图文法形式框架

作为一种二维的形式化方法,图文法为可视化语言提供了直观而规范的描述手段.然而,大多数图文法形式框架在空间语义处理能力方面有所不足,影响了图文法的表达能力及其实际应用范围.针对现存的问题,构建了一种新型空间图文法形式框架vCGG （virtual-node based coordinate graph grammar）.区别于其他空间图文法,vCGG在产生式中通过定义虚结点的概念描述产生式与主图之间的语法结构与空间语义关系,在保留抽象能力的同时,提高了其空间语义配置性能.通过与几种典型空间图文法框架比较,vCGG形式框架在直观性、规范性、表达能力以及分析效率方面均有着较好的表现.     

教育测评知识图谱的构建及其表示学习

知识图谱旨在描述现实世界中存在的实体以及实体之间的关系.自2012年谷歌提出“Google Knowledge Graph”以来，知识图谱在学术界和工业界受到广泛关注.针对教育领域中信息缺乏系统性组织的不足，本文构建了面向高中的教育测评知识图谱（Educational Assessment Knowledge Graph，EAKG），其中EAKG的构建包括基于本体技术的知识图谱模式层构建和依托于模式层结构的知识图谱数据层构建.与传统通过网页爬虫等技术手段构建的知识图谱相比，本文构建的知识图谱优点在于逻辑结构清晰，实体间关系的刻画遵循知识图谱模式层的定义.EAKG为领域内知识共享，知识推理，知识表示学习等任务提供了良好的支撑.在真实模考数据上的实验结果表明：在试卷得分预测，知识点得分预测的实体链接预测和三元组分类嵌入式表示学习任务上，引入领域本体作为模式层构建的EAKG的性能优于没有领域本体模式层单纯由数据事实构成的EAKG，实验表明，领域本体的引入对知识图谱的表示学习具有一定的指导意义.     

A genetic algorithm for multiprocessor scheduling

The problem of multiprocessor scheduling can be stated as finding a schedule for a general task graph to be executed on a multiprocessor system so that the schedule length can be minimized. This scheduling problem is known to be NP-hard, and methods based on heuristic search have been proposed to obtain optimal and suboptimal solutions. Genetic algorithms have recently received much attention as a class of robust stochastic search algorithms for various optimization problems. In this paper, an efficient method based on genetic algorithms is developed to solve the multiprocessor scheduling problem. The representation of the search node is based on the order of the tasks being executed in each individual processor. The genetic operator proposed is based on the precedence relations between the tasks in the task graph. Simulation results comparing the proposed genetic algorithm, the list scheduling algorithm, and the optimal schedule using random task graphs, and a robot inverse dynamics computational task graph are presented     

基于循环冗余校验的动态图软件水印方案*

针对动态图编码时间复杂度较高的问题,提出一种四进制编码方案,利用空间换时间的思想,通过增加两个专门用来编码系数的指针域,在空间复杂度不变的情况下,降低构造水印图的时间复杂度。同时借鉴计算机网络和数据通信的差错检验原理,提出一种基于循环冗余校验的动态图软件水印防窜改技术,实现了水印图的动态验证。实验表明,该方案提高了水印数据率,增强了水印抗攻击性,并使之具有一定的纠错能力。     

Graph grammars for evolutionary 3D design

A new interactive evolutionary 3D design system is presented. The representation is based on graph grammars, a fascinating and powerful formalism in which nodes and edges are iteratively rewritten by rules analogous to those of context-free grammars and shape grammars. The nodes of the resulting derived graph are labelled with Euclidean coordinates: therefore the graph fully represents a 3D beam design. Results from user-guided runs are presented, demonstrating the flexibility of the representation. Comparison with results using an alternative graph representation demonstrates that the graph grammar search space is more rich in organised designs. A set of numerical features are defined over designs. They are shown to be effective in distinguishing between the designs produced by the two representations, and between designs labelled by users as good or bad. The features allow the definition of a non-interactive fitness function in terms of proximity to target feature vectors. In non-interactive experiments with this fitness function, the graph grammar representation out-performs the alternative graph representation, and evolution out-performs random search.     

一种基于模式分析的防止遗传算法过早收敛的方法

本文提出一种遗传算法中模式的表示方法和个体间最大共有模式的获取方法,并以此为基础提出了基于模式分析的种群插入策略来解决遗传算法过早收敛问题.通过与其他种群插入算法的对比证明该 方法的有效性.给出了采用该种群插入策略的遗传算法的收敛性定理及其证明.     

Semantic schema modeling for genetic programming using clustering of building blocks

Semantic schema theory is a theoretical model used to describe the behavior of evolutionary algorithms. It partitions the search space to schemata, defined in semantic level, and studies their distribution during the evolution. Semantic schema theory has definite advantages over popular syntactic schema theories, for which the reliability and usefulness are criticized. Integrating semantic awareness in genetic programming (GP) in recent years sheds new light also on schema theory investigations. This paper extends the recent work in semantic schema theory of GP by utilizing information based clustering. To this end, we first define the notion of semantics for a tree based on the mutual information between its output vector and the target and introduce semantic building blocks to facilitate the modeling of semantic schema. Then, we propose information based clustering to cluster the building blocks. Trees are then represented in terms of the active occurrence of building block clusters and schema instances are characterized by an instantiation function over this representation. Finally, the expected number of schema samples is predicted by the suggested theory. In order to evaluate the suggested schema, several experiments were conducted and the generalization, diversity preserving capability and efficiency of the schema were investigated. The results are encouraging and remarkably promising compared with the existing semantic schema.     

XML-based genetic programming framework: design philosophy, implementation, and applications

We present the design philosophy, implementation, and various applications of an XML-based genetic programming (GP) framework (XGP). The key feature of XGP is the distinct representation of genetic programs as DOM parsing trees featuring corresponding flat XML text. XGP contributes to the achievements of: (i) fast prototyping of GP by using the standard built-in API of DOM parsers for manipulating the genetic programs, (ii) human readability and modifiability of the genetic representations, (iii) generic support for the representation of the grammar of a strongly typed GP using W3C-standardized XML schema; (iv) inherent inter-machine migratability of the text-based genetic representation (i.e., the XML text) in the distributed implementations of GP.     

概率关系模式与概率XML模式转换算法的研究*

通过比较基于可能世界模型的概率数据在关系数据模型和XML数据模型中的表示方法,根据概率属性与普通属性的关系把概率关系模式分为1NF和3NF,根据分布节点与普通节点的关系把概率XML模式也分为1NF和3NF,以扩展的概率DTD文件为例设计了概率关系模式和概率XML模式之间的转换算法。实例分析结果表明该算法是有效的,也为现存的概率关系数据与概率XML数据之间提供了一种有效的模式转换方法。     

基于属性文法和语义网络的综合知识表示模型

本文提出了一个属性文法计算模型与语义网络表示模型相结合的综合知识表示模型.根据形式化的语义网络表示模型和属性文法的特点,该模型使用属性文法的符号建立了一些适合于语义网络表示模型的语法和语义规则模式,并且可通过扩充的属性文法的解释器来实现推理.     

Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools

Several grammar-based genetic programming algorithms have been proposed in the literature to automatically generate heuristics for hard optimization problems. These approaches specify the algorithmic building blocks and the way in which they can be combined in a grammar; the best heuristic for the problem being tackled is found by an evolutionary algorithm that searches in the algorithm design space defined by the grammar.In this work, we propose a novel representation of the grammar by a sequence of categorical, integer, and real-valued parameters. We then use a tool for automatic algorithm configuration to search for the best algorithm for the problem at hand. Our experimental evaluation on the one-dimensional bin packing problem and the permutation flowshop problem with weighted tardiness objective shows that the proposed approach produces better algorithms than grammatical evolution, a well-established variant of grammar-based genetic programming. The reasons behind such improvement lie both in the representation proposed and in the method used to search the algorithm design space.