In this paper, we consider the NP-hard problem of finding the metric dimension of graphs. A set of vertices B of a connected graph G = (V, E) resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B. The cardinality of the smallest resolving set of G is the metric dimension of G. The metric dimension problem arises in several different fields, such as robot navigation, telecommunication, and geographical routing protocol. The slime mould algorithm (SMA) is an efficient population-based optimizer based on the oscillation mode of slime mould in nature. The SMA has a specific mathematical model and very competitive results, along with fast convergence for many problems, particularly in real-world cases. SMA has good exploration and exploitation abilities for solving optimization problems. However, complex and high-dimensional SMA may fall into local optimal regions. SA is a very preferable technique among the other heuristic approaches as it provides practical randomness in the search to avoid the local extreme points. However, SA involves a trade-off between computing time and solution sensitivity. The SA is used to enhance the fitness of the best agent if it falls in a suboptimal region, which will lead to the enhancement of all individuals. We solve the problem as integer linear programming and introduce the hybrid algorithm SMA-SA, which combines simulated annealing SA and SMA for determining the metric dimension of graphs. Comparisons were performed on the graphs: k-home chain graph, tadpole graph, alternate triangular snake graph, and mirror graph. Finally, computational results and comparisons with pure SA, SMA, and PSO algorithms confirm the effectiveness of the proposed SMA-SA for solving metric dimension problem.
| Published in | Machine Learning Research (Volume 8, Issue 1) |
| DOI | 10.11648/j.mlr.20230801.12 |
| Page(s) | 9-16 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2024. Published by Science Publishing Group |
Mirror Graph, Metric Dimension, Simulated Annealing Algorithm, Slime Mould Algorithm
| [1] | P. J. Slater, “Leaves of trees,” Congressus Numerantium, vol. 14, pp. 549-559, 1975. |
| [2] | F. Harary and R. A. Melter, “On the metric dimension of a graph,” Ars Combinatoria, vol. 2, pp. 191–195, 1976. |
| [3] | M. R. Garey, Computers and Intractability: A Guide to the Theory of NP-Completeness WH Freeman and Company, New York, 1979. |
| [4] | S. Khuller, B. Raghavachari and A. Rosenfeld, “Landmarks in graphs,” Discrete applied mathematics, vol. 70, no. 3, pp. 217-229, 1996. |
| [5] | Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann et al.,“Network discovery and verification,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 12, pp. 2168-2181, 2006. |
| [6] | K. Liu and N. Abu-Ghazaleh, “Virtual coordinates with backtracking for void traversal in geographic routing,” In International Conference on Ad-Hoc Networks and Wireless, Springer, Berlin, Heidelberg, pp. 46-59, 2006. |
| [7] | H. Faris, A. Z. Ala’M, A. A. Heidari, I. Aljarah, M. Mafarja, et al, “An intelligent system for spam detection and identification of the most relevant features based on evolutionary random weight networks,” Information Fusion, vol. 48, pp. 67-83, 2019. |
| [8] | J. Kratica, V. Kovačević-Vujčić and M. Čangalović, “Computing the metric dimension of graphs by genetic algorithms,” Computational Optimization and Applications, vol. 44, no. 2, pp. 343-361, 2009. |
| [9] | F. Muhammad and L. Susilowati, “Algorithm and computer program to determine metric dimension of graph,” In Journal of Physics: Conference Series, IOP Publishing, vol. 1494, no. 1, pp. 012018, 2020. |
| [10] | N. Mladenović, J. Kratica, V. Kovačević-Vujčić and M. Čangalović, “Variable neighborhood search for metric dimension and minimal doubly resolving set problems,” European Journal of Operational Research, vol. 220 no. 2, pp. 328-337, 2012. |
| [11] | D. T. Murdiansyah,“Computing the metric dimension of hypercube graphs by particle swarm optimization algorithms,” In International Conference on Soft Computing and Data Mining, Springer, Cham, pp. 171-178, 2016. |
| [12] | S. Li, H. Chen, M. Wang, A. A. Heidari and S. Mirjalili, “Slime mould algorithm: A new method for stochastic optimization,” Future Generation Computer Systems, vol. 111, pp. 300-323, 2020. |
| [13] | S. Yin, Q. Luo, Y. Zhou, “EOSMA: an equilibrium optimizer slime mould algorithm for engineering design problems,” Arabian Journal for Science and Engineering, pp. 1-32, 2022. |
| [14] | S. Yin, Q. Luo, Y. Du, Y. Zhou, “DTSMA: Dominant swarm with adaptive t-distribution mutation-based slime mould algorithm,” Mathematical Biosciences and Engineering, vol. 19, no. 3, pp. 2240-2285, 2022. |
| [15] | S. Yin, Q. Luo, G. Zhou, Y. Zhou, B. Zhu, “ An equilibrium optimizer slime mould algorithm for inverse kinematics of the 7-DOF robotic manipulator, ” Scientific Reports; vol. 12, no. 1, pp. 1-28, 2022. |
| [16] | Y. Wei, Y. Zhou, Q. Luo, W. Deng, “Optimal reactive power dispatch using an improved slime mould algorithm, ” Energy Reports, vol. 7, pp. 8742-8759, 2021. |
| [17] | B. Mohamed and M. Amin,"The Metric Dimension of Subdivisions of Lilly Graph, Tadpole Graph and Special Trees", vol. 12, no. 1, pp. 9-14, 2023. |
| [18] | B. Mohamed, L. Mohaisen and M. Amin,"Computing Connected Resolvability of Graphs Using Binary Enhanced Harris Hawks Optimization," Intelligent Automation & Soft Computing, vol. 36, no. 2, 2023. |
| [19] | B. Mohamed, L. Mohaisen and M. Amin," Binary Equilibrium Optimization Algorithm for Computing Connected Domination Metric Dimension Problem," Scientific Programming, 2022. |
| [20] | B. Mohamed and M. Amin,"Domination Number and Secure Resolving Sets in Cyclic Networks,"Applied and Computational Mathematics, vol. 12, no. 2, pp. 42-45, 2023. |
| [21] | R. W. Eglese,"Simulated annealing: a tool for operational research,” European journal of operational research, vol. 46, no. 3, pp. 271-281, 1990. |
| [22] | D. Abramson, "Constructing school timetables using simulated annealing: sequential and parallel algorithms,” Management science, vol. 37, no. 1, pp. 98-113, 1991. |
| [23] | D. Abramson, M. Krishnamoorthy and H. Dang, "Simulated annealing cooling schedules for the school timetabling problem,” Asia Pacific Journal of Operational Research, 16, pp. 1-22, 1999. |
| [24] | E. Poupaert and Y. Deville, "Simulated annealing with estimated temperature,” AI Communications, vol. 13, no. 1, pp. 19-26, 2000. |
| [25] | J. Thompson and K. A. Dowsland, "General cooling schedules for a simulated annealing based timetabling system,” in Proc. ICPTAT, Springer, Berlin, Heidelberg, pp. 345-363, 1995. |
| [26] | B. Mohamed and M. Amin, "A hybrid optimization algorithms for solving metric dimension problem," International Journal on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC), vol. 15, no. 1, 2023. |
| [27] | B. Mohamed,"A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types, International Journal of Theoretical and Applied Mathematics, vol. 9, no. 1, 2023. |
| [28] | B. Mohamed, Metric Dimension of Graphs and its Application to Robotic Navigation, International Journal of Computer Applications, vol. 184, no. 15, 2022. |
APA Style
Basma Mohamed, Mohamed Amin. (2023). Hybridizing Slime Mould Algorithm with Simulated Annealing for Solving Metric Dimension Problem . Machine Learning Research, 8(1), 9-16. https://doi.org/10.11648/j.mlr.20230801.12
ACS Style
Basma Mohamed; Mohamed Amin. Hybridizing Slime Mould Algorithm with Simulated Annealing for Solving Metric Dimension Problem . Mach. Learn. Res. 2023, 8(1), 9-16. doi: 10.11648/j.mlr.20230801.12
AMA Style
Basma Mohamed, Mohamed Amin. Hybridizing Slime Mould Algorithm with Simulated Annealing for Solving Metric Dimension Problem . Mach Learn Res. 2023;8(1):9-16. doi: 10.11648/j.mlr.20230801.12
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.mlr.20230801.12,
author = {Basma Mohamed and Mohamed Amin},
title = {Hybridizing Slime Mould Algorithm with Simulated Annealing for Solving Metric Dimension Problem
},
journal = {Machine Learning Research},
volume = {8},
number = {1},
pages = {9-16},
doi = {10.11648/j.mlr.20230801.12},
url = {https://doi.org/10.11648/j.mlr.20230801.12},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mlr.20230801.12},
abstract = {In this paper, we consider the NP-hard problem of finding the metric dimension of graphs. A set of vertices B of a connected graph G = (V, E) resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B. The cardinality of the smallest resolving set of G is the metric dimension of G. The metric dimension problem arises in several different fields, such as robot navigation, telecommunication, and geographical routing protocol. The slime mould algorithm (SMA) is an efficient population-based optimizer based on the oscillation mode of slime mould in nature. The SMA has a specific mathematical model and very competitive results, along with fast convergence for many problems, particularly in real-world cases. SMA has good exploration and exploitation abilities for solving optimization problems. However, complex and high-dimensional SMA may fall into local optimal regions. SA is a very preferable technique among the other heuristic approaches as it provides practical randomness in the search to avoid the local extreme points. However, SA involves a trade-off between computing time and solution sensitivity. The SA is used to enhance the fitness of the best agent if it falls in a suboptimal region, which will lead to the enhancement of all individuals. We solve the problem as integer linear programming and introduce the hybrid algorithm SMA-SA, which combines simulated annealing SA and SMA for determining the metric dimension of graphs. Comparisons were performed on the graphs: k-home chain graph, tadpole graph, alternate triangular snake graph, and mirror graph. Finally, computational results and comparisons with pure SA, SMA, and PSO algorithms confirm the effectiveness of the proposed SMA-SA for solving metric dimension problem.
},
year = {2023}
}
TY - JOUR T1 - Hybridizing Slime Mould Algorithm with Simulated Annealing for Solving Metric Dimension Problem AU - Basma Mohamed AU - Mohamed Amin Y1 - 2023/10/28 PY - 2023 N1 - https://doi.org/10.11648/j.mlr.20230801.12 DO - 10.11648/j.mlr.20230801.12 T2 - Machine Learning Research JF - Machine Learning Research JO - Machine Learning Research SP - 9 EP - 16 PB - Science Publishing Group SN - 2637-5680 UR - https://doi.org/10.11648/j.mlr.20230801.12 AB - In this paper, we consider the NP-hard problem of finding the metric dimension of graphs. A set of vertices B of a connected graph G = (V, E) resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B. The cardinality of the smallest resolving set of G is the metric dimension of G. The metric dimension problem arises in several different fields, such as robot navigation, telecommunication, and geographical routing protocol. The slime mould algorithm (SMA) is an efficient population-based optimizer based on the oscillation mode of slime mould in nature. The SMA has a specific mathematical model and very competitive results, along with fast convergence for many problems, particularly in real-world cases. SMA has good exploration and exploitation abilities for solving optimization problems. However, complex and high-dimensional SMA may fall into local optimal regions. SA is a very preferable technique among the other heuristic approaches as it provides practical randomness in the search to avoid the local extreme points. However, SA involves a trade-off between computing time and solution sensitivity. The SA is used to enhance the fitness of the best agent if it falls in a suboptimal region, which will lead to the enhancement of all individuals. We solve the problem as integer linear programming and introduce the hybrid algorithm SMA-SA, which combines simulated annealing SA and SMA for determining the metric dimension of graphs. Comparisons were performed on the graphs: k-home chain graph, tadpole graph, alternate triangular snake graph, and mirror graph. Finally, computational results and comparisons with pure SA, SMA, and PSO algorithms confirm the effectiveness of the proposed SMA-SA for solving metric dimension problem. VL - 8 IS - 1 ER -
Email: