Abstract
In this paper 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.
Similar content being viewed by others
References
Bäck, T., Fogel, D.B., Michalewicz, Z.: Evolutionary Computation 1: Basic Algorithms and Operators. Institute of Physics Publishing, Bristol (2000)
Bäck, T., Fogel, D.B., Michalewicz, Z.: Evolutionary Computation 2: Advanced Algorithms and Operators. Institute of Physics Publishing, Bristol (2000)
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
Beasley, J.E., Cao, B.: A tree search algorithm for the crew scheduling problem. Eur. J. Oper. Res. 94, 517–526 (1996)
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)
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)
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)
Chappell, G.G., Gimbel, J., Hartman, C.: Bounds on the metric and partition dimensions of a graph. Manuscript (2003)
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)
Chartrand, G., Poisson, C., Zhang, P.: Resolvability and the upper dimension of graphs. Comput. Math. Appl. 39, 19–28 (2000)
Currie, J.D., Oellerman, O.R.: The metric dimension and metric independence of a graph. J. Comb. Math. Comb. Comput. 39, 157–167 (2001)
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)
Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)
Fehr, M., Gosselin, S., Oellermann, O.R.: The metric dimension of Cayley digraphs. Discrete Math. 306(1), 31–41 (2006)
Filipović, V.: Fine-grained tournament selection operator in genetic algorithms. Comput. Inform. 22, 143–161 (2003)
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)
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)
Fleurent, C., Ferland, J.A.: Genetic and hybrid algorithms for graph coloring. Ann. Oper. Res. 63, 437–461 (1996)
Glover, F., Laguna, F.: Tabu Search. Kluwer Academic, Norwell (1997)
Hansen, P., Mladenović, N.: Variable neighborhood search: Principles and applications. Eur. J. Oper. Res. 130(3), 449–467 (2001)
Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Comb. 2, 191–195 (1976)
Hertz, A., Widmer, M.: Guidelines for the use of meta-heuristics in combinatorial optimization. Eur. J. Oper. Res. 151, 247–252 (2003)
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)
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)
Kennedy, J., Eberhart, R.C., Shi, Y.: Swarm Intelligence. Morgan Kaufmann, San Francisco (2001)
Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discrete Appl. Math. 70, 217–229 (1996)
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983). http://citeseer.ist.psu.edu/kirkpatrick83optimization.html
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)
Kratica, J.: Improving performances of the genetic algorithm by caching. Comput. Artif. Intell. 18, 271–283 (1999)
Kratica, J.: Parallelization of genetic algorithms for solving some NP-complete problems. Ph.D. thesis, Faculty of Mathematics, University of Belgrade (2000) (in Serbian)
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)
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)
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)
Ljubić, I.: Exact and memetic algorithms for two network design problems. Ph.D. thesis, Institute of Computer Graphics, Vienna University of Technology (2004)
Ljubić, I., Raidl, G.R.: A memetic algorithm for minimum-cost vertex-biconnectivity augmentation of graphs. J. Heuristics 9, 401–427 (2003)
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)
Merz, P.: Advanced fitness landscape analysis and the performance of memetic algorithms. Evol. Comput. 12(3), 303–325 (2004)
Misevicius, A.: A tabu search algorithm for the quadratic assignment problem. Comput. Optim. Appl. 30(1), 95–111 (2005)
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
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)
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)
Peters-Fransen, J., Oellermann, O.: The metric dimension of Cartesian products of graphs. Util. Math. 69, 33–41 (2006)
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)
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)
Rochat, Y., Taillard, E.D.: Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1, 147–167 (1995)
Saenpholphat, V., Zhang, P.: Connected resolvability of graphs. Czechoslov. Math. J. 53(128), 827–840 (2003)
Saenpholphat, V., Zhang, P.: On connected resolving decompositions in graphs. Czechoslov. Math. J. 54(129), 681–696 (2004)
Shanmukha, B., Sooryanarayana, B., Harinath, K.S.: Metric dimension of wheels. Far East J. Appl. Math. 8, 217–229 (2002)
Stanimirović, Z.: Solving some discrete location problems by using genetic algorithms. Master’s thesis, Faculty of Mathematics, University of Belgrade (2004) (in Serbian)
Stanimirović, Z.: An efficient genetic algorithm for the uncapacitated multiple allocation p-hub median problem. Control Cybern. (submitted)
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)
Xu, K., Li, W.: Many hard examples in exact phase transitions. Theor. Comp. Sci. 355, 291–302 (2006). http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/pb-benchmarks.htm
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partially supported by Serbian Ministry of Science under the grant No. 144015G.
Rights and permissions
About this article
Cite this article
Kratica, J., Kovačević-Vujčić, V. & Čangalović, M. Computing the metric dimension of graphs by genetic algorithms. Comput Optim Appl 44, 343–361 (2009). https://doi.org/10.1007/s10589-007-9154-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-007-9154-5