Evolutionary approach to constrained minimum spanning tree problem - commercial software based application

• Autorzy: Pagacz A. , Raidl G. , Zawiślak S.
• Konferencja: Evolutionary Computation and Global Optimization 2006 / National Conference (9 ; 31.05-2.06.2006 ; Murzasichle, Poland)
• Języki publikacji: EN

Abstrakty

EN

The constrained minimum spanning tree problem is considered in the paper. We assume that the degree of any vertex should not exceed a particular constraint d. In this formulation the problem turns into NP-hard one, therefore the evolutionary approach is applicable. The edge set representation of a chromosome was utilized for a tree in the algorithm. The evolutionary algorithm was worked out and the related computer program has been written. Interfaces between the core program and MS Visio as well as the data base system were prepared. The results obtained by means of the system are shown.

Słowa kluczowe

EN

evolutionary computation; evolutionary algorithm; EA; minimum spanning tree; MST; graph theory

PL

obliczenia ewolucyjne; algorytm ewolucyjny; minimalne drzewo rozpinające; teoria grafu

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2006
• Tom: z. 156
• Strony: 331--341
• Opis fizyczny: Bibliogr. 19 poz., tab., rys., wykr.

Twórcy

autor

Pagacz A.

autor

Raidl G.

autor

Zawiślak S.

• Vienna University of Technology, Socrates student 2004/2005; regular since 2005-onwards, Vienna, Austria,

Bibliografia

• [1] Garey M.R., Johnson D.S., Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979.
• [2] Gen M., Kumar A., Kim J.R., Recent network design techniques using evolutionary algorithms, Int. J. of Production Economics, 98, 2006, 251-261.
• [3] Kirshnamoorthy M., Ernst A.T., Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree, Journal of Heuristic, 7, 2001, 587-611.
• [4] Knowles J.D., Corne D.W., A Comparison of Encodings and Algorithms for Multi-objective Minimum Spanning Tree Problems, University of Reading, UK, http://www.rdg.ac.uk/~ssr97jdak
• [5] Lin G-H., Xue G., Steiner problem with minimum number of Steiner points and bounded edge-length, Information Processing Letters, 69, 1999, 53-57.
• [6] Mak B., Blanning R., Ho S., Genetic algorithm in logic tree decision modeling, European Journal of Operation Research, 170, 2006, 597-612.
• [7] Mehlhorn K., Data Structures and algorithms, Vol. II, Graph Algorithms and NP-Completeness, Springer Verlag 1984.
• [8] Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne", PWN, Warszawa 2002.
• [9] Ovalle-Martinez F.J, Stojmenovic I., Garcia-Nocetti F., Solano-Gonzalez J., Finding minimum transmission radii for preserving connectivity and constructing minimal spanning tree in ad hoc and sensor networks, J. Parallel Distrib. Comput., 65, 2005, 132-141.
• [10] Pagacz A., The system of optimal network designing based on evolutionary algorithms, B. Eng.-thesis, University of Bielsko-Biała, Poland, Supervisor (Host University) S. Zawislak, Co-supervisor (SOCRATES placement) G. Raidl (TU Vienna), Bielsko-Biała, Poland, 2005.
• [11] Palmer C.C., Kershenbaum A., "Representing trees in genetic algorithms", in Proceedings of the First IEEE Conference on Evolutionary Computation, David Scharrer, Hans-Paul Schwefel and David B. Fogel, Eds., IEEE Press, 1994, 379-384.
• [12] Raidl G.R., An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem. In C. Fonseca et al., editors, Proceedings of the 2000 IEEE Congress on Evolutionary Computation, IEEE Press, 2000, 104-111.
• [13] Raidl G.R., Drexel C., A Predecessor Coding in an Evolutionary Algorithm for the Capacitated Minimum Spanning Tree Problem, in Late-Breaking-Papers Proc. of the 2000 Genetic and Evolutionary Computation Conference, Las Vegas, NV, July 2000, 309-316.
• [14] Raidl G.R., Julstrom B.A., Edge-sets: An effective evolutionary coding of spanning trees. IEEE Transactions on Evolutionary Computation, 7(3): 2003, 225-239.
• [15] Raidl G.R., Julstrom B.A., Greedy Heuristics and an Evolutionary Algorithm for the Bounded-Diameter Minimum Spanning Tree Problem, in Proc. of the 2003 ACM Symposium on Applied Computing, March 2000, 747-752.
• [16] Rothlauf F., Representations for Genetic and Evolutionary Algorithms, Studies in Fuzziness and Soft Computing, Physica, Heidelberg, 2002.
• [17] Sinclair M.C., Evolutionary Telecommunications: A Summary, Proc. GECCO'99 Workshop on Evolutionary Telecommunications: Past, Present and Future, Orlando, Florida, USA, July 1999, 209-212.
• [18] Xu W.: On the quadratic minimum spanning tree problem. Proceedings of 1995 Japan-China International Workshop on Information Systems, eds. M. Gen and W. Xu, Ashikaga, 1995, 141-148.
• [19] Zhou G., Gen M., An effective genetic algorithm approach to the quadratic minimum spanning tree problem, F. J. Computers Ops Res., Vol. 25 (3), 1998, 229-237.