Международный журнал роевого интеллекта и эволюционных вычислений

Абстрактный

Сравнительное исследование методов оптимизации, основанных на рое выдающихся частиц, для решения задачи коммивояжера

Акханд МАХ, Шейх Имран Хоссейн и Шахина Актер

Вычислительные методы, вдохновленные природными явлениями, в последние годы приобрели большой интерес. Среди разработанных алгоритмов оптимизация роя частиц (PSO), имитирующая поведение стаи птиц или косяка рыб, кажется самым известным методом из-за своей простоты и производительности. Вариант ряда методов на основе PSO был разработан для задачи коммивояжера (TSP), самой популярной комбинаторной задачи. Целью исследования является сравнительное исследование нескольких известных методов на основе PSO при решении TSP. Исследование важно, поскольку разные исследователи разработали разные методы на основе PSO и протестировали их на разных наборах задач. Поэтому описание известных методов на основе PSO аналогичным образом раскрывает различные особенности людей. Более того, экспериментальные результаты на общем наборе данных эталонного TSP покажут производительность каждого метода. В этом исследовании методы были протестированы на большом количестве эталонных TSP и результаты сравнены между собой, а также с оптимизацией колонии муравьев (ACO), известным методом решения TSP. Экспериментальные результаты показали, что улучшенный самоосмотрительный PSO (ESTPSO) и скоростной ориентировочный PSO (VTPSO) превзошли ACO; а самоосмотрительный PSO (STPSO) конкурентоспособен с ACO. С другой стороны, экспериментальный анализ показал, что ESTPSO вычислительно тяжелее других, а VTPSO потребовал меньше всего времени для решения контрольной задачи. Объясняются причины, лежащие в основе производительности и временных требований каждого отдельного метода, и VTPSO оказывается наиболее эффективным методом на основе PSO для решения TSP.