In our previous work, we showed that regime changes in the market are retrospectively detectable using historic data in directional changes (DC). In this paper, we build on such results and show that DC indicators can be used for market tracking - using data up to the present - to understand what is going on in the market. In particular, we wanted to track the market to see whether the market is entering an abnormally volatile regime. The proposed approach used DC indicator values observed in the past to model the normal regime of a market (in which volatility is normal) or an abnormal regime (in which volatility is abnormally high). Given a particular value observed in the current market, we used a naive Bayes model to calculate independently two probabilities: one for the market being in the normal regime and one for it being in the abnormal regime. These two probabilities were combined to decide which regime the market was in, two decision rules were examined: a Simple Rule and a Stricter Rule. We used DJIA, FTSE 100 and S&P 500 data from 2007 to 2010 to build the Bayes model. The model was used to track the S&P 500 market from 2010 to 2012, which saw two spells of abnormal regimes, as identified by our previous work, with the benefit of hindsight. The tracking method presented in this paper, with either decision rule, managed to pick up both spells of regime changes accurately. The tracking signals could be useful to market participants. This study potentially lays the foundation of a practical financial early warning system.

Market prices are traditionally recorded in fixed time intervals. Directional Change is an alternative approach to summarize price movements in financial markets that is consistent with across all time scales. Unlike time series, directional change summarizes the big data in finance by focusing on the intrinsic time of the data. This captures deeper intrinsic data qualities and thus trading strategies based on directional change are more sustainable and less disruptive. In this paper, we propose four trading strategies using the concept of directional change and explore the combination with technical analysis. The trading strategies are tested using EUR/USD and GBP/USD high frequency FX market data. Empirical results show good performance of our trading strategies based on thresholds, and that combining with technical analysis brings further improvement.

The development of computational intelligence‐based strategies for electronic markets has been the focus of intense research. To be able to design efficient and effective automated trading strategies, one first needs to understand the workings of the market, the strategies that traders use, and their interactions as well as the patterns emerging as a result of these interactions. In this article, we develop an agent‐based model of the foreign exchange (FX) market, which is the market for the buying and selling of currencies. Our agent‐based model of the FX market comprises heterogeneous trading agents that employ a strategy that identifies and responds to periodic patterns in the price time series. We use the agent‐based model of the FX market to undertake a systematic exploration of its constituent elements and their impact on the stylized facts (statistical patterns) of transactions data. This enables us to identify a set of sufficient conditions that result in the emergence of the stylized facts similarly to the real market data, and formulate a model that closely approximates the stylized facts. We use a unique high‐frequency data set of historical transactions data that enables us to run multiple simulation runs and validate our approach and draw comparisons and conclusions for each market setting.

Hyper-heuristics have successfully been applied to a vast number of search and optimization problems. One of the novelties of hyper-heuristics is the fact that they manage and automate the meta-heuristic's selection process. In this paper, we implemented and analyzed a hyper-heuristic framework on three meta-heuristics namely Simulated Annealing, Tabu Search, and Guided Local Search, which had successfully been applied in the past to a Financial Forecasting algorithm called EDDIE. EDDIE uses Genetic Programming to extract and learn from historical data in order to predict future financial market movements. Results show that the algorithm's effectiveness has been improved, thus making the combination of meta-heuristics under a hyper-heuristic framework an effective Financial Forecasting approach.

Guided Local Search is a powerful meta-heuristic algorithm that has been applied to a successful Genetic Programming Financial Forecasting tool called EDDIE. Although previous research has shown that it has significantly improved the performance of EDDIE, it also increased its computational cost to a high extent. This paper presents an attempt to deal with this issue by combining Guided Local Search with Fast Local Search, an algorithm that has shown in the past to be able to significantly reduce the computational cost of Guided Local Search. Results show that EDDIE's computational cost has been reduced by an impressive 77%, while at the same time there is no cost to the predictive performance of the algorithm.

