Решение задачи коммивояжёра модифицированной моделью Голдберга с использованием поколенческой стратегии при различных эвристиках

ISSN 1560-3644 BULLETIN OF HIGHER EDUCATIONAL INSTITUTIONS. NORTH CAUCASUS REGION. TECHNICAL SCIENCES. 2024. No 1

УПРАВЛЕНИЕ, КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ MANAGEMENT, COMPUTER AND INFORMATION SCIENCES

Научная статья УДК 681.3+681.5

http://dx.doi.org/10.17213/1560-3644-2024-1-5-11

Решение задачи коммивояжёра модифицированной моделью Голдберга с использованием поколенческой стратегии при различных эвристиках

В.Г. Кобак, А.А. Рязанов

Донской государственный технический университет, г. Ростов-на-Дону, Россия

Аннотация. Проведено исследование применения различных модификаций при решении задачи коммивояжёра моделью Голдберга. Данная задача относится к классу NP-полных задач (от англ. non-deterministic polynomial - «недетерминированные с полиномиальным временем») - это класс вычислительных задач, для которых не найден эффективный алгоритм решения. Вычислительный эксперимент проводился на графе размерностью 48 вершин. Алгоритм реализован с использованием путевого представления маршрута в виде хромосомы, для которого используется упорядоченный кроссовер и одноточечная мутация. Для решения задачи коммивояжёра модифицированной моделью Голдберга с использованием различных эвристик разработано программное средство, с помощью которого получены результаты, и на их основе сделан вывод, что наиболее перспективной эвристикой является поколенческая стратегия, использование которой с модифицированной моделью Голдберга дает результаты, более близкие к оптимальным при кратном увеличении времени работы алгоритма.

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

Для цитирования: Кобак В.Г., Рязанов А.А. Решение задачи коммивояжёра модифицированной моделью Голдберга с использованием поколенческой стратегии при различных эвристиках // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2024. № 1. С. 5-11. http://dx.doi.org/10.17213/1560-3644-2024-1-5-11.

Original article

Solution the traveling salesman problem with a modified Goldberg model using a generational strategy for various heuristics

V.G. Kobak, A.A. Ryazanov

Don State Technical University, Rostov-on-Don, Russia

Abstract. The application of various modifications to the solution of the traveling salesman problem by the Goldberg model has been investigated. This problem belongs to the class of NP-complete problems (from non-deterministic polynomial - «non-deterministic with polynomial time») - this is a class of computational problems for which no effective solution algorithm has been found. The computational experiment was conducted on graphs of size 48 vertices. The algorithm was implemented using a path representation of a route in the form of a chromosome, for which an ordered crossover and a single-point mutation are used. A software tool was developed to solve the traveling salesman problem with the modified Goldberg model using various heuristic, with the help of which the results а obtained, and on their basis it concluded that the most promising heuristic is the generational strategy, the use of which with the modified Goldberg model givesresults closer to optimal with a multiple increase in the running time of the algorithm.

© Кобак В.Г., Рязанов А.А., 2024

ISSN 1560-3644 BULLETIN OF HIGHER EDUCATIONAL INSTITUTIONS. NORTH CAUCASUS REGION. TECHNICAL SCIENCES. 2024. No 1

Keywords: travelling salesman problem, genetic algorithm, generational strategy, gene, path representation, crossover, ordered crossover, mutation, single-point mutation

For citation: Kobak V.G., Ryazanov A.A. Solution the traveling salesman problem with a modified Goldberg model using a generational strategy for various heuristics. Izv. vuzov. Sev.-Kavk. region. Techn. nauki=Bulletin of Higher Educational Institutions. North Caucasus Region. Technical Sciences. 2024;(1):5-11. (In Russ.). http://dx.doi.org/10.17213/1560-3644-2024-1-5-11.

Введение

В настоящее время с каждым годом происходит усложнение транспортных систем, непрерывно развивается сфера услуг по доставке, повышается товарооборот, вследствие чего увеличивается интенсивность перевозки товаров, частота пользования услугами доставки и грузоперевозки. Для любой компании актуальны задачи своевременной доставки товаров и услуг, повышения числа потребителей и улучшения функционирования компании в целом. Также без решения данной проблемы не обходятся области, которые связаны с замкнутыми и к тому же зависимыми от времени системами, например, логистические системы, системы планирования, производство микрочипов, капитальный ремонт газотурбинных двигателей, рентгеновская кристаллография, комплектование заказов на складах.

