Skip to main content

2016 | OriginalPaper | Buchkapitel

Genetic Algorithms for Constrained Tree Problems

verfasst von : Riham Moharam, Ehab Morsy

Erschienen in: Recent Advances in Computational Optimization

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Given an undirected weighted connected graph \(G=(V,E)\) with vertex set V, edge set E and a designated vertex \(r \in V\), this chapter studies the following constrained tree problems in G. The first problem, called Constrained Minimum Spanning Tree Problem (CMST), asks for a rooted tree T in G that minimizes the total weight of T such that the distance between the r and any vertex v in T is at most a given constant C times the shortest distance between the two vertices in G. The second problem, Constrained Shortest Path Tree Problem (CSPT) requires a rooted tree T in G that minimizes the maximum distance between r and all vertices in V such that the total weight of T is at most a given constant C times the minimum tree weight in G. It is easy to conclude from the literatures that the above problems are NP-hard. This chapter presents efficient genetic algorithms that return (as shown by our experimental results) high quality solutions for those two problems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Abdoun, O., Abouchabaka, J., Tajani, C.: Analyzing the performance of mutation operators to solve the travelling salesman problem. IJES, Int. J. Emerg. Sci. 2(1), 61–77 (2012)MATH Abdoun, O., Abouchabaka, J., Tajani, C.: Analyzing the performance of mutation operators to solve the travelling salesman problem. IJES, Int. J. Emerg. Sci. 2(1), 61–77 (2012)MATH
2.
Zurück zum Zitat Awerbuch, B., Baratz, A., Peleg, D.: Cost-sensetive analysis of communication protocols. In: Proceedings on Principles of Distributed Computing, pp. 177–187 (1990) Awerbuch, B., Baratz, A., Peleg, D.: Cost-sensetive analysis of communication protocols. In: Proceedings on Principles of Distributed Computing, pp. 177–187 (1990)
3.
Zurück zum Zitat Awerbuch, B., Baratz, A. Peleg, D.: Efficient broadcast and light-weight spanners. Manuscript (1991) Awerbuch, B., Baratz, A. Peleg, D.: Efficient broadcast and light-weight spanners. Manuscript (1991)
4.
Zurück zum Zitat Bharath-Kumar, K., Jaffe, J.M.: Routing to multiple destinations in computer networks. IEEE Trans. Commun. 31(3), 343–351 (1983)CrossRefMATH Bharath-Kumar, K., Jaffe, J.M.: Routing to multiple destinations in computer networks. IEEE Trans. Commun. 31(3), 343–351 (1983)CrossRefMATH
5.
Zurück zum Zitat Blickle, T., Thiele, L.: A comparison of selection schemes used in genetic algorithms (Technical Report No. 11), Swiss Federal Institute of Technology (ETH) Zurich, Computer Engineering and Communications Networks Lab (TIK) (1995) Blickle, T., Thiele, L.: A comparison of selection schemes used in genetic algorithms (Technical Report No. 11), Swiss Federal Institute of Technology (ETH) Zurich, Computer Engineering and Communications Networks Lab (TIK) (1995)
6.
Zurück zum Zitat Campos, R., Ricardo, M.: A fast algorithm for computing minimum routing cost spanning trees. Comput. Netw. 52(17), 3229–3247 (2008)CrossRefMATH Campos, R., Ricardo, M.: A fast algorithm for computing minimum routing cost spanning trees. Comput. Netw. 52(17), 3229–3247 (2008)CrossRefMATH
7.
Zurück zum Zitat Chipperfield, A., Fleming, P., Pohlheim, H., Fonseca, C.: The matlab genetic algorithm user’s guide, UK SERC (1994) Chipperfield, A., Fleming, P., Pohlheim, H., Fonseca, C.: The matlab genetic algorithm user’s guide, UK SERC (1994)
8.
Zurück zum Zitat Cong, J., Kahng, A., Robins, G., Sarrafzadeh, M., Wong, C.K.: Performance-driven global routing for cell based IC’s. In: Proceedings of the IEEE International Conference on Computer Design, pp. 170-173 (1991) Cong, J., Kahng, A., Robins, G., Sarrafzadeh, M., Wong, C.K.: Performance-driven global routing for cell based IC’s. In: Proceedings of the IEEE International Conference on Computer Design, pp. 170-173 (1991)
9.
Zurück zum Zitat Cong, J., Kahng, A., Robins, G., Sarrafzadeh, M., Wong C.K.: Provably good performance-driven global routing. IEEE Transaction on CAD, pp. 739–752 (1992) Cong, J., Kahng, A., Robins, G., Sarrafzadeh, M., Wong C.K.: Provably good performance-driven global routing. IEEE Transaction on CAD, pp. 739–752 (1992)
10.
Zurück zum Zitat Davis, L., Orvosh, D., Cox, A., Qiu, Y.: A genetic algorithm for survivable network design. In: Proceedings 5th International Conference on Genetic Algorithms, pp. 408–415 (1993) Davis, L., Orvosh, D., Cox, A., Qiu, Y.: A genetic algorithm for survivable network design. In: Proceedings 5th International Conference on Genetic Algorithms, pp. 408–415 (1993)
11.
Zurück zum Zitat Engelbrecht, A.P.: Computational Intelligence: An Introduction. Wiley, New York (2007)CrossRef Engelbrecht, A.P.: Computational Intelligence: An Introduction. Wiley, New York (2007)CrossRef
12.
Zurück zum Zitat Erdos, P., Renyi, A.: On random graphs. Publ. Math 6, 290–297 (1959) Erdos, P., Renyi, A.: On random graphs. Publ. Math 6, 290–297 (1959)
13.
Zurück zum Zitat Farley, A.M., Zappala D., Proskurowski, A., Windisch, K.: Spanners and message distribution in networks, Dicret. Appl. Math. 137, 159–171 (2004) Farley, A.M., Zappala D., Proskurowski, A., Windisch, K.: Spanners and message distribution in networks, Dicret. Appl. Math. 137, 159–171 (2004)
14.
Zurück zum Zitat Gottlieb, J., Julstrom, B.A., Rothlauf, F., Raidl, G.R.: Prüfer numbers: a poor representation of spanning trees for evolutionary search. In: Proceedings of the 2001 Genetic and Evolutionary Computation Conference, pp. 343350. Morgan Kaufmann (2000) Gottlieb, J., Julstrom, B.A., Rothlauf, F., Raidl, G.R.: Prüfer numbers: a poor representation of spanning trees for evolutionary search. In: Proceedings of the 2001 Genetic and Evolutionary Computation Conference, pp. 343350. Morgan Kaufmann (2000)
15.
Zurück zum Zitat Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31, 1479–1500 (2002) Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31, 1479–1500 (2002)
16.
Zurück zum Zitat Hesser, J., Mnner, R.: Towards an optimal mutation probability for genetic algorithms. In: Proceedings of the 1st Workshop in Parallel Problem Solving from Nature, pp. 23-32 (1991) Hesser, J., Mnner, R.: Towards an optimal mutation probability for genetic algorithms. In: Proceedings of the 1st Workshop in Parallel Problem Solving from Nature, pp. 23-32 (1991)
17.
Zurück zum Zitat Huang, G., Li, X., He, J.: Dynamic minimal spanning tree routing protocol for large wireless sensor networks. In: Proceedings of the 1st IEEE Conference on Industrial Electronics and Applications, Singapore, pp. 1-5 (2006) Huang, G., Li, X., He, J.: Dynamic minimal spanning tree routing protocol for large wireless sensor networks. In: Proceedings of the 1st IEEE Conference on Industrial Electronics and Applications, Singapore, pp. 1-5 (2006)
18.
Zurück zum Zitat Julstrom, B. A.: Encoding rectilinear Steiner trees as lists of edges. In: Proceedings of the 16th ACM Symposium on Applied Computing, pp. 356–360. ACM Press (2001) Julstrom, B. A.: Encoding rectilinear Steiner trees as lists of edges. In: Proceedings of the 16th ACM Symposium on Applied Computing, pp. 356–360. ACM Press (2001)
19.
Zurück zum Zitat Khullar, S., Raghavachari, B., Young, N.: Balancing minimum spanning trees and shortest-path trees. Algorithmica 14, 305–322 (1995)MathSciNetCrossRefMATH Khullar, S., Raghavachari, B., Young, N.: Balancing minimum spanning trees and shortest-path trees. Algorithmica 14, 305–322 (1995)MathSciNetCrossRefMATH
20.
Zurück zum Zitat Li, C., Zhang, H., Hao, B., Li, J.: A survey on routing protocols for large-scale wireless sensor networks. Sensors 11, 3498–3526 (2011)CrossRef Li, C., Zhang, H., Hao, B., Li, J.: A survey on routing protocols for large-scale wireless sensor networks. Sensors 11, 3498–3526 (2011)CrossRef
21.
Zurück zum Zitat Lin, W.-Y. Lee, W.-Y., T.-P. Hong (2001) Adapting Crossover and Mutation Rates in Genetic Algorithms, the Sixth Conference on Artificial Intelligence and Applications, Kaohsiung, Taiwan (2001) Lin, W.-Y. Lee, W.-Y., T.-P. Hong (2001) Adapting Crossover and Mutation Rates in Genetic Algorithms, the Sixth Conference on Artificial Intelligence and Applications, Kaohsiung, Taiwan (2001)
22.
Zurück zum Zitat Mathur, R., Khan, I., Choudhary, V.: Genetic algorithm for dynamic capacitated minimum spanning tree. Int.l J. Comput. Tech. Appl. 4, 404–413 (2013) Mathur, R., Khan, I., Choudhary, V.: Genetic algorithm for dynamic capacitated minimum spanning tree. Int.l J. Comput. Tech. Appl. 4, 404–413 (2013)
23.
Zurück zum Zitat Navarro, G., Paredes, R., Chavez, E.: t-spanners as a data structure for metric space searching. In: International Symposium on String Processing and Information Retrieval, SPIRE. LNCS, vol. 2476, 298–309 (2002) Navarro, G., Paredes, R., Chavez, E.: t-spanners as a data structure for metric space searching. In: International Symposium on String Processing and Information Retrieval, SPIRE. LNCS, vol. 2476, 298–309 (2002)
24.
Zurück zum Zitat Piggott, P., Suraweera, F.: Encoding graphs for genetic algorithms: an investigation using the minimum spanning tree problem. In: Yao X. (ed.) Progress in Evol. Comput. LNAI, vol. 956, pp. 305–314. Springer, New York (1995) Piggott, P., Suraweera, F.: Encoding graphs for genetic algorithms: an investigation using the minimum spanning tree problem. In: Yao X. (ed.) Progress in Evol. Comput. LNAI, vol. 956, pp. 305–314. Springer, New York (1995)
25.
Zurück zum Zitat Raidl, G.R., Julstrom, B.A.: Edge-sets: an effective evolutionary coding of spanning trees, IEEE Trans. Evol. Comput. 7, 225–239 (2003) Raidl, G.R., Julstrom, B.A.: Edge-sets: an effective evolutionary coding of spanning trees, IEEE Trans. Evol. Comput. 7, 225–239 (2003)
26.
Zurück zum Zitat Roeva, O., Fidanova, S., Paprzycki, M.: Influence of the population size on the genetic algorithm performance in case of cultivation process modelling. In: Proceedings of the Federated Conference on Computer Science and Information Systems, pp. 371-376 (2013) Roeva, O., Fidanova, S., Paprzycki, M.: Influence of the population size on the genetic algorithm performance in case of cultivation process modelling. In: Proceedings of the Federated Conference on Computer Science and Information Systems, pp. 371-376 (2013)
27.
Zurück zum Zitat Sigurd, M., Zachariasen, M.: Construction of Minimum-Weight Spanners. Springer, Berlin (2004)CrossRefMATH Sigurd, M., Zachariasen, M.: Construction of Minimum-Weight Spanners. Springer, Berlin (2004)CrossRefMATH
28.
Zurück zum Zitat Tan, Q.P.: A genetic approach for solving minimum routing cost spanning tree problem. Int. J. Mach. Learn. Comput. 2(4), 410–414 (2012)CrossRef Tan, Q.P.: A genetic approach for solving minimum routing cost spanning tree problem. Int. J. Mach. Learn. Comput. 2(4), 410–414 (2012)CrossRef
29.
Zurück zum Zitat Vekaria, K., Clack, C.: Selective Crossover in Genetic Algorithms: An Empirical Study. Lecture Notes in Computer Science, vol. 1498, pp. 438–447. Springer, Berlin (1998) Vekaria, K., Clack, C.: Selective Crossover in Genetic Algorithms: An Empirical Study. Lecture Notes in Computer Science, vol. 1498, pp. 438–447. Springer, Berlin (1998)
30.
Zurück zum Zitat Xiao, B., ZhuGe, Q., Sha, E.H.-M.: Minimum dynamic update for shortest path tree construction, global telecommunications conference, San Antonio, TX, pp. 126-130 (2001) Xiao, B., ZhuGe, Q., Sha, E.H.-M.: Minimum dynamic update for shortest path tree construction, global telecommunications conference, San Antonio, TX, pp. 126-130 (2001)
31.
Zurück zum Zitat Ye We, B., Chao, K.: Spanning Trees and Optimization Problems. Chapman & Hall, Boca Raton (2004)MATH Ye We, B., Chao, K.: Spanning Trees and Optimization Problems. Chapman & Hall, Boca Raton (2004)MATH
Metadaten
Titel
Genetic Algorithms for Constrained Tree Problems
verfasst von
Riham Moharam
Ehab Morsy
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-40132-4_13