EDDIE is a Genetic Programming (GP) tool, which is used to tackle problems in the field of financial forecasting. The novelty of EDDIE is in its grammar, which allows the GP to look in the space of technical analysis indicators, instead of using prespecified ones, as it normally happens in the literature. The advantage of this is that EDDIE is not constrained to use prespecified indicators; instead, thanks to its grammar, it can choose any indicators within a pre-defined range, leading to new solutions that might have never been discovered before. However, a disadvantage of the above approach is that the algorithm's search space is dramatically larger, and as a result good solutions can sometimes be missed due to ineffective search. This paper presents an attempt to deal with this issue by applying to the GP three different meta-heuristics, namely Simulated Annealing, Tabu Search, and Guided Local Search. Results show that the algorithm's performance significantly improves, thus making the combination of Genetic Programming and meta-heuristics an effective financial forecasting approach.

Following the global economic crisis, many financial organisations around the World are seeking efficient frameworks for predicting and assessing financial risks. However, in the current economic situation, transparency became an important factor where there is a need to fully understand and analyse a given financial model. In this paper, we will present a Genetic Type-2 Fuzzy Logic System (FLS) for the modelling and prediction of financial applications. The proposed system is capable of generating summarized optimised type-2 FLSs based financial models which are easy to read and analyse by the lay user. The system is able to use the summarized model for prediction within financial applications. We have performed several evaluations in two distinctive financial domains one for the prediction of good/bad customers in a credit card approval application and the other domain was in the prediction of arbitrage opportunities in the stock markets. The proposed Genetic type-2 FLS has outperformed white box financial models like the Evolving Decision Rule (EDR) procedure (which is based on Genetic Programming (GP) and decision trees) and gave a comparable performance to black box models like neural networks while the proposed system provided a white box model which is easy to understand and analyse by the lay user.

Fiber optics is a relatively new technology, one which has not yet been extensively used, because of its high cost. In order to evaluate the viability of such a costly investment, techno-economic models are employed. These models evaluate the investment from both technical (e.g., optimal network design) and economical (e.g., profitability) perspectives. However, an area that has not received much attention is the deployment plans of a given fiber optic investment. Existing works usually compare manually predefined deployment plans that are considered profitable, and then apply techno-economic analysis. While this indeed offers valuable information, it does not guarantee that the examined plans are the optimal ones. This should be considered as a major disadvantage, because there could be other deployment plans that could offer significantly higher profit. This paper offers a first attempt at looking for the optimal deployment plan of fiber optics, based on profit. Our method can be considered as a framework that wraps around existing techno-economic models. We employ a Genetic Algorithm (GA), which creates a population of deployment plans. These plans can then be evaluated through the usual techno-economic approach. The GA then evolves the population of these plans and at the end of the process acts as a decision support tool that advises on the optimal deployment plan, without the need for any human interference in the decision-making process. For comparison purposes, we compare the GA's results with results under other profitable plans. Results show that the introduction of the use of the GA is very advantageous and leads to a significant increase in profit.

In this work, we propose a new genetic programming algorithm with local search strategies, named Memetic Genetic Programming(MGP), for classification problems. MGP aims to acquire a classifier with large Area Under the ROC Curve (AUC), which has been proved to be a better performance metric for traditionally used metrics (e.g., classification accuracy). Three new points are presented in our new algorithm. First, a new representation called statistical genetic decision tree (SGDT) for GP is proposed on the basis of Genetic Decision Tree (GDT). Second, a new fitness function is designed by using statistic in formation from SGDT. Third, the concept of memetic computing is introduced into SGDT. As a result, the MGP is equipped with a local search method based on the training algorithms for decision trees. The efficacy of the MGP is empirically justified against a number of relevant approaches.

In this paper, we show that a minimal agent-based model for the Foreign Exchange (FX) market is capable of reproducing, to a certain extent, FX market trading activity. The model is minimal in that it has the advantage of having the minimum set of elements necessary for modelling the FX market in order to reproduce the FX market trading activity. The key elements are zero-Intelligence directional-change events traders, historical prices, actual FX traders' behaviour, limit orders, FX market trading sessions, market holidays, and the activation of the initial condition. All of these play a fundamental role. Most importantly, the simulation output is evaluated by contrast against the microscopic behavioural analysis of high-frequency data of individual traders' transactions on an account level provided by OANDA LTD. The results of this comparison prove that the trading agents' behaviour reproduces the FX market trading activity. Overall, the model leads to the identification of the key elements that may be responsible for the emergence of FX market trading activity in an agent-based model.

