JournalTOCs

Evolutionary Intelligence

Subscription journal
ISSN (Print) 1864-5917 - ISSN (Online) 1864-5909
Published by Springer-Verlag

[2216 journals]

Accelerating IEC and EC searches with elite obtained by dimensionality reduction in regression spaces
- Abstract: Abstract We propose a method for accelerating interactive evolutionary computation (IEC) and evolutionary computation (EC) searches using elite obtained in one-dimensional spaces and use benchmark functions to evaluate the proposed method. The method projects individuals onto n one-dimensional spaces corresponding to each of the n searching parameter axes, approximates each landscape using interpolation or an approximation method, finds the best coordinate from the approximated shape, obtains the elite by combining the best n found coordinates, and uses the elite for the next generation of the IEC or EC. The advantage of this method is that the elite may be easily obtained thanks to their projection onto each one-dimensional space and there is a higher possibility that the elite individual locates near the global optimum. We compare the proposal with methods for obtaining the landscape in the original search space, and show that our proposed method can significantly save computational time. Experimental evaluations of the technique with differential evolution using a simulated IEC user (Gaussian mixture model with different dimensions) and 34 benchmark functions show that the proposed method substantially accelerates IEC and EC searches.
  PubDate: 2013-05-16
Knowledge extraction and rule set compaction in XCS for non-Markov multi-step problems
- Abstract: Abstract The application of the XCS family of classifier systems within multi-step problems has shown promise, but XCS classifier systems usually solve those problems with a large number of classifiers. If they can generate compact and readily interpretable solutions when used in multi-step problems, it will enhance their applicability and usefulness in a wide range of robot control and knowledge discovery tasks. In this paper, we describe some methods developed for XCS to compact the rule set and acquire explicit policy knowledge for multi-step problems, especially non-Markov problems. Experimental results show the ability to obtain a very compact rule set out of the final population of classifiers with little or no degradation of overall performance.
  PubDate: 2013-04-30
Scalable multiagent learning through indirect encoding of policy geometry
- Abstract: Abstract Multiagent systems present many challenging, real-world problems to artificial intelligence. Because it is difficult to engineer the behaviors of multiple cooperating agents by hand, multiagent learning has become a popular approach to their design. While there are a variety of traditional approaches to multiagent learning, many suffer from increased computational costs for large teams and the problem of reinvention (that is, the inability to recognize that certain skills are shared by some or all team member). This paper presents an alternative approach to multiagent learning called multiagent HyperNEAT that represents the team as a pattern of policies rather than as a set of individual agents. The main idea is that an agent’s location within a canonical team layout (which can be physical, such as positions on a sports team, or conceptual, such as an agent’s relative speed) tends to dictate its role within that team. This paper introduces the term policy geometry to describe this relationship between role and position on the team. Interestingly, such patterns effectively represent up to an infinite number of multiagent policies that can be sampled from the policy geometry as needed to allow training very large teams or, in some cases, scaling up the size of a team without additional learning. In this paper, multiagent HyperNEAT is compared to a traditional learning method, multiagent Sarsa(λ), in a predator–prey domain, where it demonstrates its ability to train large teams.
  PubDate: 2013-01-01
Embodied artificial evolution
- Abstract: Abstract Evolution is one of the major omnipresent powers in the universe that has been studied for about two centuries. Recent scientific and technical developments make it possible to make the transition from passively understanding to actively using evolutionary processes. Today this is possible in Evolutionary Computing, where human experimenters can design and manipulate all components of evolutionary processes in digital spaces. We argue that in the near future it will be possible to implement artificial evolutionary processes outside such imaginary spaces and make them physically embodied. In other words, we envision the “Evolution of Things”, rather than just the evolution of digital objects, leading to a new field of Embodied Artificial Evolution (EAE). The main objective of this paper is to present a unifying vision in order to aid the development of this high potential research area. To this end, we introduce the notion of EAE, discuss a few examples and applications, and elaborate on the expected benefits as well as the grand challenges this developing field will have to address.
  PubDate: 2012-12-01
