Мультиагентное моделирование логистических систем с нечёткими характеристиками тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Кошуняева Надежда Владимировна

• Кошуняева Надежда Владимировна
• кандидат наук
• 2026

Оглавление диссертации кандидат наук Кошуняева Надежда Владимировна

ВВЕДЕНИЕ

ГЛАВА 1 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МОДЕЛИРОВАНИЯ ЛОГИСТИЧЕСКИХ СИСТЕМ НА ОСНОВЕ МУЛЬТИАГЕНТНОГО ПОДХОДА И НЕЧЕТКИХ МНОЖЕСТВ

1.1 Обзор методов моделирования логистических систем

1.2 Мультиагентное моделирование логистических систем

1.3 Классическая задача коммивояжёра

1.4 Особенности моделирования логистических систем

1.5 Проблемы и ограничения на стандартные модели логистических систем

1.6 Нечёткие характеристики в моделировании логистических систем

1.6.1 Нечёткая логика

1.6.2 Оценочные шкалы

1.6.3 Нечеткие множества

1.6.4 Нечеткие числа

ГЛАВА 2 ОПТИМИЗАЦИОННАЯ МОДЕЛЬ ЛОГИСТИЧЕСКИХ СИСТЕМ С НЕЧЁТКИМИ ХАРАКТЕРИСТИКАМИ

2.1 Преимущества моделирования транспортных логистических систем с нечёткими характеристиками

2.2 Формирование матриц корреспонденций экстраполяционными

методами с нечеткими характеристиками

2.3 Ограничения использования классической модели задачи

коммивояжёра в реальных логистических системах

2.4 Математическая модель задачи коммивояжёра с нечеткими числами

2.5 Математическая модель многокритериальной нечёткой задачи

коммивояжёра для арктического судоходства

ГЛАВА 3 ИСПОЛЬЗОВАНИЕ МУЛЬТИАГЕНТНЫХ МЕТОДОВ ДЛЯ

РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ ЛОГИСТИЧЕСКИХ СИСТЕМ

3.1 Сравнительный анализ некоторых алгоритмов для решения классической задачи коммивояжёра

3.1.1 Алгоритм имитации отжига для решения задачи коммивояжёра

3.1.2 Муравьиный алгоритм для решения задачи коммивояжёра

3.1.3 Метод роя частиц для решения задачи коммивояжёра

3.1.4 Сравнение характеристик алгоритма муравьиной колонии и

алгоритма роя частиц

3.2 Разработка мультиагентных методов с нечеткими характеристиками для решения задачи коммивояжёра

3.2.1 Муравьиный алгоритм с нечеткими характеристиками

в задаче коммивояжёра

3.2.2 Алгоритм роя частиц с нечеткими характеристиками

в задаче коммивояжёра

3.2.3 Сравнительная характеристика решения задачи коммивояжёра методом муравьиной колонии и методом роя частиц с нечеткими характеристиками

3.3 Разработка мультиагентных методов с нечеткими характеристиками для

решения нечёткой задачи коммивояжёра

ГЛАВА 4 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ НЕЧЁТКОЙ МОДЕЛИ ЗАДАЧИ КОММИВОЯЖЁРА ДЛЯ ОПТИМИЗАЦИИ ПЕРЕВОЗОК В АРКТИЧЕСКОМ РЕГИОНЕ С ИСПОЛЬЗОВАНИЕМ МУЛЬТИАГЕНТНОГО ПОДХОДА

4.1 Реализация классической задачи коммивояжёра с использованием

нечёткого муравьиного алгоритма для оптимизации маршрутов судов в

Белом море

4.2 Реализация нечёткой задачи коммивояжёра с использованием

нечёткого муравьиного алгоритма для оптимизации маршрутов судов в

Белом море

4.3 Реализация нечёткого муравьиного алгоритма для оптимизации

маршрутов судов в Белом море с дополнительными

ограничениями при необходимости ледокольных проводок

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

Приложение 1 Классификация формулировок задачи коммивояжёра

Приложение 2 Расстояние между основными пунктами и портопунктами

Белого моря в километрах

Приложение 3 Нечёткая матрица расстояний между основными пунктами и портопунктами Белого моря в километрах, построенная по методу

единственного коэффициента роста

Приложение 4 Листинг программы решения задачи коммивояжёра методом

имитации отжига

Приложение 5 Значения стоимостей маршрутов, полученных с использованием алгоритма имитации отжига, при различных начальных

параметрах

Приложение 6 Блок-схема муравьиного алгоритма

Приложение 7 Листинг программы решения задачи коммивояжёра

муравьиным алгоритмом

Приложение 8 Определение наилучших параметров в муравьином алгоритме .. 143 Приложение 9 Листинг программы решения задачи коммивояжёра методом

роя частиц

Приложение 10 Зависимость значения стоимости маршрута от параметров

с1 и с2

Приложение 11 Листинг программы решения задачи коммивояжёра нечётким

муравьиным алгоритмом

Приложение 12 Значения стоимости маршрутов в задаче коммивояжёра с использованием нечёткого муравьиного алгоритма с дефаззификацией по

методу центра тяжести

Приложение 13 Листинг программы решения задачи коммивояжёра нечётким

алгоритмом роя частиц

Приложение 14 Значения стоимости маршрутов в задаче коммивояжёра с использованием нечёткого алгоритма роя частиц с дефаззификацией по

методу центра тяжести

Приложение15 Листинг программы решения задачи коммивояжёра с нечёткими расстояниями нечётким муравьиным алгоритмом

Приложение 16 Листинг программы для решения задачи маршрутизации

судов в Белом море нечётким муравьиным алгоритмом

Приложение 17 Графики сходимости, графы маршрутов, визуализация маршрутов на карте, полученные решением задачи маршрутизации судов в

Белом море нечётким муравьиным алгоритмом

Приложение 18 Схема алгоритма для решения нечёткой задачи

маршрутизации судов в Белом море нечётким муравьиным алгоритмом

Приложение 19 Листинг программы для решения нечёткой задачи

маршрутизации судов в Белом море нечётким муравьиным алгоритмом

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

судов в Белом море нечётким муравьиным алгоритмом

Приложение 21 Листинг программы для решения нечёткой задачи маршрутизации с дополнительными ограничениями для судов в Белом море

нечётким муравьиным алгоритмом

Приложение 22 Акты внедрения

Приложение 23 Свидетельства о регистрации программ для ЭВМ

Введение диссертации (часть автореферата) на тему «Мультиагентное моделирование логистических систем с нечёткими характеристиками»

ВВЕДЕНИЕ

Логистическая система представляет собой сложную систему управления материальными потоками, объектами которой являются промышленные и торговые предприятия, а также территориально-производственные комплексы. Среди логистических систем выделяют производственные, транспортные, складские и другие виды систем.

В рамках данной работы будут рассматриваться логистические системы транспортного типа. К системам такого типа относятся совокупность объектов инфраструктуры и потоки (материальные, финансовые, информационные), предназначенные для распределения товаров, а также управление этими потоками. Учитывая, что в настоящее время объемы транспортных потоков постоянно увеличиваются, необходимы современные методы для мониторинга и анализа данных систем для принятия оптимальных управленческих решений. Ярким примером, иллюстрирующим необходимость учета изменяющихся внешних условий, является ситуация в Арктике. Так, изменение климатических условий в морях Северного Ледовитого океана повлекло за собой ухудшение условий для судоходства на их акваториях [10], что делает необходимым пересмотр значимости факторов природной среды, используемых для моделирования. Это определяет актуальность данного исследования. В работе предложено моделирование логистических систем с использованием модифицированной модели задачи коммивояжёра, основанной на нечёткой логике с решением численным мультиагентным методом, которое является новым в исследуемой области.

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

ный метод является наиболее современным в изучении сложных систем. Построению мультиагентных систем в различных областях посвящено множество работ, среди которых необходимо отметить работы В.А. Виттиха, А.А. Белоусова, А.Б. Шабунина, Н.А. Кузнецова, П.О. Скобелева [9, 43, 42], занимающихся построением многоагентных моделей систем логистических сетей, теоретические исследования мультиагентных систем представлены в работах А.Р. Бахтизина, В.Л. Макарова, Г.Н. Тырина, Е.Д. Сушко [30, 31, 53] и других авторов.

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