Математическую постановку задачи впервые смогли сформулировать только в XIX веке, а точное решение задачи начали изучать в середине XX века. Задача коммивояжёра является одной из основных задач комбинаторной оптимизации [1]. Решением задачи является нахождение экономичного маршрута, который по одному разу проходит через каждую точку города и обязательно возвращается в ту точку, из которой начал движение. В теории графов такая задача является нахождением кратчайшего га-мильтонова цикла графа [2]. На сегодняшний момент времени для решения этой задачи размерности больше 100 не выявлено алгоритмов, которые дают полиномиальное время. Таким образом, из этого следует, что данная задача относится к классу ^Р-полных [3]. К настоящему времени ученые разных стран не привели никаких твердых математических доказательств, что такого алгоритма в принципе не существует. Исходя из вышеперечисленных положений, решение задачи коммивояжера большой размерности является актуальной задачей.

Длина маршрута, общая стоимость проезда или совокупное время нахождения в пути

может являться показателем рентабельности маршрута. Простейшее точное решение задачи коммивояжера может быть получено перечислением всех возможных вариаций маршрута и выбором кратчайшего из них. Но при этом такое решение задачи означает, что совокупное множество всех допустимых маршрутов будет экспоненциально расти при увеличении общего количества городов. В этом случае, если число городов равно п, то число всех возможных маршрутов будет равно п!. Из теории графов и дискретной математики известно, что число всех различных вариантов решения задачи п! (п-1)!

равно-—

к 2 •п

2

-. Из этих же источников из-

вестно, что к категории трансвычислительных задач [4] относится задача нахождения гамиль-тонова цикла.

Математическая постановка задачи

Задачу коммивояжёра можно представить в виде графа. В таком случае зададим полный взвешенный граф G = (V, Е), где \V | = п - множество вершин (города), |£| = т - множество рёбер (пути между городами). Задана матрица весов W(i,j), i,j е 1,2,...,п, где (1,])-й элемент, который равен весу ребра (расстоянию между вершинами Vi и Vj).

Необходимо найти перестановку ф из элементов множества V, такую, чтобы значение целевой функции было равно [5]:

Fitness (ф)Я(ф(1), ф(п)) +

+ ^{Д(ф(0,ф0 + 1))} ^ min.

i

Метод решения задачи

Исходя из того, что задача коммивояжёра, в которой содержится более 66 городов, при использовании метода перебора всех возможных вариантов будет являться трансвычислительной, то принято решение использовать модификации модели генетического алгоритма Голд-берга, позволяющие найти приближенное к оптимальному значение маршрута за полиноминальное время [6].

ISSN 1560-3644 BULLETIN OF HIGHER EDUCATIONAL INSTITUTIONS. NORTH CAUCASUS REGION. TECHNICAL SCIENCES. 2024. No 1

Механизм работы генетического алгоритма заимствован у живой природы и заключается в имитировании эволюционного процесса, итоговой целью которого является получение решения сложной оптимизационной задачи. Общее описание генетического алгоритма выглядит следующим образом [7]:

1. Формирование начальной популяции.

2. Оценка особей популяции.

3. Отбор (селекция).

4. Скрещивание (оператор кроссинговера).

5. Мутация.

6. Формирование новой популяции.

7. Если популяция не сошлась, то возвращение к пункту 2. Иначе - конец алгоритма.

Модель генетического алгоритма Голд-берга отличается от каноничной наличием турнирного отбора. При турнирном отборе после операции кроссовера производится мутация, после которой худший потомок уничтожается, а оставшийся сравнивается с родительской особью и если он лучше неё, то занимает её место, а если получившийся потомок хуже родительской особи, то он уничтожается.

В используемом алгоритме решения применяются путевое представление маршрута в виде хромосомы [8], упорядоченный кроссовер [9] и одноточечная мутация. Выбор в пользу упорядоченного кроссовера и одноточечной мутации обусловлен ранее полученными результатами проведенных исследований [10, 11]. В статье рассматривается применение различных модификаций данного алгоритма. Будет рассмотрено, как влияет на результат упорядочивание поколений и выбор особи для кроссовера из двух соседних, а также рассмотрено использование поколенческой стратегии в данном алгоритме.

Путевое представление заключается в определении маршрута как списка городов в порядке следования. Например, маршрут 3^5^ будет представлен в виде хромосомы [3, 5, 2, 1, 8, 4, 7, 6, 9].