Meta-heuristic approach to proportional fairness
- Abstract: Abstract Proportional fairness is a concept from resource sharing tasks among n users, where each user receives at least 1/n of her or his total value of the infinitely divisible resource. Here we provide an approach to proportional fairness that allows its extension to discrete domains, as well as for the direct application of evolutionary computation to approximate proportional fair states. We employ the concept of relational optimization, where the optimization task becomes the finding of extreme elements of a binary relation, and define a proportional fairness relation correspondingly. By using a rank-ordered version of proportional fairness, the so-called ordered proportional fairness, we can improve the active finding of maximal proportional fair elements by evolutionary meta-heuristic algorithms. This is demonstrated by using modified versions of the strength pareto evolutionary algorithm (version 2, SPEA2) and multi-objective particle swarm optimization. In comparison between proportional and ordered proportional fairness, and by using relational SPEA2, the evolved maximum sets of ordered proportional fairness achieve 10 % more dominance cases against a set of random vectors than proportional fairness.
  PubDate: 2012-12-01
Exploratory analysis of an on-line evolutionary algorithm in simulated robots
- Abstract: Abstract In traditional evolutionary robotics, robot controllers are evolved in a separate design phase preceding actual deployment; we call this off-line evolution. Alternatively, robot controllers can evolve while the robots perform their proper tasks, during the actual operational phase; we call this on-line evolution. In this paper we describe three principal categories of on-line evolution for developing robot controllers (encapsulated, distributed, and hybrid), present an evolutionary algorithm belonging to the first category (the (μ + 1) on-line algorithm), and perform an extensive study of its behaviour. In particular, we use the Bonesa parameter tuning method to explore its parameter space. This delivers near-optimal settings for our algorithm in a number of tasks and, even more importantly, it offers profound insights into the impact of our algorithm’s parameters and features. Our experimental analysis of (μ + 1) on-line shows that it seems preferable to try many alternative solutions and spend little effort on refining possibly faulty assessments; that there is no single combination of parameters that performs well on all problem instances and that the most influential parameter of this algorithm—and therefore the prime candidate for a control scheme—is the evaluation length τ.
  PubDate: 2012-12-01
Evolutionary linkage creation between information sources in P2P networks
- Abstract: Abstract The present paper proposes a peer-to-peer (P2P) information retrieval and sharing system that evolutionarily creates linkages of information sources that are useful for both information publishers and information users, where information is managed in a decentralized manner. The proposed system relies on interactions among information publishers who actually generate information and have the greatest knowledge of the information, information users who use the information, and a network that creates useful linkages of information sources (information publishers). In order to enhance the value of their own information sources, information publishers propose new linkages of information sources that indicate information sources with which they would like to have their own information sources co-occur. The information users evaluate the linkages proposed by the information publishers. The network evolutionarily reconstructs the topological structures of the P2P network based on the fitness obtained from the users. Simulation results suggest that it is possible to find more information sources that users desire using the topological structures reconstructed by the proposed system, as compared to the use of non-reconstructed topological structures.
  PubDate: 2012-12-01
Kernel representations for evolving continuous functions
- Abstract: Abstract To parameterize continuous functions for evolutionary learning, we use kernel expansions in nested sequences of function spaces of growing complexity. This approach is particularly powerful when dealing with non-convex constraints and discontinuous objective functions. Kernel methods offer a number of beneficial properties for parameterizing continuous functions, such as smoothness and locality, which make them attractive as a basis for mutation operators. Beyond such practical considerations, kernel methods make heavy use of inner products in function space and offer a well established regularization framework. We show how evolutionary computation can profit from these properties. Searching function spaces of iteratively increasing complexity allows the solution to evolve from a simple first guess to a complex and highly refined function. At transition points where the evolution strategy is confronted with the next level of functional complexity, the kernel framework can be used to project the search distribution into the extended search space. The feasibility of the method is demonstrated on challenging trajectory planning problems where redundant robots have to avoid obstacles.
  PubDate: 2012-09-01