This paper extends a previous market microstructure model, where we used Genetic Programming (GP) as an inference engine for trading rules, and Self Organizing Maps as a clustering machine for those rules. Experiments in that work took place under a single financial market and investigated whether its behavior is non-stationary or cyclic. Results showed that the market's behavior was constantly changing and strategies that would not adapt to these changes, would become obsolete, and their performance would thus decrease over time. However, because experiments in that work were based on a specific GP algorithm, we are interested in this paper to prove that those results are independent of the choice of such algorithms. We thus repeat our previous tests under two more GP frameworks. In addition, while our previous work surveyed only a single market, in this paper we run tests under 10 markets, for generalization purposes. Finally, we deepen our analysis and investigate whether the performance of strategies, which have not co-evolved with the market, follows a continuous decrease, as it has been previously suggested in the agent-based artificial stock market literature. Results show that our previous results are not sensitive to the choice of GP. Strategies that do not co-evolve with the market, become ineffective. However, we do not find evidence for a continuous performance decrease of these strategies.

Guided Pareto Local Search (GPLS) is an extension to the Guided Local Search algorithm to contain multiobjective combinatorial optimization. GPLS is shown to improve the convergence of the underlying Pareto local search algorithms. This paper demonstrates the potential of GPLS to be an effective searching technique that can be a central part of a multi-phase or hybrid frameworks. To confirm this, two simple frameworks based on GPLS are proposed: iGPLS and mGPLS. Both frameworks only require an initial set of diverse solutions. While GPLS starts from a randomly (or heuristically) generated solution, iGPLS starts with the initial diverse solution set. On the other hand, mGPLS is a parallel version of GPLS, in which each GPLS run starts independently from a solution in the initial set. The application of these frameworks to the biobjective 0/1 knapsack problem reveals the effectiveness of the GPLS based frameworks, demonstrated by achieving state-of-the-art results.

In this paper we present a new version of a GP-based financial forecasting tool called EDDIE. The novelty of this new version (EDDIE 8), is its enlarged search space, where we allow the GP to search in the space of the technical indicators, in order to form its Genetic Decision Trees. In this way, EDDIE 8 is not constrained in using pre-specified indicators, but it is left up to the GP to choose the optimal ones. We then proceed to compare EDDIE 8 with EDDIE 7, which is based on previous EDDIE versions; EDDIE 7 has a smaller space where the indicators are pre-specified by the user and are part of EDDIE 8's space. Results show that thanks to the bigger search space, new and improved solutions can be found by EDDIE 8. However, there are cases where EDDIE 8 can still be outperformed by its predecessor. Analysis shows that this depends on the nature of the solutions. If the solutions come from EDDIE 8's search space, then EDDIE 8 can find them and perform better; if, however, solutions come from the smaller search space of EDDIE 7, then EDDIE 8 is having difficulties focusing in such a small space and is thus outperformed by EDDIE 7.

MOEA/D is a generic multiobjective evolutionary optimization algorithm. MOEA/D needs a approach to decompose a multiobjective optimization problem into a number of single objective optimization problems. The commonly-used weighted sum approach and the Tchebycheff approach may not be able to handle disparately scaled objectives. This paper suggests a new decomposition approach, called NBI-style Tchebycheff approach, for MOEA/D to deal with such objectives. A portfolio management MOP has been used as an example to test the effectiveness of MOEA/D with NBI-style Tchebycheff approach.

In some expensive multiobjective optimization problems (MOPs), several function evaluations can be carried out in a batch way. Therefore, it is very desirable to develop methods which can generate multipler test points simultaneously. This paper proposes such a method, called MOEA/D-EGO, for dealing with expensive multiobjective optimization. MOEA/D-EGO decomposes an MOP in question into a number of single-objective optimization subproblems. A predictive model is built for each subproblem based on the points evaluated so far. Effort has been made to reduce the overhead for modeling and to improve the prediction quality. At each generation, MOEA/D is used for maximizing the expected improvement metric values of all the subproblems, and then several test points are selected for evaluation. Extensive experimental studies have been carried out to investigate the ability of the proposed algorithm.

Gaussian process model is an effective and efficient method for approximating a continuous function. However, its computational cost increases exponentially with the size of training data set. A very popular way to alleviate this shortcoming is to cluster the whole training data set into a number of small clusters and then a local model is built for each cluster. However, widely used crisp clustering might not be accurate in the boundary areas among different clusters. This paper proposes a fuzzy clustering based method for improving approximation quality. Several clusters with overlaps are firstly obtained by Fuzzy C-Means clustering and then local models are built for these clusters. It has been demonstrated that this method can be used with evolutionary algorithms for dealing expensive optimization problems.