Для выбранного представления хромосомы используется упорядоченный кроссовер, который заключается во взятии части пути от первого родителя и сохранении родственного порядка городов из второго родителя. Случайным образом выбираются две точки сечения кроссовера. К примеру, Р1 = [1, 2 |3, 4| 5] и Р2 = [1, 3 |2, 5| 4] Каждый элемент, находящийся

между точками сечения кроссовера первого родителя, копируется в ребёнка С = [_, _ |3, 4| _]. После чего, начиная со второй точки сечения кроссовера, элементы второго родителя собираются в список [4, 1, 3, 2, 5]. Далее из полученного списка удаляются города, уже находящиеся в ребёнке [1, 2, 5], а оставшиеся элементы, начиная со второй точки сечения кроссовера, копируются в незаполненные ячейки ребенка С = [2, 5, 3, 4, 1]. Упорядоченный кроссовер изображен на рис. 1.

Рис. 1. Упорядоченный кроссовер Fig. 1. Ordered crossover

Одноточечная мутация заключается в случайном выборе двух городов в хромосоме и заменой мест друг друга. Например, в хромосоме P = [1, 4, 2, 3, 5] первый и третий элементы меняются местами, в результате получаем особь P' [2, 4, 1, 3, 5], что изображено на рис. 2.

Рис. 2. Одноточечная мутация Fig. 2. Single-point mutation

Поколенческая стратегия. В целях улучшения работы алгоритма может быть полезным изменять размер популяции, т.е. производить

ISSN 1560-3644 BULLETIN OF HIGHER EDUCATIONAL INSTITUTIONS. NORTH CAUCASUS REGION.

TECHNICAL SCIENCES. 2024. No 1

генерацию поколений с переменным числом особей. В данной работе в качестве модификации применяются различные схемы поколенче-ской стратегии. Следуя схеме 1-3-5-10, опишем последовательность этапов:

1. Начальное поколение задается количеством особей, равным к

2. Во втором поколении генерируется в три раза больше особей, чем в начальном поколении.

3. В третьем поколении генерируется в пять раз больше особей, чем в начальном поколении.

4. В четвертом поколении генерируется в 10 раз больше особей, чем в начальном поколении.

5. В пятом поколении происходит возврат к исходному количеству особей к.

Процесс продолжается, пока не будет достигнуто заданное значение критерия останова.

Поколенческая стратегия изображена на рис. 3.

Поколение 1

Поколение 2

Поколение 3

Поколение 4

Поколение 5

Рис. 3. Поколенческая стратегия Fig. 3. Generational strategy

Один из исследуемых подходов заключается в упорядочивании поколений по возрастанию длины маршрута. Графически данный подход изображен на рис. 4.

Неупорядоченное поколение

Поколение упорядоченное по возрастанию длины маршрута

Поколение

Особь Длина маршрута

1 30

2 10

3 40

4 60

5 50

6 20

Поколение

Особь Длина маршрута

2 10

6 20

1 30

3 40

5 50

4 60

Рис. 4. Упорядочивание поколения по возрастанию маршрута

Fig. 4. Ordering generation by ascending route

Следующий подход заключается в выборе особей для скрещивания из двух соседних. Графически суть подхода представлена на рис. 5.

Поколение

Особь Длина маршрута

1 30

2 10

3 40

4 60

5 50

6 20

Сосед 1

Особь для скрещивания

Сосед 2

Рис. 5. Выбор особи для скрещивания из двух соседних Fig. 5. Selecting an individual for crossing from two neighboring ones

Вычислительный эксперимент

При решении задачи коммивояжёра модифицированной моделью Голдберга с использований упорядоченного кроссовера, одноточечной мутации и различными модификациями, аналитически не получится определить какие модификации улучшают работу алгоритма.

Для решения поставленной задачи проведено множество вычислительных экспериментов, которые позволили сравнить влияние различных модификаций на результаты работы алгоритма. Входными параметрами являются: n - количество городов; m - количество особей; pc - вероятность кроссовера; pm - вероятность мутации; stop - условие останова; s - количество запусков; scheme - схема поколенческаой стратегии. Для комплексного решения поставленной задачи в виде программы реализованы алгоритмы:

Алгоритм 1 - модифицированная модель Голдберга.

