Kratica, Jozef; Kovačević-Vujčić, Vera; Čangalović, Mirjana Computing the metric dimension of graphs by genetic algorithms. (English) Zbl 1191.68469 Comput. Optim. Appl. 44, No. 2, 343-361 (2009). Summary: We consider the NP-hard problem of determining the metric dimension of graphs. We propose a genetic algorithm (GA) that uses the binary encoding and the standard genetic operators adapted to the problem. The feasibility is enforced by repairing the individuals. The overall performance of the GA implementation is improved by a caching technique. Since the metric dimension problem up to now has been considered only theoretically, standard test instances for this problem do not exist. For that reason, we present the results of the computational experience on several sets of test instances for other NP-hard problems: pseudo boolean, crew scheduling and graph coloring. Testing on instances with up to 1534 nodes shows that GA relatively quickly obtains approximate solutions. For smaller instances, GA solutions are compared with CPLEX results. We have also modified our implementation to handle theoretically challenging large-scale classes of hypercubes and Hamming graphs. In this case the presented approach reaches optimal or best known solutions for hypercubes up to 131072 nodes and Hamming graphs up to 4913 nodes. Cited in 12 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects) 68W05 Nonnumerical algorithms 68T05 Learning and adaptive systems in artificial intelligence Keywords:graph theory; metric dimension; evolutionary approach Software:CPLEX; Tabu search; GLOB PDFBibTeX XMLCite \textit{J. Kratica} et al., Comput. Optim. Appl. 44, No. 2, 343--361 (2009; Zbl 1191.68469) Full Text: DOI References: [1] Bäck, T., Fogel, D.B., Michalewicz, Z.: Evolutionary Computation 1: Basic Algorithms and Operators. Institute of Physics Publishing, Bristol (2000) · Zbl 0973.68197 [2] Bäck, T., Fogel, D.B., Michalewicz, Z.: Evolutionary Computation 2: Advanced Algorithms and Operators. Institute of Physics Publishing, Bristol (2000) · Zbl 0973.68197 [3] Beasley, J.E.: Obtaining test problems via internet. J. Glob. Optim. 8, 429–433 (1996). http://www.brunel.ac.uk/depts/ma/research/jeb/orlib · Zbl 0848.90126 [4] Beasley, J.E., Cao, B.: A tree search algorithm for the crew scheduling problem. Eur. J. Oper. Res. 94, 517–526 (1996) · Zbl 0947.90577 [5] Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C.: On the metric dimension of some families of graphs. In: Proc. 7th Internacional Colloquium on Graph Theory–ICGT’05, Hyères, France (2005) · Zbl 1182.05050 [6] Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C., Wood, D.R.: On the metric dimension of graph products. In: Proc. 20th British Combinatorial Conference, Durham, England (2005) · Zbl 1167.05022 [7] Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C., Wood, D.R.: On the metric dimension of Cartesian products of graphs. SIAM J. Discrete Math. 21(2), 423–441 (2007) · Zbl 1139.05314 [8] Chappell, G.G., Gimbel, J., Hartman, C.: Bounds on the metric and partition dimensions of a graph. Manuscript (2003) · Zbl 1224.05133 [9] Chartrand, G., Eroha, L., Johnson, M.A., Oellermann, O.R.: Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math. 105, 99–113 (2000) · Zbl 0958.05042 [10] Chartrand, G., Poisson, C., Zhang, P.: Resolvability and the upper dimension of graphs. Comput. Math. Appl. 39, 19–28 (2000) · Zbl 0953.05021 [11] Currie, J.D., Oellerman, O.R.: The metric dimension and metric independence of a graph. J. Comb. Math. Comb. Comput. 39, 157–167 (2001) · Zbl 0986.05040 [12] Cvetković, D., Hansen, P., Kovačević-Vujčić, V.: On some interconnections between combinatorial optimization and extremal graph theory. Yugosl. J. Oper. Res. 14(2), 147–154 (2004) · Zbl 1274.05239 [13] Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004) · Zbl 1092.90066 [14] Fehr, M., Gosselin, S., Oellermann, O.R.: The metric dimension of Cayley digraphs. Discrete Math. 306(1), 31–41 (2006) · Zbl 1085.05034 [15] Filipović, V.: Fine-grained tournament selection operator in genetic algorithms. Comput. Inform. 22, 143–161 (2003) · Zbl 1076.68609 [16] Filipović, V.: Selection and migration operators and Web services in parallel evolutionary algorithms. Ph.D. thesis, Faculty of Mathematics, University of Belgrade (2006) (in Serbian) [17] Filipović, V., Kratica, J., Tošić, D., Ljubić, I.: Fine grained tournament selection for the simple plant location problem. In: Proceedings of the 5th Online World Conference on Soft Computing Methods in Industrial Applications–WSC5, pp. 152–158 (2000) [18] Fleurent, C., Ferland, J.A.: Genetic and hybrid algorithms for graph coloring. Ann. Oper. Res. 63, 437–461 (1996) · Zbl 0851.90095 [19] Glover, F., Laguna, F.: Tabu Search. Kluwer Academic, Norwell (1997) · Zbl 0930.90083 [20] Hansen, P., Mladenović, N.: Variable neighborhood search: Principles and applications. Eur. J. Oper. Res. 130(3), 449–467 (2001) · Zbl 0981.90063 [21] Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Comb. 2, 191–195 (1976) · Zbl 0349.05118 [22] Hertz, A., Widmer, M.: Guidelines for the use of meta-heuristics in combinatorial optimization. Eur. J. Oper. Res. 151, 247–252 (2003) · Zbl 1053.90053 [23] Hernando, C., Mora, M., Pelayo, I.M., Seara, C., Cáceres, J., Puertas, M.L.: On the metric dimension of some families of graphs. Electron. Notes Discrete Math. 22, 129–133 (2005) · Zbl 1182.05050 [24] Juhos, I., van Hemert, J.I.: Improving graph colouring algorithms and heuristics using a novel representation. In: Lecture Notes in Computer Science, vol. 3906, pp. 123–134. Springer, Berlin (2006) · Zbl 1401.68290 [25] Kennedy, J., Eberhart, R.C., Shi, Y.: Swarm Intelligence. Morgan Kaufmann, San Francisco (2001) [26] Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discrete Appl. Math. 70, 217–229 (1996) · Zbl 0865.68090 [27] Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983). http://citeseer.ist.psu.edu/kirkpatrick83optimization.html · Zbl 1225.90162 [28] Kovačević-Vujčić, V., Mladenović, N., Čangalović, M., Dražić, M.: Continuous variable neighborhood search: comparison with exact methods. Yugosl. J. Oper. Res. (accepted for publication) [29] Kratica, J.: Improving performances of the genetic algorithm by caching. Comput. Artif. Intell. 18, 271–283 (1999) · Zbl 0986.90016 [30] Kratica, J.: Parallelization of genetic algorithms for solving some NP-complete problems. Ph.D. thesis, Faculty of Mathematics, University of Belgrade (2000) (in Serbian) [31] Kratica, J., Stanimirović, Z.: Solving the uncapacitated multiple allocation p-hub center problem by genetic algorithm. Asia-Pacific J. Oper. Res. 24(4), 425–438 (2006) · Zbl 1202.90175 [32] Kratica, J., Stanimirović, Z., Tošić, D., Filipović, V.: Genetic algorithms for solving uncapacitated multiple allocation hub median problem. Comput. Inform. 24, 415–426 (2005) · Zbl 1109.68127 [33] Kratica, J., Stanimirović, Z., Tošić, D., Filipović, V.: Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem. Eur. J. Oper. Res. 182(1), 15–28 (2007) · Zbl 1128.90038 [34] Ljubić, I.: Exact and memetic algorithms for two network design problems. Ph.D. thesis, Institute of Computer Graphics, Vienna University of Technology (2004) [35] Ljubić, I., Raidl, G.R.: A memetic algorithm for minimum-cost vertex-biconnectivity augmentation of graphs. J. Heuristics 9, 401–427 (2003) · Zbl 02184548 [36] Ljubić, I., Weiskircher, R., Pferschy, U., Klau, G.W., Mutzel, P., Fischetti, M.: An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem. Math. Program. Series B 105(2–3), 427–449 (2006) · Zbl 1085.90061 [37] Merz, P.: Advanced fitness landscape analysis and the performance of memetic algorithms. Evol. Comput. 12(3), 303–325 (2004) · Zbl 05412950 [38] Misevicius, A.: A tabu search algorithm for the quadratic assignment problem. Comput. Optim. Appl. 30(1), 95–111 (2005) · Zbl 1130.90041 [39] Mladenović, N., Dražić, M., Kovačević-Vujčić, V., Čangalović, M.: General variable neighborhood search for the continuous optimization. Eur. J. Oper. Res. (2007). doi: 10.1016/j.ejor.2006.12.064 [40] Mondel, S.K., Dey, J.K., Maiti, M.: A single period inventory model of a deteriorating item sold from two shops with shortage via genetic algorithm. Yugosl. J. Oper. Res. 17(1), 75–94 (2007) · Zbl 1265.90017 [41] Moscato, P.: Memetic algorithms. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Applied Optimization, pp. 157–167. Oxford University Press, Oxford (2002) [42] Peters-Fransen, J., Oellermann, O.: The metric dimension of Cartesian products of graphs. Util. Math. 69, 33–41 (2006) · Zbl 1109.05041 [43] Puchinger, J., Raidl, G.R., Pferschy, U.: The core concept for the multidimensional knapsack problem. In: Lecture Notes in Computer Science, vol. 3906, pp. 195–208. Springer, Berlin (2006) · Zbl 1401.90198 [44] Raidl, G.R., Gottlieb, J.: Empirical analysis of locality, heritability and heuristic bias in evolutionary algorithms: a case study for the multidimensional knapsack problem. Evol. Comput. 13(4), 441–475 (2005) · Zbl 05412958 [45] Rochat, Y., Taillard, E.D.: Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1, 147–167 (1995) · Zbl 0857.90032 [46] Saenpholphat, V., Zhang, P.: Connected resolvability of graphs. Czechoslov. Math. J. 53(128), 827–840 (2003) · Zbl 1080.05507 [47] Saenpholphat, V., Zhang, P.: On connected resolving decompositions in graphs. Czechoslov. Math. J. 54(129), 681–696 (2004) · Zbl 1080.05508 [48] Shanmukha, B., Sooryanarayana, B., Harinath, K.S.: Metric dimension of wheels. Far East J. Appl. Math. 8, 217–229 (2002) · Zbl 1032.05044 [49] Stanimirović, Z.: Solving some discrete location problems by using genetic algorithms. Master’s thesis, Faculty of Mathematics, University of Belgrade (2004) (in Serbian) [50] Stanimirović, Z.: An efficient genetic algorithm for the uncapacitated multiple allocation p-hub median problem. Control Cybern. (submitted) · Zbl 1190.90043 [51] Stanimirović, Z., Kratica, J., Dugošija, Dj.: Genetic algorithms for solving the discrete ordered median problem. Eur. J. Oper. Res. 182(3), 983–1001 (2007) · Zbl 1121.90087 [52] Xu, K., Li, W.: Many hard examples in exact phase transitions. Theor. Comp. Sci. 355, 291–302 (2006). http://www.nlsde.buaa.edu.cn/\(\sim\)kexu/benchmarks/pb-benchmarks.htm · Zbl 1088.68163 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.