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.     

进化算法中的模式定理及建筑块

探讨了进化算法中的模式定理及建筑块理论．通过引入模式进化、模式进化能力、适度模式等概念，以标准遗传算法为例，证明了在变异算子独立的条件下，进化算法中模式的构成与多点交叉和变异的顺序无关，然后证明了具有强进化能力的模式，将以指数阶增长．该文的模式理论有别于Holland等人提出的模式理论，特别是在交叉算子上采用了多点交叉算子，给出了相应的公式；并从这一推导过程论证了建筑块假设的合理性，可以称之为建筑块理论．     

Schema theory for genetic programming with one-point crossover and point mutation

We review the main results obtained in the theory of schemata in genetic programming (GP), emphasizing their strengths and weaknesses. Then we propose a new, simpler definition of the concept of schema for GP, which is closer to the original concept of schema in genetic algorithms (GAs). Along with a new form of crossover, one-point crossover, and point mutation, this concept of schema has been used to derive an improved schema theorem for GP that describes the propagation of schemata from one generation to the next. We discuss this result and show that our schema theorem is the natural counterpart for GP of the schema theorem for GAs, to which it asymptotically converges.     

A framework for relating syntactic and semantic model differences

Model differencing is an important activity in model-based development processes. Differences need to be detected, analyzed, and understood to evolve systems and explore alternatives. Two distinct approaches have been studied in the literature: syntactic differencing, which compares the concrete or abstract syntax of models, and semantic differencing, which compares models in terms of their meaning. Syntactic differencing identifies change operations that transform the syntactical representation of one model to the syntactical representation of the other. However, it does not explain their impact on the meaning of the model. Semantic model differencing is independent of syntactic changes and presents differences as elements in the semantics of one model but not the other. However, it does not reveal the syntactic changes causing these semantic differences. We define Diffuse, a language-independent, abstract framework, which relates syntactic change operations and semantic difference witnesses. We formalize fundamental relations of necessary, exhibiting, and sufficient sets of change operations and analyze their properties. We further demonstrate concrete instances of the Diffuse framework for three different popular modeling languages, namely class diagrams, activity diagrams, and feature models. The Diffuse framework provides a novel foundation for combining syntactic and semantic differencing.     

General schema theory for genetic programming with subtree-swapping crossover: Part II

This paper is the second part of a two-part paper which introduces a general schema theory for genetic programming (GP) with subtree-swapping crossover (Part I (Poli and McPhee, 2003)). Like other recent GP schema theory results, the theory gives an exact formulation (rather than a lower bound) for the expected number of instances of a schema at the next generation. The theory is based on a Cartesian node reference system, introduced in Part I, and on the notion of a variable-arity hyperschema, introduced here, which generalises previous definitions of a schema. The theory includes two main theorems describing the propagation of GP schemata: a microscopic and a macroscopic schema theorem. The microscopic version is applicable to crossover operators which replace a subtree in one parent with a subtree from the other parent to produce the offspring. Therefore, this theorem is applicable to Koza's GP crossover with and without uniform selection of the crossover points, as well as one-point crossover, size-fair crossover, strongly-typed GP crossover, context-preserving crossover and many others. The macroscopic version is applicable to crossover operators in which the probability of selecting any two crossover points in the parents depends only on the parents' size and shape. In the paper we provide examples, we show how the theory can be specialised to specific crossover operators and we illustrate how it can be used to derive other general results. These include an exact definition of effective fitness and a size-evolution equation for GP with subtree-swapping crossover.     

A Complete Uniform Substitution Calculus for Differential Dynamic Logic

This article introduces a relatively complete proof calculus for differential dynamic logic (dL) that is entirely based on uniform substitution, a proof rule that substitutes a formula for a predicate symbol everywhere. Uniform substitutions make it possible to use axioms instead of axiom schemata, thereby substantially simplifying implementations. Instead of subtle schema variables and soundness-critical side conditions on the occurrence patterns of logical variables to restrict infinitely many axiom schema instances to sound ones, the resulting calculus adopts only a finite number of ordinary dLformulas as axioms, which uniform substitutions instantiate soundly. The static semantics of differential dynamic logic and the soundness-critical restrictions it imposes on proof steps is captured exclusively in uniform substitutions and variable renamings as opposed to being spread in delicate ways across the prover implementation. In addition to sound uniform substitutions, this article introduces differential forms for differential dynamic logic that make it possible to internalize differential invariants, differential substitutions, and derivatives as first-class axioms to reason about differential equations axiomatically. The resulting axiomatization of differential dynamic logic is proved to be sound and relatively complete.     

Global extensional assertions and local integrity constraints in federated schemata