Stock markets are very important in modern societies and their behavior has serious implications for a wide spectrum of the world's population. Investors, governing bodies, and society as a whole could benefit from better understanding of the behavior of stock markets. The traditional approach to analyzing such systems is the use of analytical models. However, the complexity of financial markets represents a big challenge to the analytical approach. Most analytical models make simplifying assumptions, such as perfect rationality and homogeneous investors, which threaten the validity of their results. This motivates alternative methods.In this paper, we report an artificial financial market and its use in studying the behavior of stock markets. This is an endogenous market, with which we model technical, fundamental, and noise traders. Nevertheless, our primary focus is on the technical traders, which are sophisticated genetic programming based agents that co- evolve (by learning based on their fitness function) by predicting investment opportunities in the market using technical analysis as the main tool. With this endogenous artificial market, we identify the conditions under which the statistical properties of price series in the artificial market resemble some of the properties of real financial markets. By performing a careful exploration of the most important aspects of our simulation model, we determine the way in which the factors of such a model affect the endogenously generated price. Additionally, we model the pressure to beat the market by a behavioral constraint imposed on the agents reflecting the Red Queen principle in evolution. We have demonstrated how evolutionary computation could play a key role in studying stock markets, mainly as a suitable model for economic learning on an agent- based simulation.

The six papers in this special section focus on computational finance and economics.

Black-box expensive function is ubiquitous in real world problems. Much research has been done on scalar objective optimization for such problems with great success. Comparatively, very little work has been done in multi-objective optimization. In many cases, it is not straightforward to convert methods from scalar objective optimization to multi-objective optimization due to the complexities incurred by Pareto domination. In our pervious research, concept of model composition based on Gaussian Process metamodel and the powerful MOEA/D framework proved to be a successful approach for multi-objective optimization with black-box expensive functions. We derived Weighted-Sum and Tchebycheff model composition for bi-objective problems. However, due to the complexity of Tchebycheff decomposition structure, it is very hard, if not impossible, to extend the method to three or more objective problems in a nature way. In this paper, we propose an approximation method for Tchebycheff model composition which greatly simplify the derivation for three or more objective cases. Experiments show the approximation produces very similar performance as the Weighted-Sum and Tchebycheff without approximation. Thus, the new method enables us to tackle multi-objective problems with black-box expensive functions that could not be tackled effectively so far.

BT workforce scheduling problem considers technicians (with different skills) which are assigned to tasks which arrive (partially) dynamically during the day. In order to manage their workforce, BT divides the different regions into several areas. In the beginning of each day all the technicians in a region are assigned to one of these areas. During the day, tasks can only be allocated to technicians from the same area. In this paper we use a (1+1) EA in order to decide, once the area have been defined, which technicians to assign to which areas.

This work is motivated by the interest in finding significant movements in financial stock prices. The detection of such movements is important because these could represent good opportunities for invest. However, when the number of profitable opportunities is very small the prediction of these cases is very difficult. In previous works, we have introduced the repository method (RM). The aim of this approach is to classify financial data sets in extreme imbalanced environments. When opportunities are extremely rare, the investor needs a sharper balance between not making mistakes and not missing opportunities. RM offers a range of solutions to suit the risk guidelines of the investor. The aims of this paper are 1) to show that RM can produce a range of solutions to suit the investor's preferences and 2) to analyze the impact of the evolutionary process to RM's performance. Three series of experiments were performed, RM was tested using two artificial data sets whose solutions have different level of complexity. Finally RM was tested in a data set from the London stock market. Experimental results show that: 1) RM offers a range of solutions to fit the risk guidelines of the investor and 2) the contribution of the evolutionary process is very valuable to the performance of RM and 3) RM is able to extract predictive rules even from earliest stages of the evolutionary process.

Multiobjective optimization problems with many local Pareto fronts is a big challenge to evolutionary algorithms. In this paper, two operators, biased initialization and biased crossover, are proposed to improve the global search ability of RM-MEDA, a recently proposed multiobjective estimation of distribution algorithm. Biased initialization inserts several globally Pareto optimal solutions into the initial population; biased crossover combines the location information of some best solutions found so far and globally statistical information extracted from current population. Experiments have been conducted to study the effects of these two operators.

