Abstract
Minimal Switching Graph (MSG) is a graph-theoretic representation of the constrained via minimization problem — a combinatorial optimization problem in integrated circuit design automation. From a computational point of view, the problem is NP-complete. Hence, a genetic algorithm (GA) was proposed to tackle the problem, and the experiments showed that the GA was efficient for solving large-scale via minimization problems. However, it is observed that the GA is sensitive to the permutation of the genes in the encoding scheme. For an MSG problem, if different permutations of the genes are used the performances of the GA are quite different. In this paper, we present a new GA for MSG problem. Different from the original GA, this new GA has a self-adaptive encoding mechanism that can adapt the permutation of the genes in the encoding scheme to the underlying MSG problem. Experimental results show that this adaptive GA outperforms the original GA.
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
Tang, M., Eshraghian, K., Cheung, H.N.: An Efficient Approach to Constrained Via Minimization for Two-Layer VLSI Routing. In: Proc. IEEE Asia and South Pacific Design Automation Conference, Hong Kong, pp. 149–152 (1999)
Naclerio, N.J., Masuda, S., Nakajima, K.: The Via Minimization problem is NP-complete. IEEE Transactions on Computers 38, 1604–1608 (1989)
Tang, M., Eshraghian, K., Cheung, H.N.: A Genetic Algorithm for Constrained Via Minimization. In: Proc. IEEE International Conference on Neural Information Processing, Perth, pp. 435–440 (1999)
Harik, G.R., Goldberg, D.E.: Linkage Learning. IlliGAL Technical Report 96006 (1996)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading (1989)
Goldberg, D.E., Korb, B., Deb, K.: Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems 3, 493–530 (1989)
Harik, G.R.: Lingake Learning Via Probabilistic Modeling. IlliGAL Technical Report 99010 (1999)
Mühlenbein, H., Paaß, G.: From Recombination of Genes to the Estimation of Distributions I. Binary Parameters. In: Eiben, A., Bäck, T., Shoenauer, M., Schwefel, H.-P. (eds.) Parallel Problem Solving from Nature - PPSN IV, pp. 178–187. Springer, Berlin (1996)
Harik, G.R., Lobo, F.G., Goldberg, D.E.: The Compact Genetic Algorithm. In: International Conference on Evolutionary Computation, pp. 523–528. IEEE, New Jersey (1998)
Pelikan, M., Goldberg, D.E., Cantu-Paz, K.: Linkage Problem, Distribution Estimation, and Bayesian Networks. Evolutionary Computation 8, 311–340
Sastry, K.: Analysis of Mixing in Genetic Algorithms: A survey. IlliGAL Report No. 2002012 (2002)
Sastry, K., Goldberg, D.E.: How Well Does A Single-Point Crossover Mix Building Blocks with Tight Linkage? IlliGAL Report No. 2002013 (2002)
Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd edn. Springer, Heidelberg (1996)
Prügel-Bennett, A.: Modeling Cross-Induced Linkage in Genetic Algorithms. IEEE Trans. on Evolutionary Computation 5, 376–387 (2001)
Thierens, D., Goldberg, D.E.: Mixing in Genetic Algorithms. In: Proc. the 5th Int. Conf. on Genetic Algorithms, pp. 38–45 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tang, M. (2005). An Adaptive Genetic Algorithm for the Minimal Switching Graph Problem. In: Raidl, G.R., Gottlieb, J. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2005. Lecture Notes in Computer Science, vol 3448. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31996-2_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-31996-2_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25337-2
Online ISBN: 978-3-540-31996-2
eBook Packages: Computer ScienceComputer Science (R0)