Розв’язання динамічної задачі комівояжера з використанням поведінкової моделі колонії мурах в багатоагентних системах

Abstract

Дисертація присвячена вирішенню актуального наукового завдання – розв’язанню динамічної задачі комівояжера з використанням поведінкової моделі колонії мурах в багатоагентних системах. Удосконалено метод розв’язання задачі комівояжера, який базується на використанні поведінкової моделі колонії мурах, шляхом зміни початкової установки значень міток та імовірнісного вибору наступного вузла для переходу мурахи-агента, що дозволило зменшити час розв’язання задачі комівояжера. Розроблено метод опрацювання результуючого маршруту при розв’язанні динамічної задачі комівояжера, який базується на використанні алгоритмів локальної оптимізації 2-opt, 2.5-opt, 3-opt в залежності від інтенсивності динамічних змін вхідних даних, що дозволило зменшити вартість результуючих маршрутів. Розроблено метод і отримано експериментальні результати подолання виявлених негативних наслідків нескінченного збільшення значень цифрових міток, який базується на використанні адаптивної верхньої межі значення цифрової мітки, що дозволило розробленій багатоагентній системі відновити пошук маршрутів меншої вартості. Розроблено та апробовано модель багатоагентної системи, яка базується на використанні поведінкової моделі колонії мурах при розміщенні цифрових міток на комунікаційних вузлах, що дозволило розв’язати динамічну асиметричну задачу комівояжера в умовах частково невідомих вхідних даних. Диссертация посвящена разрешению актуальной научной проблемы – решению динамической задачи коммивояжера с использованием поведенческой модели колонии муравьев в многоагентных системах. Усовершенствовано метод решения задачи коммивояжера, который базируется на использовании поведенческой модели колонии муравьев, путем изменения начальной установки значений меток и вероятностного выбора следующего узла для перехода муравья-агента, что позволило уменьшить время нахождения результата задачи коммивояжера. Разработан метод обработки результирующего маршрута при решении динамической задачи коммивояжера, который базируется на использовании алгоритмов локальной оптимизации 2-opt, 2.5-opt, 3-opt в зависимости от интенсивности динамических изменений входящих данных, что позволило уменьшить стоимость результирующих маршрутов. Разработан метод и получено экспериментальные результаты преодоления негативных последствий бесконечного увеличения значений цыфровых меток, который базируется на использовании адаптивной верхней границы значения цыфровой метки, что позволило разработанной многоагентной системе возобновить поиск маршрутов меньшей стоимости. Разработана и апробирована модель многоагентной системы, которая базируется на использовании поведенческой модели колонии муравьев при размещении цифровых меток на коммуникационных, что позволило решить динамическую асимметрическую задачу коммивояжера в условиях частично неизвестных входящих данных. The thesis is devoted to popular scientific task – dynamic travelling salesman problem solving using ant colony behavior model in multiagent systems. In thesis a model of multiagent system was firstly developed, based on applying ant colony behavior model with distributed placement of digital marks on communication nodes, which enables to solve dynamic asymmetric travelling salesman problem in conditions of a partly unknown input data. Classification of existed methods for solving travelling salesman problem of dynamic type was represented, based on it ant colony optimization and local search methods were selected with potential of realization in scope of multiagent systems. Method for solving dynamic travelling salesman problem, which is based on ant colony behavior model was improved by modification of digital marks’ values initialization procedure and procedure of next node selection for movement of ant-agent. Developed improvement of method decreases calculation time. Two models of multiagent systems using ant colony behavior model were developed: 1) for dynamic travelling salesman problem solving using developed modification of base method, where each agent – is separate thread; 2) for dynamic asymmetrical travelling salesman problem in conditions of a partly unknown input data by distributed placement of digital marks on nodes and using developed methods and tools. Investigation of travelling salesman problem parameters was done. Method for travelling salesman problem result route processing was developed, which is based on 2-opt, 2.5-opt and 3-opt local search algorithms, that are used depend on intensity of dynamic changes, such method decreases cost of result routes. Multiagent system for solving dynamic asymmetrical travelling salesman problem in conditions of a partly unknown input data based on applying: developed method to detect and overcome by ant-agent “trap” and “deadlock” critical situations, proposed method of digital marks’ values update during moving of agents by links between nodes, proposed organization of system functionality in mode of union two processes: routes search and data transfer. Developed method to overcome discovered negative effect of endless digital marks’ values augmentation, which is based on adaptive digital mark’s value top limit, enables developed multiagent system recover a search of routes with lower cost even after long term static state of input data. Multiagent system for solving dynamic travelling salesman problem was developed, using ant colony behavior model, technologies of parallel calculations and method of result routes processing; it can output optimal result or quasi-optimal result with difference from optimal less than 2% for symmetrical and asymmetrical travelling salesman problem in less time than existed calculation systems. Method of memory consumption’s calculation for both systems was described, calculated results were represented. Test set of travelling salesman tasks from library were solved, which proves achieved efficiency of developed methods and tools in scope of multiagent systems. Developed system with existed system based on Lin-Kernighan Heuristic method were compared, developed multiagent system demonstrates better results by time required for calculation, which is very important for travelling salesman problem tasks of dynamic type.