An evolutionary algorithm (EA) can be used to tune the control parameters of a construction heuristic to an optimization problem and generate a nearly optimal solution. This approach is in the spirit of indirect encoding EAs. Its performance relies on both the heuristic and the EA. This paper proposes a three-phase parameterized construction heuristic for the shared-path protection problem in wavelength division multiplexing networks with shared-risk link group constraints and applies an EA for optimizing the control parameters of the proposed heuristics. The experimental results show that the proposed approach is effective on all the tested network instances. It was also demonstrated that an EA with guided mutation performs better than a conventional genetic algorithm for tuning the control parameters, which indicates that a combination of global statistical information extracted from the previous search and location information of the best solutions found so far could improve the performance of an algorithm.

The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently declarative, attention is quickly turning toward developing high-level programming languages within which such problems can be modeled and also solved. Along these lines, this paper presents DEPICT, the language. Its use is illustrated through modeling a number of benchmark examples. The paper continues with a description of a prototype system within which such models may be interpreted. The paper concludes with a description of a sample run of this interpreter showing how a problem modeled as such is typically solved.

This work is motivated by financial forecasting using genetic programming. This paper presents a method to post-process decision trees. The processing procedure is based on the analysis and evaluation of the components of each tree, followed by pruning. The idea behind this approach is to identify and eliminate rules that cause misclassification. As a result we expect to keep and generate rules that enhance the classification. This method was tested on decision trees generated by a genetic program whose aim was to discover classification rules in financial stock markets. From experimental results we can conclude that our method is able to improve the accuracy and precision of the classification.

In the future a need will exist, if it does not already, to automate supply chains as trading electronically becomes increasingly important. Using the Simple Supply Chain Model (SSCM) allows a supply chain situation to be captured for experimentation. This paper describes efforts to evolve strategies for tackling SSCM specified problems through the use of a Strategy Framework (SSF) and Market Simulation System (SMSS). While the SSF provides a basic strategy representation system, the SMSS evolves strategies over multiple supply chain simulations using Population Based Incremental Learning with Guided Mutation. The paper further discuss some of the techniques being used to analyse the resultant data.

Bargaining is fundamental in social activities. Game-theoretic methodology has provided theoretic solutions for certain abstract models. Even for a simple model, this method demands substantial human intelligent effort in order to solve game-theoretic equilibriums. The analytic complexity increases rapidly when more elements are included in the models. In our previous work, we have demonstrated how co-evolutionary algorithms can be used to find approximations to game-theoretic equilibriums of bargaining models that consider bargaining costs only. In this paper, we study more complicated bargaining models, in which outside option is taken into account besides bargaining cost. Empirical studies demonstrate that evolutionary algorithms are efficient in finding near-perfect solutions. Experimental results reflect the compound effects of discount factors and outside options upon bargaining outcomes. We argue that evolutionary algorithm is a practical tool for generating reasonably good strategies for complicated bargaining models beyond the capability of game theory.

In our previous work [1], it has been shown that the performance of multi-objective evolutionary algorithms can be greatly enhanced if the regularity in the distribution of Pareto-optimal solutions is used. This paper suggests a new hybrid multi-objective evolutionary algorithm by introducing a convergence based criterion to determine when the model-based method and when the genetics-based method should be used to generate offspring in each generation. The basic idea is that the genetics-based method, i. e., crossover and mutation, should be used when the population is far away from the Pareto front and no obvious regularity in population distribution can be observed. When the population moves towards the Pareto front, the distribution of the individuals will show increasing regularity and in this case, the model-based method should be used to generate offspring. The proposed hybrid method is verified on widely used test problems and our simulation results show that the method is effective in achieving Pareto-optimal solutions compared to two state-of-the-art evolutionary multi-objective algorithms: NSGA-II and SPEA2, and our pervious method in [1].

Axelrod's original experiments for evolving IPD player strategies involved the use of a basic GA. In this paper we examine how well a simple GA performs against the more recent population based incremental learning system under similar conditions. We find that GA performs slightly better than standard PBIL under most conditions. This difference in performance can be mitigated and reversed through the use of a 'guided' mutation operator.

