Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Design of Representations and Search Operators
2015
Successful and efficient use of evolutionary algorithms depends on the choice of genotypes and the representation – that is, the mapping from genotype to phenotype – and on the choice of search operators that are applied to the genotypes. These choices cannot be made independently of each other. This chapter gives recommendations on the design of representations and corresponding search operators and discusses how to consider problem-specific knowledge. For most problems in the real world, similar solutions have similar fitness values. This fact can be exploited by evolutionary algorithms if they ensure that the representations and search operators used are defined in such a way that simila…
Representations for evolutionary algorithms
2015
Successful and efficient use of evolutionary algorithms (EA) depends on the choice of the genotype, the problem representation (mapping from genotype to phenotype) and on the choice of search operators that are applied to the genotypes. These choices cannot be made independently of each other. The question whether a certain representation leads to better performing EAs than an alternative representation can only be answered when the operators applied are taken into consideration. The reverse is also true: deciding between alternative operators is only meaningful for a given representation. In EA practice one can distinguish two complementary approaches. The first approach uses indirect repr…
High Locality Representations for Automated Programming
2011
We study the locality of the genotype-phenotype mapping used in grammatical evolution (GE). GE is a variant of genetic programming that can evolve complete programs in an arbitrary language using a variable-length binary string. In contrast to standard GP, which applies search operators directly to phenotypes, GE uses an additional mapping and applies search operators to binary genotypes. Therefore, there is a large semantic gap between genotypes (binary strings) and phenotypes (programs or expressions). The case study shows that the mapping used in GE has low locality leading to low performance of standard mutation operators. The study at hand is an example of how basic design principles o…
Optimal Resource Discovery Paths of Gnutella2
2008
This paper shows that the performance of peer-to-peer resource discovery algorithms is upper bounded by a k-Steiner minimum tree and proposes an algorithm locating near-optimal query paths for the peer-to-peer resource discovery problem. Global knowledge of the topology and the resources from the peer-to-peer network are required as an input to the algorithm. The algorithm provides an objective measure for defining how good local search algorithms are. The performance is evaluated in simulated peer-to-peer scenarios and in the measured Gnutella2 P2P network topology with four local search algorithms: breadth-first search, self-avoiding random walker, highest degree search and Dynamic Query …
Online Induction of Probabilistic Real Time Automata
2012
Probabilistic real time automata (PRTAs) are a representation of dynamic processes arising in the sciences and industry. Currently, the induction of automata is divided into two steps: the creation of the prefix tree acceptor (PTA) and the merge procedure based on clustering of the states. These two steps can be very time intensive when a PRTA is to be induced for massive or even unbounded data sets. The latter one can be efficiently processed, as there exist scalable online clustering algorithms. However, the creation of the PTA still can be very time consuming. To overcome this problem, we propose a genuine online PRTA induction approach that incorporates new instances by first collapsing…
E-learning approach of the graph coloring problem applied to register allocation in embedded systems
2016
The main aim of this paper consists in developing an effective e-learning tool, focused on evolutionary algorithms, in order to solve the graph coloring problem. Subsidiary, we apply graph coloring for register allocation in embedded systems. From didactic viewpoint, our tool has benefits in the learning process because it helps students to observe the relationship between the graph coloring problem and CPU registers allocation with the help of four developed modules: the genetic algorithm, the graphical viewer, the interference graph for a C program and a web application which collects the simulation results. All these applications are combined by a graphical interface which allows the use…
LeSSS: Learned Shared Semantic Spaces for Relating Multi-Modal Representations of 3D Shapes
2015
In this paper, we propose a new method for structuring multi-modal representations of shapes according to semantic relations. We learn a metric that links semantically similar objects represented in different modalities. First, 3D-shapes are associated with textual labels by learning how textual attributes are related to the observed geometry. Correlations between similar labels are captured by simultaneously embedding labels and shape descriptors into a common latent space in which an inner product corresponds to similarity. The mapping is learned robustly by optimizing a rank-based loss function under a sparseness prior for the spectrum of the matrix of all classifiers. Second, we extend …
Learning small programs with additional information
1997
This paper was inspired by [FBW 94]. An arbitrary upper bound on the size of some program for the target function suffices for the learning of some program for this function. In [FBW 94] it was discovered that if “learning” is understood as “identification in the limit,” then in some programming languages it is possible to learn a program of size not exceeding the bound, while in some other programming languages this is not possible.
On the use of neighbourhood-based non-parametric classifiers
1997
Alternative non-parametric classification schemes, which come from the use of different definitions of neighbourhood, are introduced. In particular, the Nearest Centroid Neighbourhood along with the neighbourhood relation derived from the Gabriel Graph and the Relative Neighbourhood Graph are used to define the corresponding (k-)Nearest Neighbour-like classifiers. Experimental results are reported to compare the performance of the approaches proposed here to the one obtained with the k-Nearest Neighbours rule.
The power of procrastination in inductive inference: How it depends on used ordinal notations
1995
We consider inductive inference with procrastination. Usually it is defined using constructive ordinals. For constructive ordinals there exist many different systems of notations. In this paper we study how the power of inductive inference depends on used system of notations.