Departmental Reports

Printer-friendly version

Expanding Text Test

The following is a list of technical reports authored by computer science faculty at Brock University. Many of these reports are prepublications of papers submitted to journals, conferences, workshops, student theses, and work in progress. Please contact the authors for information about the most current versions of their research:


  • Mixed algebras and their logics
    Ivo Düntsch, Ewa Orlowska, and Tinko Tinchev, January 2016.  [PDF]   [abstract] [close]

    We investigate complex algebras of the form <2X , <R>, [[S]]> arising from a frame <X, R, S> where S ⊆ R, and exhibit their abstract algebraic and logical counterparts.


  • Simplifying contextual structures
    Ivo Düntsch and Günther Gediga, January 2015.  [PDF]   [abstract] [close]

    We present a method to reduce a formal context while retaining much of its information content. Although simple, our ICRA approach offers an effective way to reduce the complexity of concept lattices and / or knowledge spaces by changing only little information in comparison to a competing model which uses fuzzy K-Means clustering.

  • Rough set clustering
    Ivo Düntsch and Günther Gediga, January 2015.  [PDF]   [abstract] [close]

    We present a survey of clustering methods based on rough set data analysis.

  • A relational logic for spatial contact based on rough set approximation
    Ivo Düntsch and Ewa Orloska, Hui Wang, November 2015.  [PDF]   [abstract] [close]

    In previous work we have presented a class of algebras enhanced with two contact relation used in spatial reasoning on the basis of rough sets. In this paper we present a relational logic for such structures in the spirit of Rasiowa -- Sikorki proof systems.


  • Virtual Photography Using Multi-Objective Particle Swarm Optimization
    William Barry and Brian J. Ross, January 2014.  [PDF]   [abstract] [close]

    Particle swarm optimization (PSO) is a stochastic population-based search algorithm that is inspired by the flocking behaviour of birds. Here, a PSO is used to implement swarms of cameras flying through a virtual world in search of an image that satisfies a set of compositional constraints, for example, the rule of thirds and horizon line rules. To effectively process these multiple, and possible conflicting, criteria, a new multi-objective PSO algorithm called the sum of ranks PSO (SR-PSO) is introduced. The SR-PSO is useful for solving high-dimensional search problems, while discouraging degenerate solutions that can arise with other approaches. Less user intervention is required for the SR-PSO, as compared to a conventional PSO. A number of problems using different virtual worlds and user-supplied constraints were studied. In all cases, solution images were obtained that satisfied the majority of given constraints. The SR-PSO was shown to be superior to other algorithms in solving the high-dimensional virtual photography problems studied.

  • Passive Solar Building Design Using Genetic Programming
    Mohammad Mahdi Oraei Gholami and Brian J. Ross, January 2014.  [PDF]   [abstract] [close]

    Passive solar building design considers the effect that sunlight has on energy usage. The goal is to reduce the need for artificial cooling and heating devices, thereby saving energy costs. A number of competing design objectives can arise. Window heat gain during winter requires large windows. These same windows, however, reduce energy efficiency during nights and summers. Other model requirements add further complications, which creates a challenging optimization problem. We use genetic programming for passive solar building design. The EnergyPlus system is used to evaluate energy consumption. It considers factors ranging from model construction (shape, windows, materials) to location particulars (latitude/longitude, weather, time of day/year). We use a split grammar to build 3D models, and multi-objective fitness to evaluate the multiple design objectives. Experimental results showed that balancing window heat gain and total energy use is challenging, although our multi-objective strategy could find interesting compromises. Many factors (roof shape, material selection) were consistently optimized by evolution. We also found that geographic aspects of the location play a critical role in the final building design.

  • Feature Extraction Languages and Visual Pattern Recognition
    Mehran Maghoumi and Brian J. Ross, January 2014.  [PDF]   [abstract] [close]

    Visual pattern recognition and classification is a challenging computer vision problem. Genetic programming has been applied towards automatic visual pattern recognition. An important factor in evolving effective classifiers is the suitability of the GP language for defining expressions for feature extraction and classification. This research presents a comparative study of a variety of GP languages suitable for classification. Four different languages are examined, which use different selections of image processing operators. One of the languages does block classification, which means that an entire region of pixels is classified simultaneously. The other languages are pixel classifiers, which determine classification for a single pixel. Pixel classifiers are more common in the GP-vision literature. We tested the languages on different instances of Brodatz textures, as well as aerial and camera images. Our results show that the most effective languages are pixel-based ones with spatial operators. However, as is to be expected, the nature of the image will naturally determine the effectiveness of the language used.

  • Real-Time Automatic Object Classification and Tracking using Genetic Programming and NVidia® CudaTM
    Mehran Maghoumi, August 2014.  [PDF]   [abstract] [close]

    Genetic Programming (GP) is a widely used methodology for solving various computa- tional problems. GP’s problem solving ability is usually hindered by its long execution time for large and complex problems. In this thesis, GP is applied toward real-time com- puter vision. In particular, object classification and tracking using a parallel GP system is discussed. First, a study of suitable GP languages for object classification is presented. To this end two main GP approaches for visual pattern classification were studied. These approaches include the block-classifiers and the pixel-classifiers. According to the experi- ments, the pixel-classifiers were generally more accurate and performed better. Next, using the results of these experiments, a suitable language was selected for the implementation of the real-time tracking system. The real-time system was implemented using NVIDIA CUDA. Synthetic video data was used in the experiments. The goal of the experiments was to evolve a unique classifier for each texture pattern that was present in the video. The experiments revealed that the system was capable of correctly classifying and tracking the textures in the video. Furthermore, the performance of the system was on-par with real-time requirements.

  • Discrete dualities for n-potent MTL–algebras and 2-potent BL–algebras
    Ivo Düntsch, Ewa Orłowska, Clint van Alten, September 2014.  [PDF]   [abstract] [close]

    Discrete dualities are developed for n-potent MTL–algebras and for 2-potent BL–algebras. That is, classes of frames, or relational systems, are defined that serve as dual counterparts to these classes of algebras. The frames defined here are extensions of the frames that were developed for MTL–algebras by Orlowska, Radzikowska (2009) and Orlowska, Rewitzky (2010) ; the additional frame conditions required are given here and also the proofs that discrete dualities hold with respect to such frames. The duality also provides an embedding from an n-potent MTL–algebra, or 2-potent BL–algebra, into the complex algebra of its canonical frame, which is a complete algebra in the lattice sense.


  • Discrete PSO for the Uncapacitated Single Allocation Hub Location Problem
    Alexander Bailey, Beatrice Ombuki-Berman, Stephen Asobiela, January 2013.  [PDF]   [abstract] [close]

    Efficient network design and optimization of transportation and distribution systems has significant economic and service efficiency implications for both the public and private sectors. We propose a new solution based on a particle swarm optimization (PSO) for the uncapacitated single allocation hub location problem (USAHLP). Although various meta-heuristics have been proposed for this problem, to the authors. knowledge, this is the first attempt to use a PSO framework for this problem. An empirical study is done using well-known benchmark problems from the Civil Aeronautics Board and Australian Post data sets with node sizes of up to 200. The beauty of the proposed approach is its simplicity and effectiveness, where its solution quality is compared with that of other meta-heuristics. The proposed discrete PSO matches or out-performs the solution quality of the current best-known methods for the USAHLP.

  • On the homogeneous countable Boolean contact algebra
    Ivo Düntsch and Sangiang Li, March 2013.  [PDF]   [abstract] [close]

    In a recent paper, we have shown that the class of Boolean contact algebras (BCAs) has the hereditary property, the joint embedding property and the amalgamation property. By Fraïssé.s theorem, this shows that there is a unique countable homogeneous BCA. This paper investigates this algebra and the relation algebra generated by its contact relation. We first show that the algebra can be partitioned into four sets f0g, f1g, K, and L, which are the only orbits of the group of base automorphisms of the algebra, and then show that the contact relation algebra of this algebra is finite, which is the first non.trivial extensional BCA we know which has this property.

  • Generative Representations for Artificial Architecture and Passive Solar Performance
    Adrian Harrington and Brian J. Ross, March 2013.  [PDF]   [abstract] [close]

    This paper explores how the use of generative representations improves the quality of solutions in evolutionary design problems. A genetic programming system is developed with individuals encoded as generative representations. Two research goals motivate this work. One goal is to examine Hornby.s features and measures of modularity, reuse and hierarchy in new and more complex evolutionary design problems. In particular, we consider a more difficult problem domain where the generated 3D models are no longer constrained by voxels. Experiments are carried out to generate 3D models which grow towards a set of target points. The results show that the generative representations with the three features of modularity, regularity and hierarchy performed best overall. Although the measures of these features were largely consistent to those of Hornby, a few differences were found.

    Our second research goal is to use the best performing encoding on some 3D modeling problems that involve passive solar performance criteria. Here, the system is challenged with generating forms that optimize exposure to the Sun. This is complicated by the fact that a model.s structure can interfere with solar exposure to itself; for example, protrusions can block Sun exposure to other model elements. Furthermore, external environmental factors (geographic location, time of the day, time of the year, other buildings in the proximity) may also be relevant. Experimental results were successful, and the system was shown to scale well to the architectural problems studied.

  • Automatic Inference of Hierarchical Graph Models Using Genetic Programming with an Application to Cortical Networks
    Alexander Bailey, Beatrice Ombuki-Berman, Mario Ventresca, March 2013.  [PDF]   [abstract] [close]

    The pathways that relay sensory information within the brain form a network of connections, the precise organization of which is unknown. Communities of neurons can be discerned within this tangled structure, with inhomogeneously distributed connections existing between cortical areas. Classification and modelling of these networks has led to advancements in the identification of unhealthy or injured brains, however, the current models used are known to have major deficiencies. Specifically, the community structure of the cortex is not accounted for in existing algorithms, and it is unclear how to properly design a more representative graph model. It has recently been demonstrated that genetic programming may be useful for inferring accurate graph models, although no study to date has investigated the ability to replicate community structure. In this paper we propose the first GP system for the automatic inference of algorithms capable of generating, to a high accuracy, networks with community structure. We utilize a common cat cortex data set to highlight the efficacy of our approach. Our experiments clearly show that the inferred graph model generates a more representative network than those currently used in scientific literature.

  • A Scalability Study of Multi-Objective Particle Swarm Optimizers
    Kyle Robert Harrison, Andries P. Engelbrecht, Beatrice Ombuki-Berman, March 2013.  [PDF]   [abstract] [close]

    Particle swarm optimization (PSO) is a well-known optimization technique originally proposed for solving singleobjective, continuous optimization problems. However, PSO has been extended in various ways to handle multi-objective optimization problems (MOPs). The scalability of multi-objective PSO algorithms as the number of sub-objectives increases has not been well examined; most observations are for two to four objectives. It has been observed that the performance of multiobjective optimizers for a low number of sub-objectives can not be generalized to problems with higher numbers of sub-objectives. With this in mind, this paper presents a scalability study of three well-known multi-objective PSOs, namely vector evaluated PSO (VEPSO), optimized multi-objective PSO (oMOPSO), and speed-constrained multi-objective PSO (SMPSO) with up to eight sub-objectives. The study indicates that as the number of subobjectives increases, SMPSO scaled the best, oMOPSO scaled the worst, while VEPSO.s performance was dependent on the knowledge transfer strategy (KTS) employed, with parent centric recombination (PCX) based approaches scaling consistently better.

  • PRE and variable precision models in rough set data analysis
    Ivo Düntsch and Günther Gediga, April 2013.  [PDF]   [abstract] [close]

    We present a parameter free and monotonic alternative to the parametric variable precision model of rough set data analysis. The proposed model is based on the well known PRE index lambda of Goodman and Kruskal. Using a weighted lambda model it is possible to define a two dimensional space based on (Rough) sensitivity and (Rough) specificity, for which the monotonicity of sensitivity in a chain of sets is a nice feature of the model. As specificity is often monotone as well, the results of a rough set analysis can be displayed like a receiver operation curve (ROC) in statistics. Another aspect deals with the precision of the prediction of categories -- normally measured by an index alpha in classical rough set data analysis. We offer a statistical theory for alpha and a modification of alpha which fits the needs of our proposed model. Furthermore, we show how expert knowledge can be integrated without losing the monotonic property of the index. Based on a weighted lambda, we present a polynomial algorithm to determine an approximately optimal set of predicting attributes. Finally, we exhibit a connection to Bayesian analysis. We present several simulation studies for the presented concepts. The current paper is an extended version of a paper presented at FedCSiS 2012.

  • Standard errors of indices in rough set data analysis
    Günther Gediga and Ivo Düntsch, April 2013.  [PDF]   [abstract] [close]

    The sample variation of indices for approximation of sets in the context of rough sets data analysis is considered. We consider the gamma and alpha indices and some other ones - lower and upper bound approximation of decision classes. We derive confidence bounds for these indices as well as a two group comparison procedure. Finally we present procedures to compare the approximation quality of two sets within one sample.

  • Genetic Programming for Non-Photorealistic Rendering
    Maryam Baniasadi, June 2013.  [PDF]   [abstract] [close]

    This thesis focuses on developing an evolutionary art system using genetic programming. The main goal is to produce new forms of evolutionary art that alter existing images into new non-photorealistic (NPR) styles, by obtaining images that look like traditional media such as watercolor or pencil, as well as brand new effects. The approach permits GP to generate creative forms of NPR results. The GP language is extended with different techniques and methods inspired from NPR research such as colour mixing expressions, image processing filters and painting algorithm. Colour mixing is a major new contribution, as it enables many familiar and innovative NPR effects to arise. Another major innovation is that many GP functions process the canvas (rendered image), while is dynamically changing. Automatic fitness scoring uses aesthetic evaluation models and statistical analysis, and multi-objective fitness evaluation is used. Results showed a variety of NPR effects, as well as new, creative possibilities.

  • Standard Errors of Indicies in Rough Set Data Analysis
    Günther Gediga and Ivo Düntsch.  [PDF]   [abstract] [close]

    The sample variation of indices for approximation of sets in the context of rough sets data analysis is considered. We consider the gamma and alpha indices and some other ones – lower and upper bound approximation of decision classes. We derive confidence bounds for these indices as well as a two group comparison procedure. Finally we present procedures to compare the approximation quality of two sets within one sample

  • Relational Properties of Sequential Composition of Co-Algebras
    Michael Winter and Peter Kempf, October 2013.  [PDF]   [abstract] [close]

    In this paper we define a sequential composition for arbitrary co-algebras in a Dedekind category. We show some basic algebraic properties of this operation up to bisimulation. Furthermore, we consider certain recursive equations and provide an explicit solution, i.e., a solution not based on an iterative process.

  • Passive Solar Building Design Using Genetic Programming
    Mohammad Mahdi Oraei Gholami, October 2013.  [PDF]   [abstract] [close]

    Passive solar building design is the process of designing a building while considering sunlight exposure for receiving heat in winter and rejecting heat in summer. The main goal of a passive solar building design is to remove or reduce the need of mechanical and electrical systems for cooling and heating, and therefore saving energy costs and reducing environmental impact. This research will use evolutionary computation to design passive solar buildings. Evolutionary design is used in many research projects to build 3D models for structures automatically. In this research, we use a mixture of split grammar and string-rewriting for generating new 3D structures. To evaluate energy costs, the EnergyPlus system is used. This is a comprehensive building energy simulation system, which will be used alongside the genetic programming system. In addition, genetic programming will also consider other design and geometry characteristics of the building as search objectives, for example, window placement, building shape, size, and complexity. In passive solar designs, reducing energy that is needed for cooling and heating are two objectives of interest. Experiments show that smaller buildings with no windows and skylights are the most energy efficient models. Window heat gain is another objective used to encourage models to have windows. In addition, window and volume based objectives are tried. To examine the impact of environment on designs, experiments are run on five different geographic locations. Also, both single floor models and multi-floor models are examined in this research. According to the experiments, solutions from the experiments were consistent with respect to materials, sizes, and appearance, and satisfied problem constraints in all instances.


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

    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]   [abstract] [close]

    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]   [abstract] [close]

    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]   [abstract] [close]

    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]   [abstract] [close]

    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]   [abstract] [close]

    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]   [abstract] [close]

    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]   [abstract] [close]

    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]   [abstract] [close]

    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]   [abstract] [close]

    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.


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

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

    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]   [abstract] [close]

    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]   [abstract] [close]

    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 generated.

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

    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

    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]   [abstract] [close]

    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]   [abstract] [close]

    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]   [abstract] [close]

    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.


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

    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]   [abstract] [close]

    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]   [abstract] [close]

    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]   [abstract] [close]

    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]   [abstract] [close]

    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.

For reports from before 2010, please look in the Archives

All papers are Copyright © of the respective authors.