Об алгоритмах принятия решений в задачах дискретной оптимизации
Аннотация
Актуальность рассматриваемой предметной области обусловлена необходимостью эффективного решения задач дискретной оптимизации, возникающих в процессе анализа сетей связи высоких размерностей. А именно, в статье исследуются процедуры принятия решений при наличии нескольких функций-предикторов, т.е. специальных очень быстро выполняющихся вспомогательных функций, априорно оценивающих эффективность выбора разделяющего элемента для некоторого итерационного алгоритма. Рассматриваются случаи одного, двух или трех предикторов, а также различные схемы так называемого голосования, то есть выбора одного предиктора из предложенных с оценкой вероятности принятия правильного решения. Приводится качественный результат проведенных исследований с выработкой рекомендации использования предикторов. Данный подход может быть распространен и на ситуации, не связанные непосредственно с алгоритмами дискретной оптимизации. В частности, полученные результаты могут использоваться при организации получения экспертного мнения при наличии одного, двух или трех экспертов, обладающих в общем случае различными квалификациями, и возможных схемах принятия ими решения.
Литература
2. Terentyeva Yu.Yu. Algoritmy rascheta nadezhnosti krupnomasshtabnyh setej svyazi [Algorithms for calculation of reliability of large-scale communication networks]. Informatizatsiya i svyaz' = Informatization and communication. 2021;(6):171-175. (In Russ., abstract in Eng.) https://doi.org/10.34219/2078-8320-2021-12-6-171-175
3. Terentyeva Yu.Yu. Metod polucheniya ocenki nadezhnosti krupnomasshtabnoj seti svyazi s uchetom zavisimyh putej [Method of calculating of large-scale networks reliability estimation allowing for dependent routes]. Informatizatsiya i svyaz' = Informatization and communication. 2017;(1):122-128. (In Russ., abstract in Eng.) EDN: YMHEPR
4. Terentyeva Yu.Yu. Nekotorye teoreticheskie voprosy prakticheskih algoritmov defragmentacii seti svyazi [Some theoretical issues related to the description of practical algorithms for constructing spanning trees]. International Journal of Open Information Technologies. 2021;9(3):23-27. (In Russ., abstract in Eng.) EDN: KRVLTR
5. Terentyeva Yu.Yu., Melnikov B.F. Special Theoretical Issues of Practical Algorithms for Communication Network Defragmentation. In: Silhavy R., Silhavy P. (eds.) Software Engineering Research in System Science. CSOC 2023. Lecture Notes in Networks and Systems. Vol. 722. Cham: Springer; 2023. p. 31-38. https://doi.org/10.1007/978-3-031-35311-6_4
6. Melnikov B.F., Terentyeva Yu.Yu. Greedy and branches-and-boundaries methods for the optimal choice of a subset of vertices in a large communication network. Cybernetics and Physics. 2023;12(1):51-59. https://doi.org/10.35470/2226-4116-2023-12-1-51-59
7. Melnikov B.F., Meshchanin V.Y., Terentyeva Yu.Yu. Implementation of optimality criteria in the design of communication networks. Journal of Physics: Conference Series. Engineering and Innovative Technologies. 2020;1515:042093. https://doi.org/10.1088/1742-6596/1515/4/042093
8. Jamroż L., Raszka J. Scheduling access to common resources in periodic discrete processes. In: 2015 IEEE 2nd International Conference on Cybernetics (CYBCONF). Gdynia, Poland: IEEE Computer Society; 2015. p. 190-195. https://doi.org/10.1109/CYBConf.2015.7175930
9. Werner F. Advances and Novel Approaches in Discrete Optimization. Mathematics. 2020;8(9):1426. https://doi.org/10.3390/math8091426
10. Melnikov B.F., Terentyeva Yu.Yu. O grafovoj modeli dlya zadach reflektometrii i nekotoryh algoritmah ih resheniya. Chast' I. Postanovka zadachi i podhody k algoritmizacii [On a graph model for reflectometry issues and some algorithms for their solution. Part 1. Issue statement and approaches to algorithmics]. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki = University proceedings. Volga region. Physical and mathematical sciences. 2022;(2):28-39. (In Russ., abstract in Eng.) https://doi.org/10.21685/2072-3040-2022-2-3
11. Melnikov B.F., Terentyeva Yu.Yu. O grafovoj modeli dlya zadach reflektometrii i nekotoryh algoritmah ih resheniya. Chast' II. Podhod k programmnoj realizacii [On a graph model for reflectometry issues and some algorithms for their solution. Part 2. An approach to software implementation]. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki = University proceedings. Volga region. Physical and mathematical sciences]. 2022;(3):32-42. (In Russ., abstract in Eng.) https://doi.org/10.21685/2072-3040-2022-3-4
12. Melnikov B.F., Terentyeva Yu.Yu. O grafovoj modeli dlya zadach reflektometrii i nekotoryh algoritmah ih resheniya. Chast' III. Podhod k generacii testovyh dannyh i rezul'taty vychislitel'nyh eksperimentov [On a graph model for reflectometry problems and some algorithms for their solution. Part III. An approach to test data generation and some results of computational experiments]. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki = University proceedings. Volga region. Physical and mathematical sciences]. 2022;(4):31-41. (In Russ., abstract in Eng.) https://doi.org/10.21685/2072-3040-2022-4-3
13. Baumgertner S.V., Melnikov B. F. Obobshchennye nedeterminirovannye konechnye avtomaty [Generalized indeterministic finite automata]. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki = University proceedings. Volga region. Physical and mathematical sciences. 2013;(2):64-74. (In Russ., abstract in Eng.) EDN: RLEENF
14. Melnikov B.F., Tsyganov A. The State Minimization Problem for Nondeterministic Finite Automata: The Parallel Implementation of the Truncated Branch and Bound Method. In: 2012 Fifth International Symposium on Parallel Architectures, Algorithms and Programming. Taipei, Taiwan: IEEE Computer Society; 2012. p. 194-201. https://doi.org/10.1109/PAAP.2012.36
15. Melnikov B., Dudnikov V., Pivneva S. Heuristic Algorithm and Results of Computational Experiments of Solution of Graph Placement Problem. In: Sukhomlin V., Zubareva E. (eds.) Modern Information Technology and IT Education. SITITO 2017. Communications in Computer and Information Science. Vol. 1204. Cham: Springer; 2021. p. 157-166. https://doi.org/10.1007/978-3-030-78273-3_16
16. Melnikov B.F. Heuristics in Programming of Nondeterministic Games. Programming and Computer Software. 2001;27(5):277-288. https://doi.org/10.1023/A:1012345111076
17. Melnikov B.F., Terentyeva Yu.Yu. Development of Large Communication Networks: Optimization Problems and Heuristics. Modern Information Technologies and IT-Education. 2021;17(1):69-79. (In Russ., abstract in Eng.) https://doi.org/10.25559/SITITO.17.202101.727
18. Bulynin A.G., Melnikov B.F., Meshchanin, V.Y., Terentyeva Yu.Yu. Optimizacionnye zadachi, voznikajushhie pri proektirovanii setej svjazi vysokoj razmernosti, i nekotorye jevristicheskie metody ih reshenija [Optimization problem, arising in the development of high-dimensional communication networks, and some heuristic methods for solving them]. Informatizatsiya i svyaz' = Informatization and communication. 2020;(1):34-40. (In Russ., abstract in Eng.) https://doi.org/10.34219/2078-8320-2020-11-1-34-40
19. Tomlinson K., Benson A.R. Choice Set Optimization Under Discrete Choice Models of Group Decisions. In: Daumé III H., Singh A. (eds.) Proceedings of the 37th International Conference on Machine Learning (PMLR). Vol. 119. 2020. p. 1-12. Available at: https://proceedings.mlr.press/v119/tomlinson20a/tomlinson20a.pdf (accessed 26.07.2023).
20. Yukalov V.I., Yukalova E.P. Discrete versus Continuous Algorithms in Dynamics of Affective Decision Making. Algorithms. 2023;16(9):416. https://doi.org/10.3390/a16090416
21. Terentyeva Yu.Yu. Ob optimal'noj skheme organizacii ekspertnoj gruppy s uchetom strategii golosovaniya dlya prinyatiya kollegial'nogo resheniya [On the optimal scheme for organizing an expert group, taking into account the voting strategy for making a collegial decision]. Informatizatsiya i svyaz' = Informatization and communication]. 2014;(4):138-143. (In Russ., abstract in Eng.) EDN: SZQYSD
22. Evertsz R., Thangarajah J., Ly T. Why Model Dynamic Decision Making? In: Practical Modelling of Dynamic Decision Making. SpringerBriefs in Intelligent Systems. Cham: Springer; 2019. p. 1-12. https://doi.org/10.1007/978-3-319-95195-9_1
23. Melnikov B. F., Eyrih S. N. Podhod k kombinirovaniyu nezavershennogo metoda vetvej i granic i algoritma imitacionnoj normalizacii [On the approach to combining truncated branch-and-bound method and simulated annealing]. Vestnik Voronezhskogo gosudarstvennogo universiteta. Serija: Sistemnyj analiz i informacionnye tehnologii = Proceedings of Voronezh State University. Series: Systems Analysis and Information Technologies. 2010;(1):35-38. (In Russ., abstract in Eng.) EDN: MUPYVH
24. Melnikov B.F., Melnikova E.A. On the Classical Version of the Branch and Bound Method. Computer Tools in Education. 2021;(1):21-44. (In Russ., abstract in Eng.) https://doi.org/10.32603/2071-2340-2021-1-21-45
25. Buryak Yu.I., Skrynnikov A.A. Mixed-integer model of information resources security control in the corporate information environment. Vestnik komp'iuternykh i informatsionnykh tekhnologii = Herald of computer and information technologies. 2023;20(3):29-39. (In Russ., abstract in Eng.) https://doi.org/10.14489/vkit.2023.03.pp.029-039
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
