Довольно много задач, с которыми сталкиваются люди в реальном мире, зависимы друг от друга. Ученые зачастую делят сложные задачи на различные хорошо изученные подзадачи и решают их по-отдельности. Однако не всегда оптимальные решения подзадач дают оптимальное решение исходной задачи. Поэтому представлена задача о воре, являющаяся смешением двух известных подзадач: задачи коммивояжера (Travelling Salesman Problem, TSP) и задачи о ранце (Knapsack Problem, KP). Целью данной работы является ознакомление с задачей о воре, её решение с помощью эволюционного алгоритма, а также выявление зависимостей оптимального решения задачи от решений ее подзадач. В статье рассмотрена постановка задачи, а также представлены её возможные решения с помощью эволюционных алгоритмов.
Абзалтдинов Л.И. (науч. рук. Буздалов М.В.) Эволюционный алгоритм для решения задачи Travelling Thief Problem // Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, [2019]. URL: https://kmu.itmo.ru/digests/article/668