8590688
Evolutionary tree genetic programming
We introduce a clustering-based method of subpopulation management in genetic programming (GP) called Evolutionary Tree Genetic Programming (ETGP). The biological motivation behind this work is the observation that the natural evolution follows a tree-like phylogenetic pattern. Our goal is to simulate similar behavior in artificial evolutionary systems such as GP. To test our model we use three common GP benchmarks: the Ant Algorithm, 11-Multiplexer, and Parity problems.The performance of the ETGP system is empirically compared to those of the GP system. Code size and variance are consistently reduced by a small but statistically significant percentage, resulting in a slight speedup in the Ant and 11-Multiplexer problems, while the same comparisons on the Parity problem are inconclusive.
39278459
Genetic Algorithms for Reformulation of Large-Scale KDD Problems with Many Irrelevant Attributes
The goal of this research is to apply genetic implementations of algorithms for selection, partitioning, and synthesis of attributes in large-scale data mining problems. Domain knowledge about these operators has been shown to reduce the number of fitness evaluations for candidate attributes. We report results on genetic optimization of attribute selection problems and current work on attribute partitioning, synthesis specifications, and the encoding of domain knowledge about operators in a fitness function. The purpose of this approach is to reduce overfitting in inductive learning and produce more general genetic versions of existing search-based algorithms (or wrappers) for KDD performance tuning [KS98, HG00]. Several GA implementations of alternative attribute synthesis algorithms are applied to concept learning problems in military and commercial KDD applications. One of these, Jenesis, is deployed on several network-of-workstation clusters. It is shown to achieve strongly improved test set accuracy, compared to unwrapped decision tree learning and search-based wrappers [KS98].
18622837
Graph Drawing Heuristics for Path Finding in Large Dimensionless Graphs
This paper presents a heuristic for guiding A*search for approximating the shortest path between two vertices in arbitrarily-sized dimensionless graphs. First we discuss methods by which these dimensionless graphs are laid out into Euclidean drawings. Next, two heuristics are computed based on drawings of the graphs. We compare the performance of an A*-search using these heuristics with breadth-first search on graphs with various topological properties. The results show a large savings in the number of vertices expanded for large graphs.
5371240
A machine learning approach to algorithm selection for 
$\mathcal{NP}$
-hard optimization problems: a case study on the MPE problem
Abstract
Given one instance of an 
$\mathcal{NP}$
-hard optimization problem, can we tell in advance whether it is exactly solvable or not? If it is not, can we predict which approximate algorithm is the best to solve it? Since the behavior of most approximate, randomized, and heuristic search algorithms for 
$\mathcal{NP}$
-hard problems is usually very difficult to characterize analytically, researchers have turned to experimental methods in order to answer these questions. In this paper we present a machine learning-based approach to address the above questions. Models induced from algorithmic performance data can represent the knowledge of how algorithmic performance depends on some easy-to-compute problem instance characteristics. Using these models, we can estimate approximately whether an input instance is exactly solvable or not. Furthermore, when it is classified as exactly unsolvable, we can select the best approximate algorithm for it among a list of candidates. In this paper we use the MPE (most probable explanation) problem in probabilistic inference as a case study to validate the proposed methodology. Our experimental results show that the machine learning-based algorithm selection system can integrate both exact and inexact algorithms and provide the best overall performance comparing to any single candidate algorithm.

2749970
Layered Learning in Genetic Programming for a Cooperative Robot Soccer Problem
We present an alternative to standard genetic programming (GP) that applies layered learning techniques to decompose a problem. GP is applied to subproblems sequentially, where the population in the last generation of a subproblem is used as the initial population of the next subproblem. This method is applied to evolve agents to play keep-away soccer, a subproblem of robotic soccer that requires cooperation among multiple agents in a dynnamic environment. The layered learning paradigm allows GP to evolve better solutions faster than standard GP. Results show that the layered learning GP outperforms standard GP by evolving a lower fitness faster and an overall better fitness. Results indicate a wide area of future research with layered learning in GP.
28678366
Genetic Wrappers for Constructive Induction in High-Performance Data Mining
We present an application of genetic algorithm-based design to configuration of high-level optimization systems, or wrappers, for relevance determination and constructive induction. Our system combines genetic wrappers with elicited knowledge on attribute relevance and synthesis. We discuss decision support issues in a large-scale commercial data mining project (cost prediction for multiple automobile insurance markets), and report experiments using D2K, a Java-based visual programming system for data mining and information visualization, and several commercial and research tools. Our GA system, Jenesis [HWRC00], is deployed on several network-of-workstation systems (Beowulf clusters). It achieves a linear speedup, due to a high degree of task parallelism, and improved test set accuracy, compared to decision tree learning with only constructive induction and state-space search-based wrappers [KJ97].
38525575
Parameter significance estimation and financial prediction
This paper deals with the problem of parameter significance estimation, and its application to currency exchange rate prediction. The basic problem is that over the years, practitioners in the field of financial engineering have developed dozens of technical and fundamental indicators on the basis of which they try to predict financial time series. The practitioners are now faced with the problem of finding out which combinations of those indicators are most significant or relevant, and how their significance changes over time. The authors propose a novel neural architecture calledSupNet for estimating the significance of various parameters. The methodology is based on the principle of penalizing those features that are the largest contributors to the error term. Two algorithms based on this principle are proposed. This approach is different from related methodologies, which are based on the principle of removing parameters with the least significance. The proposed methodology is demonstrated on the next day returns of the DM-US currency exchange rate, and promising results are obtained.
39997128
The Clusnet Algorithm And Time Series Prediction
This paper describes a novel neural network architecture named ClusNet. This network is designed to study the trade-offs between the simplicity of instance-based methods and the accuracy of the more computational intensive learning methods. The features that make this network different from existing learning algorithms are outlined. A simple proof of convergence of the ClusNet algorithm is given. Experimental results showing the convergence of the algorithm on a specific problem is also presented. In this paper, ClusNet is applied to predict the temporal continuation of the Mackey-Glass chaotic time series. A comparison between the results obtained with ClusNet and other neural network algorithms is made. For example, ClusNet requires one-tenth the computing resources of the instance-based local linear method for this application while achieving comparable accuracy in this task. The sensitivity of ClusNet prediction accuracies on specific clustering algorithms is examined for an application. The simplicity and fast convergence of ClusNet makes it ideal as a rapid prototyping tool for applications where on-line learning is required.