An Encoding in Metaheuristics for the Minimum Communication Spanning Tree Problem

References

• Berry L. T. M., Murtagh B. A., McMahon G. Applications of a genetic-based algorithm for optimal design of tree-structured communication networks. Proc. Regional Teletraffic Engrg. Conf. Internat. Teletraffic Congress (1995) (Telkom South Africa, Pretoria, South Africa) 361–370Google Scholar
• Caminiti S., Finocchi I., Petreschi R., Farach-Colton M. A unified approach to coding labeled trees. LATIN 2004: Theoretical Informatics, 6th Latin Amer. Sympos. (2004) 2976(Springer, Berlin) 339–348Lecture Notes in Computer ScienceCrossref, Google Scholar
• Chou H., Premkumar G., Chu C.-H. Genetic algorithms for communications network design—An empirical study of the factors that influence performance. IEEE Trans. Evolutionary Comput. (2001) 5:236–249Crossref, Google Scholar
• Cohoon J., Hegde S., Martin W., Richards D. Floorplan design using distributed genetic algorithms. IEEE Internat. Conf. Comp. Aided Design (1988) (IEEE Press, Los Alamitos, CA) 452–455Crossref, Google Scholar
• Ernst A. T., Krishnamoorthy M., Storer R. H. Heuristic and exact algorithms for scheduling aircraft landings. Networks (1999) 34(3):229–241Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman, New York) Google Scholar
• Goldberg D. E.Genetic Algorithms in Search, Optimization, and Machine Learning (1989) (Addison-Wesley, Reading, MA) Google Scholar
• Gottlieb J., Julstrom B. A., Raidl G. R., Rothlauf F. Prüfer numbers: A poor representation of spanning trees for evolutionary search. (2001) . IlliGAL Report 2001001, University of Illinois at Urbana-Champaign, UrbanaGoogle Scholar
• Grefenstette J. J., Gopal R., Rosmaita B. J., Van Gucht D., Grefenstette J. J. Genetic algorithms for the traveling salesman problem. Proc. Internat. Conf. Genetic Algorithms and Their Appl. (1985) (Lawrence Erlbaum Associates, Hillsdale, NJ) 160–168Google Scholar
• Harik G. R., Cantú-Paz E., Goldberg D. E., Miller B. L., Bäck T. The gambler's ruin problem, genetic algorithms, and the sizing of populations. Proc. Fourth Internat. Conf. Evolutionary Comput. (1997) Indianapolis(IEEE Press, New York) 7–12Crossref, Google Scholar
• Holland J. H.Adaptation in Natural and Artificial Systems (1975) (University of Michigan Press, Ann Arbor) Google Scholar
• Hu T. C. Optimum communication spanning trees. SIAM J. Comput. (1974) 3(3):188–195Crossref, Google Scholar
• Kim J. R., Gen M., Angeline P. J., Michalewicz Z., Schoenauer M., Yao X., Zalzala A., Porto W. Genetic algorithm for solving bicriteria network topology design problem. Proc. 1999 IEEE Congress Evolutionary Comput. (1999) (IEEE Press, Los Alamitos, CA) 2272–2279Google Scholar
• Kruskal J. B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. (1956) 7(1):48–50Crossref, Google Scholar
• Li Y., Bouchebaba Y., Fonlupt C., Hao J.-K., Lutton E., Ronald E., Schoenauer M. A new genetic algorithm for the optimal communication spanning tree problem. Proc. Artificial Evolution: Fifth Eur. Conf (1999) 1829(Springer, Berlin) 162–173Lecture Notes in Computer ScienceGoogle Scholar
• Liepins G. E., Vose M. D. Representational issues in genetic optimization. J. Experiment. Theoret. Artificial Intelligence (1990) 2(2):101–115Crossref, Google Scholar
• Mühlenbein H., Schlierkamp-Voosen D. Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization. Evolutionary Comput. (1993) 1(1):25–49Crossref, Google Scholar
• Naphade K. S., Wu S. D., Storer R. H. Problem space search algorithms for resource-constrained project scheduling. Ann. Oper. Res. (1997) 70:307–326Crossref, Google Scholar
• Palmer C. C. An approach to a problem in network design using genetic algorithms. (1994) . Unpublished Ph.D. thesis, Polytechnic University, Troy, NYGoogle Scholar
• Papadimitriou C. H., Yannakakis M. Optimization, approximation, and complexity classes. J. Comput. System Sci. (1991) 43:425–440Crossref, Google Scholar
• Peleg D., Reshef E., Larsen K. G., Skyum S., Winskel G. Deterministic polylog approximation for minimum communication spanning trees. Automata, Languages, and Programming (ICALP'98) (1998) 1443(Springer-Verlag, Berlin) 670–682Lecture Notes in Computer ScienceCrossref, Google Scholar
• Picciotto S. How to encode a tree. (1999) . Ph.D. thesis, University of California, San Diego, San DiegoGoogle Scholar
• Prim R. C. Shortest connection networks and some generalizations. Bell System Tech. J. (1957) 36:1389–1401Crossref, Google Scholar
• Prüfer H. Neuer Beweis eines Satzes Über Permutationen. Arch. Math. Physik (1918) 27:742–744Google Scholar
• Radcliffe N. J., Surry P. D., Whitley L. D., Vose M. D. Fitness variance of formae and performance prediction. Foundations of Genetic Algorithms 3 (1995) (Morgan Kaufmann Publishers, San Mateo, CA) 51–72Crossref, Google Scholar
• Raidl G. R. Various instances of optimal communication spanning tree problems. (2001) February). Personal communicationGoogle Scholar
• Raidl G. R., Julstrom B. A., Carroll J., Damiani E., Haddad H., Oppenheim D. A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem. Proc. 2000 ACM Sympos. Appl. Comput. (2000) (ACM Press, New York) 440–445Crossref, Google Scholar
• Raidl G. R., Julstrom B. A. Edge-sets: An effective evolutionary coding of spanning trees. IEEE Trans. Evolutionary Comput. (2003) 7(3):225–239Crossref, Google Scholar
• Reshef E. Approximating minimum communication cost spanning trees and related problems. (1999) . Master's thesis, Feinberg Graduate School of the Weizmann Institute of Science, Rehovot, IsraelGoogle Scholar
• Rothlauf F. Design of metaheuristics. (2006a) . Habilitationsschrift (Postdoctoral thesis), University of Mannheim, Mannheim, GermanyGoogle Scholar
• Rothlauf F.Representations for Genetic and Evolutionary Algorithms (2006b) 2nd ed.(Springer, Heidelberg, Germany) Crossref, Google Scholar
• Rothlauf F., Goldberg D. E. Redundant representations in evolutionary computation. Evolutionary Comput. (2003) 11(4):381–415Crossref, Google Scholar
• Rothlauf F., Gerstacker J., Heinzl A. On the optimal communication spanning tree problem. (2003) . Technical Report 15/2003, Department of Information Systems, University of Mannheim, Mannheim, GermanyGoogle Scholar
• Rothlauf F., Goldberg D. E., Heinzl A. Network random keys—A tree network representation scheme for genetic and evolutionary algorithms. Evolutionary Comput. (2002) 10(1):75–97Crossref, Google Scholar
• Soak S. M., Corne D. W., Ahn B. H. On a property analysis of representations for spanning tree problems. EA 2005 (2006) 3871(Springer, Berlin) 107–118Lecture Notes in Computer ScienceCrossref, Google Scholar
• Storer R. H., Wu S. D., Vaccari R. New search spaces for sequencing problems with application to job shop scheduling. Management Sci. (1992) 38(10):1495–1509Link, Google Scholar
• Storer R. H., Wu S. D., Vaccari R. Problem and heuristic space search strategies for job shop scheduling. ORSA J. Computing (1995) 7(4):453–467Link, Google Scholar
• Tzschoppe C., Rothlauf F., Pesch H.-J., Deb K., Poli R., Banzhaf W., Beyer H.-G., Burke E., Darwen P., Dasgupta D., et al. The edge-set encoding revisited: On the bias of a direct representation for trees. Proc. Genetic and Evolutionary Comput. Conf. 2004 (2004) 3103(Springer, Heidelberg, Germany) 1174–1185Lecture Notes in Computer ScienceCrossref, Google Scholar