Evolving technical trading rules for spot foreign-exchange markets using grammatical evolution

Grammatical Evolution (GE) is a novel, data-driven, model-induction tool, inspired by the biological gene-to-protein mapping process. This study provides an introduction to GE, and applies the methodology in an attempt to uncover useful technical trading rules which can be used to trade foreign exchange markets. In this study, each of the evolved rules (programs) represents a market trading system. The form of these programs is not specified ex-ante, but emerges by means of an evolutionary process. Daily US-DM, US-Stg and US-Yen exchange rates for the period 1992 to 1997 are used to train and test the model. The findings suggest that the developed rules earn positive returns in hold-out sample test periods, after allowing for trading and slippage costs. This suggests potential for future research to determine whether further refinement of the methodology adopted in this study could improve the returns earned by the developed rules. It is also noted that this novel methodology has general utility for rule-induction, and data mining applications.MSC codes: 91B84, 68W10, 62J02     

Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners’ heuristic

This paper proposes a four corners’ heuristic for application in evolutionary algorithms (EAs) applied to two-dimensional packing problems. The four corners’ (FC) heuristic is specifically designed to increase the search efficiency of EAs. Experiments with the FC heuristic are conducted on 31 problems from the literature both with rotations permitted and without rotations permitted, using two different EA algorithms: a self-adaptive parallel recombinative simulated annealing (PRSA) algorithm, and a self-adaptive genetic algorithm (GA). Results on bin packing problems yield the smallest trim losses we have seen in the published literature; with the FC heuristic, zero trim loss was achieved on problems of up to 97 rectangles. A comparison of the self-adaptive GA to fixed-parameter GAs is presented and the benefits of self-adaption are highlighted.     

A learning process for fuzzy control rules using genetic algorithms

The purpose of this paper is to present a genetic learning process for learning fuzzy control rules from examples. It is developed in three stages: the first one is a fuzzy rule genetic generating process based on a rule learning iterative approach, the second one combines two kinds of rules, experts rules if there are and the previously generated fuzzy control rules, removing the redundant fuzzy rules, and the thrid one is a tuning process for adjusting the membership functions of the fuzzy rules. The three components of the learning process are developed formulating suitable genetic algorithms.     

Robustness in multi-objective optimization using evolutionary algorithms

This work discusses robustness assessment during multi-objective optimization with a Multi-Objective Evolutionary Algorithm (MOEA) using a combination of two types of robustness measures. Expectation quantifies simultaneously fitness and robustness, while variance assesses the deviation of the original fitness in the neighborhood of the solution. Possible equations for each type are assessed via application to several benchmark problems and the selection of the most adequate is carried out. Diverse combinations of expectation and variance measures are then linked to a specific MOEA proposed by the authors, their selection being done on the basis of the results produced for various multi-objective benchmark problems. Finally, the combination preferred plus the same MOEA are used successfully to obtain the fittest and most robust Pareto optimal frontiers for a few more complex multi-criteria optimization problems.     

An empirical study on similarity-based mating for evolutionary multiobjective combinatorial optimization

We have already proposed a similarity-based mating scheme to recombine extreme and similar parents for evolutionary multiobjective optimization. In this paper, we examine the effect of the similarity-based mating scheme on the performance of evolutionary multiobjective optimization (EMO) algorithms. First we examine which is better between recombining similar or dissimilar parents. Next we examine the effect of biasing selection probabilities toward extreme solutions that are dissimilar from other solutions in each population. Then we examine the effect of dynamically changing the strength of this bias during the execution of EMO algorithms. Computational experiments are performed on a wide variety of test problems for multiobjective combinatorial optimization. Experimental results show that the performance of EMO algorithms can be improved by the similarity-based mating scheme for many test problems.     

Extracting compact fuzzy rules for nonlinear system modeling using subtractive clustering,GA and unscented filter

This paper presents a two stage procedure for building optimal fuzzy model from data for nonlinear dynamical systems. Both stages are embedded into Genetic Algorithm (GA) and in the first stage emphasis is placed on structural optimization by assigning a suitable fitness to each individual member of population in a canonical GA. These individuals represent coded information about the structure of the model (number of antecedents and rules). This information is consequently utilized by subtractive clustering to partition the input space and construct a compact fuzzy rule base. In the second stage, Unscented Filter (UF) is employed for optimization of model parameters, that is, parameters of the input–output Membership Functions (MFs).     