Алгоритм 2 - модифицированная модель Голдберга с упорядочиванием поколений по возрастанию длины маршрута.

Алгоритм 3 - модифицированная модель Голдберга с выбором особи для скрещивания из двух соседних.

Алгоритм 4 - модифицированная модель Голдберга с использованием поколенческой стратегии.

Алгоритм 5 - модифицированная модель Голдберга с использованием поколенческой стратегии и упорядочиванием поколений.

ISSN 1560-3644 BULLETIN OF HIGHER EDUCATIONAL INSTITUTIONS. NORTH CAUCASUS REGION. TECHNICAL SCIENCES. 2024. No 1

Алгоритм 6 - модифицированная модель Голдберга с использованием поколенческой стратегии и выбором особей для скрещивания из двух соседних

Алгоритм реализован в среде разработки Microsoft Visual Studio 2022 на языке программирования C#. Эксперимент проведен на ЭВМ с операционной системой Microsoft Windows 10, процессором Intel i3-6006U 2.0 ГГц и оперативной памятью 4 Гб.

В качестве тестовых графов для осуществления вычислительного эксперимента использованы графы из библиотеки TSP LIB [12] Гей-дельбергского университета.

Входные параметры алгоритма имеют следующее значения: n - различно для каждого графа; m - 300; pc - 1,00; pm - 1,00; stop - 300; s - 100; scheme - различно. Результаты вычислительных экспериментов представлены в табл. 1-3.

Таблица 1 Table 1

Результаты вычислительных экспериментов для графа размерности 48 вершин Results of computational experiments for a graph of size 48 vertices

Алгоритм 1 Алгоритм 2 Алгоритм 3

№ экс. Точное Ср. Ср. Точное Ср. Ср. Точное Ср. Ср.

решение, % решение время, с решение, % решение время, с решение, % решение время, с

1 4 5114,04 12,1 8 5114,49 11.3 1 5222,15 15,3

Таблица 2 Table 2

Результаты вычислительных экспериментов для графов размерности 48 вершин Results of computational experiments for graphs of size 48 vertices

Вариант поколенческой стратегии Алгоритм 4 Алгоритм 5

Точное решение, % Ср. решение Ср. время, с Точное решение, % Ср. решение Ср. время, с

1-3-5 0 5434,69 12,3 0 5436,64 9,4

1-5-10 0 5441,51 20,2 0 5359,29 21,5

1-10-20 1 5385,51 43,8 1 5336,57 40,7

10-20-30 5 5131,6 101,2 2 5153,07 94,4

10-20-40 1 5157,5 103,3 4 5150,03 104,3

10-25-50 6 5151,32 140,8 8 5154,61 148,5

10-20-30-40 7 5124,36 133,1 5 5161,74 127,3

10-20-35-50 6 5140,18 174,5 8 5140,43 135,1

10-20-30-40-50 10 5121,21 205,9 8 5150,08 164,2

Таблица 3 Table 3

Результаты вычислительных экспериментов для графа размерностью 48 вершин Results of computational experiments for graph of size 48 vertices

Вариант поколенческой стратегии Алгоритм 6

Точное решение, % Ср. решение Ср. время, с

1-3-5 0 5690,43 21,1

1-5-10 0 5623,3 33,3

1-10-20 0 5556,84 41,9

10-20-30 0 5276,74 124,1

10-20-40 0 5258,64 106,7

10-25-50 5 5254,12 172,9

10-20-30-40 0 5223,56 145,6

10-20-35-50 1 5242,23 152,8

10-20-30-40-50 2 5180,4 205,1

ISSN 1560-3644 BULLETIN OF HIGHER EDUCATIONAL INSTITUTIONS. NORTH CAUCASUS REGION. TECHNICAL SCIENCES. 2024. No 1

Заключение

Как видно из вычислительных экспериментов, наиболее перспективной эвристикой является поколенческая стратегия, использование которой с модифицированной моделью Голд-берга дает результаты, более близкие к оптимальным при кратном увеличении времени работы алгоритма.

Список источников

1. Задача коммивояжёра [электронный ресурс] URL: https://studfile.net/preview/987700/ (дата обращения: 26.06.2023).

2. Гладков Л.А., КурейчикВ.В., КурейчикВ.М. Генетические алгоритмы: учеб. пособие / под ред. В.М. Курейчика. Ростов н/Д.: Ростиздат, 2004. 400 с.

