Abstract
This paper proposes a memory-efficient elitist genetic algorithm (me2GA) for solving hard optimization problems quickly and effectively. The idea is to properly reconcile multiple probability (distribution) vectors (PVs) with elitism. Multiple PVs (rather than a single PV as in compact GA (cGA)) provide an effective framework for representing the population as a probability distribution over the set of solutions. A coordinated interplay amongst multiple PVs maintains genetic diversity, thereby recovery from decision errors is possible. On the other hand, reconciling with elitism allows a potentially optimal (elitist) solution to be kept current as long as other (competing) solutions generated from PVs are no better. This is because it exerts a selection pressure that is high enough to offset the disruptive effects of uniform crossover. It also attempts to adaptively alter the selection pressure in accordance with the degree of problem difficulty through pair-wise tournament selection strategy. Experimental results show that the proposed algorithm generally exhibits a superior quality of solution. Moreover, the proposed algorithm deploys memory more efficiently than extant sGA and cGA, especially when the problem is difficult.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Goldberg, D.E.: The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Dordrecht (2002)
Ahn, C.W., Ramakrishna, R.S.: A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations. IEEE Transactions on Evolutionary Computation 6(6) (2002)
Baluja, S.: Population-based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning. Technical Report CMU-CS-94-163, Carnegie Mellon University, Pittsburgh, PA (1994)
Harik, G., Lobo, F.G., Goldberg, D.E.: The Compact Genetic Algorithm. IEEE Transactions on Evolutionary Computation 3(4), 287–297 (1999)
Ahn, C.W., Ramakrishna, R.S.: Elitism-based Compact Genetic Algorithms. IEEE Transaction on Evolutionary Computation 7(4), 367–385 (2003)
Cantŭ-Paz, E.: Efficient and Accurate Parallel Genetic Algorithms. Kluwer Academic Publishers, Dordrecht (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ahn, C.W., Kim, K.P., Ramakrishna, R.S. (2004). A Memory-Efficient Elitist Genetic Algorithm. In: Wyrzykowski, R., Dongarra, J., Paprzycki, M., Waśniewski, J. (eds) Parallel Processing and Applied Mathematics. PPAM 2003. Lecture Notes in Computer Science, vol 3019. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24669-5_72
Download citation
DOI: https://doi.org/10.1007/978-3-540-24669-5_72
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21946-0
Online ISBN: 978-3-540-24669-5
eBook Packages: Springer Book Archive