Abstract
A frequently observed difficulty in the application of genetic algorithms to the domain of optimization arises from premature convergence. In order to preserve genotype diversity we develop a new model of auto-adaptive behavior for individuals. In this model a population member is an active individual that assumes social-like behavior patterns. Different individuals living in the same population can assume different patterns. By moving in a hierarchy of “social states” individuals change their behavior. Changes of social state are controlled by arguments of plausibility. These arguments are implemented as a rule set for a massively-parallel genetic algorithm. Computational experiments on 12 large-scale job shop benchmark problems show that the results of the new approach dominate the ordinary genetic algorithm significantly.
Supported by the Deutsche Forschungsgemeinschaft (Project Parnet)
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adams, J., Balas, E., Zawack, D.: The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science 34 (1988) 391–401
Applegate, D., Cook, W.: A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing 2 (1991) 149–156
Bierwirth, C.: A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms. OR Spektrum (to appear)
Davidor, Y.: A Naturally Occurring Nice & Species Phenomenon: The Model and First Results. Proc. of ICGA 4, Morgan Kaufmann (1991) 257–263
Davidor, Y., Yamada, T., Nakano, R.: The ECOlogical Framework II, Improving GA Performance at Virtually Zero Cost. Proc. of ICGA 5, Morgan Kaufmann (1993) 171–176
Dell'Amico, M., Trubian, M.: Applying Tabu-Search to the Job Shop Scheduling Problem. Annals of Operations Research 41 (1993) 231–252
Eshelman, L.J., Schaffer, J.D.: Preventing Premature Convergence in Genetic Algorithms by Preventing Incest. Proc. of ICGA 4, Morgan Kaufmann (1991) 115–122
Gorges-Schleuter, M.: Comparison of Local Mating Strategies in Massively Parallel Genetic Algorithms. Proc. of PPSN 2, North-Holland (1992) 553–562
van Laarhoven, P.J., Aarts, E.H., Lenstra, J.K.: Job Shop Scheduling by Simulated Annealing. Operations Research 40 (1993) 113–125
Mehlhorn, K., Näher, S.: LEDA, A Library of Efficient Data Types and Algorithms. TR A 05/89 University of Saarbrücken (1989)
Mühlenbein, H., Gorges-Schleuter, M.: Die Evolutionsstrategie: Prinzip für parallele Algorithmen. GMD Annual Report (1988)
Staats, A.W.: Social behaviorism. The Dorsey Press, Illinois (1975)
Taillard, E.: Parallel Taboo Search Techniques for the Job Shop Problem. TR ORWP 89/11, Ecole Polytechnique de Lausanne (1989)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mattfeld, D.C., Kopfer, H., Bierwirth, C. (1994). Control of parallel population dynamics by social-like behavior of GA-individuals. In: Davidor, Y., Schwefel, HP., Männer, R. (eds) Parallel Problem Solving from Nature — PPSN III. PPSN 1994. Lecture Notes in Computer Science, vol 866. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58484-6_246
Download citation
DOI: https://doi.org/10.1007/3-540-58484-6_246
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58484-1
Online ISBN: 978-3-540-49001-2
eBook Packages: Springer Book Archive