Анализ литературы позволил выявить высокий интерес в изучении нечетких систем среди отечественных и зарубежных авторов и коллективов авторов. Так, например, А.Н. Аверкин в [1] описывает применение теории нечетких множеств к различным областям математики и её приложений, а также применение полученных методов нечеткой логики в системах искусственного интеллекта; в [35] коллективом авторов описаны математическое и компьютерное моделирование нечеткости и её применение в различных сферах деятельности; в монографии [11] исследованы вопросы, связанные с проектированием нечетко-логических систем управления, где особое внимание уделено алгоритмам вывода и анализу устойчивости исследуемых систем; в [26] описано применение аппарата нечеткой логики в искусственных нейронных сетях. Изучением нечетких отношений и их применения занимались также такие авторы как Ю.Н. Золотухин, Е.С. Семенкин, А.В. Язенин, J. Casillas, S. Guillaume и другие.

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

коммивояжёра в условиях неопределенности (на примере арктического судоходства), представляет собой новое и перспективное направление исследований, нуждающееся в дальнейшей разработке.

Целью диссертационного исследования является разработка модели логистических систем с нечёткими характеристиками для оптимизации пути перевозки с использованием мультиагентных алгоритмов.

Для достижения поставленной цели определены и решены следующие задачи:

1. Обзор и анализ математических моделей логистических систем транспортного типа.

2. Разработка модели для оптимизации задачи коммивояжёра, основанной на применении нечётких отношений.

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

4. Практическая реализация нечёткой модели задачи коммивояжёра для оптимизации перевозок в Арктическом регионе с использованием мультиагентного подхода.

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

Объектом исследования выбраны логистические системы транспортного

типа.

Предлагаемый математический инструментарий - мультиагентное моделирование, теория нечетких множеств, алгоритмы моделирования логистических систем.

Научная новизна. Автором предложена математическая модель задачи коммивояжёра с нечёткими входными параметрами (временем, стоимостью, расстоянием), формализованная на основе теории нечётких множеств и отношений для оп-

тимизации логистических систем транспортного типа. В отличие от известных детерминированных постановок, в модель впервые введены нечёткие треугольные числа для весов рёбер и параметр «штрафа» за ледокольную проводку. Данная модель позволяет адекватно учитывать неопределённость и стохастичность реальных условий функционирования. Автором выявлено, что мультиагентный подход является наиболее подходящим для решения практических задач анализа логистических систем транспортного типа. В работе разработан и модифицирован комплекс мультиагентных метаэвристических алгоритмов (муравьиной колонии и роя частиц) для решения NP-полной нечёткой задачи коммивояжёра, позволяющих проводить оптимизацию маршрутов в условиях неполноты и неточности исходных данных. В отличие от известных подходов, где данные алгоритмы применяются к детерминированным задачам, в работе впервые предложена их модификация для работы с нечёткими входными данными (расстояниями между пунктами) и нечёткими параметрами самих алгоритмов (а, в, ci, С2). Это позволило снизить критическую зависимость результатов от точной настройки параметров и повысить устойчивость решений в условиях неопределённости. В работе разработан программный комплекс на языке Python, реализующий имитационные модели на основе модифицированных мультиагентных алгоритмов для решения классической и нечёткой задач коммивояжёра, предназначенный для проведения численных экспериментов и анализа результатов в целях оптимизации маршрутов.

Теоретическая значимость заключается в развитии математического аппарата и модификации метаэвристических методов оптимизации для решения NP-трудных комбинаторных задач оптимизации в условиях неопределённости. А именно:

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

2. Получены модификации алгоритмов роевого интеллекта (муравьиного алгоритма и алгоритма роя частиц), адаптированные для работы с нечёткими входными данными, что расширяет область применения этих метаэвристик.

3. Теоретически обоснована и экспериментально подтверждена эффективность применения модифицированных алгоритмов для анализа и оптимизации логистических систем транспортного типа.

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

Методология и методы исследования. Методологическую основу исследования составили принципы мультиагентного моделирования, аппарат теории нечетких множеств и метаэвристические алгоритмы. В работе использованы методы математического и компьютерного моделирования. Программная реализация разработанных нечётких модификаций алгоритмов муравьиной колонии и роя частиц была выполнена на языке программирования Python. Численные эксперименты проведены с использованием специализированных библиотек.

На защиту выносятся следующие положения:

1. Математическая модель задачи коммивояжёра с нечёткими входными параметрами (временем, стоимостью, расстоянием), формализованная на основе теории нечётких множеств для оптимизации логистических систем в условиях неопределённости.

2. Модифицированные мультиагентные алгоритмы (муравьиной колонии и роя частиц) для решения задачи коммивояжёра с нечёткими числами, и результаты их сравнительного анализа.

3. Комплекс программ, разработанных на языке программирования Python, для реализации моделей оптимизации маршрутов арктических морей с учетом специфических факторов, основанных на нечётком муравьином алгоритме, что подтверждается наличием актов о внедрении и свидетельствами о регистрации программы на ЭВМ (Приложения 22 и 23).

Исходя из сказанного, можно утверждать, что тема данного диссертационного исследования является, во-первых, актуальной и, во-вторых, относится к предметной области специальности 1.2.2 «Математическое моделирование, численные методы и комплексы программ» и непосредственно соответствуют пунктам: 7 «Качественные или аналитические методы исследования математических моделей»; 3 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».

Степень достоверности и апробация результатов работы. Основные результаты диссертационной работы были рассмотрены и представлены на многочисленных научных и научно-практических конференциях:

1. «Экономический рост, ресурсозависимость и социальное неравенство»: VI Всероссийская конференция, Санкт-Петербург, 2018 г.

2. «Модели развития малого и среднего предпринимательства в условиях Арктики»: Всероссийская (с международным участием) молодежная научно-практическая конференция Сыктывкар - СГУ им. Питирима Сорокина, 2019 г.

3. «Фундаментальные и прикладные проблемы эффективности научных исследований и пути их решения»: Международная научно-практическая конференция, Уфа, 2021 г.

4. «Российская наука в современном мире»: XXXV международная научно-практическая конференция, Москва, 2021 г.

5. III Международная научная конференция «Приоритетные направления инновационной деятельности в промышленности», Казань, 2021 г.

6. VI Международная научно-практическая конференция «Инновационные аспекты развития науки и техники», Саратов, 2021 г.

7. Международная конференция «Чтения Ушинского», Ярославль, 2021 г.

8. XXIV Всероссийский симпозиум «Стратегическое планирование и развитие предприятий», Москва, 2023 г.

9. IV Международная научно-практическая конференция «Формирование транспортных систем и социально-экономическое развитие городских агломераций», Санкт-Петербург, 2024 г.

10. «II Лавёровские чтения - Арктика: актуальные проблемы и вызовы», Архангельск, 2024 г.

11. IX Международная научно-практическая интернет-конференция «Проблемы экономического роста и устойчивости развития территорий», Вологда, 2024 г.

12. Всероссийская научно-практическая конференция МИКМО, Симферополь, 2024, 2025 г.г.

13. XXIV Международная научно-практическая конференция «Логистика: Современные тенденции развития», Санкт-Петербург, 2025 г.

14. III форум «Арктика-Регионы», Архангельск, 2025 г.

15. Научно-методологический семинар «Исследования социальных и экономических систем» Института социально-экономических и биоресурсных исследований ФГБУН ФИЦКИА УрО РАН, Архангельск, 2025 г.

Работа выполнена в рамках государственного задания лаборатории проблем развития территорий по теме НИР «Теоретико-методологические основы комплексного управления ресурсами развития территорий в современных условиях (на примере западной части Арктической зоны Российской Федерации)».

По теме исследования опубликовано 18 научных работ, в том числе 4 в изданиях из списка Высшей аттестационной комиссии Российской Федерации.

Структура и объем работы. Диссертационная работа состоит из введения, четырёх глав, заключения, перечня литературы из 121 источника, 23 приложений, имеет в своем составе 23 рисунка и 10 таблиц. Полный объем работы составляет 211 листов машинописного текста.

ГЛАВА 1 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МОДЕЛИРОВАНИЯ ЛОГИСТИЧЕСКИХ СИСТЕМ НА ОСНОВЕ МУЛЬТИАГЕНТНОГО ПОДХОДА И НЕЧЕТКИХ МНОЖЕСТВ