On finding multiple Pareto-optimal solutions using classical and evolutionary generating methods

In solving multi-objective optimization problems, evolutionary algorithms have been adequately applied to demonstrate that multiple and well-spread Pareto-optimal solutions can be found in a single simulation run. In this paper, we discuss and put together various different classical generating methods which are either quite well-known or are in oblivion due to publication in less accessible journals and some of which were even suggested before the inception of evolutionary methodologies. These generating methods specialize either in finding multiple Pareto-optimal solutions in a single simulation run or specialize in maintaining a good diversity by systematically solving a number of scalarizing problems. Most classical generating methodologies are classified into four groups mainly based on their working principles and one representative method from each group is chosen in the present study for a detailed discussion and for its performance comparison with a state-of-the-art evolutionary method. On visual comparisons of the efficient frontiers obtained for a number of two and three-objective test problems, the results bring out interesting insights about the strengths and weaknesses of these approaches. The results should motivate researchers to design hybrid multi-objective optimization algorithms which may be better than each of the individual methods.     

On solving multiobjective bin packing problems using evolutionary particle swarm optimization

The bin packing problem is widely found in applications such as loading of tractor trailer trucks, cargo airplanes and ships, where a balanced load provides better fuel efficiency and safer ride. In these applications, there are often conflicting criteria to be satisfied, i.e., to minimize the bins used and to balance the load of each bin, subject to a number of practical constraints. Unlike existing studies that only consider the issue of minimum bins, a multiobjective two-dimensional mathematical model for bin packing problems with multiple constraints (MOBPP-2D) is formulated in this paper. To solve MOBPP-2D problems, a multiobjective evolutionary particle swarm optimization algorithm (MOEPSO) is proposed. Without the need of combining both objectives into a composite scalar weighting function, MOEPSO incorporates the concept of Pareto’s optimality to evolve a family of solutions along the trade-off surface. Extensive numerical investigations are performed on various test instances, and their performances are compared both quantitatively and statistically with other optimization methods to illustrate the effectiveness and efficiency of MOEPSO in solving multiobjective bin packing problems.     

Framework for efficient feature selection in genetic algorithm based data mining

We present the design of more effective and efficient genetic algorithm based data mining techniques that use the concepts of feature selection. Explicit feature selection is traditionally done as a wrapper approach where every candidate feature subset is evaluated by executing the data mining algorithm on that subset. In this article we present a GA for doing both the tasks of mining and feature selection simultaneously by evolving a binary code along side the chromosome structure used for evolving the rules. We then present a wrapper approach to feature selection based on Hausdorff distance measure. Results from applying the above techniques to a real world data mining problem show that combining both the feature selection methods provides the best performance in terms of prediction accuracy and computational efficiency.     

On the analysis of a dynamic evolutionary algorithm

Evolutionary algorithms are applied as problem-independent optimization algorithms. They are quite efficient in many situations. However, it is difficult to analyze even the behavior of simple variants of evolutionary algorithms like the (1+1) EA on rather simple functions. Nevertheless, only the analysis of the expected run time and the success probability within a given number of steps can guide the choice of the free parameters of the algorithms. Here static (1+1) EAs with a fixed mutation probability are compared with dynamic (1+1) EAs with a simple schedule for the variation of the mutation probability. The dynamic variant is first analyzed for functions typically chosen as example-functions for evolutionary algorithms. Afterwards, it is shown that it can be essential to choose the suitable variant of the (1+1) EA. More precisely, functions are presented where each static (1+1) EA has exponential expected run time while the dynamic variant has polynomial expected run time. For other functions it is shown that the dynamic (1+1) EA has exponential expected run time while a static (1+1) EA with a good choice of the mutation probability has polynomial run time with overwhelming probability.     

Modeling and optimizing a vendor managed replenishment system using machine learning and genetic algorithms

Using a supply chain network, we demonstrate the feasibility, viability, and robustness of applying machine learning and genetic algorithms to respectively model, understand, and optimize such data intensive environments. Deployment of these algorithms, which learn from and optimize data, can obviate the need to perform more complex, expensive, and time consuming design of experiments (DOE), which usually disrupt system operations. We apply and compare the behavior and performance of the proposed machine learning algorithms to that obtained via DOE in a simulated Vendor Managed Replenishment system, developed for an actual firm. The results show that the models resulting from the proposed algorithms had strong explanatory and predictive power, comparable to that of DOE. The optimal system settings and profit were also similar to that obtained from DOE. The virtues of using machine learning and evolutionary algorithms to model and optimize data rich environments thus seem promising because they are automatic, involving little human intervention and expertise. We believe and are exploring how they can be made adaptive to improve parameter estimates with increasing data, as well as seamlessly detecting system (and therefore model) changes, thus being capable of recursively updating and reoptimizing a modified or new model.     

