You are here

Archived Departmental Reports

    2012

  • Extension Properties of Boolean Contact Algebras
    Ivo Düntsch and Sanjiang Li, February 2012.  [PDF]

    We show that the class of Boolean contact algebras has the joint embedding property and the amalgamation property, and that the class of connected Boolean contact algebras has the joint embedding property but not the amalgamation property.

  • Evolutionary Approaches to the Generation of Optimal Error Correcting Codes
    Daniel E. McCarney, Sheridan Houghten and Brian J. Ross, March 2012.  [PDF]

    Error-correcting codes allow for reliable transmission of data over mediums subject to interference. They guarantee detection and recovery from a level of transmission corruption. Larger error-correcting codes increase the amount of error tolerable, which improves system reliability and performance. However, discovering optimal error-correcting codes for different size specifications is equivalent to the NP-Hard problem of determining maximum cliques of a graph.
    In this research, three different binary error correcting code problems are considered. Both genetic algorithm and genetic programming are examined for generating optimal error correcting codes for these problems. A new chromosome representation of the GA system is examined, which shows some benefits in certain conditions. The use of GP is novel in this problem domain, and in combination with the Baldwin effect, it is shown to be a promising new approach for code discovery.

  • Automatic Generation of Graph Models for Complex Networks by Genetic Programming
    Alexander Bailey, Mario Ventresca, and Beatrice Ombuki-Berman, March 2012.  [PDF]

    Complex networks have attracted a large amount of research attention, especially over the past decade, due to their prevalence and importance in our daily lives. Numerous humandesigned models have been proposed that aim to capture and model different network structures, for the purpose of improving our understanding the real-life phenomena and its dynamics in different situations. Groundbreaking work in genetics, medicine, epidemiology, neuroscience, telecommunications, social science and drug discovery, to name some examples, have directly resulted. Because the graph models are human made (a very time consuming process) using a small subset of example graphs, they often exhibit inaccuracies when used to model similar structures. This paper represents the first exploration into the use of genetic programming for automating the discovery and algorithm design of graph models, representing a totally new approach with great interdisciplinary application potential. We present exciting initial results that show the potential of GP to replicate existing complex network algorithms.

  • Relation Algebras, Matrices, and Multi-Valued Decision Diagrams
    Francis Atampore, Michael Winter, April 2012.  [PDF]

    In this paper we want to further investigate the usage of matrices as a representation of relations within arbitrary heterogeneous relation algebras. First, we want to show that splittings do exist in matrix algebras assuming that the underlying algebra of the coefficients provides this operation. Second, we want to outline an implementation of matrix algebras using reduced ordered multi-valued decision diagrams. This implementation combines the efficiency of operations based on those data structures with the general matrix approach to arbitrary relation algebras.

  • On Deriving Conditional Diagnosability of Interconnection Networks
    E. Cheng, L. Lipták, Ke Qiu, Z. Shen, May 2012.  [PDF]

    We provide general techniques to estimate an upper bound of the conditional diagnosability of a graph G, and to prove that such a bound is also tight when a certain connectivity result is available for G. As an example, we derive the exact value of the conditional diagnosability for the (n, k)-star graph.

  • Towards Quantum Relation Algebras
    Michael Winter, June 2012.  [PDF]

    Propositional quantum logic is a non-classical logic system based on the structure of quantum mechanics. It is based on the concept of physical observations or experimental propositions. These propositions correspond to closed linear subspaces of a Hilbert space or, more abstractly, to elements of an orthomodular lattice. In this paper we want to start the investigation of relations that are based on such a logic system as a first step towards an algebraic version of quantum first-order logic using a relation algebraic approach.

  • Knowledge Transfer Strategies for Vector Evaluated Particle Swarm Optimization
    Kyle Robert Harrison, Beatrice Ombuki-Berman, and Andries P. Engelbrecht, September 2012.  [PDF]

    Vector evaluated particle swarm optimization (VEPSO) is a multi-swarm variant of the traditional particle swarm optimization (PSO) algorithm applied to multi-objective problems (MOPs). Each sub- objective is allocated a single sub-swarm and knowledge transfer strate- gies (KTSs) are used to pass information between swarms. The original VEPSO used a ring KTS, and while VEPSO has shown to be successful in solving MOPs, other algorithms have been shown to produce better results. One reason for VEPSO to perform worse than other algorithms may be due to the ineffciency of the KTS used in the original VEPSO. This paper investigates new KTSs for VEPSO in order to improve its performance. The results indicated that a hybrid strategy using parent- centric crossover (PCX) on global best solutions generally lead to a higher hypervolume while using PCX on archive solutions generally lead to a better distributed set of solutions.

  • Generative Aesthetically Pleasing Images in a Virtual Environment Using Particle Swarm Optimization
    William Barry, October 2012.  [PDF]

    This research focuses on generating aesthetically pleasing images in virtual environments using the particle swarm optimization (PSO) algorithm. The PSO is a stochastic population based search algorithm that is inspired by the ocking behavior of birds. In this research, we implement swarms of cameras ying through a virtual world in search of an image that is aesthet- ically pleasing. Virtual world exploration using particle swarm optimization is considered to be a new research area and is of interest to both the sci- enti^Lc and artistic communities. Aesthetic rules such as rule of thirds, sub- ject matter, colour similarity and horizon line are all analyzed together as a multi-objective problem to analyze and solve with rendered images. A new multi-objective PSO algorithm, the sum of ranks PSO, is introduced. It is empirically compared to other single-objective and multi-objective swarm al- gorithms. An advantage of the sum of ranks PSO is that it is useful for solving high-dimensional problems within the context of this research. Throughout many experiments, we show that our approach is capable of automatically producing images satisfying a variety of supplied aesthetic criteria.

  • Enabling and Measuring Complexity in Evolving Designs using Generative Representations for Artificial Architecture
    Adrian Harrington, October 2012.  [PDF]

    As the complexity of evolutionary design problems grow, so too must the quality of solutions scale to that complexity. In this research, we develop a genetic programming system with individuals encoded as tree-based generative representations to address scalability. This system is capable of multi-objective evaluation using a ranked sum scoring strategy. We examine Hornby's features and measures of modularity, reuse and hierarchy in evolutionary design problems. Experiments are carried out, using the system to generate three-dimensional forms, and analyses of feature characteristics such as modularity, reuse and hierarchy were performed. This work expands on that of Hornby's, by examining a new and more difficult problem domain. The results from these experiments show that individuals encoded with those three features performed best overall. It is also seen, that the measures of complexity conform to the results of Hornby. Moving forward with only this best performing encoding, the system was applied to the generation of three-dimensional external building architecture. One objective considered was passive solar performance, in which the system was challenged with generating forms that optimize exposure to the Sun. The results from these and other experiments satisfied the requirements. The system was shown to scale well to the architectural problems studied.

  • Genetic Programming for the Automatic Inference of Graph Models for Complex Networks
    Alexander Bailey, Mario Ventresca, Beatrice Ombuki-Berman, October 2012.  [PDF]

    Complex networks are becoming an integral tool for our understanding of an enormous variety of natural and artificial systems. A number of human-designed network generation procedures have been proposed that reasonably model specific real-life phenomena in structure and dynamics. Consequently, breakthroughs in genetics, medicine, epidemiology, neuroscience, telecommunications and the social sciences have recently resulted. A graph model is an algorithm capable of constructing arbitrarily sized networks, whose end structure will exhibit certain statistical and structural properties. The process of deriving an accurate graph model is very time intensive and challenging and may only yield high accurate models for very specific phenomena. An automated approach based on Genetic Programming was recently proposed by the authors. However, this initial system suffered from a number of drawbacks, including an under-emphasis on creating hub vertices, the requirement of user intervention to determine objective weights and the arbitrary approach to selecting the most representative model from a population of candidate models. In this paper we propose solutions to these problems and show experimentally that the new system is a very significant improvement and is very capable of reproducing existing common graph models from even a single small initial network.


  • 2011

  • Automatic and Interactive Evolution of Vector Graphics Images
    with Genetic Algorithms

    Steven Bergen and Brian J. Ross, January 2011.  [PDF]

    Vector graphics images are composed of lists of discrete geometric shapes, such as circles, squares, and lines. Vector graphics is popular in illustration and graphic design. The generation of vector images by evolutionary computation techniques, however, has been given little attention. This paper uses genetic algorithms to evolve vector images. By restricting the numbers of primitives and colour schemes used, stylized interpretations of target images are produced. Automatic evolution involves measuring the pixel-by-pixel colour distance between a candidate and target image. The JNetic evolutionary vector graphics system is described. JNetic supports automatic and user-guided evolution, chromosome editing, and high-detail masks. The user can paint masks over areas of the target image, which will be used to reproduce the high-detail features within those areas. The system has been successfully used by the authors as a creative tool.

  • Automatic Evolution of Conceptual Building Architectures
    Corrado Coia and Brian J. Ross, January 2011.  [PDF]

    An evolutionary approach to the automatic generation of 3D building topologies is presented. Genetic programming is used to evolve shape grammars. When interpreted, the shape grammars generate 3D models of buildings. Fitness evaluation considers user-specified criteria that evaluate different aspects of the model geometry. Such criteria might include maximizing the number of unique normals, satisfying target height requirements, and conforming to supplied shape contours. Multi-objective evaluation is used to analyze and rank model fitness, based on the varied user-supplied criteria. A number of interesting models complying to given geometric specifications have been successfully evolved with the approach. A motivation for this research application is that it can be used as a generator of conceptual designs, to be used as inspirations for refinement or further exploration.

  • Evolution of Architectural Floor Plans
    Robert W.J. Flack, January 2011.  [PDF]

    Layout planning is a process of sizing and placing rooms (e.g. in a house) while attempting to optimize various criteria. Often there are conflicting criteria such as construction cost, minimizing the distance between related activities, and meeting the area requirements for these activities. The process of layout planning has mostly been done by hand, with a handful of attempts to automate the process. This thesis explores some of these past attempts and describes several new techniques for automating the layout planning process using evolutionary computation. These techniques are inspired by the existing methods, while adding some of their own innovations. Additional experiments are done to test the possibility of allowing polygonal exteriors with rectilinear interior walls. Several multi-objective approaches are used to evaluate and compare fitness. The evolutionary representation and requirements specification used provide great flexibility in problem scope
    and depth and is worthy of considering in future layout and design attempts. The system outlined in this thesis is capable of evolving a variety of floor plans conforming to functional and geometric specifications. Many of the resulting plans look reasonable even when compared to a professional floor plan. Additionally polygonal and multi-floor buildings were also enerated.

  • Fundamentals of Cochlear Nerve Signal Processing: Towards a New Generation of Cochlear Implant Devices
    Vlad Wojcik and W. Gregory Wojcik, January 2011.  [PDF]

    We present an engineering model of the inner ear focusing on the cochlea, together with the emerging cochlear nerve signal protocol suggesting a new generation of cochlear implants. We demonstrate mathematically that signals generated by proposed electronic devices can be used as restorative signals feeding the cochlear nerve, and in audio pattern recognition, including audio location, perception, pattern recognition and perhaps even subjective enjoyment of music and comprehension of speech.
    This paper was written for the multi-disciplinary audience of engineers, biologists, mathematicians, computer and medical practitioners. Each of those groups might find some of its sections basic

  • Evolution of Stochastic Bio-Networks Using Summed Rank Strategies
    Brian J. Ross, February 2011.  [PDF]
    Stochastic models defined in the stochastic pi-calculus are evolved using genetic programming. The interpretation of a stochastic model results in a set of time series behaviors. Each time series denotes changing quantities of components within the modeled system. The time series are described by their statistical features. This paper uses genetic programming to reverse engineer stochastic pi-calculus models. Given the statistical characteristics of the intended model behavior, genetic programming attempts to construct a model whose statistical features closely match those of the target process. The feature objectives comprising model behavior are evaluated using a multi-objective strategy. A contribution of this research is that, rather than use conventional Pareto ranking, a summed rank scoring strategy is used instead. Summed rank scoring was originally derived for high-dimensional search spaces. This paper shows that it is likewise effective for evaluating stochastic models with low- to moderate-sized search spaces. A number of stochastic models with oscillating behaviors were successfully evolved. Attempts on a larger-sized model were not successful. Reasons for its poor performance are likely due to poor choices in feature selection, and too many selected features and channels contributing to a overly difficult search space.
  • Automatic Evolution of Conceptual Building Architectures
    Corrado Coia, May 2011.  [PDF]

    This thesis describes research in which genetic programming is used to automatically evolve shape grammars that construct three dimensional models of possible external building architectures. A completely automated fitness function is used, which evaluates the three dimensional building models according to different geometric properties such as surface normals, height, building footprint, and more. In order to evaluate the buildings on the different criteria, a multi-objective fitness function is used. The results obtained from the automated system were successful in satisfying the multiple objective criteria as well as creating interesting and unique designs that a human-aided system might not discover. In this study of evolutionary design, the architectures created are not meant to be fully functional and structurally sound blueprints for constructing a building, but are meant to be inspirational ideas for possible architectural designs. The evolved models are applicable for today’s architectural industries as well as in the video game and movie industries. Many new avenues for future work have also been discovered and highlighted.

  • Automatic Structure Generation using Genetic Programming and Fractal Geometry
    Steve Bergen, December 2011.  [PDF]

    Three dimensional model design is a well-known and studied field, with numerous real-world applications. However, the manual construction of these models can often be time-consuming to the average user, despite the advantages offered through computational advances. This thesis presents an approach to the design of 3D structures using evolutionary computation and L-systems, which involves the automated production of such designs using a strict set of fitness functions. These functions focus on the geometric properties of the models produced, as well as their quantifiable aesthetic value - a topic which has not been widely investigated with respect to 3D models. New extensions to existing aesthetic measures are discussed and implemented in the presented system in order to produce designs which are visually pleasing. The system itself facilitates the construction of models requiring minimal user initialization and no user-based feedback throughout the evolutionary cycle. The genetic programming evolved models are shown to satisfy multiple criteria, conveying a relationship between their assigned aesthetic value and their perceived aesthetic value. Exploration into the applicability and effectiveness of a multi-objective approach to the problem is also presented, with a focus on both performance and visual results. Although subjective, these results offer insight into future applications and study in the field of computational aesthetics and automated structure design.


  • 2010

  • Machine Perception and Learning from the Evolutionary Viewpoint: The Hyperball Algorithms (Take Two)
    Vlad Wojcik and Behzad Salami, December 2010.  [PDF]

    We present a set of highly parallel (fine grain), general pattern classification algorithms aimed at mimicking pattern identification, classification and learning skills of animals. We cover first an idealized case of supervised learning from an
    infallible expert, followed by the realistic cases of learning from fallible experts as well as the case of autonomous (i.e. self-supervised) learning. To ensure wide range of applicability in our algorithms we use only the basic concepts of mathematics: set theory and theory of metric spaces. This methodology, already tested in computer vision domain, allows for creation of expert systems capable of continuous learning and forgetting of less useful facts, and to demonstrate curiosity and initiative in maintaining their adaptation to an environment evolving sufficiently slowly.
    As proof of concept we offer a sketch of automated deep sky observation in search for unknown objects together with a detailed solution to the problem of automated mineral identification in petrographic thin sections. These illustration problems seem intractable using traditional means.

  • The Evolution of Higher-level Biochemical Reaction Models
    Brian J. Ross, December 2010.  [PDF]
    Computational tools for analyzing biochemical phenomena are becoming increasingly important. Recently, high-level formal languages for modeling and simulating biochemical reactions have been proposed. These languages make the formal modeling of complex reactions accessible to domain specialists outside of theoretical computer science. This research explores the use of genetic programming to automate the construction of models written in one such language. Given a description of desired timecourse data, the goal is for genetic programming to construct a model that might generate the data. The language investigated is Kahramanogullari’s and Cardelli’s PIM language. The PIM syntax is defined in a grammar-guided genetic programming system. All time series generated during simulations are described by statistical feature tests, and the fitness evaluation compares feature proximity between the target and candidate solutions. Target PIM models of varying complexity are used as target expressions for genetic programming. Results were very successful in all cases. One reason for this success is the compositional nature of PIM, which is amenable to genetic program search.
  • Splitting Atoms in Relational Algebras
    Prathap Siddavaatam and Michael Winter, December 2010.  [PDF]

    Splitting atoms in a relation algebra is a common tool to generate new algebras from old ones. This includes constructing non-representable algebras from representable structures. The known method of splitting atoms does not allow that bijections different from the identity are contained in the starting algebra. This is a major drawback of this method because interesting candidates in mereotopology do contain such bijections. An ad-hoc splitting was done in those examples, and the results have been published in several papers. With this paper we want to start a thorough investigation of possible splitting methods.

  • A First-Order Calculus for Allegories
    Bahar Aameri and Michael Winter, December 2010.  [PDF]

    In this paper we a language and first-order calculus for formal reasoning about relations based on the theory of allegories. Since allegories are categories the language is typed in Church-style. We show soundness and completeness of the calculus and demonstrate its usability by presenting the RelAPS system; a proof assistant for relational categories based on the calculus presented here.

  • A First-Order Characterization of Allen’s Interval Algebra
    Michael Winter, December 2010.  [PDF]
    In this paper we are interested in the order structure induced by the relations 'before' and 'meets' of Allen's interval algebra. We provide an abstract definition of this kind of order structure called an interval order. We prove that every interval order is isomorphic to the corresponding order on a set of finite intervals over a linear order without endpoints. As a consequence of this characterization we obtain that any partition of the set of relations on a set consisting of 13 relations that satisfy the composition table of Allen's algebra is indeed an algebra of intervals.

  • 2009

  • Functions Definable by Arithmetic Circuits
    Ian Pratt-Hartmann and Ivo Düntsch, January 2009.  [PDF]

    An arithmetic circuit is a labelled, directed graph specifying a cascade of arithmetic and logical operations to be performed on sets of non-negative integers. In this paper, we consider the definability of functions by means of arithmetic circuits. We prove two negative results: the first shows, roughly, that a function is not circuit-definable if it has an infinite range and sub-linear growth; the second shows, roughly, that a function is not circuit-definable if it has a finite range and fails to converge on certain `sparse' chains under inclusion. We observe that various functions of interest fall under these descriptions.

  • Stonian p-Ortholattices: A new approach to the mereotopology RT0
    Torsten Hahmann, Michael Gruninger and Michael Winter, April 2009.  [PDF]

    This paper gives a isomorphic representation of the subtheories RT-, RT-EC, and RT of Asher and Vieu's first-order ontology of mereotopology RT0. It corrects and extends previous work on the representation of these mereotopologies. We develop the theory of p-ortholattices -- lattices that are both orthocomplemented and pseudocomplemented -- and show that the identity (x • y)*=x*+y* defines the natural class of Stonian p-ortholattices. Equivalent conditions for a p-ortholattice to be Stonian are given. The main contribution of the paper consists of a representation theorem for RT- as Stonian p-ortholattices. Moreover, it is shown that the class of models of RT-EC is isomorphic to the non-distributive Stonian p-ortholattices and a representation of RT is given by a set of four algebras of which one need to be a subalgebra of the present model. As corollary we obtain that Axiom (A11) -- existence of two externally connected regions -- is in fact a theorem of the remaining axioms of RT.

  • Timed Contact Algebras
    Ivo Düntsch and Michael Winter, April 2009.  [PDF]

    Timed contact algebras constitute an approach to a temporal version of a region based theory of space. In the general theory the underlying model of time does not have any structure, i.e. time is neither ordered nor required to be discrete or continuous. In this paper we want to investigate contact structures with a betweenness relation on points in time. Furthermore, we are interested in the relationship of a continuity axiom, an axiom of construction, and the fine structure of the time relation.

  • Cardinal Addition in Distributive Allegories
    Yasuo Kawahara and Michael Winter, April 2009.  [PDF]

    In this paper we want to develop an addition operation on an abstract notion of cardinality of relations in a distributive allegory. Assuming suitable extra structure on the underlying allegory we are going to define addition and investigate its basic properties.

  • Cylindric algebras and relational databases
    Ivo Düntsch, April 2009.  [PDF]

    An interpretation of the relational data model and various dependencies is given within the framework of cylindric algebras. It turns out that there is a natural translation of relational databases into cylindric set lattices, and that Codd's relational operators have a simple interpretation in these structures. Consequently, various database constraints can be expressed in the equational language, and recent results in equational logic have been able to shed some light on the expressiveness and axiomatizability of these constraints.

  • Complements in Distributive Allegories
    Michael Winter, April 2009.  [PDF]

    It is know in topos theory that axiom of choice implies that the topos is Boolean. In this paper we want to prove and generalize this result in the context of allegories. In particular, we will show that partial identities do have complements in distributive allegories with relational sums and total splittings assuming the axiom of choice. Furthermore, we will discuss possible modifications of the assumptions used in the that theorem.

  • On the Skeleton of Stonian p-Ortholattices
    Michael Winter, Torsten Hahmann and Michael Gruninger, April 2009.  [PDF]

    Boolean Contact Algebras (BCA) establish the algebraic counterpart of the mereotopolopy induced by the Region Connection Calculus. Similarly, Stonian p-ortholattices serve as a lattice theoretic version of the onthology $RT^-$ of Asher and Vieu. In this paper we study the relationship between BCAs and Stonian p-ortholat\-tices. We show that the skeleton of every Stonian p-ortholattice is a BCA, and, conversely, that every BCA is isomorphic to the skeleton of a Stonian p-ortholattice. Furthermore, we prove the equivalence between algebraic conditions on Stonian p-ortholattices and the axioms C5, C6, and C7 for BCAs.

  • Choosing the root node of a quadtree
    Xiang Yin, Ivo Düntsch and Günther Gediga, May 2009.  [PDF]

    Granular computing is closely related to the depth of the detail of information with which we are presented, or choose to process. In spatial cognition and image processing such detail is given by the resolution of a picture. The quadtree representation of an image offers a quick look at the image at various stages of granularity, and successive quadtree representations can be used to represent change. In this paper we present a heuristic algorithm to find a root node of a region quadtree which reduces the number of leaves when compared with the standard quadtree decomposition.

  • User-Guided Evolution of Granular Synthesis
    Corrado Coia and Brian J. Ross, July 2009.  [PDF]

    Granular synthesis is a form of audio synthesis that consists of breaking audio into tiny millisecond chucks. This paper describes the EGDE system. EGDE (Evolutionary Granular Delay Environment) is a software plug-in that permits its granular delay effects to be time synchronized with the host application. Its interface features an interactive genetic algorithm, to be used for user exploration of granular synthesis parameters. Interactive evolution is ideal in this application, as it permits a user to interactively explore a wide variety of effects that arise with different combinations of the granular delay parameters. A goal of EGDE is to provide a granular synthesis interface with an intuitive and efficient means of auditioning and rating effect parameters, while minimizing user exhaustion. This is particularly important with a granular synthesis, since many parameter settings will be undesirable to most listeners. Typically, each parameter set in the population can be auditioned in a matter of a few seconds or less. A minimalist 3-value evaluation scheme lets the user either clone, use, or delete candidate parameter sets. Mutation and crossover rates can also be fine tuned as desired. The interface lets the user directly tweak parameters, thus permitting direct user editing of chromosomes. The evolutionary interface could be easily adapted to other musical applications in the future, for example, generalized synthesis engines.

  • Evolutionary Synthesis of Stochastic Gene Network Models using Feature-based Search Spaces
    Janine Imada, November 2009.  [PDF]

    A feature-based fitness function is applied in a genetic programming system to synthesize stochastic gene regulatory network models whose behaviour is defined by a time course of protein expression levels. Typically, when targeting time series data, the fitness function is based on a sum-of-errors involving the values of the fluctuating signal. While this approach is successful in many instances, its performance can deteriorate in the presence of noise. This thesis explores a fitness measure determined from a set of statistical features characterizing the time series’ sequence of values, rather than the actual values themselves. Through a series of experiments involving symbolic regression with added noise and gene regulatory network models based on the stochastic pi-calculus, it is shown to successfully target oscillating and non-oscillating signals. This practical and versatile fitness function offers an alternate approach, worthy of consideration for use in algorithms that evaluate noisy or stochastic behaviour.

  • Functions Definable by Numerical Set-Expressions
    Ian Pratt-Hartmann and Ivo Düntsch, December 2009.  [PDF]

    A numerical set-expression is a term specifying a cascade of arithmetic and logical operations to be performed on sets of non-negative integers. If these operations are confined to the usual Boolean operations together with the result of lifting addition to the level of sets, we speak of additive circuits. If they are confined to the usual Boolean operations together with the result of lifting addition and multiplication to the level of sets, we speak of arithmetic circuits. In this paper, we investigate the definability of sets and functions by means of additive and arithmetic circuits, occasionally augmented with additional operations.

  • Complex Algebras of Arithmetic
    Ivo Düntsch and Ian Pratt-Hartmann, December 2009.  [PDF]

    An arithmetic circuit is a labeled, acyclic directed graph specifying a sequence of arithmetic and logical operations to be performed on sets of natural numbers. Arithmetic circuits can also be viewed as the elements of the smallest subalgebra of the complex algebra of the semiring of natural numbers. In the present paper we investigate the algebraic structure of complex algebras of natural numbers and make some observations regarding the complexity of various theories of such algebras.


  • 2008

  • The Lattice of Contact Relations on a Boolean Algebra
    Ivo Düntsch and Michael Winter, January 2008.  [PDF]

    Contact relations on an algebra have been studied since the early part of the previous century, and have recently become a powerful tool in several areas of artificial intelligence, in particular, qualitative spatial reasoning and ontology building. In this paper we investigate the structure of the set of all contact relations on a Boolean algebra.

  • A discrete duality between apartness algebras and apartness frames
    Ivo Düntsch and Ewa Orlowska, January 2008.  [PDF]

    Apartness spaces were introduced as a constructive counterpart to proximity spaces which, in turn, aimed to model the concept of nearness of sets in a metric or topological environment. In this paper we introduce apartness algebras and apartness frames intended to be abstract counterparts to the apartness spaces of Bridges and Vita, and we prove a discrete duality for them.

  • Using Feature-based Fitness Evaluation in Symbolic Regression with Added Noise
    Janine Imada and Brian Ross, April 2008.  [PDF]

    Symbolic regression is a popular genetic programming (GP) application. Typically, the fitness function for this task is based on a sum-of-errors, involving the values of the dependent variable directly calculated from the candidate expression. While this approach is extremely successful in many instances, its performance can deteriorate in the presence of noise. In this paper, a feature-based fitness function is considered, in which the fitness scores are determined by comparing the statistical features of the sequence of values, rather than the actual values themselves. The set of features used in the fitness evaluation are customized according to the target, and are drawn from a wide set of features capable of characterizing a variety of behaviours. Experiments examining the performance of the feature-based and standard fitness functions are carried out for non-oscillating and oscillating targets in a GP system which introduces noise during the evaluation of candidate expressions. Results show strength in the feature-based fitness function, especially for the oscillating target

  • Probabilistic Granule Analysis
    Ivo Düntsch and Günther Gediga, May 2008.  [PDF]

    We present a semi--parametric approach to evaluate the reliability of rules obtained from a rough set information system by replacing strict determinacy by predicting a random variable which is a mixture of latent probabilities obtained from repeated measurements of the decision variable. It is demonstrated that the algorithm may be successfully used for unsupervised learning.

  • Task Performance Metrics on Liquid Crystal Displays
    Dave Bockus and Jenny Quay, July 2008.  [PDF]

    Twenty participants performed a selection and targeting task where performance indices were recorded. User performance varied as the sizes and resolutions of the screen changed during task performance. Performance was calculated using formula's represented in the Fitts' and Hicks' Models. Results show that the largest screen with the highest resolution had good performance times but also a smaller screen with a lower resolution yielded good performance times. The results indicate that bigger is not always better when working on LCD screens and that the user can become optically challenged when trying to work with a high resolution on a smaller screen. Results show that there is a relationship between the perceived font size on the screen and the users' ability to perform comprehension and recognition while performing certain tasks.

  • Towards Automated Derivation in Theory of Allegories
    Joel Glanfield, July 2008.  [PDF

    We provide an algorithm that automatically derives many provable theorems in the equational theory of allegories (ALL). This was accomplished by noticing properties of an existing decision algorithm that could be extended provide a derivation in addition to a decision certificate. We also suggest improvements and corrections to previous research in order to motivate further work on a complete derivation mechanism. The results presented here are significant for those interested in relational theories, since we essentially have a subtheory where automatic proof-generation is possible. This is also relevant to program verification since relations are well-suited to describe the behaviour of computer programs. It is likely that extensions of the theory of allegories are also decidable and possibly suitable for further expansions of the algorithm presented here.

  • Algorithms for Speedy Visual Recognition and Classification of Patterns Formed on Rectangular Imaging Sensors
    Vlad Wojcik and Pascal Comte, July 2008.  [PDF]

    The real-time tasks of image interpretation, pattern clustering, recognition and classification necessitate quick analysis of registered patterns. Current algorithms and technological approaches are slow and rigid. Within the evolutionary context we present here a novel, biologically inspired solution to these problems, with aim to accelerate processing. Our massively parallel algorithms are applicable to patterns recorded on rectangular imaging arrays of arbitrary sizes and resolutions. The systems we propose are capable of continuous learning, as well as of selective forgetting of less important facts, and so to maintain their adaptation to an environment evolving sufficiently slowly. A case study of visual signature recognition illustrates the presented ideas and concepts.

  • Machine Perception and Learning from the Evolutionary Viewpoint: The Hyperball Algorithms
    Vlad Wojcik and Behzad Salami, Sept 2008.  [PDF]

    We present a set of highly parallel (fine grain), general pattern classification algorithms aimed at mimicking pattern identification, classification and learning skills of animals. We cover first an idealized case of supervised learning from an infallible expert, followed by the realistic cases of learning from fallible experts as well as the case of autonomous (i.e. self-supervised) learning. To ensure wide range of applicability in our algorithms we use only the basic concepts of mathematics: set theory and theory of metric spaces. The proposed methodology allows for creation of expert systems capable of continuous learning and forgetting of less useful facts, and so to maintain their adaptation to an environment evolving sufficiently slowly.
    As proof of concept we offer a sketch of automated deep sky observation in search for unknown objects together with a detailed solution to the problem of automated mineral identification in petrographic thin sections. These illustration problems seem intractable using traditional means.


  • 2007

  • A multi-modal logic for disagreement and exhaustiveness
    Ivo Düntsch and Beata Konikowska, January 2007.  [PDF]

    The paper explores two basic types of relations between objects of a Pawlak-style information system generated by the values of some attribute of those objects: disagreement (disjoint sets of values) and exhaustiveness (sets of values adding up to the whole universe of the attribute). Out of these two fundamental types of relations, most other types of relations on objects of an information system considered in the literature can be derived - as, for example, indiscernibility, similarity and complementarity. The algebraic properties of disagreement and indiscernibility relations are explored, and a representation theorem for each of these two types of relations is proved.
    The notions of disagreement and exhaustiveness relations for a single attribute are extended to relations generated by arbitrary sets of attributes, yielding two families of relations parametrized by sets of attributes. They are used as accessibility relations to define a multi-modal logic with modalities corresponding to the lower and upper approximation of a set in Pawlak's rough set theory. Finally, a complete Rasiowa-Sikorski deduction system of that logic is developed.

  • Arrow Categories
    Michael Winter, January 2007.  [PDF]

    Goguen categories were introduced as a suitable categorical description of L-fuzzy relations, i.e., of relations taking values from an arbitrary complete Brouwerian lattice L instead of the unit interval [0,1] of the real numbers. In this paper we want to study the algebraic structures derived from Goguen categories by replacing its second-order axiom by some weaker versions.

  • Using Genetic Programming to Synthesize Monotonic Stochastic Processes
    Brian Ross, April 2007.  [PDF]

    The automatic synthesis of stochastic concurrent processes is investigated. We use genetic programming to automatically evolve a set of stochastic pi-calculus expressions that generate execution behaviour conforming to some supplied target behaviour. We model the stochastic pi-calculus in a grammatically-guided genetic programming system, and we use an efficient interpreter based on the SPIM abstract machine model by Phillips and Cardelli. The behaviours of target systems are modelled as streams of numerical
    time series for different variables of interest. We were able to successfully evolve stochastic pi-calculus systems that exhibited the target behaviors. Successful experiments considered target processes with continuous monotonic behaviours.

  • Waste Collection Vehicle Routing Problem with Time Window using Multi-objective Genetic Algorithms
    Beatrice Ombuki-Berman, Andrew Runka and Franklin Hanshar, May 2007.  [PDF]

    We study a waste collection vehicle routing problem with time windows (VRPTW) complicated by multiple disposal trips and driver's lunch breaks. Recently Kim et al. [1] introduced and addressed this problem using an extension of the well-known Solomon's insertion approach, and a clustering-based algorithm. We propose and present the results of an initial study of a multi-objective genetic algorithm for the waste collection VRPTW using a set of benchmark data from real-world problems obtained by Kim et al.

  • An Ordered Category of Processes
    Michael Winter, Oct 2007.  [PDF]

    Processes can be seen as relations extended in time. In this paper we want to investigate this observation by deriving an ordered category of processes. We model processes as co-algebras of a relator on Dedekind category up to bisimilarity. On those equivalence classes we define a lower semi-lattice structure and a monotone composition operation.

  • Cardinality in Allegories
    Yasuo Kawahara and Michael Winter, Nov 2007.  [PDF]

    In this paper we want to investigate two notions of the cardinality of relations in the context of allegories. The different axiom systems are motivated on the existence of injective and surjective functions, respectively. In both cases we provide a canonical cardinality function and show that it is initial in the category of all cardinality functions over the given allegory.

  • Safe Control Architectures for Mobile Robots Interacting with Humans
    Jerzy A. Barchanski, Nov 2007.  [PDF]

    We review first the principal concepts of system safety. Then we analyze hazards of human - robot interactions. We focus on hazards of a robot collision with a human and devise an appropriate robot behavior mitigating this hazard. After reviewing the principal classes of robot control architectures, we evaluate their effectiveness in collision avoidance. In conclusion, we recommend one of the hybrid control architectures which seems to be the safest according to our analysis.


  • 2006

  • Remarks on lattices of contact relations
    I. Düntsch and Michael Winter, February 2006.   PDF]

    In the present report, we study collections of contact relations on a fixed Boolean algebra and show that they can be provided with a rich lattice structure. This follows from a representation theorem which associates with each contact relation a closed graph on the ultrafilter space of the underlying Boolean algebra and vice versa. We also consider collections of special contact relations which have gained some importance in qualitative spatial reasoning.

  • Search Space Analysis of Recurrent Spiking and Continuous-time Neural Networks
    Mario Ventresca and Beatrice Ombuki , February 2006.   PDF]

    The problem of designing recurrent continuous-time and spiking neural networks is NP-Hard. A common practice is to utilize stochastic searches, such as evolutionary algorithms, to automatically construct acceptable networks. The outcome of the stochastic search is related to its ability to navigate the search space of neural networks and discover those of high quality. In this paper we investigate the search space associated with designing the above recurrent neural networks in order to differentiate which network should be easier to automatically design via a stochastic search. Our investigation utilizes two popular dynamic systems problems; (1) the Henon map and (2) the inverted pendulum as a benchmark.

  • Weak Realtional Products
    Michael Winter, March 2006.  [PDF

    The existence of relational products in categories of relations is strongly connected with the representability of that category. In this paper we propose a canonical weakening of the notion of a relational product. Unlike the strong version any (small) category of relations can be embedded into a suitable category providing all weak relational products. Furthermore, we investigate the categorical properties of the new construction and proof several (weak) versions of propositions well-known for relational products.

  • A Relation Algebraic Theory of Bisimulations
    Michael Winter, March 2006.  PDF

    In this paper we develop an algebraic/categorical theory of bisimulations using relational methods. We define a general notion, which is capable to handle different version of bisimilarity in a common context. Furthermore, the approach relates bisimulations with the notion of a covering known from the theory of graphs and their applications in topology and complex analysis.

  • Betweenness and comparability obtained from binary relations
    Ivo Düntsch and Alasdair Urquhart, March 2006.  PDF

    We give a brief overview of the axiomatic development of betweenness relations, and investigate the connections between these and comparability graphs. Furthermore, we characterize betweenness relations induced by reflexive and antisymmetric binary relations, thus generalizing earlier results on partial orders. We conclude with a sketch of the algorithmic aspects of recognizing induced betweenness relations.

  • Epistasis in Multi-Objective Evolutionary Recurrent Neuro-Controllers
    Mario Ventresca and Beatrice Ombuki-Berman, October 2006.  PDF

    This paper presents an information-theoretic analysis of the epistatic effects present in evolving recurrent neural networks. That is, how do the gene-gene interactions change as the evolutionary process progresses and what does this reveal about the problem difficulty. Also, to what end does the environment influence epistasis. Our investigation concentrates on multi-objective evolution, where the major task to be performed is broken into sub-tasks which are then used as our objectives. Our results show that the behavior of epistasis during the evolutionary process is strongly dependant on the environment. The experimental results are presented for the path finding robot application using continuous-time and spiking neuro-controllers.

  • Search Difficulty of Two-Connected Ring-based Topological Network Designs
    Beatrice Ombuki-Berman and Mario Ventresca, November 2006.  PDF

    Ring-based network design problems have many important applications, especially in the fields of logistics and telecommunications. This paper focuses on the recently proposed two-connected network with bounded rings problem. We investigate the search difficulty of both the Euclidean edge and unit edge length ring size bounds flavors of this problem by performing an information-theoretic fitness landscape analysis for several instances of the problem. Our results further confirm the hypothesis that the unit edge length version of the problem is indeed more difficult. The investigation also further reveals that smaller sized ring bounds lead to more difficult problems for both the Euclidean and unit edge length problems.


  • 2005

  • Relation algebras and their application in qualitative spatial reasoning
    I. Düntsch, February 2005.
    [abstract, PDF]
     
  • Evolutionary Algorithms for Optimal Error-Correcting Codes
    W. Haas and S. Houghten, May 2005.
    [abstract, PDF]
     
  • Evolving Dynamic Bayesian Networks with Multi-objective Genetic Algorithms
    B.J. Ross and E. Zuviria, May 2005.
    [abstract, PDF]
     
  • On Problems in Polymorphic Object-Oriented Languages With Self Types and Matching
    M. Winter, June 2005.
    [abstract, PDF]
     
  • Time-Dependent Contact Structures in Goguen Categories
    M. Winter, June 2005.
    [abstract, PDF]
     
  • Weak Contact Structures
    I. Düntsch and M. Winter, June 2005.
    [abstract, PDF]
     
  • Bounds on Optimal Edit Metric Codes
    S.K. Houghten, D. Ashlock and J. Lennarz, July 2005.
    [abstract, PDF]
     
  • Relational semantics through duality
    E. Orlowska, I. Rewitzky and I. Düntsch, July 2005.
    [abstract, PDF]
     
  • A Novel Variation Operator for More Rapid Evolution of DNA Error Correcting Codes
    D. Ashlock and S. Houghten, July 2005.
    [abstract, PDF]
     
  • Relational attribute systems II : Reasoning with relations in information structures
    I. Düntsch, G. Gediga and Ewa Orlowska, October 2005.
    [abstract, PDF]
     
  • Rough relation algebras revisited
    I. Düntsch and M. Winter, October 2005.
    [abstract, PDF]
     
  • Dynamic Vehicle Routing using Genetic Algorithms
    F.T. Hanshar and B.M. Ombuki, November 2005.
    [abstract, PDF]
     

2004

  • Construction of Boolean contact algebras
    I. Düntsch and M. Winter, January 2004.
    [abstract, PDF]
     
  • Multi-objective Genetic Algorithms for Vehicle Routing Problem with Time Windows
    B. Ombuki, B.J. Ross and F. Hanshar, January 2004.
    [abstract, PDF]
     
  • Rough set data representation using binary decision diagrams
    A. Muir, I. Düntsch and G. Gediga, February 2004.
    [abstract, PDF]
     
  • Ant Colony Optimization for Job Shop Scheduling Problem
    M. Ventresca and B.M. Ombuki, February 2004.
    [abstract, PDF]
     
  • Safety aspects of autonomous robot software development
    J.A. Barchanski, February 2004.
    [abstract, PDF]
     
  • On the direct scaling approach of eliciting aggregated fuzzy information: The psychophysical view
    G. Gediga, I. Düntsch and J. Adams-Webber, March 2004.
    [abstract, PDF]
     
  • Relational representation theorems for some lattice-based structures
    I. Düntsch, E. Orlowska, A.M. Radzikowska and D. Vakarelov, March 2004.
    [PDF]
     
  • Parsing probabilistic context free languages with multi-objective genetic algorithms
    R. Lefuel and B.J. Ross, May 2004.
    [in revision]
     
  • A genetic algorithm for the design of two-connected networks with bounded rings
    M. Ventresca and B. Ombuki, July 2004.
    [abstract, PDF]
     
  • An effective genetic algorithm for the multi-depot vehicle routing problem
    B. Ombuki and F. Hanshar, October 2004.
    [abstract, PDF(in revision)]
     
  • Region-based theory of discrete spaces: A proximity approach
    I. Düntsch and D. Vakarelov, November 2004.
    [abstract, PDF]
     

2003

  • Approximation operators in qualitative data analysis
    I. Düntsch and G. Gediga, January 2003.
    [abstract, PDF]
     
  • Lattice-based relation algebras and their representability
    I. Düntsch, E. Orlowska and A.M. Radzikowska, March 2003.
    [PDF]
     
  • Region-based theory of discrete spaces: A proximity approach
    I. Düntsch and D. Vakarelov, March 2003.
    [abstract, PDF]
     
  • Subject-Based File-Link System for the Web
    T. Arakawa and J.A. Barchanski, April 2003.
    [abstract, PDF]
     
  • Procedural 3D Texture Synthesis Using Genetic Programming
    A. Hewgill and B.J. Ross, April 2003.
    [abstract, PDF]
     
  • Relation algebras and their application in qualitative spatial reasoning
    I. Düntsch, September 2003.
    [PDF]
     
  • A Representation Theorem for Boolean Contact Algebras
    I. Düntsch and M. Winter, September 2003.
    [abstract, PDF]
     
  • An Algorithm for Adaptive Maximization of Speedup
    V. Wojcik and J. Martin, September 2003.
    [abstract, PDF]
     
  • Investigation of Perfect Ternary Arrays PTA(60,25)
    P. Becker, S. Houghten and W. Haas, October 2003.
    [abstract, PDF]
     
  • Relational Unsharpness and Processes
    P. Kempf and M. Winter, November 2003.
    [abstract, PDF]
     
  • Meta-heuristics for the Job Shop Scheduling Problem
    M. Ventresca and B.M. Ombuki, December 2003.
    [abstract, PDF]
     

2002

  • Skill Set Analyis in Knowledge Structures
    G. Gediga and I. Düntsch, May 2002.
    [abstract, PDF]
     
  • On model evaluation, indices of importance, and interaction values in rough set analysis
    G. Gediga and I. Düntsch, May 2002.
    [abstract, PDF]
     
  • Maximum consistency of incomplete data via non-invasive imputation
    G. Gediga and I. Düntsch, May 2002.
    [abstract, PDF]
     
  • Approximation quality for sorting rules
    G. Gediga and I. Düntsch, May 2002.
    [abstract, PDF]
     
  • Boolean algebras arising from information systems
    I. Düntsch and E. Orlowska, May 2002.
    [abstract, PDF]
     
  • Tangent circle algebras
    I. Düntsch and M. Roubens, May 2002.
    [abstract, PDF]
     
  • A Hybrid Search Based on Genetic Algorithms and Tabu Search for Vehicle Routing
    B.M. Ombuki, M. Nakamura and M. Osamu, May 2002.
    [abstract, PDF]
     
  • A Comparative Study of Search Techniques Applied to the Minimum Distance Problem of BCH Codes
    J.L. Wallis and S.K. Houghten, May 2002.
    [abstract, PDF]
     
  • The Extended Quadratic Residue Code is the only (48, 24, 12) Self-Dual Doubly-Even Code
    S.K. Houghten, C.W.H. Lam, L.H. Thiel, and J.A. Parker, May 2002.
    [abstract, PDF]
     
  • Optimal Ternary (10, 7) Error-Correcting Codes
    M.J. Letourneau and S.K. Houghten, May 2002.
    [abstract, PDF]
     
  • Evolving Protein Motifs Using a Stochastic Regular Language with Codon-Level Probabilities
    B.J. Ross, May 2002.
    [abstract, PDF]
     
  • Hyperspectral Image Analysis Using Genetic Programming
    B.J. Ross, A.G. Gualtieri, F. Fueten, and P. Budkewitsch, May 2002.
    [abstract, PDF]
     
  • Parallel Software Engineering: a Tutorial for the State of Mind
    V. Wojcik, May 2002.
    [abstract, PDF]
     
  • A Library of Anticipatory Random Number Generators
    V. Wojcik, May 2002.
    [abstract, PDF]
     
  • Modal-style Operators in Qualitative Data Analysis
    G. Gediga and I. Düntsch, May 2002.
    [abstract, PDF]
     
  • A Fast Randomisation Test for Rule Significance
    G. Gediga and I. Düntsch, May 2002.
    [abstract, PDF]
     
  • Real-Time Competitive Evolutionary Computation
    A. Hewgill, June 2002.
    [abstract, PDF]
     
  • Procedural Texture Evolution Using Multiobjective Optimization
    B.J. Ross and H. Zhu, July 2002.
    [abstract, PDF]
     
  • rmath User's and Technical Guide
    M.J. Letourneau, August 2002.
    [abstract, PDF]
     
  • Optimal Ternary (11, 7) and (14, 10) Codes
    M.J. Letourneau and S.K. Houghten, September 2002.
    [abstract, PDF]
     
  • A Proximity Approach to Some Region-Based Theories of Space
    D. Vakarelov, G. Dimov, I. Düntsch, and B. Bennett, November 2002.
    [abstract, PDF]
     
  • Local Search Genetic Algorithms for the Job Shop Scheduling Problem
    B. Ombuki, and M. Ventresca, November 2002.
    [abstract, PDF]
     
  • Searching for Search Algorithms: Experiments in Meta-search
    B.J. Ross, December 2002.
    [abstract, PDF]
     

2001

  • An Examination of Lamarckian Genetic Algorithms
    C. Wellock and B.J. Ross, July 2001.
    [abstract, PDF]
     

2000

  • Edge Detection of Petrographic Images Using Genetic Programming
    B.J. Ross, F. Fueten, and D. Yashkir, January 2000.
    [PS, ZIP]
     
  • Gentropy: Evolutionary 2D Texture Generation
    A. Wiens and B.J. Ross, May 2000.
    [PS, ZIP]
     
  • Autonomous Life Agent Using Recurrent Neural Networks and Genetic Algorithms
    T. Abou-Assaleh and J. Zhang, November 2000.
    [PS, ZIP]
     
  • The Search for a (46, 6, 1) Block Design
    S.K. Houghten, L.H. Thiel, J. Janssen, and C.W.H. Lam, November 2000.
    [Abstract, PDF]
     

1999

  • Probabilistic Pattern Matching and the Evolution of Stochastic Regular Expressions
    B.J. Ross, May 1999.
    [PS, ZIP]
     
  • Logic-based Genetic Programming with Definite Clause Translation Grammars
    B.J. Ross, June 1999.
    [PS, ZIP]
     
  • The Effects of Randomly Sampled Training Data on Program Evolution
    B.J. Ross, November 1999.
    [PS, ZIP]
     
  • Automatic Mineral Identification Using Genetic Programming
    B.J. Ross, F. Fueten, and D. Yashkir, December 1999.
    [PS]
     

1998

  • Design Issues of Wireless Communication for Cooperative Mobile Robot Teams
    J. Barchanski, September 1998.
     

1997


1996

  • The Evolution of Concurrent Programs
    B.J. Ross, July 1996.
     
  • Simulation Study of Digital Video Transfer on an Ethernet LAN
    J. Barchanski, November 1996.
     

1995

  • On Resolution of Ambiguity of Raster Images and addendum
    V. Wojcik, January 1995.
    [PS, addendum ZIP]
     
  • A Process Algebra for Stochastic Music Composition
    B.J. Ross, February 1995.
    [PS]
     
  • Loopless Gray Code Algorithms
    T. Jenkyns, July 1995.
    [PS]
     
  • A Symbiosis of Animation and Music
    R. Pringle and B.J. Ross, December 1995.
    [PS, addendum ZIP]
     

1994

  • A Process Algebra for Sequential and Concurrent Logic Programming
    B.J. Ross, June 1994.
     
  • The Inductive Inference of Finite Interleaving with Synchronization
    B.J. Ross, June 1994.
    [PS]
     
  • Running Programs Backwards: the Logical Inversion of Imperative Computation
    B.J. Ross, June 1994.
    [PS]