В данной главе представлен анализ методов моделирования логистических систем транспортного типа. Рассмотрены три ключевых подхода: аналитический, численный и имитационный. Проведено сравнение их возможностей, ограничений и области применения. Определены особенности и проблемы, возникающие при моделировании логистических систем. На основании проведённого исследования установлено, что для моделирования сложных систем, характеризующихся нелинейными взаимосвязями и динамичностью процессов, наиболее эффективными являются имитационные методы, обладающие возможностью учёта большого числа переменных и гибкостью при воспроизведении реальных сценариев. Дополнительно рассмотрено применение теории нечётких множеств для формализации факторов, оказывающих влияние на систему, но трудно поддающихся точной количественной оценке. Использование нечётких чисел позволяет повысить адекватность модели в условиях неполноты или неточности исходных данных.

1.1 Обзор методов моделирования логистических систем

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

Системный анализ служит теоретической базой для моделирования сложных систем. Его ключевые этапы включают:

- выбор значимых параметров - определение внутренних характеристик системы;

- формирование базы данных - сбор и структурирование информации;

- анализ взаимосвязей - изучение взаимодействий между элементами и подсистемами;

- определение целевой функции - разработка критериев для оптимизации управления.

Моделью системы является её упрощённое представление, которое должно отвечать ключевым требованиям:

- адекватность и точность (соответствие модели реальной системе, проверяемое через верификацию путём расчёта отклонений результатов моделирования от эталонных значений);

- соответствие конкретной задаче (при построении модели важно учитывать специфику решаемой проблемы);

- баланс сложности и простоты (компромисс между детализацией и управляемостью);

- модульность (использование готовых блоков для ускорения разработки и повышения надёжности модели за счёт проверенных решений);

- учёт неопределённости (необходим для большинства реальных систем, являющихся стохастическими);

- масштабируемость (возможность расширения функционала, повышения точности и адаптации к новым условиям).

Методы моделирования классифицируются по способу представления и анализа системы. Одна из общепринятых классификаций выделяет три основных подхода: аналитический, численный и имитационный. Анализ литературных источников позволил выделить особенности каждого из трёх видов моделирования, представленные в таблице 1.

Таблица 1 - Сравнительная характеристика методов моделирования

Название Содержание метода

метода Преимущества Недостатки

Составляются уравне- - Получение точных - Применим только к

« к ния или системы урав- значений оценивае- простым системам;

о е нений, через решение мых параметров. - не дает адекватных

ЕТ К которых определяются моделей для слож-

т и ч системные параметры. ных систем;

а н - сложности с разре-

^ шимостью уравнений и систем.

Метод обеспечивает - Позволяют получить - Невозможность по-

решение заранее сфор- решения с определен- лучения точных па-

мированных уравне- ной точностью; раметрических оце-

35 ний/систем уравнений - круг решаемых задач нок;

с определенной точно- значительно шире, - ограниченность при-

н н и ч о стью посредством ап- чем для аналитиче- менения для слабо

проксимационных под- ских методов. формализуемых си-

и ^ ходов, включая преобразование непрерывных моделей в дискретные. стем.

Метод основывается на - Учитывает динамику - Сложность в оценке

проведении виртуаль- и стохастический ха- точности получен-

ных экспериментов с рактер системы; ных значений пара-

системой с соблюде- - является экономич- метров.

35 нием временных про- ным и безрисковым

нО н н порций. В процессе мо- способом исследова-

о делирования оценива- ния системы;

к

ст а т ются исследуемые па- - отслеживает процесс

и в течение всего мо-

м раметры.

К дельного времени; - применим даже при отсутствии строгой математической формализации.

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

Имитационное моделирование формализуется как система правил, определяющих поведение объекта исследования в дискретные моменты времени. Реализация может осуществляться посредством сетевых, автоматных или других дискретных структур. Многократное исполнение модели с последующей статистической обработкой результатов обеспечивает получение достоверных оценок параметров системы, что делает данный метод незаменимым инструментом для анализа и оптимизации сложных динамических систем. В современной практике сформировались три ключевых метода имитационного моделирования: системная динамика для анализа непрерывных процессов, дискретно-событийное моделирование (включая теорию массового обслуживания) и мультиагентное моделирование, изучающее взаимодействие интеллектуальных агентов.

Самый высокий уровень абстракции присущ системной динамике, где отдельные элементы системы заменяются их агрегатами. Основоположником данного подхода является Джей Форрестер. Изначальная цель метода была показать, как организационная структура, усиления и задержки (в принятии решений и действиях) взаимодействуют, влияя на успешность предприятия [55]. Указанный подход позволяет получить общее представление о процессе функционирования системы, отбрасывая при этом мелкие детали. Данный метод принимается для долговременного стратегического планирования стохастических систем и рассматривается в работах многих авторов. Так, например, Ярыгин О.Н. и Костылев А.А. в [66] описывают системную динамику как метод управления систем с нелинейными и обратными связями. А также указывают на необходимость изучения и применения указанного метода в управленческой деятельности специалистов в различных областях.

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

простоям обслуживающих каналов. Задача моделирования таких систем сводится к нахождению оптимального баланса между временем ожидания клиентов и коэффициентом загрузки обслуживающих каналов [13]. Идеальное решение должно минимизировать как очереди, так и простои, обеспечивая эффективное функционирование системы в целом.

Мультиагентное моделирование изучает поведение сложных систем через взаимодействие их элементов, а не через агрегированные показатели. Этот подход реализует принцип «снизу-вверх», то есть построение модели производится на основе наблюдений за поведением агентов и их взаимодействий между собой и средой. Взаимодействие агентов порождает эмерджентные свойства системы. При этом не существует универсального алгоритма - моделировщик должен индивидуально изучать особенности системы, поведение агентов и внешние факторы.

Чаще всего мультиагентные модели имеют следующие составные части:

- агенты, наделенные определенными свойствами;

- правила, которым придерживаются агенты для принятия индивидуальных решений;

- внешняя среда;

- общие правила для реализации.

Агенты в зависимости от уровня интеллекта и способа поведения подразделяются на несколько видов:

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

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

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

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

- Эмоционально-мотивированные агенты. Наиболее сложный тип, включающий эмоциональные состояния и психологические характеристики. Эти агенты максимально приближены к моделированию человеческого поведения.

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

- сбор информации и накапливание знаний о среде;

- взаимодействие с другими агентами;

- адаптивный выбор целевой функции;

- подбор оптимальной стратегии из имеющегося набора.

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

Общий алгоритм поведения агента представлен на рисунке 1. В результате анализа литературных источников [13, 55, 66, 67] были выделены особенности подходов в моделировании систем имитационными методами, представленные в таблице 2.

нет

Sensor - сигналы из внешней среды

Perception - идентификация ситуации

*

Behavior 1 - рефлексивное поведение агента для выживания

Behavior 2 - «осмысленное» принятие решений для достижения цели

Останов или выбор следующей цели

Рисунок 1 - Алгоритм поведения любого интеллектуального агента.

Таблица 2 - Сравнительная характеристика методов имитационного моделирования

Системная динамика Дискретно-событийное моделирование Мультиагентное моделирование

Основные элементы модели Петля обратной связи Заявки, каналы обслуживания Агенты

Уровень абстракции Высокий Средний Низкий

Направление моделирования Сверху вниз Сверху вниз Снизу вверх

Список литературы диссертационного исследования кандидат наук Кошуняева Надежда Владимировна, 2026 год

х - с.

, если х £ [си а]

, если х £ [а, сг] 0, в противном случае

г

(19)

Результатом сложения, вычитания, умножения или деления нечетких чисел будет тройка чисел, где каждое число в этой тройке равно сумме, разности, произведению или делению соответствующих элементов заданных случайных чисел соответственно.

Одной из разновидностей экстраполяционных методов, предназначенных для формирования матрицы корреспонденций, является метод единственного коэффициента роста. Фактическое расстояние между пунктами или время прохождения этих расстояний указывают как исходные данные. На практике расстояния и время их прохождения могут изменяться. Так, например, в зависимости от времени суток ситуация на дорогах может кардинально меняться, поэтому возникает необходимость прогнозирования загрузки элементов сети [7]. Временные задержки из-за пробок могут значительно увеличить время в пути между городами в определенные часы. Для морского транспорта, в особенности для арктического региона, природные условия являются определяющим фактором в изменении длины маршрута и времени его прохождения. Изменение ледового покрытия может блокировать одни маршруты и открывать другие, может изменять длину маршрута, а также влиять на скорость движения судов. Морские течения могут, как помогать, так и мешать движению судов, влияя на время в пути и расход топлива. В таких ситуациях кратчайший путь между пунктами не всегда будет самым оптимальным и даже не всегда возможным (особенно в условиях Арктики). В матрицах корреспонденций прогнозируется изменение весов рёбер, выражающих расстояния между пунктами или время прохождения этих расстояний.