Integrated access to multiple data sources requires a homogeneous interface provided by a federated schema. Such a federated schema should correctly reflect the semantics of the component schemata of which it is composed. Since the semantics of a database schema is also determined by a set of semantic integrity constraints, a correct schema integration has to deal with integrity constraints existing in the different component schemata. Traditionally, most schema integration approaches solely concentrate on the structural integration of given database schemata. Local integrity constraints are often simply neglected. Their relationship to global extensional assertions, which form the basic integration constraints, are even ignored completely. In this paper, we discuss the impact of global extensional assertions and local integrity constraints on federated schemata. In particular, we point out the correspondence between local integrity constraints and global extensional assertions. The knowledge about the correspondences between the given integrity constraints and extensional assertions can then be utilized for an augmented schema integration process.     

基于语法和语义结合的源代码精确搜索方法

针对在编写软件、复用源代码的过程中仅依靠关键词无法精准搜索到适用源代码的问题,提出一种将语法和语义结合的源代码精准搜索方法。首先依据源代码语法语义的客观和唯一性,增加语法结构和"输入/输出"语义作为用户录入请求的一部分,并规范了具体的请求格式;然后在此基础上分别设计源代码语法匹配算法、"输入/输出"语义匹配算法、关键词兼容匹配,以及源代码搜索结果可信度计算算法;最后综合上述算法实现对源代码的精准搜索。测试结果表明：与单纯的关键词搜索相比,提出的方法对搜索的平均排序倒数（MRR）有超过62%的提升,有助于实现源代码的精准搜索。     

Schema processing under proportional selection in the presence ofrandom effects

Traditional selection in genetic algorithms has relied on reproduction in proportion to observed fitness. This method of selection devotes samples to the observed schemata in a form described by the well known schema theorem. When schema fitness takes the form of a random variable, however, the expected number of samples from extant schemata may not be described by the schema theorem and varies according to the specific random variables involved     

Structural search spaces and genetic operators

In a previous paper (Rowe et al., 2002), aspects of the theory of genetic algorithms were generalised to the case where the search space, omega, had an arbitrary group action defined on it. Conditions under which genetic operators respect certain subsets of omega were identified, leading to a generalisation of the term schema. In this paper, search space groups with more detailed structure are examined. We define the class of structural crossover operators that respect certain schemata in these groups, which leads to a generalised schema theorem. Recent results concerning the Fourier (or Walsh) transform are generalised. In particular, it is shown that the matrix group representing omega can be simultaneously diagonalised if and only if omega is Abelian. Some results concerning structural crossover and mutation are given for this case.     

The schema deceptiveness and deceptive problems of genetic algorithms

Genetic algorithms (GA) are a new type of global optimization methodology based on na-ture selection and heredity, and its power comes from the evolution process of the population of feasi-ble solutions by using simple genetic operators. The past two decades saw a lot of successful industrial cases of GA application, and also revealed the urgency of practical theoretic guidance. This paper sets focus on the evolution dynamics of GA based on schema theorem and building block hypothesis (Schema Theory), which we thought would form the basis of profound theory of GA. The deceptive-ness of GA in solving multi-modal optimization problems encoded on {0,1} was probed in detail. First, a series of new concepts are defined mathematically as the schemata containment, schemata compe-tence. Then, we defined the schema deceptiveness and GA deceptive problems based on primary schemata competence, including fully deceptive problem, consistently deceptive problem, chronically deceptive problem, and fundamentally decepti     

The constructions for comparing situations with the indices <Emphasis Type="Italic">sort of</Emphasis> and <Emphasis Type="Italic">as if</Emphasis>

The Russian comparative constructions with the word combinations sort of and as if are described with the help of the apparatus of construction grammar that was suggested by Ch. Chilmor. The semantics of these constructions and their syntactic properties that are determined only by semantic differences are analyzed. In particular, it is shown that both constructions must be considered comparative, despite the syntactic differences existing between them. On the other hand, the modal-discursive uses of these constructions that may be of typological interest are analyzed.     

Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

A few schema theorems for genetic programming (GP) have been proposed in the literature in the last few years. Since they consider schema survival and disruption only, they can only provide a lower bound for the expected value of the number of instances of a given schema at the next generation rather than an exact value. This paper presents theoretical results for GP with one-point crossover which overcome this problem. First, we give an exact formulation for the expected number of instances of a schema at the next generation in terms of microscopic quantities. Due to this formulation we are then able to provide an improved version of an earlier GP schema theorem in which some (but not all) schema creation events are accounted for. Then, we extend this result to obtain an exact formulation in terms of macroscopic quantities which makes all the mechanisms of schema creation explicit. This theorem allows the exact formulation of the notion of effective fitness in GP and opens the way to future work on GP convergence, population sizing, operator biases, and bloat, to mention only some of the possibilities.     

图文法遗传算法

本文讨论了进化神经网络的编码表示机制，分析了它们的优缺点；提出了遗传算法的一种图文法编码表示机制，给出了相应的算子定义，以及模式、模式长度及其阶的定义；证明了一个基于图文法表示机制的遗传算法模式定理，描述了交叉和突变对模式作用的效果。     

CLIN-S - A Semantically Guided First-Order Theorem Prover

