?
Экспериментальное исследование временных и точностных характеристик меметического алгоритма решения ассиметричной задачи коммивояжера в зависимости от входных параметров алгоритма
С. 42–44.
Горденко М. К., Коротков Д. А.
В работе рассмотрен меметический алгоритм, являющий-ся комбинацией генетического алгоритма и алгоритмов ло-кального поиска решения ассиметричной задачи коммивоя-жера (A TSP). Приведена математическая постановка задачиA TSP . Кратко описан принцип работы меметического алгорит-ма. Проведено экспериментальное исследование временных и точностных характеристик меметического алгоритма на откры-той базе данных TSPLIB в зависимости от входных параметров с целью выявления оптимальных настроек алгоритма.
Язык:
русский
Ключевые слова: задача коммивояжера
В книге
МИЭМ НИУ ВШЭ, 2018.
Фомичев М. И., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47–54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Добавлено: 22 марта 2020 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Системы компьютерной математики и их приложения 2017 № 18 С. 136–138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Добавлено: 22 марта 2020 г.
Ульянов М. В., Фомичев М. И., Информационные технологии 2019 Т. 25 № 10 С. 590–595
Алгоритм, реализующий метод ветвей и границ, для решения задачи коммивояжера - один из востребованных точных алгоритмов ее решения. Метаэвристические алгоритмы решения этой задачи не гарантируют получения точного решения, но работают "быстро". Для сокращения числа вершин порожденного дерева решений в методе ветвей и границ можно использовать решение, полученное метаэвристическим алгоритмом. За счет выбора метаэвристического алгоритма и ...
Добавлено: 16 февраля 2020 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054–2067
Добавлено: 24 ноября 2019 г.
Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin- Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного ...
Добавлено: 10 ноября 2019 г.
Добавлено: 18 октября 2018 г.
В статье приведены результаты статистического исследования сложности несимметричной задачи коммивояжера (NTSP), полученные в результате обработки специального сгенерированного пула матриц. Основная цель - вероятностной прогноз сложности индивидуальных задач, для больших значений размерности матрицы стоимостей. Показано, что нормальное распределение удовлетворительно приближает распределение логарифма сложности при фиксированной размерности задачи. Построено семейство вероятностных распределений, являющихся удовлетворительными приближениями распределения сложности ...
Добавлено: 16 июля 2018 г.
G. N. Zhukova, M. V. Ulyanov, M. I. Fomichev и др., Automation and Remote Control 2018 Vol. 79 No. 7 P. 1296–1310
Добавлено: 16 июля 2018 г.
Береснева Е. Н., Горденко М. К., Открытые системы. СУБД 2018 № 01 С. 40–42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Добавлено: 22 июня 2018 г.
Горденко М. К., В кн.: Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского.: МИЭМ НИУ ВШЭ, 2018. С. 20–21.
В данной работе рассмотрены алгоритмы ближайшего соседа решения обобщенной задачи коммивояжера в качестве начальной инициализации для алгоритма LKH. Проведено экспериментальное исследование алгоритма LKH с целью сравнительной оценки рациональности полученных решений при различных начальных инициализациях. ...
Добавлено: 5 июня 2018 г.
Maria Gordenko, Sergey Avdoshin, , in: Материалы пятой международной конференции «Актуальные проблемы системной и программной инженерии», сборник научных трудовVol. 1989: CEUR Workshop Proceedings.: M.: HSE, 2017. P. 272–290.
Задачи маршрутизации важны для логистической и транспортной сферы. В основном, задачи маршрутизации связаны с определением оптимального набора маршрутов в мультиграфе. Задача китайского почтальона (CPP) является частным случаем обобщенной задачи маршрутизации, решение которой имеет много потенциальных приложений. В работе приведены варианты CPP. Представлены математические формулировки некоторых задач CPP. Предлагается решить MCPP (NP-турдный случай CPP, определенный на ...
Добавлено: 18 ноября 2017 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Современные информационные технологии и ИТ-образование 2015 Т. 2 № 11 С. 151–159
Сравниваются ресурсные характеристики модифицированного и классического МВГ для TSP. На основании экспериментальных результатов показано, что по величине затраченного на поиск решения времени модифицированный вариант МВГ эффективнее классического. Исследована стохастическая зависимость между временем работы каждого из двух исследуемых вариантов МВГ при фиксированном порядке матрицы стоимостей. Также описана зависимость затраченной памяти и времени работы алгоритма от порядка ...
Добавлено: 9 октября 2017 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., Современные информационные технологии и ИТ-образование 2016 Т. 12 № 3-2 С. 131–137
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности.
<img /> ...
Добавлено: 5 октября 2017 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 7–12
Исследуется сложность индивидуальных задач коммивояжера, т.е. число порожденных вершин поискового дерева в классическом методе ветвей и границ. Вероятностное распределение логарифма сложности аппроксимируется нормальным распределением. На основе экспериментальных данных рассчитаны значения параметров линейного преобразования, обеспечивающих минимальное среднеквадратическое отклонение выборочных квантилей логарифма сложности от соответствующих квантилей стандартного нормального распределения, получена формула зависимости этих параметров от числа вершин ...
Добавлено: 5 октября 2017 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., Автоматизация. Cовременные технологии 2016 № 10 С. 22–29
Рассмотрено новое обобщённое представление для классов индивидуальных задач коммивояжёра - матрица номеров порядка, предназначенное для выделения классов задач, обладающих близкой сложностью. Полученный результат направлен на решение задачи прогнозирования сложности для индивидуальных задач коммивояжёра. Сформулированы две гипотезы относительно мощности предложенного обобщения. Приведены метод получения матрицы номеров порядка и ряд предварительных экспериментальных результатов, не противоречащих одной из ...
Добавлено: 5 октября 2017 г.
M.K. Gordenko, S.M. Avdoshin, Proceedings of the Institute for System Programming of the RAS 2017 Vol. 29 No. 4 P. 107–122
Задачи маршрутизации важны для областей логистики и управления трансортом. Задачи маршрутизации в основном связаны с определением оптимального набора путей в мультиграфе. Задача китайского почтальона (CPP) является особым случаем задачи маршрутизации, имющим много потенциальных приложений. Мы предлагаем решение MCPP (специального NP-полного случая CPP на смешанном мультиграфе) с использованием редуцирования исходной задачи к обобщенной задаче коммивояжера (General ...
Добавлено: 27 сентября 2017 г.
Ульянов М. В., Фомичев М. И., Головешкин В. А. и др., 2017 Т. 13 № 1 С. 19–24
Проведен статистический анализ сложности индивидуальных задач коммивояжера, определяемой как число вершин дерева решений, порожденного алгоритмом ветвей и границ. Получены приближенные представления зависимости параметров вероятностного распределения натурального логарифма сложности от размерности задачи. Линейная зависимость используется для построения оценки сверху квантилей натурального логарифма сложности уровня больше 0.5 и снизу для квантилей уровня меньше 0.5. Нелинейная зависимость параметра ...
Добавлено: 26 сентября 2017 г.
Фомичев М. И., Ульянов М. В., Головешкин В. А. и др., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 131–137
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности. ...
Добавлено: 19 августа 2017 г.
Фомичев М. И., Вестник Волжской государственной академии водного транспорта 2017 № 49 С. 68–78
Классический алгоритм, реализующий метод ветвей и границ для решения задачи коммивояжёра, предложенный в 1963 году Дж. Литл, К. Мурти, Д. Суини и К. Кэрол, остаётся по настоящее время самым востребованным алгоритмом при решении задачи нахождения гамильтонового цикла минимальной стоимости в полном графе. Существует много различных источников, в которых представлен псевдокод алгоритма с текстовыми комментариями. Однако ...
Добавлено: 19 августа 2017 г.
Maria K. Gordenko, Авдошин С. М., International Journal of Open Information Technologies 2017 Vol. 5 No. 6 P. 6–11
Добавлено: 1 июня 2017 г.
Ekaterina N. Beresneva (Chirkova), Sergey M. Avdoshin, International Journal of Open Information Technologies 2017 Vol. 5 No. 5 P. 16–24
Добавлено: 29 мая 2017 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., В кн.: CEUR Workshop ProceedingsVol. 1761: SITITO 2016. Modern Information Technologies and IT-Education. Selected Papers of the XI International Scientific-Practical Conference Modern Information Technologies and IT-Education (SITITO 2016). Moscow, Russia, November 25-26, 2016.: CEUR Workshop Proceedings, 2016. С. 304–310.
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности. ...
Добавлено: 30 марта 2017 г.