Прогноз коэффициента изменения чаще всего устанавливается экспертами, поэтому присутствует некоторая субъективность в определении данного параметра. Коэффициент роста представим в виде нечеткого числа с треугольной функцией принадлежности.

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

экономических факторов, могут оказывать существенное влияние временные факторы, такие как погодные условия (в случае морского транспорта в Арктике), влияющие на скорость и доступность маршрутов, или время суток (в случае наземного транспорта), определяющее уровень загруженности дорог.

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

Матрица корреспонденций между N транспортными узлами АА2,..., Ам со значениями, выраженными треугольными нечёткими числами, в начальный момент времени, выглядит следующим образом:

А1 А2 . • • Ам Р

А1 - Р? 2 р1N N !р?/ }=1

А2 Р? 1 - Р20N N 1Р2> } = 1

... -

Ам рт Р?М2 - N }=1

Р0 N 1Р?1 ¿ = 1 N =1 N =1 р? = (р0,р2,р?)

В данной матрице каждый элемент р? представляет собой нечёткое число с треугольной функцией распределения, то есть

Р? = (а?;, Ьф ф, 1 = 1.....N,7 = 1.....N (20)

Элементы матрицы в правом столбце и нижней строке представляют собой суммы значений по строке и по столбцу соответственно и определяются согласно правилам сложения и умножения треугольных чисел.

N

£ Р0 = (а°12> Ь02> с?2) + -+ (а0ю Ь0Ю с0т )

}=1

N

£ PNi = (а^1' ^1' Ст) + + №N(N-1)' ^N(N-1)' ^(N-1)) ] = 1

N

£ Р01 = (а01, Ь2^ с01) + -+ (ааЬ01' сЪ)

=1

N

У£Рш = (аш' ' + + (а1N-1)N'b(N-1)N'C(N-1)N)

=1

N N

р1 = ££р11 (22)

=1 =1

Обозначим общий объем прогнозных корреспонденций за Р* = (Р*, Р*, Рз).Тогда расчет коэффициента роста будет производиться по формуле:

Р* (Р* Р* Рз\ К = (к±, к2,к3)=^=№,?1,!Щ) (23)

р1 \Р0 Р2 Ръ)

Для построения матрицы прогнозных корреспонденций воспользуемся формулой:

р*=К ^0,1 = 1.....М,] = 1.....N (24)

Таким образом, все элементы прогнозной матрицы также будут представлять собой нечеткие треугольные числа.

Для практического определения расстояний между выбранными портами и портопунктами Белого моря в разные периоды навигации рассмотрим применение метода единственного коэффициента роста.

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

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

Для примера были рассмотрены три порта Белого моря, расстояния между которым получены по данным, представленным компанией АО «Белфрахт». Данные расстояния в километрах представлены в таблице 4.

Таблица 4 - Расстояния между некоторыми пунктами Белого моря (в км)

Архангельск Мезень Онега

Архангельск - 226 224

Мезень 226 - 328

Онега 224 328 -

Для отображения возможного увеличения расстояния из-за погодных и сезонных условий расстояние между каждым из пунктов было представлено как нечёткое число с треугольной функцией принадлежности, где левая границы задана значением из таблицы расстояний по данным АО «Белфрахт», мода - увеличением значения из таблицы на случайное значение от 5% до 10%, и правая - увеличением значения из таблицы на случайное значение от 15% до 20%.

Прогнозный объем корреспонденций представим в виде треугольного нечёткого числа, у которого мода будет увеличена на 5% по сравнению с первоначальным объемом корреспонденций, левая граница останется, как у первоначального объема, а правая граница будет увеличена на 10% от первоначального объема кор-респонденций. В данном случае предполагается, что все расстояния могут быть увеличены из-за погодных условий. Коэффициент роста будет равен К = (1,1.05,1.1). Полученная матрица корреспонденций для трёх рассматриваемых пунктов представлена в таблице 5.

Таблица 5 - Нечёткие расстояния между некоторыми пунктами Белого моря (в км)

Архангельск Мезень Онега

Архангельск - (226.0, 257.0,293.1) (224.0, 257.8, 290.5)

Мезень (226.0, 257.0,293.1) - (328.0, 366.1, 427.0)

Онега (224.0, 257.8, 290.5) (328.0, 366.1, 427.0) -

Полная матрица расстояний в километрах (по данным компании АО «Бел-фрахт») между 25 портами и портопунктами Белого моря и полученная матрица корреспонденций с нечёткими расстояниями представлены в Приложениях 2 и 3 соответственно.

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

(Р!ь р'а Р'Л к_р;_ (Р'ц Р'п Р]з\ „

где Р®, Р® - объемы фактических корреспонденций в /-м и у-м районах; Р¡, Р? - объемы прогнозируемых корреспонденцийв /-м и у-м районах.

Для нахождения трендовых корреспонденций на первом шаге исследования применим формулу:

рЬ .....Ы,]_1.....N. где р® _ (а®, Ь®, с®) (26)

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

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

.....N,¡ = 1.....N. (27)

гдер^г1 _ (а^.Ь^.с*-1).

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

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

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

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

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

тк-1 . тк-1

р* = рг^гч*'1 • ' 2 ' (28)

где Ь0, Ь0 - коэффициенты роста корреспонденций в зоне т, т = 1,..., N. Данные коэффициенты также будут представляться тройками чисел.

тО _ 1щ=1 Р'т тО _ 1ш=1 рт /00ч

¿' = Уп п К ' Ь = Уп п К ' (29)

¿-¡т=1р'тКт ¿.¡т=1р}тКт

где Кт - коэффициент развития для зоны т.

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

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

Данный метод является самым трудоемким среди остальных экстраполяци-онных методов. Он дает наиболее точные результаты. Учитывая, что наложение нечетких отношений на входные данные ещё более усложнит расчеты, то для моделирования матриц корреспонденций заданным методом необходимо использование программного обеспечения.

Среди существующих подходов к построению матриц корреспонденций экс-траполяционные методы занимают особое положение благодаря своей вычислительной простоте. Однако использование этих методов в классическом виде влечёт за собой низкую точность прогнозирования, они не учитывают динамику транспортных потоков и не подходят для долгосрочного моделирования. Применение нечетких чисел усложняет вычислительные процедуры, требуя специальных операций с нечеткими матрицами. Однако эти сложности компенсируются существенным преимуществом - возможностью получать принципиально более достоверные оценки транспортных потоков, адекватно отражающие реальную неопределенность арктической логистической системы.

Для исследования оптимального маршрута был выбран метод единственного коэффициента роста, дополненный нечёткими треугольными числами. Данный метод обеспечивает достаточную точность для краткосрочного прогнозирования, что необходимо при постоянно изменяющихся природных условиях Арктической зоны. К достоинствам указанного метода относится также эффективность интегрирования нечётких чисел в расчёты и сохранение относительной простоты вычислений при работе с нечёткими матрицами. Полученная нечеткая матрица корреспон-денций для портов и портопунктов Белого моря будет использоваться для решения

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

2.3 Ограничения использования классической модели задачи коммивояжёра в реальных логистических системах

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

Данная задача предполагает, что вся информация о пунктах, расстояниях между ними и времени в пути известна заранее и не изменяется в процессе решения задачи. В реальных логистических системах эти параметры могут меняться динамически из-за пробок, погодных условий, задержек при погрузке/разгрузке и других факторов. Так, например, при оптимизации длины пройденного пути судами в арктических морях необходимо, в первую очередь, учитывать ледовую обстановку. Под влиянием данного фактора длина пути между пунктами может увеличиваться, а соответственно, будет увеличиваться время пути (если оптимизируемый параметр время), а возможно, для прохождения необходима будет ледовая проводка, что будет сопровождаться дополнительными расходами (если оптимизируемым параметром является стоимость пути). Классическая задача коммивояжёра не учитывает эту динамику, что может привести к неоптимальным или даже невыполнимым маршрутам.

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

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

^-трудность классической задачи коммивояжёра представляет собой серьезное препятствие для её применения в реальных логистических системах. Даже с использованием современных вычислительных ресурсов, точное решение для задач с большим количеством пунктов доставки занимает неприемлемо много времени. Это вынуждает использовать эвристические или метаэвристические алгоритмы, которые не гарантируют нахождение оптимального решения, а лишь позволяют получить «достаточно хорошее» решение за приемлемое время.

