Abstract
Uniform sampling in the permutation space is very important for solving permutation problems with NP-hard nature. However, due to the complexity of this space, there is no uniform sampling method for it up to now. In this paper, the description of permutation space and a review of uniform sampling in other space are given. After that, the limitation of the random method for uniform sampling is analyzed, and a k-means clustering algorithm with an improved Borda's method is introduced for sampling based on the above analysis. An extended Latin matrix is defined, and a sampling method based on this matrix that can only solve for a fixed number of sampling is presented. The properties of this method are explored and demonstrated. A uniform sampling method is then proposed for an arbitrary number of sampling points. Experiments are implemented under different sizes of permutation spaces and the results show that the method proposed in this paper has superior performance, which is more than 100 times better than the random method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data availability statements
The datasets generated by the survey research during and/or analyzed during the current study are available in the GitHub repository, https://github.com/54gl/Uniform-Sampling-Method.
References
Aidara, C. (2019). Quasi random resampling designs for multiple frame surveys. Statistica, 79(3), 321–338. https://doi.org/10.6092/issn.1973-2201/8930
Akritidis, L., Alamaniotis, M., & Bozanis, P. (2023). FLAGR: A flexible high-performance library for rank aggregation. SoftwareX, 21, 101319. https://doi.org/10.1016/j.softx.2023.101319
Chong, H. Y., Yap, H. J., Tan, S. C., Yap, K. S., & Wong, S. Y. (2021). Advances of metaheuristic algorithms in training neural networks for industrial applications. Soft Computing, 25(16), 11209–11233. https://doi.org/10.1007/s00500-021-05886-z
Chi, H., Mascagni, M., & Warnock, T. (2005). On the optimal Halton sequence. Mathematics and Computers in Simulation, 70(1), 9–21. https://doi.org/10.1016/j.matcom.2005.03.004
Cicirello, V. A. (2022). On fitness landscape analysis of permutation problems: From distance metrics to mutation operator selection. Mobile Networks and Applications, 1–11. https://doi.org/10.1007/s11036-022-02060-z.
Clément, F., Doerr, C., & Paquete, L. (2022). Star discrepancy subset selection: Problem formulation and efficient approaches for low dimensions. Journal of Complexity, 70, 101645. https://doi.org/10.1016/j.jco.2022.101645
Deshwal, A., Belakaria, S., Doppa, J. R., & Kim, D. H. (2022). Bayesian optimization over permutation spaces. In Proceedings of the AAAI conference on artificial intelligence, 36(6), 6515–6523. https://doi.org/10.1609/aaai.v36i6.20604.
Deza, M. M., & Deza, E. (2009). Encyclopedia of distances (pp. 1–583). Springer.
Fang, K. T., Lin, D. K., Winker, P., & Zhang, Y. (2000). Uniform design: Theory and application. Technometrics, 42(3), 237–248. https://doi.org/10.1080/00401706.2000.10486045
Hafezalkotob, A., Liao, H., & Herrera, F. (2019). An overview of MULTIMOORA for multi-criteria decision-making: Theory, developments, applications, and challenges. Information Fusion, 51, 145–177. https://doi.org/10.1016/j.inffus.2018.12.002
Hassoun, M., Shoval, S., Simchon, E., & Yedidsion, L. (2020). The single line moving target traveling salesman problem with release times. Annals of Operations Research, 289, 449–458. https://doi.org/10.1007/s10479-019-03412-x
Irurozki, E. (2014). Sampling and learning distance-based probability models for permutation spaces (Doctoral dissertation).
Jiao, Y., & Vert, J. P. (2017). The Kendall and Mallows kernels for permutations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(7), 1755–1769. https://doi.org/10.1109/tpami.2017.2719680
Kazimipour, B., Li, X., & Qin, A. K. (2014). A review of population initialization techniques for evolutionary algorithms. CEC 2014 (Institute of Electrical and Electronics Engineers, Beijing), 2585–2592. https://doi.org/10.1109/CEC.2014.6900618.
Li, Q., Liu, S. Y., & Yang, X. S. (2020). Influence of initialization on the performance of metaheuristic optimizers. Applied Soft Computing, 91, 106193. https://doi.org/10.1016/j.asoc.2020.106193
Malan, K. M., & Engelbrecht, A. P. (2013). A survey of techniques for characterising fitness landscapes and some possible ways forward. Information Sciences, 241, 148–163. https://doi.org/10.1016/j.ins.2013.04.015
Maaranen, H., Miettinen, K., & Mäkelä, M. M. (2004). Quasi-random initial population for genetic algorithms. Computers & Mathematics with Applications, 47(12), 1885–1895. https://doi.org/10.1016/j.camwa.2003.07.011
Mattfeld, D. C., Bierwirth, C., & Kopfer, H. (1999). A search space analysis of the job shop scheduling problem. Annals of Operations Research, 86, 441–453. https://doi.org/10.1023/A:1018979424002
Morokoff, W. J., & Caflisch, R. E. (1994). Quasi-random sequences and their discrepancies. SIAM Journal on Scientific Computing, 15(6), 1251–1279. https://doi.org/10.1137/0915077
Orouskhani, M., Shi, D., & Cheng, X. (2020). A fuzzy adaptive dynamic NSGA-II with fuzzy-based borda ranking method and its application to multimedia data analysis. IEEE Transactions on Fuzzy Systems, 29(1), 118–128. https://doi.org/10.1109/TFUZZ.2020.2979119
Pagès, G. (1992). Van der Corput sequences, Kakutani transforms and one-dimensional numerical integration. Journal of Computational and Applied Mathematics, 44(1), 21–39. https://doi.org/10.1016/0377-0427(92)90051-X
Tellache, N. E. H., & Boudhar, M. (2018). Flow shop scheduling problem with conflict graphs. Annals of Operations Research, 261, 339–363. https://doi.org/10.1007/s10479-017-2560-x
Wagner, R. A., & Fischer, M. J. (1974). The string-to-string correction problem. Journal of the ACM, 21(1), 168–173. https://doi.org/10.1145/321796.321811
Funding
This work was supported by the National Key R&D Program of China (No. 2022YFB3302700) and the National Natural Science Foundation of China (No. U21B2029).
Author information
Authors and Affiliations
Contributions
Conceptualization: Lin Gui; Methodology: Lin Gui, Xinyu Li, Qingfu Zhang & Liang Gao; Formal analysis and investigation: Lin Gui; Writing—original draft preparation: Lin Gui; Writing—review and editing: Xinyu Li, Qingfu Zhang & Liang Gao; Funding acquisition: Xinyu Li; Supervision: Xinyu Li, Qingfu Zhang & Liang Gao.
Corresponding author
Ethics declarations
Competing interests
The authors have no competing interests to declare that are relevant to the content of this article.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Gui, L., Li, X., Zhang, Q. et al. A uniform sampling method for permutation space. Ann Oper Res 338, 925–945 (2024). https://doi.org/10.1007/s10479-024-06039-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-024-06039-9