The Pareto optimal solutions to a multi-objective optimization problem often distribute very regularly in both the decision space and the objective space. Most existing evolutionary algorithms do not explicitly take advantage of such a regularity. This paper proposed a model-based evolutionary algorithm (M-MOEA) for bi-objective optimization problems. Inspired by the ideas from estimation of distribution algorithms, M-MOEA uses a probability model to capture the regularity of the distribution of the Pareto optimal solutions. The local principal component analysis (local PCA) and the least-squares method are employed for building the model. New solutions are sampled from the model thus built. At alternate generations, M-MOEA uses crossover and mutation to produce new solutions. The selection in M-MOEA is the same as in non-dominated sorting genetic algorithm-II (NSGA-II). Therefore, MOEA can be regarded as a combination of EDA and NSGA-II. The preliminary experimental results show that M-MOEA performs better than NSGA-II.

Estimation of distribution algorithms sample new solutions (offspring) from a probability model which characterizes the distribution of promising solutions in the search space at each generation. The location information of solutions found so far (i.e., the actual positions of these solutions in the search space) is not directly used for generating offspring in most existing estimation of distribution algorithms. This paper introduces a new operator, called guided mutation. Guided mutation generates offspring through combination of global statistical information and the location information of solutions found so far. An evolutionary algorithm with guided mutation (EA/G) for the maximum clique problem is proposed in this paper. Besides guided mutation, EA/G adopts a strategy for searching different search areas in different search phases. Marchiori's heuristic is applied to each new solution to produce a maximal clique in EA/G. Experimental results show that EA/G outperforms the heuristic genetic algorithm of Marchiori (the best evolutionary algorithm reported so far) and a MIMIC algorithm on DIMACS benchmark graphs.

This paper reports a case study in applying constraint satisfaction techniques to university and school timetabling. It involves the construction of a substantial, carefully specified, fully tested and fully operational system. The software engineering aspect of constraint satisfaction is emphasized. Constraint satisfaction problems are expressed in a language more familiar to the formal software engineering community. This brings constraint satisfaction one step closer to formal specification, program verification and transformation; issues extensively studied in software engineering. In problem formulation, explicit domain constraints and heuristic information are made explicit. Moreover, the user's needs are considered more closely; for instance, when the program fails to find a solution, useful indications are produced to help in relaxation or reformulation of the problem.

Financial investment decision making is extremely difficult due to the complexity of the domain. Many factors could influence the change of share prices. FGP (Financial Genetic Programming) is a genetic programming based forecasting system, which is designed to help users evaluate the impact of factors and explore their interactions in relation to future prices. Users channel into FGP factors which they believe are relevant to the prediction. Examples of such factors may include fundamental factors such as "price-earning ratio", "inflation rate" and/or technical factors such as "5-days moving average", "63-days trading range breakout", etc. FGP uses the power of genetic generated decision trees through technical rules with self-adjusted thresholds. In earlier papers, we have reported how FGP used well-known technical analysis rules to make investment decisions (E.P.K. Tsang et al., 1998; J. Li and E.P.K. Tsang, 1999). The paper tests the versatility of FGP by testing it on shorter term investment decisions. To evaluate FGP more thoroughly, we also compare it with C4.5, a well known machine learning classifier system. We used six and a half years' daily closing price of the Dow Jones Industrial Average (DJIA) index for training and over three and half years' data for testing, and obtained favourable results for FGP.

The Processor Configuration Problem (PCP) is an NP hard real life problem. The goal involves designing a network of a finite set of processors, such that the maximum distance between any two processors that a parcel of data needs to travel is kept to a minimum. Since each processor has a limited number of communication channels, a carefully designed layout would assist in reducing the overhead for message switching in the entire network. The Guided Genetic Algorithm (GGA) is a hybrid of genetic algorithm and meta heuristic search algorithm: Guided Local Search. As the search progresses, GGA modifies both the fitness function and fitness templates of the candidate solutions based on feedback from the constraints. We are interested in generating processor configurations between eight and 128 processors. GGA is used as a tool to generate these configurations, and is shown to have considerable advantages over published results.

