# genetic algorithms

## Natural selection is a mechanism for generating an exceedingly high degree of improbability - *Ronald Aylmer Fisher*

## General optimisation/AI resources

## Special topics

Selected articles | References | Journals | Software | Links

# Selected articles

As a starting point I have prepared a brief overview of genetic algorithms, using some of the sources further on. In a similar vein the following brief introduction to GAs mentions the core ideas.

The overwhelming and definitive resource is, of course, The Hitch-Hiker's Guide to Evolutionary Computation, presented here as a PDF file. The Hitch-Hiker's site will, of course, continue evolving relative to the document.

Another excellent general introduction is by Whitely, while Beasley, Bull and Martin provide a two- part document consisting of fundamentals and research topics.

Another good source of both some introductory text and some Java applets demonstrating the application of genetic algorithms (as well as cellular automata and natural systems) is Coyote Gulch Productions. For convenience, the first three chapters of their (uncompleted) online book are provided here in PDF format. They are Software Biology, Tools for Software Evolution and Optimization by Evolution.

# .. and more specialised and advanced

**(May take a while to download these PDFs)**

Heuristics for cardinality constrained portfolio optimisation by Chang, Meade and Beasley presents three heuristic algorithms based upon genetic algorithms, tabu search and simulated annealing for finding the cardinality constrained efficient frontier.

Metaheuristic approaches to realistic portfolio optimization investigates the application of two heuristic methods genetic algorithms and tabu/scatter search, to the optimisation of realistic portfolios. The model is based on the classical mean-variance approach, but enhanced with floor and ceiling constraints, cardinality constraints and nonlinear transaction costs which includes a substantial illiquidity premium, and is then applied to a large 100-stock portfolio.

An interesting paper is on the comparison of iterative searches, consisting of various tabu searches and genetic hybrids; it is, however, applied to the quadratic assignment problem rather than a financial application.

In Evolution of trading rules for the FX market genetic programming is used to search for trading rules for the foreign exchange market using very high frequency data. Trading systems with retraining at regular intervals are studied and were found to generate higher returns than buy-and-hold strategies.

Heuristic Approaches for Portfolio Optimization shows that constraints on downside risk lead to optimal asset allocations which differ from the mean-variance optimum. They also introduce constraints restricting the trading variables to be integers, on the holding size of assets and on the maximum number of different assets in the portfolio and use an optimization heuristic called threshold accepting.

Another application is index tracking. Portfolio selection using genetic algorithms and quadratic programming techniques to find both their performance and the proportion of the available capital that should be invested in each member company is described in Index Tracking: Genetic Algorithms for Investment Portfolio Selection

A paper by Manzini and Speranza, Heuristic algorithms for the portfolio selection problem with minimum transaction lots, deals with linear risk functions and minimum transaction lots, a rather limited subset of all possible real-world constraints.

Quite mathematical in style, Enhancing Q-Learning for optimal asset allocation describes a method which allows the construction of a multi-period portfolio management system which handles transaction costs and risk preferences as well as other constraints.

An early but interesting approach to optimising portfolios is Applying Neural Networks and Genetic Algorithms to Tactical Asset Allocation (zipped) by Ypke Hiemstra.

And for those who would like to go right back to the beginning of it all, here are Origin of Species (1859) and The Descent of Man (1871) by Charles Darwin.

# References

The GA Bibliography provides a huge bibliography of documents related to genetic algorithms. An excellent resource.

A good source of papers on GAs and other AI topics which are available for downloading is the Evolutionary Algorithms Group at the University of Edinburgh.

Another useful source of papers is thethe University of Idaho.

# Journals

The AI Topics page enables you to access all the major AI resources on the Internet by subject or resources.

# Software

Crystal Ball is an integrated software suite for risk analysis and what-if exercises. The Optquest module in the professional version is a tabu/scatter search procedure. Crystal Ball is a highly integrated and professional package.

Palisade Corporation is the supplier of Evolver genetic algorithm software, as well as other risk analysis, distribution fitting, decision analysis and optimisation software. We found Evolver significantly superior to Crystal Ball for portfolio optimization, when the number of assets in the portfolio became large (i.e. over 30).

(Both of these packages are Excel add-ins.)

Generatoris a general software package which also has a financial version. Another commercial product is Gene Hunter, by Ward Systems. We haven't used it, so we can't recommend it.

ForeTrade Technologies supplies the Genetic Pattern Finder, which attempts to find patterns in market price data and give short-term entry and exit signals. Excel-compatible. An additional tool for the trader. s armoury.

For those with a programming bent, the Genetic Server/Library provides general purpose APIs for genetic algorithm design. Genetic Server is an ActiveX component that can be used to easily build custom genetic applications in Visual Basic.

# Links

The CMU Artificial Intelligence Group was established in 1993 to collect files, programs and publications of interest to artificial intelligence researchers, educators, students, and practitioners.

J E Beasley's home page is an entry point for the Mathforum OR library, a collection of problem test sets, as well as a useful reference to OR work done at Imperial College. The online availability of working papers is particularly useful.

IlliGAL isn't really, being the home page for the Illinois GA Laboratory. Research papers and technical reports are available on-line, as is a limited amount of source code.

Here is a 3-D example of a GA searching for a maximum, on another site, Introduction to Genetic Algorithms.

For all forms of artificial life (a virtual bug-fest?) go to Zooland.

The Santa Fe Institute is one of the leading sites for evolutionary computation and artificial life research.

The GA playground is a general GA toolkit implemented in Java, for experimenting with genetic algorithms and handling optimization problems. Plenty of test problems and test functions.

Memetic algorithms are a population-based approach for heuristic search in optimization problems. They are orders of magnitude faster than traditional genetic algorithms for some problem domains.

Slightly more off the beaten path is swarming. The Swarm Development Wiki is the starting point, which also offers Swarm, an experimental software package for multi-agent simulation of complex systems, originally developed at the Santa Fe Institute. Possibly a way of modelling investor behaviour in markets?

Readers might also be interested in agent-based computational economics (ACE), the computational study of economies modelled as evolving systems of autonomous interacting agents. The fastest growing area within ACE is agent-based computational finance.