Bayesian network approach to multinomial parameter learning using data and expert judgments

One of the hardest challenges in building a realistic Bayesian Network (BN) model is to construct the node probability tables (NPTs). Even with a fixed predefined model structure and very large amounts of relevant data, machine learning methods do not consistently achieve great accuracy compared to the ground truth when learning the NPT entries (parameters). Hence, it is widely believed that incorporating expert judgments can improve the learning process. We present a multinomial parameter learning method, which can easily incorporate both expert judgments and data during the parameter learning process. This method uses an auxiliary BN model to learn the parameters of a given BN. The auxiliary BN contains continuous variables and the parameter estimation amounts to updating these variables using an iterative discretization technique. The expert judgments are provided in the form of constraints on parameters divided into two categories: linear inequality constraints and approximate equality constraints. The method is evaluated with experiments based on a number of well-known sample BN models (such as Asia, Alarm and Hailfinder) as well as a real-world software defects prediction BN model. Empirically, the new method achieves much greater learning accuracy (compared to both state-of-the-art machine learning techniques and directly competing methods) with much less data. For example, in the software defects BN for a sample size of 20 (which would be considered difficult to collect in practice) when a small number of real expert constraints are provided, our method achieves a level of accuracy in parameter estimation that can only be matched by other methods with much larger sample sizes (320 samples required for the standard machine learning method, and 105 for the directly competing method with constraints).     

Evolving fuzzy rule based controllers using genetic algorithms

The synthesis of genetics-based machine learning and fuzzy logic is beginning to show promise as a potent tool in solving complex control problems in multi-variate non-linear systems. In this paper an overview of current research applying the genetic algorithm to fuzzy rule based control is presented. A novel approach to genetics-based machine learning of fuzzy controllers, called a Pittsburgh Fuzzy Classifier System # 1 (P-FCS1) is proposed. P-FCS1 is based on the Pittsburgh model of learning classifier systems and employs variable length rule-sets and simultaneously evolves fuzzy set membership functions and relations. A new crossover operator which respects the functional linkage between fuzzy rules with overlapping input fuzzy set membership functions is introduced. Experimental results using P-FCS 1 are reported and compared with other published results. Application of P-FCS1 to a distributed control problem (dynamic routing in computer networks) is also described and experimental results are presented.     

Decomposing technical inefficiency using the principle of least action

In for-profit organizations, profit efficiency decomposition is considered important since estimates on profit drivers are of practical use to managers in their decision making. Profit efficiency is traditionally due to two sources – technical efficiency and allocative efficiency. The contribution of this paper is a novel decomposition of technical efficiency that could be more practical to use if the firm under evaluation really wants to achieve technical efficiency as soon as possible. For this purpose, we show how a new version of the Measure of Inefficiency Proportions (MIP), which seeks the minimization of the total technical effort by the assessed firm, is a lower bound of the value of technical inefficiency associated with the directional distance function. The targets provided by the new MIP could be beneficial for firms since it specifies how firms may become technically efficient simply by decreasing one input or increasing one output, suggesting that each firm should focus its effort on a specific dimension (input or output). This approach is operationalized in a data envelopment analysis framework and applied to a dataset of airlines.     

A historical review of evolutionary learning methods for Mamdani-type fuzzy rule-based systems: Designing interpretable genetic fuzzy systems

The need for trading off interpretability and accuracy is intrinsic to the use of fuzzy systems. The obtaining of accurate but also human-comprehensible fuzzy systems played a key role in Zadeh and Mamdani’s seminal ideas and system identification methodologies. Nevertheless, before the advent of soft computing, accuracy progressively became the main concern of fuzzy model builders, making the resulting fuzzy systems get closer to black-box models such as neural networks. Fortunately, the fuzzy modeling scientific community has come back to its origins by considering design techniques dealing with the interpretability-accuracy tradeoff. In particular, the use of genetic fuzzy systems has been widely extended thanks to their inherent flexibility and their capability to jointly consider different optimization criteria. The current contribution constitutes a review on the most representative genetic fuzzy systems relying on Mamdani-type fuzzy rule-based systems to obtain interpretable linguistic fuzzy models with a good accuracy.     