2.4 Математическая модель задачи коммивояжёра с нечеткими числами

Классическая задача коммивояжёра оперирует с точными числами, что не всегда отражает реальную картину. Например, время в пути между двумя пунктами не всегда является фиксированной величиной. Оно может варьироваться в зависимости от трафика, погодных условий, времени суток и других факторов. Представлять это время одним числом - значит упрощать реальность и терять важную информацию.

Как было описано выше, в логистике и планировании часто сталкиваются с ситуациями, когда расстояния между пунктами не определены точно и являются нечеткими. Так, например, в Арктических морях погодные условия и ледовая обстановка крайне нестабильны. Использование нечетких чисел для определения расстояний позволяет моделировать эту нестабильность. Например, можно представить расстояние между двумя точками как нечеткое число, которое зависит от прогноза погоды и ледовой обстановки. Это позволяет найти маршрут, который будет безопасным и эффективным даже при неблагоприятных условиях. Судно может отклоняться от оптимальной траектории из-за плохой видимости, сильного ветра

или сложной ледовой обстановки [2]. Нечеткие отношения учитывают эти возможные отклонения, стремясь к маршруту, который является оптимальным с учетом вероятности этих отклонений. Использование нечетких отношений позволяет более адекватно моделировать и решать такие задачи.

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

При наложении нечеткости на математическую модель задачи коммивояжёра получается односвязный взвешенный граф О = (V, Ж), имеющий п вершин

V = {1,2,...,п} и взвешенные ребра из каждой вершины / в вершину у, Ь _ 1,п,

] _ 1, п. Веса ребер wij, определяющие длину пути между вершинами, либо время прохождения данного пути, либо затраты, представлены нечёткими треугольными

числами _ (щ1™^ ^г), где представляет собой наиболее вероятное значение, треугольного нечеткого числа определяющего вес ребра из пункта / в пункт у, параметры и щ^1 - количественно определяют степень нечеткости этого числа, указывая величину разброса значений слева и справа от центра, соответственно.

Нечеткое треугольное число w однозначно определяется соответствующим нечетким множеством А. Функция принадлежности этого множества задает степень принадлежности каждого положительного действительного числа х к А, и имеет следующую форму:

, х

^к(х) _

если х Е Ша] если х Е [ща,щг]

Ша-Шг а ^

— У х -щ

г

(30)

0, в противном случае Математическая модель задачи коммивояжёра с нечеткими весами рёбер имеет вид:

п п

1 wa , wr ^ тт

1=1 j=1 п

^ Хц = 1, ] = 1,п

1=1 п

^ Хц = 1, I = 1, п

j=1

щ — иI + пхц < п — 1,щ > 0, ¿,у = 2,п

Хц е {0,1}

Хц =

¡"1, в цикле есть переход изЬв ] 0, в цикле не перехода из I в ]

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

2.5 Математическая модель многокритериальной нечёткой задачи коммивояжёра для арктического судоходства

При моделировании транспортных маршрутов в Арктике классическая задача коммивояжёра требует существенной модификации. Стандартные ограничения, учитывающие только расстояния или детерминированные стоимости, не отражают ключевые особенности региона. Для получения более адекватной для Арктического региона модели добавим в нечёткую модель задачи коммивояжёра (31), посещающего п портов северных морей, дополнительные ограничения.

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

формализации данного ограничения введём проверку (32) соответствия класса судна kshipминимальным требованиям к?-т для каждого ребра (/у).

" i J

*ц • (КыР - kfn) > 0, (32)

где kship - класс судна (по классификации IACS); к™ - минимальные требования

(класс судна) для прохождения ребра (/у), Ь,] = 1..п,1 Ф У; Ху - бинарная переменная исходной модели.

Например, если для прохождения некоторого маршрута между портами / и у разрешён средний ледовый класс Агс4, а судно имеет к^р =Агс3, то переход i ^ ] должен быть исключён из маршрута, х^ = 0.

При проектировании оптимальных маршрутов судоходства в Арктике ключевым фактором, кардинально влияющим на логистику и экономику перевозок, является необходимость ледокольного сопровождения. Это ограничение вводится в модель по следующим причинам:

1. географические ограничения:

- В Арктике существуют зоны с многолетними паковыми льдами толщиной 3-4 метра, непроходимыми для обычных судов.

- Даже в летний период сохраняются участки с высокой концентрацией льда, особенно в проливах и у побережья.

- Динамика ледового покрова крайне изменчива из-за дрейфа и сжатия льдов.

2. Технологические ограничения:

- Ледоколы обладают ограниченной пропускной способностью.

- Скорость проводки значительно снижается по сравнению со скоростью прохождения по чистой воде.

Требуется строгая координация всех судов по времени.

3. Экономические ограничения: Высокая стоимость ледокольного сопровождения.

Возникновение возможности непредвиденных простоев из-за погоды, что приводит к экспоненциальному росту затрат. Лимитированное количество ледоколов.

4. Операционные риски при отказе от сопровождения в сложных условиях:

- Возрастает вероятность аварийных ситуаций.

- Увеличивается расход топлива.

- Возможны срывы сроков доставки.

Таким образом, учет ледокольного сопровождения преобразует задачу коммивояжёра в задачу ресурсно-временного планирования с жесткими технологическими ограничениями.

Для формализации ограничения, связанного с классом ледокола, возможным для проводки зададим неравенство:

уц = сЦе • 1(к™ы > кзЫр) , (33)

где уу - бинарная переменная, указывающая принятое решение использования ледокольной проводки на ребре (1,]); с\?е - бинарный параметр, указывающий на необходимость использования ледокольного сопровождения на ребре (\,])\ I - индикатор (1 - если условие истинно, 0 - если ложно).

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

Q(Х) = £П=1 ТП=1 (К^, wrj)xlj + (Л^, ЯГ") • уи), (34)

где Л = (Л^ЛдДГ') - параметр, выраженный треугольным нечётким числом, определяющий «штраф» за каждую ледокольную проводку, выраженный в единицах длины.

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

Таким образом, нечёткая модель задачи коммивояжёра, учитывающая дополнительные природные факторы арктической зоны, будет иметь вид:

п п

У(х) = ££((™111™а ,™г)х11 + (Л\1Л1С1,Л1Г1) • у^ ^ тт 1=11=1

п

х = 1

£ хи = 1, ] = 1,п

Ь=1 п

£ хц = 1, I = 1,п

1=1

щ — и1 + пх^ < п — 1,щ > 0,1,] = 2,п

хЬ] • (кзЫр — к?}1П>) > 0, уц = С11е • 1(к?}т > кБЫр) ,

£ Уц < К1се , ч

хц,Уц,с^е Е {0,1}

(35)

I = 1,п, ] = 1,п

_ 1,в цикле есть переход из I в ] %11 = { 0, в цикле не перехода из I в ]

_ (1, назначена ледокольная проводка из I в ] У11 = {0, не назначена ледокольная проводка из I в ]

се _ (1, необходима ледокольная проводка из I в ] 11 (0, в ледокольной проводке из I в ] нет необходимости

ГЛАВА 3 ИСПОЛЬЗОВАНИЕ МУЛЬТИАГЕНТНЫХ МЕТОДОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ ЛОГИСТИЧЕСКИХ СИСТЕМ

На сегодняшний день разработано множество алгоритмов, позволяющих решать задачу коммивояжёра. Однако, при создании моделей для реальных практических задач, исследователи упрощают задачу за счет ограничения количества вершин, вследствие чего модель не в достаточной степени соответствует действительности.

Проблема коммивояжёра (TSP) рассматривается в различных приложениях, и в большинстве случаев доказано, что она является #Я-полной [15,84]. Данный факт обуславливает интерес к задаче и актуальность разработки новых методов ее решения. Одни из первых наиболее полных исследований данной задачи приведены в монографии 1969 года [34].

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

На практике одним из способов решения #Я-трудных задач является применение приближенных методов, а именно, метаэвристических алгоритмов, к числу которых относятся алгоритмы роевого интеллекта, в частности муравьиный алгоритм, алгоритм роя частиц, пчелиный алгоритм и другие.

В данной главе исследованы возможности применения некоторых метаэври-стических алгоритмов для решения задачи коммивояжёра. Для исследования сходимости были выбраны метод имитации отжига и «природные» алгоритмы: муравьиный и метод роя частиц.

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

задачи коммивояжёра были использованы только муравьиный алгоритм и алгоритм роя частиц.

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

3.1 Сравнительный анализ некоторых алгоритмов для решения классической задачи коммивояжёра

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

