Forma Analysis of Genetic Algorithms

Annotated bibliography

Nicholas J Radcliffe
Last updated: 16th March 2008

Background

This bibliography covers mainly the papers that I wrote myself or with Patrick Surry, but also includes a section with references to other papers I am aware of that use forma analysis. If you know of any papers on or using forma analysis not listed here, please send me mail (info@StochasticSolutions.com) and I will endevour to add them.

Forma Analysis

Forma analysis is a formal but very practical approach to allowing users to build better genetic and evolutionary algorithms in a structured manner, separating out three major components:

More particularly, forma analysis allows and encourages users to codify their domain-specific knowledge of a class of search problems in such a way as to allow an algorithmic approach to derive from that codified knowledge both a representation and a set of genetic operators suitable for manipulating that representation. Any reproductive plan expressed in terms of the formal representations and operators used in forma analysis can then be applied to any problem, because the reproductive plans and (formal) genetic operators are independent of the particular problem tackled.

Forma analysis also takes a different approach to handling many kinds of constraints, which are simply integrated into the representation when possible. This avoids many of the headaches often associated with handling constrained optimization in an evolutionary context.

Forma analysis was developed between about 1988 (when I, Nick Radcliffe, started trying to use genetic algorithms to optimize neural networks) and about 1999, initially by Nick Radcliffe, and latterly by Patrick Surry, working with Nick. This page provides annotated access to all the papers in which forma analysis was developed except Radcliffe's Ph.D. thesis, (which is largely superseded by the papers anyway).

Places to start

Radcliffe, N. J. Non-Linear Genetic Representations. in Parallel Problem Solving from Nature 2, (Ed: R. Manner and B. Manderick, Elsevier Science Publishers), . 1992.

Radcliffe, N. J. The Algebra of Genetic Algorithms. Annals of Maths and Artificial Intelligence, 10. 1994.

Surry, P.D. A Prescriptive Formalism for Constructing Domain-specific Evolutionary Algorithms. Ph.D. Thesis, University of Edinburgh. 1998.

Radcliffe, N. J. Equivalence Class Analysis of Genetic Algorithms. Complex Systems, 5(2). 1991.

Radcliffe, N. J., Forma Analysis and Random Respectful Recombination. Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann. 1991.

More Recent Developments of the Theory

Radcliffe, N.J., Surry, P.D. Fitness Variance of Formae and Performance Prediction. In "Foundations of Genetic Algorithms III", (Ed: L.D. Whitley and M.D. Vose, Morgan Kaufmann). 1994.

Radcliffe, N.J., Surry, P.D. Formal memetic algorithms. In "Evolutionary Computing: AISB Workshop", (Ed: T. Fogarty, Springer-Verlag). 1994.

Radcliffe, N.J., Surry, P.D., Fundamental Limitations on Search Algorithms: Evolutionary Computing in Perspective. Computer Science Today: Recent Trends and Developments, Lecture Notes in Computer Science, Volume 1000, pp. 275-291 (ed J. van Leuwen). 1995.

Surry, P.D., Radcliffe, N.J. Formal Algorithms + Formal Representations = Search Strategies. Parallel Problem Solving From Nature IV,. 1996.

Generic Representations derived with Forma Analysis

Representations are particularly fundamental to forma analysis. Although forma analysis, in principle, provides a mechanism for deriving separate representations for each problem class tackled, in practice, it is often clear that a particular type of representation will be suitable for a representing potential solutions to a problem, e.g.

Because these representations are so common, and form the basis of so much else, we have written papers discussing most of these cases separately. k-ary strings are not covered separately, because this is the "standard", widely discussed case. Also, permutations are not discussed as a "generic class" (because it is too broad), but there are papers specifically relevant to the Travelling Sales-rep Problem (TSP).

Surry, P.D., Radcliffe, N.J. Real Representations. In "Foundations of Genetic Algorithms IV", (Morgan Kaufmann). 1996.

Radcliffe, N. J. Genetic Set Recombination. In Foundations of Genetic Algorithms 2, (Ed: L.D. Whitley, Morgan Kaufmann). 1992.

Radcliffe, N.J., Surry, P.D. Fitness Variance of Formae and Performance Prediction. In "Foundations of Genetic Algorithms III", (Ed: L.D. Whitley and M.D. Vose, Morgan Kaufmann). 1994.