Hybrid PoS-tagging: A cooperation of evolutionary and statistical approaches

The assigning of syntactic categories to words in a sentence, which is referred to as part-of-speech (PoS) tagging problem, plays an essential role in many natural language processing and information retrieval applications. Despite the vast scope of methods, PoS-tagging brings an array of challenges that require novel solutions. To address these challenges in a principled way, one solution would be to formulate the tagging problem as an optimization problem with well-specified objectives and then apply the evolutionary methods to solve the optimization problem. This paper discusses the relative advantages of different evolutionary approaches to handle Part-of-Speech tagging problem and aims at presenting novel language-independent evolutionary algorithms to solve the PoS tagging problem. We show that by exploiting statistical measures to evaluate the solutions in tagging process, the proposed algorithms are able to generate more accurate solution in a reasonable amount of time. The experiments we have conducted on few well known corpus reveal that the proposed algorithms achieve better average accuracy in comparison to other evolutionary-based and classical Part-of-Speech tagging methods.     

Fitting the control parameters of a genetic algorithm: An application to technical trading systems design

This paper studies the problem of how changes in the design of the genetic algorithm (GA) have an effect on the results obtained in real-life applications. In this study, focused on the application of a GA to the tuning of technical trading rules in the context of financial markets, our tentative thesis is that the GA is robust with respect to design changes. The optimization of technical trading systems is a suitable area for the application of the GA metaheuristic, as the complexity of the problem grows exponentially as new technical rules are added to the system and as the answer time is crucial when applying the system to real-time data. Up to now, most of GAs applications to this subject obviated the question of possible “design dependence” in their results. The data we report, based on our experiments, do not allow us to refute the hypothesis of robustness of the GA to design implementation, when applying to technical trading systems tuning.     

Balancing exploration and exploitation with adaptive variation for evolutionary multi-objective optimization

Although recent studies have shown that evolutionary algorithms are effective tools for solving multi-objective optimization problems, their performances are often bottlenecked by the suitability of the evolutionary operators with respect to the optimization problem at hand and their corresponding parametric settings. To adapt the search dynamic of evolutionary operation in multi-objective optimization, this paper proposes an adaptive variation operator that exploits the chromosomal structure of binary representation and synergizes the function of crossover and mutation. The overall search ability is deterministically tuned online to maintain a balance between extensive exploration and local fine-tuning at different stages of the evolutionary search. Also, the coordination between the two variation operators is achieved by means of an adaptive control that ensures an efficient exchange of information between the different chromosomal sub-structures throughout the evolutionary search. Extensive comparative studies with several representative variation operators are performed on different benchmark problems and significant algorithmic performance improvements in terms of proximity, uniformity and diversity are obtained with the incorporation of the proposed adaptive variation operator into the evolutionary multi-objective optimization process.     

On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions

Evolutionary algorithms are randomized search heuristics, which are often used as function optimizers. In this paper the well-known (1+1) Evolutionary Algorithm ((1+1) EA) and its multistart variants are studied. Several results on the expected runtime of the (1+1) EA on linear or unimodal functions have already been presented by other authors. This paper is focused on quadratic pseudo-boolean functions, i.e., polynomials of degree 2, a class of functions containing NP-hard optimization problems. Subclasses of the class of all quadratic functions are identified where the (1+1) EA is efficient, for other subclasses the (1+1) EA has exponential expected runtime, but a large enough success probability within polynomial time such that a multistart variant of the (1+1) EA is efficient. Finally, a particular quadratic function is identified where the EA and its multistart variants fail in polynomial time with overwhelming probability.     

GHS + LEM: Global-best Harmony Search using learnable evolution models

This paper presents a new optimization algorithm called GHS + LEM, which is based on the Global-best Harmony Search algorithm (GHS) and techniques from the learnable evolution models (LEM) to improve convergence and accuracy of the algorithm. The performance of the algorithm is evaluated with fifteen optimization functions commonly used by the optimization community. In addition, the results obtained are compared against the original Harmony Search algorithm, the Improved Harmony Search algorithm and the Global-best Harmony Search algorithm. The assessment shows that the proposed algorithm (GHS + LEM) improves the accuracy of the results obtained in relation to the other options, producing better results in most situations, but more specifically in problems with high dimensionality, where it offers a faster convergence with fewer iterations.