The Guided Genetic Algorithm (GGA) is a hybrid of genetic algorithm (GA) and meta-heuristic search algorithm, Guided Local Search (GLS). It builds on the framework and robustness of GA, and integrating GLS's conceptual simplicity and effectiveness to arrive at a flexible algorithm well meant for constraint optimization problems. GGA adds to the canonical GA the concepts of a penalty operator and fitness templates. During operation, GGA modifies both the fitness function and fitness templates of the candidate solutions based on feedback from the constraints. The Generalized Assignment Problem (GAP) is a well explored NP hard problem that has practical instances in the real world. In GAP, one has to find the optimum assignment of a set of jobs to a group of agents. However, each job can only be performed by one agent, and each agent has a work capacity. Further, assigning different jobs to different agents involve different utilities and resource requirements. These would affect the choice of job allocation. The paper reports on GGA and its successful application to the GAP.

Constraint satisfaction is at the core of many applications, such as scheduling. The study of phase transition has benefited algorithm selection and algorithm development in constraint satisfaction. Recent research provides evidence that constraint graph topology affects where phase transitions occur in constraint satisfaction problems. In this article, a new phase transition predictor which takes constraint graph information into consideration is proposed. The new predictor allows variation in the tightness of individual constraints and node degree variation in constraint graph. Experiments were conducted to study the usefulness of the new predictor on random binary constraint satisfaction problems. Results show that the new predictor is able to produce predictions as good as the state-of-the-art predictor in general, but do considerably better in sparsely constrained problems, particularly when the node degree variation in their constraint graphs is high.

Investment involves the maximisation of return on one's investment whilst minimising risk. Good forecasting, which often requires expert knowledge, can help to reduce risk. In this paper, we propose a genetic programming-based system, EDDIE (Evolutionary Dynamic Data Investment Evaluator), as a forecasting tool. Genetic programming is inspired by evolution theory, and has been demonstrated to be successful in other areas. EDDIE interacts with the users and generates decision trees, which can also be seen as rule sets. We argue that EDDIE is suitable for forecasting because apart from utilising the power of genetic programming to efficiently search the space of decision trees, it allows expert knowledge to be channelled into forecasting, and it generates rules which can easily be understood and verified. EDDIE has been applied to horse racing and achieved outstanding results. When experimented on 180 handicap races (real data) in the UK, it out-performed other common strategies used in horse race betting by great margins. The idea was then extended to financial forecasting. When tested on historical S&P-500 data EDDIE achieved a respectable annual rate of return over a three and a half year period. While luck may play a part in the success of EDDIE, our experimental results do indicate that EDDIE is a tool which deserves more research. © 1998 John Wiley & Sons, Ltd.

Dent and Mercer (1996) have introduced an algorithm called minimal forward checking (MFC) which always performs no worse than forward checking (FC) in terms of number of compatibility checks and node expanded given the same variable and value orderings. In this paper we describe an algorithm which extends MFC with backmarking and conflict-directed backtracking. The new algorithm has a smaller space complexity than MFC. Experiments were conducted to compare it with MFC and some regular FC based algorithms. The results show that the new algorithm always performs at least as good as its "non-lazy" counterpart. It outperforms MFC on average and its edge over MFC is particularly clear for problems near to phase transitions. Interestingly, the minimum width variable ordering heuristic appears to be a better choice than the fail-first heuristic for the new algorithm in many occasions, particularly for sparsely constrained problems.

The processor configuration problem (PCP) is a constraint optimization problem. The task is to link up a finite set of processors into a network; minimizing the maximum distance between processors. Since each processor has a limited number of communication channels, a carefully planned layout could minimize the overhead for message switching. We present a genetic algorithm (GA) approach to the PCP. Our technique uses a mutation based GA, a function that produces schemata by analyzing previous solutions and an effective data representation. Our approach has been shown to outperform other published techniques in this problem.

The car sequencing problem (CarSP) was seen as a challenge to artificial intelligence. The CarSP is a version of the job-shop scheduling problem, which is known to be NP-complete. The task in the CarSP is to schedule a given number of cars (of different types) in a sequence to allow the teams in each workstation on the assembly line to fit the required options (e.g. radio, sunroof) on the cars within the capacity of that workstation. In unsolvable problems, one would like to minimize the penalties associated with the violation of the capacity constraints. Previous attempts to tackle the problem either have been unsuccessful or have been restricted to solvable CarSPs only. In this paper, we report on promising results in applying a generic genetic algorithm, which we call GAcSP, to tackle both solvable and unsolvable CarSPs.