Abstract
Most evolutionary algorithms use a fixed representation space. This complicates their application to many problem domains, especially when there are dependencies between problem variables (e.g. problems naturally defined over permutations). This paper presents a method for specifying algorithms with respect to abstract representations, making them completely independent of any actual representation or problem domain. It also defines a procedure for generating a concrete representation from an explicit characterisation of a problem domain which captures beliefs about its structure. This allows arbitrary algorithms to be applied to arbitrary problems yielding well-specified search strategies suitable for implementation. The process is illustrated by showing how identical algorithms can be applied to both the TSP and real parameter optimisation to yield familiar (but superficially very different) concrete search strategies.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
T. Bäck, F. Hoffmeister, and H.-P. Schwefel, 1991. A survey of evolution strategies. In Proceedings of the Fourth International Conference on Genetic Algorithms. Morgan Kaufmann (San Mateo).
L. J. Eshelman and D. J. Schaffer, 1992. Real-coded genetic algorithms and interval schemata. In D. Whitley, editor, Foundations of Genetic Algorithms 2. Morgan Kaufmann (San Mateo, CA).
D. E. Goldberg, 1989. Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley (Reading, Mass).
D. E. Goldberg, 1990. Real-coded genetic algorithms, virtual alphabets, and blocking. Technical Report IlliGAL Report No. 90001, Department of General Engineering, University of Illinois at Urbana-Champaign.
J. J. Grefenstette, 1984. GENESIS: A system for using genetic search procedures. In Proceedings of the 1984 Conference on Intelligent Systems and Machines, pages 161–165.
J. H. Holland, 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press (Ann Arbor).
Z. Michalewicz, 1992. Genetic Algorithms+Data Structures=Evolution Programs. Springer Verlag (Berlin).
I. M. Oliver, D. J. Smith, and J. R. C. Holland, 1987. A study of permutation crossover operators on the travelling salesman problem. In Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann (San Mateo).
N. J. Radcliffe and P. D. Surry, 1994a. Fitness variance of formae and performance prediction. In L. D. Whitley and M. D. Vose, editors, Foundations of Genetic Algorithms III, pages 51–72. Morgan Kaufmann (San Mateo, CA).
N. J. Radcliffe and P. D. Surry, 1994b. Formal memetic algorithms. In T. C. Fogarty, editor, Evolutionary Computing: AISB Workshop, pages 1–16. Springer-Verlag, Lecture Notes in Computer Science 865.
N. J. Radcliffe and P. D. Surry, 1995. Fundamental limitations on search algorithms: Evolutionary computing in perspective. In J. van Leeuwen, editor, Computer Science Today: Recent Trends and Developments, Lecture Notes in Computer Science, Volume 1000, pages 275–291. Springer-Verlag (New York).
N. J. Radcliffe, 1991a. Equivalence class analysis of genetic algorithms. Complex Systems, 5(2): 183–205.
N. J. Radcliffe, 1991b. Forma analysis and random respectful recombination. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 222–229. Morgan Kaufmann (San Mateo).
N. J. Radcliffe, 1992. Genetic set recombination. In D. Whitley, editor, Foundations of Genetic Algorithms 2. Morgan Kaufmann (San Mateo, CA).
N. J. Radcliffe, 1994. The algebra of genetic algorithms. Annals of Maths and Artificial Intelligence, 10:339–384.
P. D. Surry and N. J. Radcliffe, 1996. A formalism for real-parameter evolutionary algorithms and directed recombination. In submitted to Foundations of Genetic Algorithms IV. (San Diego).
G. Syswerda, 1989. Uniform crossover in genetic algorithms. In Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann (San Mateo).
M. D. Vose and G. E. Liepins, 1991. Schema disruption. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 237–243. Morgan Kaufmann (San Mateo).
D. Whitley, T. Starkweather, and D. Fuquay, 1989. Scheduling problems and traveling salesmen: The genetic edge recombination operator. In Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann (San Mateo).
N. Wirth, 1976. Algorithms+Data Structures=Programs. Prentice-Hall (Englewood Cliffs, NJ).
D. H. Wolpert and W G. Macready, 1995. No free lunch theorems for search. Technical Report SFI-TR-95-02-010, Santa Fe Institute.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Surry, P.D., Radcliffe, N.J. (1996). Formal algorithms + formal representations =search strategies. In: Voigt, HM., Ebeling, W., Rechenberg, I., Schwefel, HP. (eds) Parallel Problem Solving from Nature — PPSN IV. PPSN 1996. Lecture Notes in Computer Science, vol 1141. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61723-X_1001
Download citation
DOI: https://doi.org/10.1007/3-540-61723-X_1001
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61723-5
Online ISBN: 978-3-540-70668-7
eBook Packages: Springer Book Archive