3.1.1 Алгоритм имитации отжига для решения задачи коммивояжёра

Первая информация касательно метаэвристического алгоритма имитации отжига (Simulated Annealing, SA) появилась в журнале «Science». Авторами работы были Киркпатрик, Гелатт и Веччи [86]. Идея метода была позаимствована из металлургии, когда атомы кристаллической решетки металла при нагревании покидают свои «места» в решетке и при остывании постепенно стараются попасть в состояние с меньшей энергией, однако, может происходить и такой вариант, что они с некоторой вероятностью попадут в место с большей энергией. Под местом понимается некоторое состояние системы. В случае, когда атом попадает в некоторое состояние с большей энергией, называется худшим состоянием. Чем ниже опускается температура, тем меньше вероятности, что система будет переходить в худшее

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

Появление худших состояний замедляет процесс сходимости алгоритма, однако помогает не застрять в локальном минимуме, когда работа алгоритма может остановиться в тот момент, когда глобальный минимум ещё не найден [60, 79].

Таким образом, метод имитации отжига предназначен для нахождения глобального минимума некоторой функции E(x), для заданных значений хеБ, где 5 - множество всех возможных состояний системы. Предполагается, что E(x) - функция энергии системы. В начальном состоянии системы задается максимальное значение температуры Ттах. В каждый рассматриваемый момент времени температура понижается, и система генерирует следующее возможное состояние хиз порожденного множества возможных состояний системы. После этого система перейдет в состояние х, гдевероятностьр определяется по формуле:

р = е-АЕ/Т, (36)

где АЕ = Е(х) — Е(х).

Величинар является вероятностью принятия нового состояния. Если А Е < 0, то вероятность равна 1. При этом переход в новое состояние произойдет в любом случае, если состояние лучше предыдущего.

Представим формальную схему метода имитации отжига:

1. Определяем начальное состояние системы.

2. Производим оценку состояния.

3. Если состояние принимается:

3.1 Обновляем текущее состояние.

3.2 Если необходимо изменить температуру: понижаем температуру.

4. Проверяем условие выхода. Если условие не выполняется, то создаём новое состояние и возвращаемся к пункту 2. Если условие выполняется, то выводим конечное состояние.

Блок-схема алгоритма представлена на рисунке 13.

Создать новое состояние

Рисунок 13- Блок-схема алгоритма имитации отжига.

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

С алгоритмом имитации отжига связана также проблема длительности выполнения моделирования. Одним из возможных вариантов решения данной проблемы является тщательный подбор начальных параметров.

В рамках настоящего диссертационного исследования производится экспериментальная верификация метода имитации отжига на задаче коммивояжёра со 100 вершинами, где веса рёбер графа заданы случайными величинами с равномерным распределением на интервале [0,1].

Алгоритм решения задачи коммивояжёра методом имитации отжига:

1. Генерация 100 случайных пунктов с координатами в диапазоне от 0 до 1.

2. Начальное решение. Создание случайного маршрута с посещением всех городов.

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

4. Создание соседнего решения. Для текущего маршрута коммивояжёра мы создаём новое, слегка изменённое решение («соседа»), переставляя местами два случайно выбранных города в маршруте.

5. Применение метода имитации отжига:

5.1.1. Начинаем с высокой «температуры», позволяющей принимать ухудшения решений.

5.1.2. Постепенно понижаем температуру, уменьшая вероятность принятия худших решений.

5.1.3. На каждой итерации рассматриваем соседнее решение и решаем, принять его или нет.

5.1.4. Сохраняем лучшее найденное решение.

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

В работе реализация алгоритма произведена с использованием языка программирования Python. Листинг программы представлен в Приложении 4.

Настраиваемые параметры в алгоритме: - initial temp - начальная температура;

- cooling_rate - скорость охлаждения (обычно выбирается из интервала 0.00010.001);

- шт^шр - минимальная температура для остановки;

- шах Нвга^от - максимальное число итераций;

Начальным параметрам зададим следующие значения:

- initialJeшp=400;

- cooling_rate=0.0008;

- шт^шр=1;

- шax_iterations=100000;

В результате реализации алгоритма было получено минимальное значение оптимизируемой функции - длина маршрута равна 39.32, достигаемое на итерации № 23000. Значение температуры снизилось до 1.0064. График сходимости представлен на рисунке 14. Лучший найденный маршрут, найденный по алгоритму имитации отжига представлен на рисунке 15.

Рисунок 14 - Сходимость алгоритма имитации отжига.

Общее расстояние по методу имитации отжига (39.32)

Рисунок 15- Реализация алгоритма имитации отжига.

Х координата

Проведём серии параметрических эксперименов (по 30 запусков), тестируя алгоритм при различных параметрах тШа!^втр (начальная температура) и cooling_rate (скорость охлаждения) с целью возможного определения значений параметров алгоритма для получения пути меньшей длины. Полученные значения найденных маршрутов представлены в таблице приложения 5. В верхней строке каждой ячейки среднее значение оптимизируемой функции, полученной в результате серии вычислительных экспериментов из 30 запусков, а в нижней строке ячейки - стандартное отклонение.

На основе полученных результатов можно сформулировать следующие выводы:

- Чем ниже изначальное значение температуры, тем алгоритм быстрее сходится к оптимальному значению.

- Чем меньше скорость охлаждения, тем требуется больше итераций.

- Наилучшие результаты (минимальная стоимость) достигаются при следующих значениях параметров:

- ^тр=400, сооПщ^е=0.0008 ^ 39.32± 2,87;

- temp=100, сооН^^е=0.0006 ^ 39.42± 2,88;

- temp=200, соо1^^е=0.0004 ^ 39.46± 2,89.

- Средние значения полученных оптимальных маршрутов после выполнения алгоритма остаются слишком высокими и варьируются от 39,32 до 46,58, количество итераций слишком большое и изменяется от 4000 до 69000.

В результате реализации метода имитации отжига и на основании проведённых вычислительных экспериментов можно заключить, что данный алгоритм, хорошо зарекомендовавший себя в задачах маршрутизации, что, в частности, продемонстрировано в работах по оптимизации транспортных сетей [60], требует дополнительных настроек и модификаций для получения улучшенных решений для задач большой размерности (N>100). Ограничения использования метода связано с

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

3.1.2 Муравьиный алгоритм для решения задачи коммивояжёра

Муравьиный алгоритм является метаэвристическим мультиагентным алгоритмом, одним из представителей так называемых «природных вычислений», к числу которых также относятся ДНК-вычисления, эволюционное программирование, нейросетевые вычисления. Направление природных вычислений образовалось при объединении процессов обработки информации, протекающих в природе, организмах, мозге человека и человеческом обществе с математическими методами [63].

Создателем муравьиного алгоритма является итальянский исследователь Марко Дориго, который с девяностых годов двадцатого века ведет научную деятельность в области ройного интеллекта. В работах [73,74] изучено применение муравьиных алгоритмов в задаче о коммивояжёре и маршрутизации сетей. Автором одной из первых работ в русскоязычной литературе, продолжающей исследования М. Дориго, стал Сергей Дмитриевич Штовба. В 2004 году им опубликована статья [63], в котором рассматривается применение элитарной муравьиной системы в задаче о коммивояжёре. Стоит отметить, что в большинстве научных работ проводятся исследования муравьиного алгоритма для задачи о коммивояжёре [19, 18, 93], наглядно интерпретируемой в терминах поведения муравьев и имеющей обширную базу тестовых задач.

Муравьиный алгоритм является мультиагентным методом. Он может быть использован для решения задачи коммивояжёра. При этом вкачестве агента выступает муравей. Муравей как агент способен самостоятельно составлять решения поставленной задачи, используя входные данные. Автономность агентов системы достигается за счет способности самостоятельного составления решения задачи.

Метод моделирует перемещение муравьёв от одной вершины к другой с откладыванием между этими точками феромона. Принцип нахождения алгоритмом решения основан на том, каким образом муравьи осуществляют поиск пищи и затем находят путь обратно в муравейник. Сначала муравьи исследуют площадь вокруг муравейника в случайном порядке. После нахождения источника пищи муравей несет пищу в муравейник, при этом оставляя за собой след феромона, который указывает другим муравьям на место расположения пищи. Через некоторое время, чем больше муравьев пройдет по этому пути за пищей, тем больше следа феромона они оставят за собой [63]. Переход между поведением настоящих муравьев, ищущих пищу, и алгоритмом, решающим некоторые комбинаторные оптимизационные задачи осуществляются с помощью аналогий между настоящими муравьями и агентами некоторой информационной системы, между количеством пищи и некоторой целевой функции, между феромонным следом и матрицей, отражающей предыдущие решения агентов в некотором виде.

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