Specific Applications of Forma Analysis

Radcliffe, N. J. Genetic Set Recombination and its Application to Neural Network Topology Optimisation. Neural Computing and Applications, 1(1). 1993.

Radcliffe, N. J. Genetic Neural Networks on MIMD Computers. Ph.D. Thesis (Edinburgh University). 1990.

Harding, T. J., Radcliffe, N. J., King, P. R. Optimisation of Production Strategies using Stochastic Search Methods. In the proceedings of the SPE European 3-D Reservoir Modelling Conference, (Stavanger, Norway). 16--17 April, 1996.

Surry, P.D., Radcliffe, N.J., Boyd, I.D. A Multi-Objective Approach to Constrained Optimisation of Gas Supply Networks: The COMOGA Method. In "Evolutionary Computing: AISB Workshop", (Ed: T. Fogarty, Springer-Verlag). 1995.

Boyd, I.D., Surry, P.D., Radcliffe, N.J., Constrained gas network pipe sizing with genetic algorithms. EPCC-TR94-11. 1994.

George, F.A.W., Radcliffe, N.J., Smith, M.A., Birkin, M., Clarke, M., Spatial Interaction Model Optimisation on Parallel Computers. "Concurrency: Practice and Experience". 1994.

The Reproductive Plan Language RPL2

Radcliffe, N.J., Surry, P.D. The Reproductive Plan Language RPL2: Motivation, Architecture and Applications. In "Genetic Algorithms in Optimisation, Simulation and Modelling", (Ed: J. Stender, E. Hillebrand, and J. Kingdon, IOS Press). 1994.

Surry, P.D., Radcliffe, N.J. RPL2: A language and parallel framework for evolutionary computing. Parallel Problem Solving From Nature III. 1994.

Other Papers on Using Forma Analysis

Reimar Hofmann Examinations on the Algebra of Genetic Algorithms. Diploma Thesis, Chair Prof. Brauer, Department of Computer Science, Technical University of Munich . 1993.

C. Cotta, J.M. Troya Genetic Forma Recombination in Permutation Flowshop Problems. Evolutionary Computation 6(1):25-44. 1998.

R.E. Berretta, C. Cotta, P. Moscato Forma Analysis and New Heuristic Ideas for the Number Partitioning Problem. 4th Metaheuristics International Conference, pp. 337-341, Oporto. 2001

C. Cotta, J.M. Troya, On the Influence of the Representation Granularity in Heuristic Forma Recombination. ACM Symposium on Applied Computing 2000, J. Carroll, E. Damiani, H. Haddad, D. Oppenheim (eds.), ACM Press, pp. 433-439 2000.

C. Cotta, E. Alba, J.M. Troya Improving the Scalability of Dynastically Optimal Forma Recombination by Tuning the Granularity of the Representation, . Proceedings of the 1999 Genetic and Evolutionary Computation Conference, W. Banzhaf et al. (eds.), Morgan Kaufmann, pp. 783. 1999.

C. Cotta, E. Alba, J.M. Troya Utilising Dynastically Optimal Forma Recombination in Hybrid Genetic Algorithms. Parallel Problem Solving from Nature V, Baeck Th., Eiben A.E., Schoenauer M., Schwefel H.-P. (eds.), Lecture Notes in Computer Science 1498, pp. 305-314, Springer-Verlag, Berlin. 1998.

J Shapcott Index Tracking: Genetic Algorithms for Investment Portfolio Selection. EPCC-SS92-24. 1992.

Andrew Tuson No Representation Without Optimisation: A Knowledge Based Systems View of Evolutionary/Neighbourhood Search Optimisation. MSc Thesis. 1999.

M. Jelasity and J. Dombi Implicit formae in Genetic Algorithms.. In The Proceedings of PPSN'96, Springer, LNCS 1141, pp154-163. 1996.

Richard A. Watson Jordan B. Pollack Recombination Without Respect: Schema Combination and Disruption in Genetic Algorithm Crossover. 2000.

Alden H. Wright, Jonathan E. Rowe and Michael D. Vose Group Properties of Crossover and Mutation. Evolutionary Computation 10(2), pages 151-184. 2002.

Valid XHTML 1.0!