3. NP-полные и NP-трудные задачи [электронный ресурс] URL:https://studfile.net/preview/5562531/page:42/ (дата обращения: 27.06.2023).

4. Трансвычислительная задача [электронный ресурс] URL: https://studwood.net/1788462/informatika/tran svychislitelnaya_zadacha (дата обращения: 27.06.2023).

5. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: ФИЗМАТ-ЛИТ, 2003. 432 с.

6. Полиномиальное время [электронный ресурс] URL: https://vuzlit.com/745246/polinomialnoe_vremya (дата обращения: 27.06.2023).

7. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: Физматлит, 2006. 320 с.

8. Каширина И.Л. Введение в эволюционное моделирование: учебное пособие / под ред. Е.С. Котляро-вой. Воронеж: Изд-во ВГУ, 2007. 40 с.

9. Оператор кроссинговера [электронный ресурс] URL: https://studfile.net/preview/8889281/page:5/ (дата обращения: 28.06.2023).

10. КобакВ.Г., РязановА.А. Исследование различных мутаций при решении задачи коммивояжера модифицированной моделью Голдберга // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2023. № 1. С. 5-9.

11. Сравнение различных кроссоверов при решении задачи коммивояжера генетическим алгоритмом с путевым представлением [электронный ресурс] URL|: https://elibrary.ru/item.asp?id=50760867 (дата обращения: 28.06.2023).

12. TSP_LIB Ruprecht-Karls-Universitat Heidelberg. [электронный ресурс] URL: http://comopt.ifi.uni-hei delberg.de/software/TSPLIB95/ (дата обращения: 28.06.2023).

References

1. The travelling salesman problem. Available at: https://studiile.net/preview/987700/ (accessed 26.06.2023).

2. Gladkov L.A., Kureichik V.V., Kureichik V.M. Genetic algorithms. Rostov-on-Don: Rostizdat. 2004. 400 p.

3. NP-complete task. Available at: https://studfile.net/preview/5562531/page:42/ (accessed 27.06.2023).

4. Transcomputational problem. Available at: https://studwood.net/1788462/informatika/transvychislitelnaya_ zadacha (accessed 27.06.2023).

5. Emel'yanov V.V., Kureichik V.V., Kureichik V.M. Theory and practice of evolutionary modeling. Moscow: FIZMATLIT. 2003. 432 p.

6. Polynomial time. Available at: https://vuzlit.com/745246/polinomialnoe_vremya (accessed 27.06.2023).

7. Gladkov L.A., Kureychik V.V., Kureychik V.M. Genetic algorithms. Moscow: Fizmatlit. 2006. 320 p.

8. Kashirina I.L. An Introduction to evolutionary simulation: a tutorial. Voronezh: Publ.VGU. 2007. 40 p.

9. Crossover operator. Available at: https://studfile.net/preview/8889281/page:5/ (accessed 28.06.2023).

10. Kobak V.G., Ryazanov A.A. Investigation of the various mutations in the solution of the traveling salesman problem by the modified Goldberg model. Izv. vuzov. Sev.-Kavk. region. Techn. nauki=Bulletin of Higher Educational Institutions. North Caucasus Region. Technical Sciences. 2023;

11. Comparison of different crossovers in solving the traveling salesman problem by a genetic algorithm with path representation. Available at: https://elibrary.ru/item.asp?id=50760867 (accessed 28.06.2023).

12. TSP LIB Ruprecht-Karls-Universitat Heidelberg. Available at: http://comopt.ifi.uni-heidelberg.de/software/ TSPLIB95/ (accessed 28.06.2023).

ISSN 1560-3644 BULLETIN OF HIGHER EDUCATIONAL INSTITUTIONS. NORTH CAUCASUS REGION. TECHNICAL SCIENCES. 2024. No 1

Сведения об авторах

Кобак Валерий Григорьевичв - д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», valera33305@mail.ru

Рязанов Александр Андреянович - магистрант, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем».

Information about the authors

Valeriy G. Kobak- Dr. Sci. (Eng.), Professor, Department «Software of Computer Facilities and Automated Systems», valera33305@mail.ru

Alexander A. Ryazanov - Master Student, Department «Software of Computer Facilities and Automated Systems».

Статья поступила в редакцию / the article was submitted 01.02.2024; одобрена после рецензирования / approved after reviewing 14.02.2024; принята к публикации / acceptedfor publication 20.02.2024.