Abstract
This paper presents a new generic Evolutionary Algorithm (EA) for retarding the unwanted effects of premature convergence. This is accomplished by a combination of interacting generic methods. These generalizations of a Genetic Algorithm (GA) are inspired by population genetics and take advantage of the interactions between genetic drift and migration. In this regard a new selection scheme is introduced, which is designed to directedly control genetic drift within the population by advantageous self-adaptive selection pressure steering. Additionally this new selection model enables a quite intuitive heuristics to detect premature convergence. Based upon this newly postulated basic principle the new selection mechanism is combined with the already proposed Segregative Genetic Algorithm (SEGA), an advanced Genetic Algorithm (GA) that introduces parallelism mainly to improve global solution quality. As a whole, a new generic evolutionary algorithm (SASEGASA) is introduced. The performance of the algorithm is evaluated on a set of characteristic benchmark problems. Computational results show that the new method is capable of producing highest quality solutions without any problem-specific additions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Affenzeller,M. (2001). “A New Approach to Evolutionary Computation: Segregative Genetic Algorithms (SEGA). Connectionist Models of Neurons, Learning Processes, and Artificial Intelligence.” Lecture Notes of Computer Science 2084, 594–601.
Affenzeller, M. (2001). “Transferring the Concept of Selective Pressure from Evolutionary Strategies to Genetic Algorithms.” In Proceedings of the 14th International Conference on Systems Science 2, pp. 346–353.
Affenzeller,M. (2001). “Segregative Genetic Algorithms (SEGA): A Hybrid Superstructure Upwards Compatible to Genetic Algorithms for Retarding Premature Convergence.” Internatinal Journal of Computers, Systems and Signals (IJCSS) 2(1), 18–32.
Affenzeller, M. (2002). “A Generic Evolutionary Computation Approach Based Upon Genetic Algorithms and Evolution Strategies.” Systems Science 28(2), 59–71.
Affenzeller, M. and S. Wagner. (2003). “SASEGASA: An Evolutionary Algorithm for Retarding Premature Convergence by Self-Adaptive Selection Pressure Steering.” Computational Methods in Neural Modeling, Lecture Notes of Computer Science-IWANN 2003. Lecture Notes in Computer Science 2686, 438–445.
Affenzeller,M. and S.Wagner. (2003). A Self-Adaptive Model for Selective Pressure Handling within the Theory of Genetic Algorithms.” Computer Aided Systems Theory: EUROCAST 2003, Lecture Notes in Computer Science 2809, 384–393.
Alba, E. and J.M. Troya. (1999). “A Survey of Parallel Distributed Genetic Algorithms.” Complexity 4(4), 31–52.
Baeck, T. (1993). “Selective Pressure in Evolutionary Algorithms: A Characterization of Selection Mechanisms.” In Proceedings of the First IEEE Conference on Evolutionary Computation 1994, pp. 57–62.
Cantu-Paz, E. (2001). Efficient and Accurate Parallel Genetic Algorithms. Kluwer Academic Publishers.
Cobb, H.J. and J.J. Grefenstette. (1993). “Genetic Algorithms forTracking Changing Environment.” In Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 523-530.
DeJong, K.A. (1975). “An Analysis of the Behaviour of a Class of Genetic Adaptive Systems.” PhD thesis. Department of Computer Science. University of Michigan.
Dumitrescu, D., B. Lazzerini, L.C. Jain. and A. Dumitrescu. (2000). Evolutionary Computation. CRC Press.
Fogel, D.B. (1994). “An Introduction to Simulated Evolutionary Optimization.” IEEE Trans. on Neural Networks 5(1), 3–14.
Goldberg, D.E. (1989). Genetic Alogorithms in Search, Optimization and Machine Learning. Addison Wesley Longman.
Gordon, V.S. and D. Whitley. (1993). “Serial and Parallel Genetic Algorithms as Function Optimizers.” In Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufman, pp. 177-183.
Hajek, B. (1988). “Cooling Schedules for Optimal Annealing.” Operations Research 13, 311–329.
Hiroyasu, T., M. Miki, M. Hamasaki, and Y. Tanimura. (2000). “A New Model of Distributed Genetic Algorithm for Cluster Systems: Dual Individual DGA.” High Performance Computing. Springer, LNCS 1940, 374–383.
Holland, J.H. (1975). Adaption in Natural and Artificial Systems. University of Michigan Press.
Larranaga, P., C.M.H. Kuijpers, R.H. Murga, I. Inza, and S. Dizdarevic. (1999). “Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators.” Artificial Intelligence Review 13, 129–170.
Liang, K., X. Yao, and C. Newton. (2000). “Evolutionary Search of Approximated N-Dimensional Landscapes.” International Journal of Knowledge-Based Intelligent Engineering Systems 4(3), 172–183.
Michalewicz, Z. (1996). Genetic Algorithms + Data Structures =Evolution Programs, 3rd edn. Berlin Heidelberg, New York: Springer-Verlag.
Mühlenbein, H., M. Schomisch, and J. Born. (1991). “The Parallel Genetic Algorithm as Function Optimizer.” Parallel Computing 17, 619–631.
Potter, M.A. and K. De Jong. (1994). “A Cooperative Coevolutionary Approach to Function Optimization. Parallel Problem Solving from Nature-PPSN III.” LNCS 866, pp. 249–257, Springer.
Rechenberg, I. (1973). Evolutionsstrategie. Friedrich Frommann Verlag.
Reinelt, G. (1991). “TSPLIB-A Traveling Salesman Problem Library.” ORSA Journal on Computing 3, 376–384.
Schoeneburg, E., F. Heinzmann, and S. Feddersen. (1994). Genetische Algorithmen und Evolutionsstrategien. Addison-Wesley.
Schwefel, H.-P. (1994). Numerische Optimierung von Computer-Modellen mittels Evolutionsstrategie. Birkhäuser Verlag. Basel.
Smith, R.E., S. Forrest, and A.S. Perelson. (1993). “Population Diversity in an Immune System Model: Implications for Genetic Search.” Foundations of Genetic Algorithms 2, 153–166.
Schwefel, H.-P. and R. Maenner. (Eds). (1999). Proceedings of the First International Conference on Parallel Problem Solving from Nature (PPSN). Berlin Heidelberg, New York: Springer-Verlag.
Srinivas, M. and L. Patnaik. (1994). Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms. IEEE Transactions on Systems, Man, and Cybernetics 24(4), 656–667.
Takahashi, O., H. Kita, and S. Kobayashi. (1999). A Distance Dependent Alternation Model on Real-Coded Genetic Algorithms. IEEE Transactions on Systems, Man, and Cybernetics 619-624.
Yao, X. (1997). “A Diploid Genetic Algorithm for Preserving Population Diversity-Pseudo-Meiosis GA.” Lecture Notes in Computer Science 866, 36–45.
Winkler, S., M. Attenzeller, and S. Wagner. (2004). “Identifying Nonlinear Model Structures Using Genetic Programming Techniques.” Accepted to be published in: Proceedings of the European Meeting on Cybernetics and Systems Research-EMCSR 2004.
Yoshida, Y. and N. Adachi. (1994). “Global Optimisation by Evolutionary Algorithms.” In Proceedings of the Second AIZU International Symposium on Parallel Algorithms/Architecture Synthesis. IEEE Computer Society Press, pp. 282-291.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Affenzeller, M., Wagner, S. SASEGASA: A New Generic Parallel Evolutionary Algorithm for Achieving Highest Quality Results. Journal of Heuristics 10, 243–267 (2004). https://doi.org/10.1023/B:HEUR.0000026895.72657.a2
Issue Date:
DOI: https://doi.org/10.1023/B:HEUR.0000026895.72657.a2