RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия высших учебных заведений. Поволжский регион. Физико-математические науки // Архив

Известия высших учебных заведений. Поволжский регион. Физико-математические науки, 2018, выпуск 4, страницы 62–77 (Mi ivpnz139)

Эта публикация цитируется в 1 статье

Математика

Кластеризация ситуаций в алгоритмах решения задачи коммивояжера и ее применение в некоторых прикладных задачах. Часть II. Списочная метрика и некоторые связанные оптимизационные проблемы

Б. Ф. Мельниковa, Е. В. Давыдоваb, Н. В. Ничипорчукa, М. А. Тренинаc

a Российский государственный социальный университет, Москва
b Московский авиационный институт (Государственный технический университет), Москва
c Тольяттинский государственный университет, Тольятти

Аннотация: Актуальность и цели. В задачах дискретной оптимизации мы рассматриваем алгоритмы решения, основанные на расширениях метода ветвей и границ. Сами эти расширения заключаются в совместной работе нескольких вспомогательных эвристических алгоритмов, и они могут быть отнесены к разным, причем независимым друг от друга, областям искусственного интеллекта. Поэтому актуальность исследования обеспечивается как предметными областями, так и алгоритмами - исследованием совместной работы разных вспомогательных алгоритмов, относящихся к различным областям искусственного интеллекта. Целью работы является дальнейшее описание применения кластеризации ситуаций в методе ветвей и границ на примере задачи коммивояжера. Материалы и методы. Применены эвристические алгоритмы искусственного интеллекта и дискретной оптимизации, объединенные в единый программный пакет, а также статистические методы анализа алгоритмов. Результаты. Результатами являются закономерности, полученные при применении кластеризации ситуаций и некоторых других эвристик в методе ветвей и границ при решении задачи коммивояжера. Выводы. Было предложено улучшение алгоритма ветвей и границ с помощью подключения к нему эвристики для кластеризации ситуаций. Кроме того, получены конкретные значения для относительного улучшения среднего времени работы этого алгоритма в рассмотренной нами прикладной задаче, являющейся вариантом задачи коммивояжера, близким к псевдогеометрическому.

Ключевые слова: эвристические алгоритмы, задачи дискретной оптимизации, метод ветвей и границ, кластеризация ситуаций.

УДК: 004.021; 004.023

DOI: 10.21685/2072-3040-2018-4-6



© МИАН, 2024