Об алгоритмах принятия решений в задачах дискретной оптимизации
Аннотация
В статье проводится сравнительный анализ эффективности использования нескольких функций-предикторов, т. е. специальных вспомогательных функций, априорно оценивающих целесообразность выбора разделяющего элемента для некоторого итерационного алгоритма. Рассматриваются случаи одного, двух или трех предикторов, а также различные схемы так называемого голосования, то есть правила выбора решения. Учитывается оценка вероятности принятия правильного решения функцией-предиктором. Приводится качественный результат проведенных исследований с выработкой рекомендации использования предикторов. Сравнительный анализ использования схем, образуемых предикторами в количестве от одного до трех включительно, выполнен детально по принципу «каждый с каждым» с представлением условий предпочтения одной схемы перед другой. Среди всех схем лидирующими были схема из трех предикторов со схемой т. н. голосования по большинству голосов и схема, состоящая из одного предиктора, который является одним из трех в лидирующей схеме и имеет максимальную из трех вероятность принятия правильного решения. Проведена оценка меры области, характеризующей предпочтение одной лидирующей схемы другой. Доказательным путем получено, что схема, состоящая из одного «самого умного» предиктора, имеет более, чем в 24 раза большую область предпочтения, нежели другая лидирующая схема из трех предикторов, голосующих по принципу большинства голосов и имеющих в своем составе «самый умный» предиктор. Процедуры применения функций-предикторов актуальны в методе ветвей и границ. В частности, актуальность данных исследований обусловлена прежде всего необходимостью эффективного решения задач дискретной оптимизации, возникающих в процессе анализа и проектирования сетей связи высоких размерностей. Реальной важной задачей и областью применения исследований является нахождение оптимального множества достраиваемых ребер в графе сети связи, при котором обеспечивается заданная устойчивость по всем направлениям связи. Данный подход может быть распространен и на ситуации, не связанные непосредственно с алгоритмами дискретной оптимизации на графах. В частности, полученные результаты могут использоваться при организации получения экспертного мнения при наличии одного, двух или трех экспертов, обладающих в общем случае различными квалификациями, и возможных схемах принятия ими решения.
Литература
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.
