Evolutionary design of oriented-tree networks using Cayley-type encodings. (English) Zbl 1180.90036
Summary: This paper introduces the oriented-tree network design problem (OTNDP), a general problem of tree network design with several applications in different fields. We also present several adaptations needed by evolutionary algorithms with Cayley-type encodings to tackle the OTNDP. In particular, we present these adaptations in two Cayley-encodings known as Prüfer and Dandelion codes. We include changes in Cayley-encodings to consider rooted trees. We also show how to use a fixed-length encoding for Cayley codes in evolutionary algorithms, and how to guarantee that the optimal solution is included in the search space. Finally, we present several adaptations of the evolutionary algorithm’s operators to deal with Cayley-encodings for the OTNDP. In the experimental part of the paper, we compare the performance of an evolutionary algorithm (implementing the two Cayley-encodings considered) in several OTNDP instances: first, we test the proposed techniques in randomly generated instances, and second, we tackle a real application of the OTNDP: the optimal design of an interactive voice response system (IVR) in a call center.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
evolutionary algorithms; tree encodings; oriented-tree network design problem; Prüfer encoding; Dandelion codeReferences:
| [1] | Anton, J., The past, present and future of customer access centers, International Journal of Service Industry Management, 11, 2, 120-130 (2000) |
| [2] | Averbakh, I.; Berman, O., Algorithms for path medi-centers of a tree, Computers and Operations Research, 26, 1395-1409 (1999) · Zbl 0967.90064 |
| [3] | Bartholdi, J. J.; Eisenstein, D.; Lim, Y. F., Bucket brigades on in-tree assembly networks, European Journal of Operational Research, 168, 870-879 (2006) · Zbl 1083.90005 |
| [4] | S. Caminiti, E.G. Fusco, R. Petreschi, A bijective code for k-trees with linear time encoding and decoding, in: Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE’07), Hangzhou, China, 7-9 April, 2007.; S. Caminiti, E.G. Fusco, R. Petreschi, A bijective code for k-trees with linear time encoding and decoding, in: Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE’07), Hangzhou, China, 7-9 April, 2007. · Zbl 1176.68057 |
| [5] | Chen, G.; Chen, S.; Guo, W.; Chen, H., The multi-criteria minimum spanning tree problem based genetic algorithm, Information Sciences, 177, 22, 5050-5063 (2007) · Zbl 1121.90127 |
| [6] | Choi, S.; Moon, B., A graph-based Lamarckian-Baldwinian hybrid for the sorting network problem, IEEE Transactions on Evolutionary Computation, 10, 2, 105-114 (2005) |
| [7] | Choudum, S. A.; Indhumathi, R., On embedding subclasses of height-balanced trees in hypercubes, Information Sciences, 179, 9, 1333-1347 (2009) · Zbl 1171.68028 |
| [8] | Eom, C.; Oh, G.; Kim, S., Deterministic factors of stock networks based on cross-correlation in financial market, Physica A: Statistical Mechanics and its Applications, 383, 1, 139-146 (2007) |
| [9] | Fatemi, A.; Zamanifar, K.; NematBakhsh, N., A new genetic approach to construct near-optimal binary search trees, Applied Mathematics and Computation, 190, 2, 1514-1525 (2007) · Zbl 1117.92045 |
| [10] | Goldberg, D. E., Genetic Algorithms in Search Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056 |
| [11] | Guan, J. F.; Yang, H.; Wirasinghe, S. C., Simultaneous optimization of transit line configuration and passenger line assignment, Transportation Research Part B: Methodological, 40, 10, 885-902 (2006) |
| [12] | Latorre, J. M.; Cerisola, S.; Ramos, A., Clustering algorithms for scenario tree generation: application to natural hybro inflows, European Journal of Operational Research, 181, 1339-1353 (2007) · Zbl 1123.90341 |
| [13] | Lecoutre, J. P.; Tassi, P., Statistique Non Parametrique et Robustesse (1987), Economica Press: Economica Press Paris |
| [14] | Lo, C.; Chang, W., A multiobjective hybrid genetic algorithm for the capacitated multipoint network design problem, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 30, 3, 461-470 (2000) |
| [15] | Öncan, T., Design of capacitated minimum spanning tree with uncertain cost and demand parameters, Information Sciences, 177, 20, 4354-4367 (2007) |
| [16] | Paulden, T.; Smith, D. K., From the Dandelion code to the rainbow code: a class of bijective spanning tree representations with linear complexity and bounded locality, IEEE Transactions on Evolutionary Computation, 10, 2, 108-123 (2006) |
| [17] | S. Piccioto, How to Encode a Tree, Ph.D. Dissertation, University of California, San Diego, 1999.; S. Piccioto, How to Encode a Tree, Ph.D. Dissertation, University of California, San Diego, 1999. |
| [18] | F. Rothlauf, D.E. Goldberg, A. Hinzl, Network Random Keys - A Tree Network Representation Scheme for Genetic and Evolutionary Algorithms. IlliGAL Internal Report, No. 2000031, 2000. Available: <http://www.illigal.ge.uiuc.edu>/.; F. Rothlauf, D.E. Goldberg, A. Hinzl, Network Random Keys - A Tree Network Representation Scheme for Genetic and Evolutionary Algorithms. IlliGAL Internal Report, No. 2000031, 2000. Available: <http://www.illigal.ge.uiuc.edu>/. |
| [19] | Sawada, K.; Wilson, R., Models of adding relations to an organization structure of a complete K-ary tree, European Journal of Operational Research, 174, 1491-1500 (2006) · Zbl 1102.90068 |
| [20] | Shioda, S.; Ohtsuka, K.; Sato, T., An efficient network-wide broadcasting based on hop-limited shortest-path trees, Computer Networks, 52, 17, 3284-3295 (2008) · Zbl 1152.68364 |
| [21] | Soak, S.; Corne, D. W.; Ahn, B., The edge-window-decoder representation for tree-based problems, IEEE Transactions on Evolutionary Computation, 10, 2, 124-144 (2006) |
| [22] | Thompson, E.; Paulden, T.; Smith, D. K., The Dandelion code: a new coding of spanning trees for genetic algorithms, IEEE Transactions on Evolutionary Computation, 11, 1, 91-100 (2007) |
| [23] | Urrutia, J., Local solutions for global problems in wireless networks, Journal of Discrete Algorithms, 5, 3, 395-407 (2007) · Zbl 1130.05059 |
| [24] | Wu, B. Y.; Chao, K. M., Spanning Trees and Optimization Problems (2004), Chapman & Hall: Chapman & Hall London, UK · Zbl 1072.90047 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