CLIN-S is an instance-based, clause-form first-order theorem prover. CLIN-S employs three inference procedures: semantic hyper-linking, which uses semantics to guide the proof search and performs well on non-Horn parts of the proofs involving small literals, rough resolution, which removes large literals in the proofs, and UR resolution, which proves the Horn parts of the proofs. A semantic structure for the input clauses is given as input. During the search for the proof, ground instances of the input clauses are generated and new semantic structures are built based on the input semantics and a model of the ground clause set. A proof is found if the ground clause set is unsatisfiable. In this article, we describe the system architecture and major inference rules used in CLIN-S.     

Semantic schema refinements for multilevel schema integration

Within the database field, schema refinements have been proved useful for documentation and maintenance purposes; moreover, schemata describing the reality of interest at different levels of abstraction are extensively used in Computer Aided Software Engineering tools and visual query languages. So, much effort has been spent in analyzing schema transformations and schema refinements. Till now, however, while the syntaxof schema transformations has been deeply investigated, the semantics has been very often neglected. In this paper we present a full formal framework, supporting both the syntax and the semantics of schema refinements. Such a formal framework is used to support a methodology able to merge a set of schemata and the top-down chains of refinement planes produced during their design. The result of this kind of integration, that we call multilevel integration, is an integrated schema plus an associated top-down chain of schemata. The integrated schema and the chain are related to the input schemata by interesting properties, giving rise to a two-dimensional structure useful for exploring the data content of complex information systems.     

A semantically-informed multirobot system for exploration of relevant areas in search and rescue settings

Coordinated multirobot exploration involves autonomous discovering and mapping of the features of initially unknown environments by using multiple robots. Autonomously exploring mobile robots are usually driven, both in selecting locations to visit and in assigning them to robots, by knowledge of the already explored portions of the environment, often represented in a metric map. In the literature, some works addressed the use of semantic knowledge in exploration, which, embedded in a semantic map, associates spatial concepts (like ‘rooms’ and ‘corridors’) with metric entities, showing its effectiveness in improving the total area explored by robots. In this paper, we build on these results and propose a system that exploits semantic information to push robots to explore relevant areas of initially unknown environments, according to a priori information provided by human users. Discovery of relevant areas is significant in some search and rescue settings, in which human rescuers can instruct robots to search for victims in specific areas, for example in cubicles if a disaster happened in an office building during working hours. We propose to speed up the exploration of specific areas by using semantic information both to select locations to visit and to determine the number of robots to allocate to those locations. In this way, for example, more robots could be assigned to a candidate location in a corridor, so the attached rooms can be explored faster. We tested our semantic-based multirobot exploration system within a reliable robot simulator and we evaluated its performance in realistic search and rescue indoor settings with respect to state-of-the-art approaches.     

Properties of stochastic syntax-directed translation schemata

Stochastic syntax-directed translation schemata describe both the syntactic structure and the probability distribution of stochastic mappings between contextfree languages. The relationship between stochastic syntax-directed translation schemata and stochastic grammars and automata are presented by proving that a stochastic pushdown transducer can be constructed to define the same translations as a simple schema, and that the simple schema are characterized by stochastic contextfree grammars. Asymptotic properties of linear schemata are established by the theory of Markov chains. Since stochastic translations contain both input and output strings, their information content can be described. Equations are developed for both the information content and the rate of stochastic translations.     

Semantic hierarchies and abstractions in conceptual schemata

A conceptual schema is a clear, easy to understand and exact representation of the semantics of an underlying universe of discourse. The role of such schemata in the specification and design of information bases is now widely recognized. However, in “real life” applications, it is often the case that the size of the conceptual schema exceeds the limit above which it is necessary to have an abstraction mechanism available, as otherwise it would become difficult to understand.In this paper, we present several concepts and heuristic procedures which allow for semantic modularization of a conceptual schema, thus providing a concise representation, using different degrees of abstraction and/or viewpoints, of a schema of any size.     

Normalization and optimization of schema mappings

Schema mappings are high-level specifications that describe the relationship between database schemas. They are an important tool in several areas of database research, notably in data integration and data exchange. However, a concrete theory of schema mapping optimization including the formulation of optimality criteria and the construction of algorithms for computing optimal schema mappings is completely lacking to date. The goal of this work is to fill this gap. We start by presenting a system of rewrite rules to minimize sets of source-to-target tuple-generating dependencies. Moreover, we show that the result of this minimization is unique up to variable renaming. Hence, our optimization also yields a schema mapping normalization. By appropriately extending our rewrite rule system, we also provide a normalization of schema mappings containing equality-generating target dependencies. An important application of such a normalization is in the area of defining the semantics of query answering in data exchange, since several definitions in this area depend on the concrete syntactic representation of the mappings. This is, in particular, the case for queries with negated atoms and for aggregate queries. The normalization of schema mappings allows us to eliminate the effect of the concrete syntactic representation of the mapping from the semantics of query answering. We discuss in detail how our results can be fruitfully applied to aggregate queries.