Clustering of situations in solving applied optimization problems (on the examples of traveling salesman problem and distance matrix recovery)
Boris Feliksovich Melnikov, Anastasia Nichiporchuk, М. А. Тренина, Mikhail Abramyan · International journal of open information technologies · 2019
В задачах дискретной оптимизации мы применяем алгоритмы, основанные на расширениях метода ветвей и границ. Сами эти расширения заключаются в совместной работе нескольких вспомогательных эвристических алгоритмов, они могут быть отнесены к разным, причём независимым друг от друга, областям искусственного интеллекта. Поэтому актуальность рассматриваемых нами задач обеспечивается как предметными областями, так и алгоритмами. В статье мы исследуем возможность применения одного из таких вспомогательных алгоритмов - т.н. кластеризации ситуаций. В качестве предметных областей мы рассматриваем две разные задачи дискретной оптимизации: задачу коммивояжёра в её классической постановке (при этом мы отдаём предпочтение исследованию её частных случаев, полученных для псевдогеометрической версии) и задачу восстановления матрицы расстояний ДНК. В результате вычислительных экспериментов мы получили некоторые закономерности, позволяющие создавать улучшенные версии алгоритма ветвей и границ - с помощью подключения к нему эвристик для кластеризации ситуаций. Результаты, полученные в вычислительных экспериментах, дают обоснование применения кластеризации ситуаций при разработке алгоритмов с помощью метода ветвей и границ. Например, для задачи коммивояжёра такое применение даёт легко наблюдаемые улучшения работы алгоритма -- прежде всего для псевдогеометрического варианта.