EUVIMEDEUVIMED entdecken
Crossref

Searching in Symmetric Solution Space for Permutation-Related Optimization Problems

Lixin Tang, Tianyang Li, Ying Meng, Jiyin Liu

IEEE Transactions on Pattern Analysis and Machine Intelligence · 2025-08 · 47 (8) · 7036-7052

DOI: 10.1109/tpami.2025.3569284 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025-08. Verfasst von Lixin Tang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 19-mal zitiert (Crossref) und nennt 43 Literaturangaben. Gefördert von: Major Program of National Natural Science Foundation of China, Higher Education Discipline Innovation Project.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Symmetry is a widespread phenomenon in nature. Recognizing symmetry can minimize redundancy to improve computing efficiency. In this paper, we take permutation-related combinatorial optimization problems as a starting point and explore the symmetric structure of its solution space through group theory. From a new perspective of group action, we discover that the meaningful symmetric feature within the solution space is subject to two conditions regarding the form of objective function and the number of objects to be permuted. To exploit the symmetric features, we design a half-solution-space search strategy for various search operators, which are commonly used for permutation-related combinatorial optimization problems. The half-solution-space search strategy can make these operators explore more promising regions without additional computational effort. When the condition of object number for symmetry is unsatisfied, we propose two dimension mapping approaches to construct the symmetric feature, making the half-solution-space search strategy applicable. We evaluate the proposed strategy on three classes of popular 68 benchmark instances, including the single row facility layout problem (SRFLP), traveling salesman problem (TSP), and multi-objective traveling salesman problem (MOTSP). Experimental results show that algorithms embedded with the half-solution-space search strategy can achieve a more competitive performance than those not exploiting the symmetric features.

Förderung

  • Major Program of National Natural Science Foundation of China
  • Higher Education Discipline Innovation Project

Zitieren

APA

Tang, L., Li, T., Meng, Y., & Liu, J. (2025). Searching in Symmetric Solution Space for Permutation-Related Optimization Problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 47(8), 7036-7052. https://doi.org/10.1109/tpami.2025.3569284

Vancouver

Tang L, Li T, Meng Y, Liu J. Searching in Symmetric Solution Space for Permutation-Related Optimization Problems. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2025;47(8):7036-7052. doi:10.1109/tpami.2025.3569284

BibTeX
@article{Tang2025,
  author = {Tang, Lixin and Li, Tianyang and Meng, Ying and Liu, Jiyin},
  title = {Searching in Symmetric Solution Space for Permutation-Related Optimization Problems},
  journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  year = {2025},
  volume = {47},
  number = {8},
  pages = {7036--7052},
  doi = {10.1109/tpami.2025.3569284}
}
Kostenlos starten →