Efficient recurrent local search strategies for semi- and unsupervised regularized least-squares classification
- Abstract: Abstract Binary classification tasks are among the most important ones in the field of machine learning. One prominent approach to address such tasks are support vector machines which aim at finding a hyperplane separating two classes well such that the induced distance between the hyperplane and the patterns is maximized. In general, sufficient labeled data is needed for such classification settings to obtain reasonable models. However, labeled data is often rare in real-world learning scenarios while unlabeled data can be obtained easily. For this reason, the concept of support vector machines has also been extended to semi- and unsupervised settings: in the unsupervised case, one aims at finding a partition of the data into two classes such that a subsequent application of a support vector machine leads to the best overall result. Similarly, given both a labeled and an unlabeled part, semi-supervised support vector machines favor decision hyperplanes that lie in a low density area induced by the unlabeled training patterns, while still considering the labeled part of the data. The associated optimization problems for both the semi- and unsupervised case, however, are of combinatorial nature and, hence, difficult to solve. In this work, we present efficient implementations of simple local search strategies for (variants of) the both cases that are based on matrix update schemes for the intermediate candidate solutions. We evaluate the performances of the resulting approaches on a variety of artificial and real-world data sets. The results indicate that our approaches can successfully incorporate unlabeled data. (The unsupervised case was originally proposed by Gieseke F, Pahikkala et al. (2009). The derivations presented in this work are new and comprehend the old ones (for the unsupervised setting) as a special case.)
  PubDate: 2012-09-01
Response to Pauline Hogeweg’s review of my book, “Evolution: a view from the 21st century”
- PubDate: 2012-09-01
Evolutionary kernel machines
- PubDate: 2012-09-01
James A. Shapiro: Evolution: a view from the twenty-first century
- PubDate: 2012-09-01
Tuning and evolution of support vector kernels
- Abstract: Abstract Kernel-based methods like Support Vector Machines (SVM) have been established as powerful techniques in machine learning. The idea of SVM is to perform a mapping from the input space to a higher-dimensional feature space using a kernel function, so that a linear learning algorithm can be employed. However, the burden of choosing the appropriate kernel function is usually left to the user. It can easily be shown that the accuracy of the learned model highly depends on the chosen kernel function and its parameters, especially for complex tasks. In order to obtain a good classification or regression model, an appropriate kernel function in combination with optimized pre- and post-processed data must be used. To circumvent these obstacles, we present two solutions for optimizing kernel functions: (a) automated hyperparameter tuning of kernel functions combined with an optimization of pre- and post-processing options by Sequential Parameter Optimization (SPO) and (b) evolving new kernel functions by Genetic Programming (GP). We review modern techniques for both approaches, comparing their different strengths and weaknesses. We apply tuning to SVM kernels for both regression and classification. Automatic hyperparameter tuning of standard kernels and pre- and post-processing options always yielded to systems with excellent prediction accuracy on the considered problems. Especially SPO-tuned kernels lead to much better results than all other tested tuning approaches. Regarding GP-based kernel evolution, our method rediscovered multiple standard kernels, but no significant improvements over standard kernels were obtained.
  PubDate: 2012-09-01
On XCSR for electronic fraud detection
- Abstract: Fraud is a serious problem that costs the worldwide economy billions of dollars annually. However, fraud detection is difficult as perpetrators actively attempt to mask their actions, among typically overwhelming large volumes of, legitimate activity. In this paper, we investigate the fraud detection problem and examine how learning classifier systems can be applied to it. We describe the common properties of fraud, introducing an abstract problem which can be tuned to exhibit those characteristics. We report experiments on this abstract problem with a popular real-time learning classifier system algorithm; results from our experiments demonstrating that this approach can overcome the difficulties inherent to the fraud detection problem. Finally we apply the algorithm to a real-world problem and show that it can achieve good performance in this domain.
  PubDate: 2012-06-01
Risk neutrality in learning classifier systems
- Abstract: Abstract Both economics and biology have come to agree that successful behavior in a stochastic environment responds to the variance of potential outcomes. Unfortunately, when biological and economic paradigms are mated together in a learning classifier system (LCS), decision-making agents called classifiers typically simply ignore risk. Since a fundamental problem of learning is risk management, LCS have not always performed as well as theoretically predicted. This paper develops a novel model of risk-neutral reinforcement learning in a traditional Bucket Brigade credit-allocation market under the pressure of a Genetic Algorithm. I demonstrate the applicability of the basic model to the classical LCS design and reexamine two basic issues where traditional LCS performance fails to meet expectations: default hierarchies and long chains of coupled classifiers. Risk-neutrality and noisy probabilistic auctions create dynamic instability in both areas, while identical preferences result in market failure in default hierarchies and exponential attenuation of price signals down classifier chains. Despite the limitations of simple risk-neutral classifiers, I show they’re capable of cheap short-run emulation of more rational behaviors. Still, risk-neutral information markets are a dead end. The model suggests a path toward a new type of LCS built on stable, heterogeneous, and risk-averse preferences under efficient auctions and access to more complete markets exploitable by competing risk management strategies. This will require a radical rethinking of the evolutionary and economic algorithms, but ultimately heralds a return to a market-based approach to LCS.
  PubDate: 2012-06-01
Production system rules as protein complexes from genetic regulatory networks: an initial study
- Abstract: Abstract This short paper introduces a new way by which to design production system rules. An indirect encoding scheme is presented which views such rules as protein complexes produced by the temporal behaviour of an artificial genetic regulatory network. This initial study begins by using a simple Boolean regulatory network to produce traditional ternary-encoded rules before moving to a fuzzy variant to produce real-valued rules. Competitive performance is shown with related genetic regulatory networks and rule-based systems on benchmark problems.
  PubDate: 2012-06-01
Analysing BioHEL using challenging boolean functions
- Abstract: Abstract In this work we present an extensive empirical analysis of the BioHEL genetics-based machine learning system using the k-Disjunctive Normal Form (k-DNF) family of boolean functions. These functions present a broad set of possible challenges for most machine learning techniques, such as different degrees of specificity, class imbalance and niche overlap. Moreover, as the ideal solutions are known, it is possible to assess if a learning system is able to find them, and how fast. Specifically, we study two aspects of BioHEL: its sensitivity to the coverage breakpoint parameter (that determines the degree of generality pressure applied by the fitness function) and the impact of the default rule policy. The results show that BioHEL is highly sensitive to the choice of coverage breakpoint and that using a default class suitable for the problem allows the system to learn faster than using other default class policies (e.g. the majority class policy). Moreover, the experiments indicate that BioHEL’s scalability depends directly on both k (the specificity of the k-DNF terms) and the number of terms in the problem. In the last part of the paper we discuss alternative policies to adjust the coverage breakpoint parameter.
  PubDate: 2012-06-01
Special issue on advances in learning classifier systems
- PubDate: 2012-06-01
XCSF with local deletion: preventing detrimental forgetting
- Abstract: Abstract The XCSF classifier system iteratively solves regression problems with a population of overlapping, local approximators. We show that problem solution stability and accuracy may be lost in particular settings—mainly due to XCSF’s global deletion. We introduce local deletion, which prevents these detrimental effects to large extents. We show experimentally that local deletion can prevent forgetting in various problems—particularly where the problem space is non-uniformly or non-independently sampled. While we use XCSF with hyper-ellipsoidal receptive fields and linear approximations herein, local deletion can be applied to any XCS version where locality can be similarly defined. For future work, we propose to apply XCSF with local deletion to unbalanced, non-uniformly distributed, locally sampled problems with complex manifold structures, within which varying target error values may be reached selectively.
  PubDate: 2012-06-01
On principal component analysis for high-dimensional XCSR
- Abstract: Abstract XCSR is an accuracy-based learning classifier system which can handle classification problems with real-value features. However, as the number of features increases, a high classification accuracy comes at the cost of more resources: larger population sizes and longer computational running times. In this paper we investigate PCA-XCSR (a sequential application of PCA and XCSR) in three environments with different characteristics: a discrete and imbalanced environment (KDD’99 network intrusion), a continuous and highly symmetric environment (MiniBooNE), and a highly discrete, highly imbalanced environment (Census/Income (KDD)). These experiments show that in the three different environments, PCA-XCSR, in addition to being able to reduce the computational resources and time requirements of XCSR by approximately 50 %, is able to consistently maintain its high accuracy. In addition to that, it reduces the required population size needed by XCSR. Also, we suggest heuristics for selecting the number of principal components to use when using PCA-XCSR.
  PubDate: 2012-06-01