Forma Analysis of Genetic Algorithms: Annotated Bibliograph

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:

• representations - which are defined very broadly, and can include conventional k-ary string representations, set-based and multiset-based ("variable length") representations, and much else;
• genetic operators which are specified in such a way as to be independent of representation, so that they can be applied extremely widely;
• reproductive plans (or "algorithms") , which specify how to apply both genetic and non-genetic operators to representations in order to form real, executable evolutionary algorithms.

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.

• This is probably the most accessible paper on forma analysis, having very little maths and being relatively strong on motivating the ideas. If you just want the general idea of forma analysis, and aren't fond of maths, this paper is probably the best starting place.
• Abstract: text
• Full paper: PDF, postscript

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

• If you are comfortable with maths (in particular, set theory and algebra), this is the nearest there is to a "reference work". Although it doesn't include all the latest material (see below), this covers almost all the key ideas more precisely than elsewhere.
• Abstract: text
• Full paper: PDF, postscript

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

• If you fancy a longer read and a very up-to-date account of forma analysis, (and much else), Patrick's thesis is the place to start. Although there is maths in places, it is less intense than most of the early papers, and does cover the full range of forma analysis, including the more recent developments.
• Full paper: postscript

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

• This was the first published paper on forma analysis, and introduces most of the key ideas. What is referred to as "redundancy" in this and the other early papers is termed (more precisely) "degeneracy" in later papers. The paper is also perhaps over-prescriptive, but most of the ideas did survive into forma analysis in its current form.
• Abstract: text
• Full paper: PDF, postscript

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

• This condenses most of the information in the first paper, and introduces the first representation-independent genetic operator - random respectful recombination (RRR). Since such operators are so crucial to forma analysis as it developed, this is in some ways a better place to start than the first paper.
• Abstract: text
• Full paper: PDF, postscript

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.

• This paper addresses the problem of what it means to say that one representation is "better" than another. In particular, it introduces a class of measures ("fitness variance") that can be computed for each representation and compared, and shows that, at least for the problem classes studied, these seem to be fairly well correlated with the performance of identical formal algorithms using these representations.
• Abstract: text
• Full paper: PDF, postscript

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

• A memetic algorithm is a genetic or evolutionary algorithm that incorporates local optimization (or "hill-climbing"). This paper extends forma analysis to cover memetic algorithms.
• Abstract: text
• Full paper: PDF, postscript

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.

• This paper focuses on a so-called "No Free Lunch" Theorem for genetic representations.
• Abstract: text
• Full paper: PDF,

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

• This is a relatively up-to-date account of the state of forma analysis, emphasizing particularly the idea of being able to use exactly the same formal algorithm across a range of problem domains when the representation is constructed uses the prescriptive formalism of forma analysis.
• Abstract: text
• Full paper: PDF, postscript

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.

• k-ary string (the "classic" representation)
• a vector (array) of real numbers
• a set of objects (a subset of some "universal set")
• a multiset ("bag") of objects (like a set, but allowing elements to be present more than once)
• a permutation (i.e. an ordering of the numbers 1 to n

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.

• This paper applies forma analysis to construct formal representations corresponding to real numbers. The result is both elegant and surprising, and extends the theory considerably. The representations constructed yield formally infinite chromosomes that can, nevertheless, be handled extremely easily, and show that some of the standard operators from genetic algorithms and forma analysis are formally equivalent, under these representations, to some of the operators long used in Evolution Strategies. This paper therefore forms an extremely interesting link between the "American" school of "Genetic Algorithms" and the "European" approach of Evolution Strategies.
• Abstract: text
• Full paper: PDF, postscript

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

• The solutions to many classes of search problems are naturally expressed as sets multisets (sets that allow repetition of elements). This paper applies forma analysis to generic sets and multisets and derives the standard operators for these representations. The representations developed for sets and multisets avoid the need to impose "constraints" when the size of the set or bag is fixed, and constitute a naturally "variable-length" representation when the size is not fixed; both cases are discussed.
• Abstract: text
• Full paper: PDF, postscript

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.

• This paper (also discussed above) includes a very detailed study of four different approaches to representing the travelling sales-rep problem (TSP). All the approaches are based on permutations, but each makes a different set of assumptions about what features of solutions are important (i.e., applies different "domain knowledge"). The four different sets of assumptions, under forma analysis, lead to four different representations and four different instantiations of the standard genetic operators. The paper is relevant to any application in which the problem is naturally represented as a permutation, though the best choice of assumptions about the problem space will be different in different domains.
• Abstract: text
• Full paper: PDF, postscript

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.

• Forma analysis was originally motivated by my grappling with the problem of how sensibly to apply genetic algorithms to the optimization of layered, feed-forward neural networks. The clear problem is that most of the obvious representations are highly degenerate, i.e., most neural networks are represented by many different chromosomes, and it is hard to tell, by inspection, whether two chromosomes in fact correspond to the same network. This is a particular problem when genetic algorithms are used because of the existence of recombination, which has the potential to make extremely odd moves if it does not "understand" any degeneracy present. This paper shows how multiset-based representations can completely remove the redundancy and allow genetic algorithms to be applied very cleanly to the optimization of neural network topology.
• Abstract: text
• Full paper: PDF postscript

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

• This covers the same ground as a number of the previous papers, and is just here for completeness. Unfortunately, some of the fonts look pretty messed up on screen in the (apologies), but they seem to print OK.
• Full thesis: PDF

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.

• Abstract: text
• Full paper: PDF postscript

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.

• Abstract: text
• Full paper: PDF postscript

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

• Abstract: text
• Full paper: PDF postscript

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.

• Abstract: text
• Full paper: PDF postscript

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.

• Abstract: text
• Full paper: PDF postscript

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

• Abstract: text
• Full paper: PDF postscript

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.

• Reference: Link rotted

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

• Reference: PDF download

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

• Reference: Download page

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.

• Reference: Author homepage

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.

• Reference: Author homepage

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.

• Reference: Author homepage

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

• Full paper: PDF

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

• Reference: Author homepage
• Full Thesis: Postscript

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

• Full paper: PDF

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

• Reference: PDF

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

• Reference: Author Home page
• Full paper: PDF