Обычно, количество муравьев берется равным числу вершин исследуемого графа. Каждого муравья «усаживают» на свою вершину. В первую очередь для каждого муравья на каждом выборе следующей точки вычисляется «желание» перейти к определённой вершине, то есть нормированная оценка перемещения муравья из вершины I в вершину у по формуле:

где а, в - представляют собой параметры, регулируя которые, можно задавать веса для определения следа оставляемого феромона и видимости для выбора дальнейшего маршрута. Если параметр а принять равным нулю, то муравьем будет выбран ближайший город, если в принять равным нулю, то алгоритм будет очень быстро сходиться к субоптимальному решению; т¿у - количество феромона между вершинами I и У; ^¿у - эвристическая информация. Для задачи коммивояжёра - протяжённость пути между вершинами I и у, обратно пропорциональна стоимости; А - множество вершин, ещё не включённых в путь.

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

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

Далее осуществляется перерасчёт феромона на каждом из путей. Сначала производится добавление феромона. Берётся маршрут г-го муравья и для каждого ребра, которое вошло в него, добавляется феромон обратно пропорционально стоимости этого маршрута. Цикл повторяется для всех муравьёв.

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

Основные свойства мультиагентной системы включают в себя свойство автономности, свойство способности агентов к обучению или коррекция их поведения для улучшения эффективности. Это достигается за счет описанного в системе механизма обратной связи. Механизм обратной связи включает в себя положительную обратную связь и отрицательную обратную связь [3, 92]. Положительная обратная связь реализуется в виде феромонного следа, оставляемого каждым муравьем в тех назначениях, которые использовались в решении. Отрицательная обратная связь формулируется наличием испарения феромона. На каждой итерации количество феромона для назначения (¿, у) изменяется по формуле:

т*}1 = t[j • (1- р) + A4j, (38)

где т1 - концентрация феромона на следующей итерации; rfj - концентрация феромона на текущей итерации; р - коэффициент интенсивности испарения феромона; ATjj - суммарное количество феромона, которое оставили муравьи, использовавшие назначение (i, )) в своем решении на текущей итерации.

Помимо весов а, ¡3 к параметрам алгоритма относится коэффициент испарения феромона и количество муравьев в системе. Изложенная система описывает общий принцип взаимодействия агентов вместе со способом создания решений. Блок-схема муравьиного алгоритма представлена в Приложении 6.

Алгоритм муравьиной колонии:

1. Устанавливается количество вершин (V) графа G = (V, E) с произвольными весами рёбер, количество муравьёв (numants), инициализируются параметры а (влияние феромона), в (влияние эвристики), скорость испарения (р), константа для обновления феромона (Q), максимальное число итераций (maxiterations), критерий останова (например, отсутствие улучшений за к итераций).

2. Размещаются случайным образом муравьев по вершинам. Инициализируются следующие параметры:

- матрица феромонов размером V*V с начальным значением initial_pheromone;

- лучшее решение (best solution = None);

- значение целевой функции (best_cost= для минимизации.

3. Основной цикл по количеству итераций. Пока не достигнут критерий останова, например, пока не достигнуто максимальное количество итераций maxiterations:

3.1 Цикл по количеству муравьев

3.1.1 Цикл по количеству вершин.

- для текущей вершины вычисляются нормированные оценки перехода в соседние вершины (по формуле 37);

- выбирается следующая случайная вершина с учётом вычисленных оценок;

- добавляется вершина в путь муравья.

3.1.2 Запоминается построенное решение.

3.2 Обновление лучшего решения:

3.2.1 Сравниваются решения всех Муравьёв с текущим bestcost.

3.2.2 Если найдено улучшение, обновляются bestcolution и bestcost.

3.3 Изменяется количества феромона.

3.3.1 Обновляется матрица феромонов. Для изменения количества феромонов из-за испарения, умножаются все значения в матрице феромонов на (1 - р).

3.3.2 Для каждого муравья вычисляется количество феромона At=Q/L, где L-стоимость решения, а Q- это параметр алгоритма, нормировочная константа, которая определяет, сколько феромона будет оставлено на ребрах пути. Её значение влияет на масштаб обновления феромонов и баланс между исследованием новых путей и эксплуатацией уже найденных решений.

3.3.3 Для каждого ребра в пути муравья увеличивается феромон на ребре на Ат.

4. Выводится bestsolution - оптимальное решение (последовательность вершин), bestcost - значение целевой функции.

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

Алгоритм муравьиной колонии для решения задачи коммивояжёра:

1. Устанавливается количество вершин (N), формируется матрица расстояний (distancematrix), задаётся начальное количество феромона на каждом ребре (initial_pheromone), количество муравьёв (numants), инициализируются параметры а (влияние феромона), в (влияние эвристики, например, обратного расстояния), скорость испарения (evaporation_rate), максимальное число итераций (max_iterations).

2. Размещаются случайным образом муравьи по вершинам. Инициализируются следующие параметры:

- матрица феромонов размером N*N с начальным значением initial_pheromone;

- лучший найденный путь (best_path = None);

- длина лучшего пути (bestlength = +да).

3. Основной цикл по количеству итераций. Пока не достигнуто максимальное количество итераций maxiterations:

3.1 Цикл по количеству муравьев

3.1.1 Цикл по количеству вершин.

- для текущей вершины вычисляется нормированная оценка перехода в непо-сещённые вершины по формуле 37;

- выбирается следующая случайная вершина с учётом вычисленных оценок;

- добавляется вершина в путь муравья.

3.1.2 Запоминается построенный путь и его длина.

3.2 Обновление лучшего решения:

3.2.1 Сравниваются пути всех муравьёв с текущим bestlength

3.2.2 Если найден более короткий путь, обновляется best_path и best length.

3.3 Изменяется количество феромона

3.3.1 Обновляется матрица феромонов. Для изменения количества феромонов из-за испарения, умножаются все значения в матрице феромонов на (1 - ivapora-tionrate)

3.3.2 Для каждого муравья вычисляеется количество феромона At=Q/L, где L -длина пути муравья, а Q- это параметр алгоритма, нормировочная константа, которая определяет, сколько феромона будет оставлено на ребрах пути. Её значение влияет на масштаб обновления феромонов и баланс между исследованием новых путей и эксплуатацией уже найденных решений.

3.3.3 Для каждого ребра в пути муравья увеличивается феромон на ребре на Ах.

4. Выводятся best_path - оптимальный найденный путь (последовательность вершин), best length - длина этого пути.

В рамках настоящего диссертационного исследования проведена экспериментальная верификация муравьиного алгоритма для решения задачи коммивояжёра со 100 пунктами, где расстояние между пунктами выраженно чёткими случайными числами в интервале (0,1), вычисленными по евклидовой метрике. Для

моделирования использован язык программирования Python. Листинг программного кода представлен в Приложении 7.

Для визуализации решения приведён график сходимости алгоритма и полученный минимальный маршрут обхода всех вершин с возвратом в исходную точку. На рисунке 16 отображается полученное оптимальное решение - минимальный путь, его длина и график сходимости алгоритма при коэффициенте влияния феромона а=3, коэффициенте в=3 - влияние эвристики и скорости испарения р=0,5. Минимальный маршрут, проходящий через все вершины с возвратом в исходную точку при указанных параметрах составляет 7,86. Алгоритм сходится на 98-й итерации.

Общее расстояние по муравьиному алгоритму (7.86)

0.4 0.6

Х координата

Рисунок 16 - Результаты имитации методом муравьиной колонии.

Для определения наилучших параметров коэффициента влияния феромона а и видимости для выбора дальнейшего маршрута в были произведены запуски программы с различными значениями параметров а и в (по 30 запусков на каждый набор параметров). Результаты данного параметрического эксперимента с коэффициентами испаренияр=0,3; 0,5 и 0,7представлены в таблице Приложения 8.

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

отклонение. Серым цветом выделены ячейки с наилучшей сходимостью, где значения полученного оптимального маршрута меньше 9.00.

Согласно результатам «прогона» программы с различными значениями коэффициентов алгоритма (значения из таблицы Приложнения 7), средние значения оптимального маршрута варьируются от 46,27 (при коэффициентах испарения феромона р=0,7, влияния феромона а=2,5и видимости дальнейшего пути в=0) до 7,86 (при коэффициентах испарения феромона р=0,5, влияния феромона а=3 и видимости дальнейшего пути в=3).

Если значение параметра видимости дальнейшего пути в=0, то алгоритм попадает в локальный минимум и средняя длина маршрута оказывается наибольшей (от 41,04 до 46,27) при любых значениях параметров а и р. Аналогично, если параметр влияния феромона а=0, то средние значения полученных оптимальных маршрутов варьируются от 10,95 до 45,08.

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

3.1.3 Метод роя частиц для решения задачи коммивояжёра

Роевой интеллект может быть определен как коллективное поведение децентрализованных и самоорганизованных роев. Известные примеры включают в себя стаи птиц, рыбные стаи и колонию социальных насекомых, такие как термиты, муравьи, пчелы и так далее. Два фундаментальных понятия, рассматриваемых в качестве необходимых свойств роевого интеллекта - самоорганизация и деление труда [4, 21].

Метод роя частиц (РБО), так же, как и муравьиный алгоритм, является муль-тиагентным методом, где частицы (агенты) перемещаются в своей среде. При этом агенты, изменяя свое местоположение и взаимодействуя друг с другом, находят оптимальное решение. Основателем данного метода является К. Рейнольдс [91]. Поведение объектов, правила для которых придумал Рейнольдс, очень схожи с поведением стаи птиц или роя пчел. Для создания своей графической модели Рейнольдс тщательно изучал коллективное поведение стаи птиц. В данной системе нет коллективного центра управления, каждая птица действует как отдельный агент, но при этом демонстрируется цельное поведение всей системы [85, 38].

Три основных правила, которым должна придерживаться каждая птица в стае, были сформулированы Рейнольдсом следующим образом:

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

2. Скорость каждой птицы должна быть наиболее близкой к птицам в её окрестности, то есть необходимо постоянно корректировать свою скорость.

3. Нельзя отрываться от стаи, то есть нужно сохранять достаточно малое расстояние с другими птицами.

Алгоритм оптимизации роя частиц был впервые опубликован Кеннеди и Эберхартом [72]. В алгоритме роя частиц каждая частица имеет скорость и положение, в соответствии с которыми она перемещается в пространстве поиска. Частицы пролетают через пространство поиска, притягиваясь к наилучшему положению, найденному стаей и самой частицей.

Блок-схема алгоритма роя частиц представлена на блок-схеме (рисунок 17).

Рисунок 17 - Алгоритм метода роя частиц.

Алгоритм метода роя частиц: 1. Формируется случайный рой, состоящий из m частиц.

1.1 Для каждой частицы случайным образом определяются:

1.1.1 начальное положение в пространстве решений (x);

1.1.2 начальная скорость (уг);

1.2 Задаются параметры алгоритма:

1.2.1 коэффициенты познания (с^) - когнитивный коэффициент (влияет на индивидуальный опыт частицы) и социальности (сг) - социальный коэффициент (влияет на коллективный опыт роя);

1.2.2 инерционный вес

1.2.3 максимальное число итераций или критерий остановки.

2. Оценивается начальное решение

2.1 Для каждой частицы вычисляется значение целевой функции Дх).

