Abstract
This paper proposes a new technique for improving the number of usefully distinct solutions produced by a Genetic Algorithm (GA) when applied to multimodal problems. The tribes method builds on the spatial selection methods proposed by Collins and Jefferson [1]. We compare the technique with two well-known niching methods (crowding and sharing), spatial selection alone, and a simple control GA method, in the domain of simple timetabling problems. We demonstrate that the tribes technique can greatly improve the efficiency with which a GA can obtain multiple distinct solutions to a problem.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Collins, R. J., Jefferson, D. R.: Selection in massively parallel genetic algorithms. Proc. 4th International Conference on Genetic Algorithms. Morgan Kaufmann (1991)
Corne, D., Fang, H.-L., Mellish, C.: Solving the modular exam scheduling problem with genetic algorithms. Proc. 6th Int'l. Conf. in Industrial & Engineering Applications of Artificial Intelligence & Expert Systems. Gordon & Breach Science Publishers (1993)
Davidor, Y.: A naturally occurring niche & species phenomenon: the model and first results. Proc. 4th International Conference on Genetic Algorithms. Morgan Kaufmann (1991)
Deb, K., Goldberg, D. E.: An investigation of niche and species formation in genetic function optimisation. Proc. 3rd International Conference on Genetic Algorithms. Morgan Kaufmann (1989)
De Jong, K. A.: An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Dissertation Abstracts International 36(10), 5140B (University Microfilms No. 769381). PhD thesis, U. of Michigan, Ann Arbor (1975)
Goldberg, D. E., Richardson J. J., Genetic algorithms with sharing for multimodal function optimization. Proc. 2nd International Conference on Genetic Algorithms. Lawrence Erlbaum Publishers (1987)
Gorges-Schleuter, M., Explicit Parallelism of Genetic Algorithms through Population Structures. Parallel Problem Solving from Nature. Springer-Verlag, pp 150–159 (1990)
Mahfoud, S. W.: Crowding and preselection revisited. Männer R., Manderick B. (eds): Parallel Problem Solving from Nature 2. Elsevier (1992)
Ross, P., Corne D.: Comparing Genetic Algorithms, Simulated Annealing, and Stochastic Hillclimbing on Timetabling Problems. Evolutionary Computing: AISB Workshop, Sheffield 1995, Selected Papers, Springer-Verlag, T. Fogarty (ed), Springer Verlag (1995).
Turner, P. A.: Genetic Algorithms and Multiple Distinct Solutions. Unpublished MSc thesis, U. of Edinburgh (1994), Postscript version available via http://boom.cs.ucl.ac.uk/staff/A.Turner/pubs.
Wright, S., Evolution and the Genetics of Population, Volume 2: The Theory of Gene Frequencies. U. of Chicago Press (1969)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Turner, A., Corne, D., Ritchie, G., Ross, P. (1996). Obtaining multiple distinct solutions with genetic algorithm niching methods. 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_1009
Download citation
DOI: https://doi.org/10.1007/3-540-61723-X_1009
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