2.2 Запоминается лучшее индивидуальное решение частицы (рЪв811 = х).

2.3 Определяется лучшее решение в целом рое

3. Основной цикл (пока не выполнен критерий остановки). Для каждой частицы в рое производится:

3.1 Обновление скорости:

VI = w•vi + в] -га^() (рЪгзи - х) +с2га^() (qЪesti - х) (гапё() - случайное число из [0,1]).

3.2 Ограничение скорости (если заданы пределы vmin, vmax).

3.3 Обновление положения: х, = х, + V,-.

3.4 Оценка нового положения:

3.4.1 Вычисляется Дх).

3.4.2 Если новое решение лучшеpЪesti, обновляетсяpЪesti=xi,

3.4.3 ЕслиДх) лучше f(qЪest), обновляется qЪest=xi,

4. Проверяется критерия остановки:

4.1 Достигнуто максимальное число итераций.

4.2 Найдено решение с достаточной точностью.

4.3 Прекратилось существенное улучшение gЪest.

5. Возвращается лучшее решение gЪest и f(gЪest).

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

на каждом шаге рассчитывается заданная функция и производится поиск наилучшего значения.

В диссертационной работе алгоритм роя частиц адаптирован для решения задачи коммивояжёра с целью поиска гамильтонова цикла минимальной длины. Алгоритм PSO для задачи коммивояжёра:

1. Создание m частиц, где каждая представляет:

position: текущий случайный маршрут (перестановка пунктов); velocity: скорость, под которой понимается список случайных обменов (перестановок) пар пунктов;

pbest: копия начального маршрута (лучшее личное решение); pbestcost: стоимость (длина) этого маршрута.

2. Определение gbest и gbestcost- лучший маршрут среди всех частиц и его длина.

3. Основной цикл (пока не достигнут критерий остановки). Для каждой частицы в рое производится:

3.1 Обновление скорости:

3.1.1 Генерация случайных чиселс (когнитивный коэффициент) и с2 (социальный коэффициент).

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

- diff_pbest: последовательность обменов, чтобы превратить текущий маршрут в pbest;

- diffgbest: последовательность обменов, чтобы превратить текущий маршрут в gbest.

3.1.3 Вычисление новой скорости:

Создание пустого списка newvelocity для новой скорости.

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

- В когнитивной части добавляются обмены, ведущие к лучшему личному решению с вероятностью c1 * r1, где r1 - случайное число в [0,1].

- В социальной части добавляются обмены, ведущие к лучшему глобальному решению с вероятностью c2 * r2, где r2 - случайное число в [0,1].

- Если скорость слишком длинная, обрезаем до N обменов (где N- число городов).

3.1.4 Обновление позиции.

- Применение всех обменов из newvelocity к текущему маршруту. Получение new_position.

- Вычисление длины нового маршрута newcost.

- Сохранение нового состояния частицы.

3.1.5 Обновление лучших решений.

- Если найден лучший личный маршрут, то обновляем его.

- Если найден лучший глобальный маршрут, то обновляем его.

4. Проверка сходимости.

- Если на итерации не было улучшений глобального маршрута gbest, то увеличивается счетчик noimprovementcount.

- Если улучшения были - сбрасывается счетчик.

- Если no improvement count достиг заданного лимита earlystoppingrounds -останавка.

5. Возвращение лучшего решения (маршрута) gbest и его длины gbestcost.

Для баланса коэффициента инерцию (w) обычно выбирают в диапазоне от 0,4 до 0,7.

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

При большом значении w (от 0,9 до 1,2) частицы сохраняют большую часть своей предыдущей скорости. Алгоритм активно исследует пространство решений, но частицы могут «проскакивать» хорошие решения.

При малом значении w (от 0,2 до 0,4) частицы быстро теряют скорость, сильнее ориентируясь на pbest и gbest. Алгоритм активно исследует пространство решений, но частицы могут «проскакивать» хорошие решения. Алгоритм уточняет найденные решения. Существует риск преждевременной сходимости к локальному минимуму.

Для баланса когнитивного и социального коэффициентов важно соблюдать условие: с± + с2 < 4, так как при с± + с2 > 4 скорость частиц может неограниченно расти и алгоритм становится неустойчивым.

Если с± = с2 = 0, частицы движутся только по инерции (w), что приводит к случайному блужданию.

Если с± > 2,5 или с2 > 2,5, то частицы могут резко менять направление, что ухудшает сходимость алгоритма.

При cj>c2 усиливается исследование (разнообразие решений), но замедляется сходимость. При c2 >cj ускоряется сходимость к gbest, но повышается риск попадания в локальный минимум.

В рамках настоящего диссертационного исследования проведена экспериментальная верификация алгоритма роя частиц для решения задачи коммивояжёра со 100 пунктами, где расстояние между пунктами выраженно чёткими случайными числами в интервале (0,1), вычисленными по евклидовой метрике. Для моделирования использован язык программирования Python. Для каждого набора параметров было выполнено по 30 запусков программы. Листинг программного кода представлен в Приложении 9.

Для визуализации решения приводим график сходимости алгоритма и полученный минимальный маршрут обхода всех вершин с возвратом в исходную точку (рисунок 18).

Общее расстояние по методу роя частиц (24.18)

~Г

0.4 0.6

Х координата

Рисунок 18 - Решение задачи коммивояжёра алгоритмом роя частиц с параметрами