Природные алгоритмы построения оптимального кольцевого маршрута (на примере карты г. Благовещенска)

Николай Колтунов

Природные алгоритмы построения оптимального кольцевого маршрута (на примере карты г. Благовещенска)

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

Математика

Диссертации

Вуз: Амурский государственный университет (АмГУ)

ID: 5f431eadcd3d3e0001572447

UUID: 2c7f2ca0-c7db-0138-1f77-0242ac180006

Язык: Русский

Опубликовано: около 4 лет назад

Просмотры: 130

12.6

Николай Колтунов

Амурский государственный университет (АмГУ)

Комментировать 10

Рецензировать 0

Скачать - 6,7 МБ

Поделиться работой

Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования АМУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ (ФГБОУ ВО «АмГУ») Факультет математики и информатики Кафедра математического анализа и моделирования УТВЕРЖДАЮ И.о. зав. кафедрой _____________Н.Н. Максимова «______»______________2020 г. ЗАДАНИЕ К магистерской диссертации студента Колтунова Николая Сергеевича 1. Тема магистерской диссертации: Природные алгоритмы построения оптимального кольцевого маршрута (на примере карты г. Благовещенска). (утверждена приказом от 10.02.2020 № 283-уч) 2. Срок сдачи студентом законченной проекта: 26 июня 2020 года. 3. Исходные данные к магистерской диссертации: отчет по преддипломной практике, средства автоматизации вычислений – ППП MATLAB, интегрированную среду разработки программного обеспечения – Microsoft Visual Studio, географические данные адресов на карте города Благовещенск. 4. Содержание выпускной квалификационной работы (перечень подлежащих разработке вопросов): обзор теории комбинаторных задач и методов их исследования, обзор природных алгоритмов, реализация муравьиного алгоритма, алгоритма имитационного отжига и пчелиного алгоритма для решения задачи коммивояжера, обзор базовой части языка Python. 5. Перечень материалов приложения (наличие чертежей, таблиц, графиков, схем, программных продуктов, иллюстративного материала и т.п.): листинги вычислительных программ, результаты работы программ в виде изображений. 6. Консультанты по магистерской диссертации: рецензент – Кузьмин И.Н., доцент кафедры сервисных технологий и общетехнических дисциплин, ФГБОУ ВО

«АмГУ», канд. техн. наук; нормоконтроль – Мороз Л.И., старший преподаватель. 7. Дата выдачи задания: 20.02.2020 г. Руководитель магистерской диссертации: Максимова Надежда Николаевна, доцент, канд. физ.-мат. наук, доцент Задание принял к исполнению (20.02.2020): ______________ Колтунов Н.С.

РЕФЕРАТ Магистерская диссертация содержит 135 с., 48 рисунков, 25 таблиц, 8 приложений, 47 источников. ЕСТЕСТВЕННЫЕ ВЫЧИСЛЕНИЯ, АЛГОРИТМ, ЗАДАЧИ КОММИВОЯЖЕРА, МАТЕМАТИЧЕСКАЯ МОДЕЛЬ, МАРШРУТ, ПУТЬ, МУРАВЬИНЫЙ АЛГОРИТМ, МЕТОД ИМИТАЦИОННОГО ОТЖИГА, АЛГОРИТМ ПЧЕЛИННОЙ КОЛОНИИ, ППП MATLAB, OSRM, OSM, ЯНДЕКС.КАРТЫ В работе исследуется задача построения кольцевого маршрута и природные алгоритмы, которые объединяют методы с природными механизмами принятия решений, и их применение для задач маршрутизации. Цель магистерской диссертации – изучение и реализация природных алгоритмов и проведение серии вычислительных экспериментов для решения задачи коммивояжера. Для достижения цели было поставлено ряд задач: - изучение научной и методической литературы по комбинаторным задачам, а именно транспортной задачи коммивояжера; - описание и постановка математической модели задачи маршрутизации; - изучение литературы и научных работ по природным алгоритмам; - моделирование и последующие тестирование модели кольцевого маршрута, с использованием выбранных природных алгоритмов в ППП MATLAB; - определение оптимальных значений коэффициентов каждого алгоритма/метода; - реализация алгоритмов/методов при решении задачи построения кольцевого маршрута на реальной карте ( г. Благовещенска). - анализ полученных результатов по каждому алгоритму/методу и определение лучшего для поставленной задачи. 4

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

СОДЕРЖАНИЕ Введение 8 1 Задача построения кольцевого маршрута 13 1.1 Математическая модель задачи коммивояжера 13 1.2 Аналитические методы исследования задачи 15 1.3 Пример решения задачи при помощи венгерского алгоритма 17 2 Природные алгоритмы 26 2.1 Описание и назначение природных алгоритмов 26 2.2 Муравьиный алгоритм 27 2.3 Имитационный отжиг 35 2.4 Пчелиный алгоритм 40 3 Реализация и тестирование алгоритмов 44 3.1 Муравьиный алгоритм 45 3.2 Метод имитационного отжига 56 3.3 Пчелиный алгоритм 62 4 Построение оптимального кольцевого маршрута на карте города Благовещенска 66 4.1 Постановка задачи 66 4.2 Муравьиный алгоритм 74 4.3 Метод имитационного отжига 78 4.4 Пчелиный алгоритм 82 4.5 Анализ результатов работы алгоритмов 86 5 Использование результатов магистерской диссертации в педагогической деятельности 88 5.1 Разработка лабораторной работы «Природные алгоритмы построения оптимального кольцевого маршрута» 88 5.2 Варианты заданий для индивидуальной работы 95 Заключение 96 Библиографический список 98 6

Приложение А Листинг программы «Distance Matrix» на языке Python 103 Приложение Б Листинг вычислительной программы «Ant Colony Algorithm» в ППП MATLAB 109 Приложение В Листинг вычислительной программы «Annealing Simulation Algorithm» в ППП MATLAB 113 Приложение Г Листинг вычислительной программы «Bee Swarm Algorithm» в ППП MATLAB 116 Приложение Д Листинг дополнительной функции к программам «ProgramData_new» в ППП MATLAB 121 Приложение Ж Оптимальные маршруты построенные в интернет сервисе OSRM, Муравьиный алгоритм 127 Приложение К Оптимальные маршруты построенные в интернет сервисе OSRM, Имитационный отжиг 130 Приложение Л Оптимальные маршруты построенные в интернет сервисе OSRM, Пчелиный алгоритм 133 7

ВВЕДЕНИЕ В последние два десятилетия при оптимизации сложных систем, исследователи все чаще и чаще применяют природные механизмы поиска наилучших решений для различных задач. Это механизмы обеспечивают эффективную адаптацию флоры и фауны к окружающей среде на протяжении миллионов лет на Земле [1]. Сегодня интенсивно разрабатывается и развивается научное направление Natural Computing – «Природные вычисления», которые объединяют методы с природными механизмами принятия решений [2]. К таким алгоритмам можно отнести следующие: - Genetic Algorithms – генетические алгоритмы; - Evolution Programming – эволюционное программирование; - Neural Network Computing – нейро-сетевые вычисления; - DNA Computing – ДНК-вычисления; - Cellular Automata – клеточные автоматы; - Ant Colony Algorithms – муравьиные алгоритмы и др. Природные вычисления успешно применяются при решении комбинаторных задач: задача выбора маршрута, задача коммивояжёра, задача о восьми ферзях, задача о ранце, задача раскроя, задача о назначениях, задачи составления расписания и т.п. [3]. Объектом исследования в магистерской диссертации являются методы и алгоритмы для исследования комбинаторных задач. Предмет исследования – это задачи построения кольцевого маршрута и природные алгоритмы, которые объединяют методы с природными механизмами принятия решений и их применение для задач маршрутизации. Научная гипотеза работы охватывает природные алгоритмы, которые применимы для решения прикладных комбинаторных задач и могут являться эффективным средством для их приближенного решения при большой размерности. 8

Цель научных исследований в целом заключается в поиске решения оптимального пути кольцевого маршрута определенных размерностей с применением природных алгоритмов и созданием маршрутов на основе реальных географических данных города Благовещенска. Новизна работы состоит в использовании реальных данных для задачи. В ходе работы над данной диссертацией было выполнено: - обзор научной и методической литературы по природным вычислениям; - описание и постановка математической модели задачи маршрутизации; - реализация природных алгоритмов, осуществление пробных вычислений в ППП MATLAB на основе случайных данных; - тестирование и определение оптимальных значений констант алгоритмов в ППП MATLAB; - испытание природных алгоритмов при решении задачи построения кольцевого маршрута на основе реальных данных и на карте г. Благовещенска. Структура работы. В магистерскую диссертацию входят - введение; - пять глав; - заключение; - библиографический список; - восемь приложений. В первом пункте первой главы рассматривается постановка задачи коммивояжера и представлена ее математическая модель. Далее во втором пункте приводится аналитические методы исследования задачи. А в третьем пункте продемонстрирован пример решения задачи венгерским алгоритмом. В первом пункте второй главы рассматриваются виды природных алгоритмов и их применение к комбинаторным задачам. В других пунктах подробно описаны реализуемые алгоритмы: муравьиный алгоритм, алгоритм имитационного отжига и пчелиный алгоритм. 9

Третья глава посвящена реализации и тестированию алгоритмов задачи кольцевого маршрута, а именно нахождение решения с ППП MATLAB, на основе случайных входных параметров (матрицы расстояний и координат). При одинаковых условиях тестируются все три алгоритма. В четвертой главе выполняется уже непосредственно моделирование на основе реальных входных данных, т.е. применяются географические параметры города Благовещенска. Аналогично третьей главе реализуются все данные алгоритмы. В пятой главе представлены индивидуальные задания и варианты к ним, предлагаемые для самостоятельной работы студентов по данной теме. В приложениях приведены листинги пяти вычислительных программ: 1) программа автоматизированного сбора данных с интернет-ресурса; 2) программа поиска решения кольцевого маршрута с использованием муравьиного алгоритма; 3) программа поиска решения кольцевого маршрута с использованием метода имитационного отжига; 4) программа поиска решения кольцевого маршрута с использованием алгоритма пчелиной колонии; 5) дополнительная функция к программам «ProgramData_new» в ППП MATLAB; 6) Оптимальные маршруты построенные в интернет сервисе OSRM, Муравьиный алгоритм; 7) Оптимальные маршруты построенные в интернет сервисе OSRM, Имитационный отжиг 8) Оптимальные маршруты построенные в интернет сервисе OSRM, Пчелиный алгоритм. Первая программа была реализована с помощью языка программирования Python в среде разработки Visual Studio. Остальные же программы были созданы в ППП MATLAB. 10

Результаты работы докладывались и обсуждались на: - научно-методических семинарах кафедры математического анализ моделирования ФГБОУ ВО «АмГУ» (2018-2020 гг.); - XIII международной научно-практической конференции «Инновации в науке и практике» (г. Барнаул, 2018 г.) - XXVIII научной конференции «День науки» в АмГУ (г. Благовещенск, 2019 г.,) очное участие, результат - диплом второй степени; - XX региональной научно-практической конференции «Молодежь ХХI века: шаг в будущее» (г. Благовещенск, 2019 г.), очное участие, результат – сертификат участника; - II всероссийской национальной научной конференции студентов, аспирантов и молодых ученых «Молодежь и наука: Актуальные проблемы фундаментальных и прикладных исследований» (г. Комсомольск-на-Амуре, 2019 г.); - III всероссийской национальной научной конференции студентов, аспирантов и молодых ученых «Молодежь и наука: Актуальные проблемы фундаментальных и прикладных исследований» (г. Комсомольск-на-Амуре, 2020 г.). Также были опубликованы по затрагиваемой теме шесть работ [4-9] в различных изданиях: 1) материалы XIII международной научно-практической конференции «Инновации в науке и практике» (г. Барнаул, 2018 г.); 2) материалы II всероссийской национальной научной конференции студентов, аспирантов и молодых ученых «Молодежь и наука: Актуальные проблемы фундаментальных и прикладных исследований», (г. Комсомольск-наАмуре, 2019 г.); 3) материалы XX региональной научно-практической конференции «Молодёжь XXI века: шаг в будущее» (г. Благовещенск, 2019 г.); 4) научный журнал «Ученые заметки ТОГУ» (г. Хабаровск, 2020 г.) – принята к публикации; 5) материалы III всероссийской национальной научной конференции молодых ученых «Молодежь и наука: Актуальные проблемы фундаментальных и 11

прикладных исследований», (г. Комсомольск-на-Амуре, 2020 г.) – принята к публикации; 6) научно-теоретический журнал «Вестник АмГУ» (г. Благовещенск, 2020 г.); Научная работа была поддержана грантом Амурского государственного университета в 2019-2020 году. Результаты магистерской диссертации могут быть использованы в образовательном процессе при изучении дисциплин «Математическое моделирование» (специальность 09.02.03 Программирование в компьютерных системах), «Планирование эксперимента», «Математическое и компьютерное моделирование» (направление подготовки 01.03.02 Прикладная математика и информатика) в рамках проведения лекционных, практических и лабораторных занятий. 12

1 ЗАДАЧА ПОСТРОЕНИЯ КОЛЬЦЕВОГО МАРШРУТА Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача построения кольцевого маршрута или как иначе называют – задача коммивояжера (англ. «Travelling salesman problem», TSP) [10]. Также встречается название «задача о бродячем торговце». Суть задачи сводится к поиску оптимального, то есть наикратчайшего пути, проходящего через некие пункты по одному разу. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальное расстояние пути [11]. Самые первые упоминания в виде математической задачи на оптимизацию относят Карлу Менгеру, которую он сформулировал еще в 1930 году на математическом коллоквиуме, примерно так: «Мы называем проблемой посыльного (поскольку этот вопрос возникает у каждого почтальона, в частности, её решают многие путешественники) задачу о нахождении кратчайшего пути между конечным множеством мест, расстояние между которыми известны» [12]. 1.1 Математическая модель задачи коммивояжера Постановка данной задачи звучит следующим образом: имеется n городов, которые обязан коммивояжер (бродячий торговец) пройти с минимальными затратами. По мимо этого на его маршрут добавляются два условия: 1) маршрут должен быть замкнутым - торговец должен в конце пути возвратится в первый город, из которого начался его путь; 2) в каждом из городов (пунктов) коммивояжер должен побывать не более одного раза. Для вычисления так называемых затрат имеется матрица условий, которая содержит затраты cij на переход из города в город, при условии, что можно перейти из любого города в любой, кроме того же самого. Выходит в матрице, как бы вычеркивается диагональ, но на деле просто ставят нули. 13

Целью решения является нахождение маршрута, который будет удовлетворять все условия и иметь минимальную сумму затрат [13]. В каком порядке бродячий торговец должен посещать n городов (пунктов), чтобы минимизировать общее расстояние (стоимость) пути маршрута, когда заданы попарно расстояния между всеми городами? Если не требовать возвращения к исходному пункту, то задача будет незамкнутой. В данном случае речь будет только о замкнутом виде. Существует  n  1! различных вариантов маршрутов. Имеется огромное количество примеров ситуаций, где имеется применение данной задачи, например применение в энергоснабжении, сбор по тревоге, телефонная связь, балансирование сборочных линий, сложные задачи теории расписаний и т.п. [14]. Итак, вводим переменные: 0, если торговец не переезжает из города i в город j , xij   1, если переезжает. Целевая функция и ограничения принимают вид: F ( x)   cij xij  min, (1) x (2) i ij i  1, j x ij  1, j xij  0, xij {0,1} , (3) где cij – расстояние между пунктами i и j (расположение городов); xij – переменная задачи, муравей. И вот, имея некую матрицу расстояний, можно из какой-либо строки или столбца, вычесть случайное положительное число. Решение задачи о коммивояжёре с этой редактированной матрицей совпадает с решением без изменения, а дистанция маршрута уменьшается на вычитаемое значение. И если эту операцию проделать и для остальных столбцов и строк, то длина маршрута будет разнится на сумму всех чисел, вычитаемых из столбцов и строк. Этот процесс называется приведением матрицы. 14

Под путем понимается последовательность дуг, в которой конец каждой предыдущей дуги будет являться началом последующей. Элементарным путем называют путь, где никакая вершина не встречается дважды. А если он еще проходящий через все вершины – гамильтоновым контуром. Контуром называют конечный путь, у которого начальная вершина соответствует с конечной. Граф называют полным, если в нем любые две вершины присоединены хотя бы в одном направлении. Задача о коммивояжёре является задачей поиска гамильтонова контура наикратчайшей дистанции в полном графе. Схема решения может быть основана на переборе всех вариантов с одновременным подсчетом пройденных путей. 1.2 Аналитические методы исследования задачи Если задача коммивояжера относится к комбинаторной оптимизации, то для нее относятся такие методы решения, как: - метод перебора (подбираются задачи на развитие мышления); - табличный метод (все условия вносятся в таблицу, в ней же выполняется решение); - построение дерева возможных вариантов решений; - построение граф-схемы. Задачи комбинаторной оптимизации рассматривают как нахождение лучшего элемента в каком-то дискретном множестве. Из-за этого могут быть использованы метаэвристические алгоритмы или же практически любые алгоритмы поиска. Однако общие алгоритмы поиска не могут гарантировать оптимального решения и быстрого решения (за полиномиальное время). Поскольку некоторые задачи дискретной оптимизации NP-полны (например, задача о коммивояжёре), такой исход следует ожидать и для других задач (если не P=NP). Итак, рассмотрим задачу коммивояжера с некой матрицей расстояний, которой соответствует таблица 1.1: 15

Таблица 1.1 – Матрица расстояний i\j 1 2 3 4 5 1 ∞ 10 12 15 13 2 10 ∞ 9 16 17 3 12 9 ∞ 13 14 4 15 16 13 ∞ 11 5 13 17 14 11 ∞ Символ «∞» означает запрет, невозможность выезда из города. Построить кольцевой маршрут объезда всех пунктов, чтобы длина маршрута была бы наименьшей, и чтобы каждый из пунктов входил в маршрут только один раз. Рассмотрим схему решения задачи согласно указанному алгоритму, как представлено на рисунке 1.1. Рисунок 1.1 – Варианты построения кольцевого маршрута Очевидно, что при большой размерности задачи такой вариант не приемлем в силу больших вычислительных затрат. Рассмотрим венгерский алгоритм, который можно применить для решения поставленной задачи. 16

1.3 Пример решения задачи при помощи венгерского алгоритма Венгерский алгоритм – алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время. Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков [15]. Идея венгерского метода в основном заключается в переходе от изначальной квадратной матрицы стоимости С к эквивалентной ей матрице С э с неотрицательными элементами и системой n независимых нулей. Для заданного n имеется только n ! допустимых решений. Если в матрице назначения X расставить n единиц так, что в каждом столбце и строке находится только по одной 1, которые составлены в соответствии с расположенными n независимыми 0 эквивалентной матрицы стоимости С э . В итоге получатся до- пустимые решения задачи о назначениях. И вот, строим приведенную матрицу с целью получения в каждой строке и столбце не меньше одного кратчайшего маршрута (нулевого приведенного значения), соответственно в таблице 1.2 и таблице 1.3. Таблица 1.2 – Приведенная матрица i\j 1 2 3 4 5 1 ∞ 10 12 15 13 2 10 ∞ 9 16 17 3 12 9 ∞ 13 14 4 15 16 13 ∞ 11 5 13 17 14 11 ∞ 17

Таблица 1.3 – Приведенная матрица i\j 1 2 3 4 5 1 ∞ 0 2 5 3 2 1 ∞ 0 7 8 3 3 0 ∞ 4 5 4 4 5 2 ∞ 0 5 2 6 3 0 ∞ Далее просуммируем коэффициенты приведения: F1  10  9  9  11  11  1  51. Рассчитаем коэффициенты: K12  2  0  2 , K 21  0  1  1 , K 23  0  2  2 , K32  2  0  2 , K 45  2  3  5 , K54  1  4  5 . Получили два максимальных значения K 45 и K54 . Рассмотрим каждый из них. АЛЬТЕРНАТИВА 1. Положим X 45  1 и вычеркнем из матрицы и получим результат как в таблице 1.4. Таблица 1.4 – Приведенная матрица i\j 1 2 3 4 1 ∞ 0 2 5 2 0 ∞ 0 7 3 2 0 ∞ 4 5 1 6 3 ∞ В каждой строке и в каждом столбце должны стоять запреты (в данном случае это клетка (5, 1), так как уже имеется перемещение из 4 в 5 пункт). Матрица не является приведенной, так как в пятой строке нет нулевого коэффициента. Находим минимальный (клетка (5, 1), это значение 0 и преобразуем матрицу, как показано в таблице 1.5: 18

Таблица 1.5 – Приведенная матрица i\j 1 2 3 4 1 ∞ 0 2 5 2 0 ∞ 0 7 3 2 0 ∞ 4 5 0 5 2 ∞ Полученная матрица опять не является приведенной, в четвертом столбце нет нулевого элемента. Находим минимальный (клетка (3, 4), значение 4) и преобразуем матрицу, как показано в таблице 1.6. Таблица 1.6 – Приведенная матрица i\j 1 2 3 4 1 ∞ 0 2 1 2 0 ∞ 0 3 3 2 0 ∞ 0 5 0 5 2 ∞ Суммируем коэффициенты приведения с прежним значением F1 : F2  F1  1  4  51  1  4  56 . Рассчитаем коэффициенты: K12  1  0  1 , K 21  0  0  0 , K 23  0  2  2 , K32  0  0  0 , K34  0  1  1 , K51  2  0  2 . Опять получаем два максимальных элемента – K 23 и K51 . Рассмотрим каждый из них. АЛЬТЕРНАТИВА 1.1. Положим X 23  1 и вычеркнем из матрицы и получим что отображено в таблице 1.7: 19

Таблица 1.7 – Приведенная матрица i\j 1 2 4 1 ∞ 0 1 3 2 ∞ 0 5 0 5 ∞ В клетке (3, 2) ставим запрет. В каждой строке и в каждом столбе стоит нулевой элемент - матрица является приведенной. Рассчитываем коэффициенты: K12  1  5  6 , K34  2  1  3 , K51  5  2  7 . Максимальный коэффициент K51 , поэтому полагаем X 51  1 и вычеркнем из матрицы, которая представлена в таблице 1.8. Таблица 1.8 – Приведенная матрица i\j 2 4 1 0 ∞ 3 ∞ 0 В клетке (1, 4) ставим запрет и получаем X12  1 и X 34  1 . Окончательно получаем матрицу поездок: 0 0  X 11   0  0 1  1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0  0 .  1 0  При этом пройденное минимальное расстояние равно: F min  10  9  13  11  13  56 ( F2 ) . АЛЬТЕРНАТИВА 1.2. Положим X 51  1 и вычеркнем из матрицы (таблица 1.9): 20

Таблица 1.9 – Приведенная матрица i\j 2 3 4 1 0 2 ∞ 2 ∞ 0 3 3 0 ∞ 0 В клетке (1, 4) ставим запрет. Если матрица приведённая, рассчитываем: K12  2  0  2 , K 23  3  2  5 , K32  0  0  0 , K34  0  3  3 . Максимальный коэффициент K 23 , поэтому полагаем X 23  1 и исключаем из матрицы. Полученный результат виден в таблице 1.10. Таблица 1.10 – Приведенная матрица i\j 2 4 1 0 ∞ 3 ∞ 0 В клетке (3, 2) ставим запрет и получаем X12  1 и X 34  1 . В данном случае ответ будет таким же, как и в альтернативе 1.1. АЛЬТЕРНАТИВА 2. Положим X 54  1 и вычеркнем из матрицы, таблица 1.11 соответствует результату этой операции. Таблица 1.11 – Приведенная матрица i\j 1 2 3 5 1 ∞ 0 2 3 2 0 ∞ 0 8 3 2 0 ∞ 5 4 3 5 2 ∞ В клетке (4, 5) ставим запрет. Матрица не является приведенной – в 21

четвертой строке и пятом столбце нет нулевых элементов. Находим минимальный элемент в четвертой строке (значение 2) и преобразуем матрицу. Полученная матрица отображена в таблица 1.12. Таблица 1.12 – Приведенная матрица i\j 1 2 3 5 1 ∞ 0 2 3 2 0 ∞ 0 8 3 2 0 ∞ 5 4 1 3 0 ∞ Находим минимальный элемент в пятом столбце (значение 3 в клетке (1, 5)) и преобразуем матрицу и полученные результаты показаны в таблице 1.13. Таблица 1.13 – Приведенная матрица i\j 1 2 3 5 1 ∞ 0 2 0 2 0 ∞ 0 5 3 2 0 ∞ 2 4 1 3 0 ∞ Суммируем коэффициенты приведения с прежним значением F1 : F3  F1  2  3  51  2  3  56 . Рассчитаем коэффициенты: K12  0  0  0 , K15  0  2  2 , K 21  0  1  1 , K 23  0  0  0 , K32  2  0  2 , K 43  1  0  1 . Имеем два максимальных значения – K15 и K32 . Рассмотрим каждый из вариантов. АЛЬТЕРНАТИВА 2.1. Положим X15  1 и вычеркнем из матрицы, результат таблица 1.14). 22

Таблица 1.14 – Приведенная матрица i\j 1 2 3 2 0 ∞ 0 3 2 0 ∞ 4 ∞ 3 0 В клетке (4, 1) ставим запрет. Матрица является приведенной, поэтому рассчитаем коэффициенты: K 21  0  1  1 , K 23  0  0  0 , K32  2  3  5 , K 43  1  0  1 . Максимальный элемент K32 , поэтому полагаем X 32  1 и вычеркиваем из матрицы, как показано в таблице 1.15. Таблица 1.15 – Приведенная матрица i\j 1 3 2 0 ∞ 4 ∞ 0 В клетке (2, 3) ставим запрет и получаем X 21  1 и X 43  1 . Окончательно получаем матрицу поездок: 0 1  21 X  0  0 0  0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0  0 .  0 0  При этом пройденное минимальное расстояние равно: F min  13  10  9  13  11  56 ( F3 ) . АЛЬТЕРНАТИВА 2.2. Положим X 32  1 и вычеркнем из матрицы. Результаты представлены в таблице 1.16: 23

Таблица 1.16 – Приведенная матрица i\j 1 3 5 1 ∞ 2 0 2 0 ∞ 5 4 1 0 ∞ В клетке (2, 3) ставим запрет. Матрица является приведенной, поэтому рассчитаем коэффициенты: K43  1  2  2 . K 21  5  1  6 , K15  2  5  7 , Максимальный элемент K15 , поэтому полагаем X15  1 и вычеркиваем из матрицы, как показано в таблице 1.17. Таблица 1.17 – Приведенная матрица i\j 1 3 2 0 ∞ 4 ∞ 0 В клетке (4, 1) ставим запрет и получаем X 21  1 и X 43  1 . Получаем такую же матрицу поездок, как и в случае 2.1. Окончательно имеет два оптимальных решения: 0 0  1 X  0  0 1  1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0  0  1 0  и 0 1  2 X  0  0 0  0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0  0.  0 0  Минимальный пройденный путь равен Fmin  56 . Графически полученные решения изображены на рисунке 1.2: 24

а) б) Рисунок 1.2 – Графическое изображение решения (а) – решение 1, б) – решение 2) Как видно из представленного примера, аналитические методы являются весьма затратными с точки зрения времени даже при малой размерности задачи. При увеличении размерности задачи применение точных алгоритмов является затруднительным. 25

2 ПРИРОДНЫЕ АЛГОРИТМЫ 2.1 Описание и назначение природных алгоритмов На сегодняшний день существует большое множество природных вычислений или алгоритмов. Природными (естественными) вычислениями называют динамические модели, которые подсмотрены так или иначе у природы и созданы на основе природных процессов, например таких направлений: - процессы, протекающие в клетках; - эволюционные процессы естественного отбора; - процессы взаимодействия простых живых организмов; - информационные процессы; - процессы образования различных материалов и т. п. Возрастающая популярность природных алгоритмов в настоящее время определена с необходимостью параллельной обработки данных: с возможностью разработки искусственных биологических систем, с созданием новых парадигм вычислений и с исследованиями многообразия нашей природы. К классическим разделам природных вычислений относят на данный момент времени: клеточные автоматы, генетические алгоритмы и искусственные нейронные сети. Дальнейшие развитие работ в направлении заимствований у природных процессов сопутствовало к созданию различных новых разделов природных вычислений. К ним относятся ДНК-вычисления, роевой интеллект, аморфные вычисления, мембранные вычисления, искусственные иммунные системы и brainвычисления. И каждый алгоритм природных вычислений нашел свое определенное направление применений. Некоторые примеры приведены в таблице 2.1: 26

Таблица 2.1 – Примеры природных вычислений Вид вычислений Применение 1) ДНК-вычисления Создание ДНК-программ 2) Искусственные нейронные сети Распознавание образов, управление, прогнозирование, аппроксимация, классификация, принятие решений, кластеризация, сжатие данных 3) Роевой интеллект Распознавание образов, поиск кратчайшего пути 4) Бактериальные вычисления Создание машин Тьюринга на клетке 5) Клеточные автоматы Распознавание языка, моделирование физических систем, машина Тьюринга 6) Эволюционные вычисления Решение NP полных задач, поиск экстремумов Муравьиный и пчелиный алгоритмы – это относительно «молодые» (1992 и 2005 г. соответственно) алгоритмы, в основе которых лежит имитация поведения соответствующих насекомых. Данные алгоритмы считаются полиноминальными эвристическими алгоритмами для решения оптимизационных задач. Еще рассмотрим метод имитационный отжиг. Он относится к дискретной и комбинаторной оптимизации. 2.2 Муравьиный алгоритм Алгоритм оптимизации подражанием муравьиной колонии (ACO – Ant Colony Optimization) – это один из эффективных и перспективных полиномиальных алгоритмов для решений задач маршрутизации транспорта, в частности для нахождения приближённых решений задачи коммивояжёра. Также алгоритм применяется для решения аналогичных задач поиска маршрутов на графах. Суть данного подхода заключается в анализе и использовании модели поведения этих насекомых, ищущих пути от колонии к источнику питания, и представляет собой метаэвристическую оптимизацию. 27

Первая версия алгоритма, предложенная доктором наук Марко Дориго в 1992 году, была направлена на поиск оптимального пути в графе [10]. Поведение муравьев выдержало испытания далеко не в лабораторных условиях, а на протяжении 100 миллионов лет – именно столько времени назад появились муравьи на Земле. Муравьи относятся к социальным насекомым, живущим внутри некоторого коллектива – колонии [17]. Муравьиные алгоритмы являются хорошо зарекомендовавшими себя метаэвристическими методами для нахождения приближенных решений прикладных оптимизационных задач на графах. Суть подхода заключается в моделировании поведения реальной колонии муравьев, которые способны находить кратчайшие пути в процессе кормодобывания [18]. Ряд других исследователей также внесли весомый вклад в развитие муравьиных алгоритмов, среди них Colorni A., Maniezzo V., Deneubourg J.-L., Gambardella L.M. и др. [19]. Муравьиные алгоритмы относят к группе алгоритмов так называемого «роевого интеллекта». Также их рассматривают в теории искусственного интеллекта, как методы оптимизации. Муравьи отличаются общественным образом жизни и живут в колониях, которые состоят из большого количества взаимодействующих индивидуумов. Поведение муравьев является коллективным, а колония муравьев – самоорганизующаяся система. С помощью самоорганизации муравьи, сравнительно простые агенты, которые способные решать сложные задачи: нахождение кратчайших путей, решение задач о назначениях рабочей силы и др. Еще они могут эффективно поддерживать осмысленное поведение, даже если их большинство неспособно взаимодействовать. Стигмергия это тип взаимодействия, когда один индивидуум изменяет некий элемент окружающей среды, а остальные в дальнейшем используют информацию об его состоянии. Этот механизм является главным в организации в муравьиных колониях [20]. 28

Занимаясь кормодобыванием и проходя от муравейника до источника пищи и обратно, муравьи оставляют феромон на своем пути, образуя таким образом след феромона [21]. Феромон – химическое вещество, вырабатываемое специальными клетками насекомых. Муравьи той же колонии могут чувствовать феромон и склонны вероятностно выбирать пути, помеченные более сильными концентрациями феромона. Распределение феромона по пространству передвижения муравьев является своего рода динамически изменяемой глобальной памятью колонии. Коллективное поведение муравьев исследовалось в ходе экспериментов в контролируемых условиях энтомологами [22]. На рисунке 2.1 иллюстрируется принцип работы муравьиного алгоритма, на примере поисков муравьями пищи [16]. Рисунок 2.1 – Пути прохождения муравьев Когда на обычном пути, как показано на рисунке 2.1.А, у муравьев возникает преграда, им необходимо вычислить новый оптимальный маршрут. Это видно на рисунке 2.1.В. Как только муравьи доберутся до преграды, им с равной вероятностью нужно будет обходить её слева и справа. И те муравьи, которые случайно выбрали наикратчайший «левый» путь, как видно на рисунке 2.1.С., будут соответственно быстрее его проходить, и за некое количество времени маршрут будет более обогащён феромоном, чем иной путь. 29

И поэтому следующие муравьи будут предпочитать именно такой вариант пути, который показан на рисунке 1.D. И тем самым продолжат его обновлять феромоном до тех пор, пока этот вариант каким-то образом не станет им недоступным. Муравьиный алгоритм непосредственно строит решение из комбинации уникальных элементов, выбираемых из конечного набора. Целью решения является поиск оптимальной комбинации элементов. Выбор элементов решения из множества допустимых элементов осуществляется вероятностно на каждом шаге построения решения, исходя из значений феромонного уровня и эвристической функции ребер графа [23]. Одна итерация алгоритма подразумевает построение каждым из муравьев колонии одного допустимого решения задачи. Феромонный уровень компонент периодически обновляется согласно следующему правилу: феромон ребра получает приращение, пропорциональное качеству (в случае минимизационной задачи качество обратно пропорционально значению целевой функции) решения, в которое это ребро входит [3]. Выбор задачи коммивояжера для иллюстрации идей муравьиных алгоритмов обусловлен следующими факторами [24]: 1. Задача очень наглядно интерпретируется в терминах поведения муравьев – перемещения муравьев и бродячего торговца интуитивно понятны и сопоставимы. 2. Это дидактическая задача, с помощью которой можно просто, без злоупотребления терминами алгоритма, объяснить суть нахождения оптимального решения. 3. Это традиционный тестовый полигон для методов комбинаторной оптимизации. Имеется огромная база учебных задач о коммивояжере и их методов решений. Многократность взаимодействия реализуется итерационным поиском маршрута коммивояжера одновременно несколькими муравьями. 30

При этом каждый муравей рассматривается как отдельная единица (независимый коммивояжер), которая решает свою задачу. Каждый муравей за одну итерацию алгоритма проходит полный маршрут коммивояжера [25]. Положительная обратная связь реализуется как имитация поведения муравьев типа «оставление следов – перемещение по следам». Чем больше следов оставлено на тропе – ребре графа в задаче коммивояжера, тем больше муравьев будет передвигаться по ней [26]. При этом на тропе появляются новые следы, которые привлекают дополнительных муравьев. Для задачи коммивояжера положительная обратная связь реализуется следующим стохастическим правилом: вероятность включения ребра графа в маршрут муравья пропорциональна количеству феромона насекомого на нем [26]. Применение такого вероятностного правила осуществляет реализацию и иной составляющей самоорганизации – случайности. Количество феромона, который оставляют муравьи на ребре графа, обратно пропорционально дистанции маршрута. И получается так, что чем короче маршрут, тем больше феромона будет оставлено на соответствующих ребрах графа и тем больше других муравьев будет пользоваться данным маршрутом при передвижении. Оставленный феромон на ребрах выступает как усилитель, который позволяет оптимальным маршрутам сохраняться в глобальной памяти муравейника. При последующих итерациях алгоритма такие маршруты могут быть улучшены. Применение только положительной обратной связи может привести к преждевременной сходимости решений. Это когда все муравьи передвигаются одним и тем же субоптимальным путем. Для избегания от такого эффекта, применяется отрицательная обратная связь, а именно испарение феромона. Время испарения не должно быть слишком большим (возникновение сходимости популяции маршрутов к одному субоптимальному решению), но и не должно быть слишком малым. Иначе это приведет к быстрому «забыванию» действующих маршрутов и потере памяти колонии. И это все впоследствии чревато некооперативным поведением муравьев. 31

Кооперативность в поведении муравьев является очень важной чертой, так как множество одинаковых муравьев в один момент времени исследуют различные точки пространства решений и соответственно передают свой опыт через преобразование ячеек глобальной памяти муравейника. Для каждого муравья перемещение из города i в город j зависит от трех компонентов: 1) память муравья; 2) видимости; 3) виртуального следа (феромона). Память муравья – это список посещенных муравьем городов (точек), которые проходить повторно нельзя. И используя этот список, муравей гарантированно не пройдет в один и тот же город дважды. Так называемый табулист будет возрастать при прохождении маршрута и обнулится при прохождении каждой новой итерации алгоритма. Обозначим через J i ,k список городов, которые еще необходимо посетить муравью k, находящемуся в городе i. Следует, что J i ,k будет являться дополнением к памяти муравья [27]. Видимость – величина, обратная расстоянию: U  1 / DU , где DU – расстояние между городами i и j . Видимость – это локальная статическая информация, выражающая эвристическое желание посетить город j из города i – чем ближе город, тем больше желание посетить его. Использование только видимости, конечно, является недостаточным для нахождения оптимального маршрута [27]. Виртуальный след на ребре  i, j  представляет подтвержденное муравьиным опытом желание посетить город j из города i . В отличие от видимости след феромона является более глобальной и динамичной информацией – она изменяется после каждой итерации алгоритма, отражая приобретенный муравьями опыт. Количество виртуального феромона на ребре  i, j  на итерации t обозначим через. U (t ) [27]. 32

Самую важную роль в муравьиных алгоритмах выступает вероятностно пропорциональное правило, которое ищет вероятность перемещения k - го муравья из города i в город j на t - й итерации:    U (t )   U   ,  PU ,k      ( t )        il il если j  J i ,k ,  i ji , k   PU ,k (t )  0, если j  J i ,k , где (4)  – настраиваемый параметр, который задает вес следа феромона;  – настраиваемый параметр, который задает видимость феромона при вы- боре пути. При   0 будет выбран близкий город (точку), как определяется жадным алгоритмом в классической теории оптимизации. А если   0 , тогда работает будет лишь феромонное усиление, которое влечет за собой только быстрое упрощение маршрутов к единому субоптимальному решению. Стоит отметить, что в формуле 4 сформировываются лишь вероятности выбора того или другого города. Непосредственно выбор каждого города выполняется по принципу «колеса рулетки»: каждый город на ней имеет свой сектор с площадью. Для выбора города нужно бросить шарик на рулетку, где сгенерируется случайное число и определиться сектор, на котором этот шарик остановится. И отметим, что правило хоть не изменяется на протяжении итерации, но значения вероятностей, PU ,k (t ) для двух муравьев в одном и том же городе могут отличаться, так как, PU ,k (t ) функция от JU ,k – список еще не посещенных городов k - ым муравьем. После завершения своего маршрута каждый муравей k оставляет на ребре  i, k  определенное количество феромона, которое определяется:  Q , если (i, j )  Tk (t ),  U ,k (t )   Lk ( t ) 0, если (i, j )  T (t ), k  (5) 33

где Tk (t ) – путь, пройденный муравьем k на итерации t ; Lk (t ) – длина данного пути; Q – настраиваемый параметр, значение которого можно выбрать одного порядка с длиной оптимального маршрута. Для исследования всего пространства решений необходимо обеспечить испарение феромона – уменьшение во времени количества, отложенного на предыдущих итерациях феромона [28]. Если обозначить коэффициент испарения феромона через p  0,1 , тогда правило его обновления примет вид: U (t  1)  (1  p)  U (t )  U (t ), (6) m где   U (t )   U , k (t ), m – количество муравьев в колонии. k 1 В начале оптимизации алгоритмом, значение феромона приравнивают к небольшому положительному числу 0 Общее количество муравьев в колонии остается постоянным на протяжении выполнения алгоритма. Многочисленная колония приводит к быстрому усилению субоптимальных маршрутов, а когда муравьев немного, возникает опасность потери кооперативности поведения изза быстрого испарения феромонов и ограниченного взаимодействия между муравьями. Как правило число муравьев назначают равным количеству городов – каждый муравей начинает маршрут со своего города [29]. Для улучшения временных характеристик работы муравьиного алгоритма добавляют так называемых элитных муравьев. Элитный муравей укрепляет ребра оптимального маршрута, который найден с начала работы алгоритма. Количество феромона, оставляемого на ребрах наилучшего потенциального маршрута 𝑇 + , принимают равным Q / L , где L – длина маршрута T  . 34

Этот феромон подталкивает муравьев к исследованию решений, содержащих несколько ребер наилучшего на данный момент пути T  . Если в муравейнике имеются элитные муравьи, то ребра маршрута T  будут получать общее усиление, как показано ниже: e  e  Q / L . (7) 2.3 Имитационный отжиг Метод имитации отжига (SA - Simulated Annealing) – алгоритм решения оптимизационных задач, который создан на моделировании реального физического процесса, а именно кристаллизации вещества из жидкого состояния в твёрдое (например отжиг металлов). История метода отжига начинается с 1953 года. В этом году Н. Метрополисом был разработан алгоритм симуляции установления равновесия в системе с множеством степеней свободы при заданной температуре [30]. В начале 80-х XX века у профессора Д. Киркпатрика впервые появилась идея применять данный алгоритм не только для моделирования физических систем, но и к решению определенных задач оптимизации. В настоящее время метод имитационного отжига используется для решения многих оптимизационных задач, которые связаны с финансами, компьютерной графикой, комбинаторикой, телекоммуникационными сетями и т.п. Очень часто метод отжига применяют для обучения нейронных сетей. Впервые описанный в [31] алгоритм имитации отжига представляет собой метаэвристический алгоритм, который находит глобальный минимум целевой функции. На рисунке 2.2 показан общепонятный принцип работы метода имитационного отжига, на примере спуска с горы лыжника [30]. 35

Рисунок 2.2 – Схема работы метода имитационного отжига Алгоритм имитации отжига является методом решения задачи глобальной оптимизации, в частности комбинаторной и дискретной оптимизации. Метод основывается на имитации физического процесса, который происходит при кристаллизации вещества. Когда атомы уже выстроились в кристаллическую решетку, но еще допустимы переходы отдельных атомов из одной ячейки в другую, то процесс будет протекать при постепенно понижающейся температуре. Перемещение атомов из одной ячейки в другую происходит с некоторой вероятностью, причем она будет только уменьшается с понижением температуры. Устойчивая кристаллическая решетка определяется минимумом энергии атомов, и поэтому атом может либо перейти в состояние с меньшим уровнем энергии, либо остается на месте [32]. После выше описанного можно сформулировать следующие моменты: 1. целью метода является приведение системы в состояние с наименьшей энергией; 36

2. совокупность позиций всех атомов — это состояние системы, где каждому состоянию соответствует определенный уровень энергии. Метод имитационного отжига имеет как свои преимущества, так и недостатки по сравнению с другими методами/алгоритмами глобальной оптимизации. К его преимуществам стоит отнести относительную простоту реализации метода и универсальность применения для многих комбинаторных задач. А недостатками будут являться необходимость многократных тестов для лучшего подбора параметров алгоритма, так как результат работы данного алгоритма сильно зависит от этих настраиваемых параметров. Для каждой задачи и реализации параметры могут существенно варьироваться, что делает проведение тестов неотъемлемым этапом метода. Рассмотрим алгоритм для решения задачи коммивояжера. Пусть имеется n городов с заданными координатами  xi , yi  . По известным координатам можно вычислить расстояние между каждой парой городов. Множество S представляется собой вектора, координатами которых являются всевозможные перестановки натуральных чисел от 1 до n . Добавляя к каждому такому вектору  n  1 -й элемент, равный первому элементу, будем получать всевозможные кольцевые маршруты. Каждому вектору s  S будет соответствовать «энергия», равная длине f (s) соответствующего кольцевого маршрута. Тогда алгоритм может быть описан 5 этапами, которые представлены далее. Этап I. Выбирается стартовая точка s 0  S и параметр T0 . В качестве начального вектора s 0 будем брать случайный вектор из S . Параметр T0 будет соответствовать начальному значению температуры (при реализации алгоритма положили начальное значение равным T0  1 ). Этап II. На  k  1 - й итерации выбирается некоторое пробное решение – вектор q k 1  S – в соответствии с заданным правилом D  , s k  . 37

Новое решение q k 1 генерируется из текущего s k путем перестановки двух случайных городов. Этап III. Случайно задается значение pk 0,1 согласно закону равномерного распределения. Дальнейшие подведение к решению выбирается по этому правилу: S k 1 k k 1 k k 1  q , если pk  A  s , q ,Tk  ,    sk иначе. (8) Основной особенностью алгоритма является его способность на каждом шаге принимать решения, увеличивающие значение целевой функции, что позволяет ему «выбираться» из локальных минимумов [33]. В качестве функции, осуществляющей принятие решение о том, принимать ли новое значение в качестве решения, может быть выбрана функция Метрополиса [34]:   f  q   f  s   A  s, q, T   min 1,exp    . T    (9) Функция Метрополиса всегда принимает положительное решение о принятии очередного q k 1 в качестве нового приближения в случае, если оно уменьшает значение f , т.е. f  qk 1   f  s k  . В то же время с определенной вероятностью может быть принято решение, увеличивающее значение целевой функции. Это свойство позволяет алгоритму не остаться в локальном минимуме. Вероятность принятия положительного решения в случае увеличения значения целевой функции зависит от параметра T , представляющего «температуру» системы. Легко заметить, что в случае, когда Tk   0, A s, q, T   0 при k   . Таким образом, вероятность принятия нового приближения, увеличивающего значение f уменьшается с ростом количества итераций. Другим возможным вариантом функции принятия нового приближения может являться, так называемый функция Баркера [35]: 38

1   f  q   f  s   A  s, q,T   1  exp   . T    (10) Важным отличием критерия Баркера от функции Метрополиса является то, что первый может не принимать решения, уменьшающие значение целевой функции, особенно те, что незначительно улучшают его. Однако с уменьшением параметра T вероятность принятия лучших решений увеличивается. В работе реализованы функции принятия новых приближений – функция Метрополиса и функция Баркера. Этап IV. Пересчитывается параметр (температуру) Tk 1  U T0 , k  . Определять температуру нужно в каждой точке индивидуально, функция определения температуры должна быть монотонно убывающей. Исторически первой схемой охлаждения была, так называемый схема Больцмана [36]: Tk 1  T0 / ln(1  k ) . Основной недостаток (11) схемы Больцмана – медленное убывание температуры, что может приводить к медленной сходимости алгоритма. Альтернативной схемой охлаждения является схема Коши [37]: Tk 1  T0 / (1  k ) . (12) В литературе встречается также экспоненциальный закон понижения температуры, определяемой формулой [38]: Tk 1  T0  ec ( k 1) , где (13) c  0 – некоторая константа; и геометрическая функция [39] Tk 1    Tk , где (14)  (0,1) . В реализации алгоритма для понижения температуры используется схема Коши [37]. Этап V. Проверяется условие остановки. Если оно не выполняется, устанавливается k  k  1 и происходит возврат к этапу II. 39

В качестве критерия остановки итераций используется достижение заданного Tmin , которая рассчитывается по формуле: Tmin  Tmax / kmax . (15) 2.4 Пчелиный алгоритм Алгоритмы пчелиной оптимизации (ABC - Artificial Bee colony optimization) – это одни из новейших природных многоагентных алгоритмов, основанных на моделировании роевого интеллекта (Swarm Intelligence). У данного алгоритма имеются высокоэффективные варианты/виды, которые предназначены для решения задач непрерывной оптимизации. Первые статьи по этим алгоритмам были опубликованы в работах Фама (D.T. Pham) с соавторами в 2005 г. Основная идея алгоритмов состоит в моделировании поведения пчел при поиске нектара [40-41]. Из них наиболее известных подвидов алгоритма стоит отметить: 1) пчелиный алгоритм (Bees algorithm, B-алгоритм); 2) алгоритм колонии искусственных пчел (Artificial Вее Colony, АВС). Данные виды успешно применяют для решения комбинаторных задач [42]. Для описания поведения пчел в природе применяют следующую терминологию: источник нектара (food sources), рабочие пчелы (worker bees), пчелы-разведчики (scout bees, scouts), пчелы-наблюдатели (onlooker bees). Радиус области поиска роем медоносных пчел может быть от 10 и более километров, что как раз и предоставляет высокую вероятность нахождения большего числа источников нектара. «Стратегию» поведения роя можно представить так: Можно выделить несколько аспектов, в поведении пчел в природе: - чем ближе будет источник и выше его качество, то тем больше пчел полетят за данным разведчиком. - при возвращении в улей пчелы снова исполняют свой танец, вербуя но- вых последователей и т. д. - такая процедура допускает пчелиной колонии достаточно эффективно выполнять поиск и сбор нектара на больших площадях. 40

Поведение пчелиной колонии можно рассматривать как адаптивное. В то время как другие пчелы собирают нектар, искать новые перспективные места продолжают разведчики. Это позволяет вести колонии мониторинг общей ситуации, т.е. как только некоторый источник нектара начнет иссякать, пчелы начинают перестраиваться на другие новые источники. На рисунке 2.3 продемонстрирован принцип поведения пчел в природе. Рисунок 2.3 – Поведение пчел в природе Для описания поведения пчел в природе используют определенные понятия [43]: - источник нектара (food sources); - рабочие пчелы (worker bees); - пчелы-разведчики (scout bees, scouts); - пчелы-наблюдатели (onlooker bees). Источник нектара описывается своей значимостью (определяются различными параметрами) и полезностью. Значимость определяют три фактора: удаленность от улья, концентрация нектара и удобство его добычи. 41

Рабочие пчелы (занятые фуражиры) это пчелы, которые связаны с одним из источников нектара, т.е. добывают на нем нектар. Занятые фуражиры обладают информацией о «своем» источнике нектара, которую получили непосредственно от пчел-разведчиков: 1. направление от улья на источник; 2. полезность источника. Фуражиры как правило закреплены за источниками нектара. В таких участках количество пчел больше, чем на прочих. Пчелы-разведчики (пчелы-скауты) выполняют непосредственно поиск источников нектара. Примерное количество разведчиков в рое составляет 5 – 10% от всего числа. Пчелы-наблюдатели выполняют некоторые работы в улье. За пчелой-разведчиком может следовать каждый незанятый фуражир к источнику нектара. С помощью своего «танца» она вербует незанятых пчел на специальной площадке улья - область танцев. После танца уже завербованная пчела следует за соответствующей пчелой-разведчиком к области с нектаром и становится занятым фуражиром. Вербовку выполняют только те пчел-разведчики, которые сумели найти участки нектара с полезностью выше определенного порога. И далее занятый фуражир после добычи нектара возвращается в улей, чтоб оставить его там. После этого у фуражира остается три варианта действий: 1) продолжить заготовку нектара из прежнего источника, не вербуя дру- гих пчел; 2) оставить «свой» источник нектара и стать незанятым фуражиром; 3) выполнить вербовку свободных пчел. Выбор пчелы из указанных действий осуществляется по определенному вероятностному закону. Одновременно в пределах так называемых областей танцев. Разные пчелы могут «рекламировать» свои участки нектара. Логика принятия решений с которыми пчела принимает решение следовать за той или иной пчелой-вербовщиком, на данный момент недостаточно хорошо исследованы. 42

Из всего выше сказанного можно сделать вывод, что самоорганизация пчелиного роя основывается на четырех следующих основных механизмах. Положительная обратная связь - основываясь на информации, полученной от других пчел, пчела летит к одному из источников нектара. Отрицательная обратная связь - уравновешивает положительную обратную связь и помогает стабилизировать коллективный шаблон поведения. То есть на основе информации полученной от других пчел, данная пчела может решить так, что «ее» источник нектара значительно хуже других найденных источников, и его стоит оставить ради более перспективного источника нектара. Множественность взаимодействия - информация об источнике нектара, добытой одной пчелой, передается многим другим пчелам улья, по цепочке. Случайность (случайные блуждания, ошибки, вероятностный поиск) – нужна для лучшего функционирования роевого интеллекта, которая позволяет рою находить новые решения. Главная идея модели пчелиной колонии состоит в использовании двухуровневой стратегии поиска: с помощью пчел разведчиков определяется множество перспективных источников и, далее, с помощью пчел фуражиров осуществляется исследование окрестностей данных источников. Главной целью пчелиной колонии является поиск источника, содержащего как можно большее количество нектара, при этом качественного. Это количество определяет значение целевой функции в исследуемой оптимизационной задаче. В данном случае нужно найти оптимальное решение задачи кольцевого маршрута. Стоит отметить, что метод роя пчёл можно эффективно распределить на несколько параллельных процессов, за счёт чего значительно увеличится его скорость поиска решения. Также стоит отметить высокую скорость работы алгоритма. 43

3 РЕАЛИЗАЦИЯ И ТЕСТИРОВАНИЕ АЛГОРИТМОВ Под реализацией и тестированием алгоритмов предполагается: 1) моделирование решения задачи с помощью только ППП MATLAB; 2) нахождение итерационным путем используемых коэффициентов для каждого алгоритма/метода. За основу разрабатываемых программ был взят код из статьи, которая была опубликована в интернет-ресурсе сообщества IT-специалистов [44]. В ходе работы над магистерской диссертацией программы были модернизированы и подведены для поставленной задачи и ее условий. Стоит отметить, что каждый алгоритм выполняется в отдельном собственном MATLAB файле. Основными общими параметрами для всех методов являются количества итераций (проходов) природного вычисления и количества точек (адресов) кольцевого маршрута. Также для вычислений используются входные параметры: матрица координат и матрица расстояний. Матрица координат — это неквадратная матрица, в которой определяется положение точек(адресов) на плоскости двумя координатами, по типу «широтадолгота». Координаты нужны как для расчета и заполнения матрицы расстояний, так и для графического отображения решения задачи оптимизации. В данной главе матрица заполняется случайным образом, в диапазоне значений от 0 до 100. Матрица расстояний — это квадратная матрица вида «объект-объект», которая содержит в себе элементы расстояний между объектами в метрическом пространстве. В данном случае предполагаются расстояния между точками (адресами) кольцевого маршрута. Размерность матрицы зависит от количества выбранных точек для маршрута. За счёт этих данных и происходит поиск оптимального маршрута для задачи коммивояжера. В дальнейшем во всех будущих экспериментах количество точек будет применяться из 3 вариантов: 10, 30 и 50 точек. А количество итераций будет уже подбираться в зависимости от эффективности работы алгоритма. 44

Здесь матрица расстояний будет рассчитываться по выведенной формуле из теоремы Пифагора на основе соответствующих координат точек. А вот в следующей главе заполнение предполагается уже на основе реальных дистанций между адресами, которые будут взяты с поисково-информационной картографической службы компании Яндекс. В последующих пунктах, будут рассматриваться алгоритмы и их программы по отдельности. 3.1 Муравьиный алгоритм На рисунке 3.1 продемонстрирована обобщённая схема вычислительной программы «Ant Colony Algorithm», которая осуществляет все идеи пункта 2.2. Рисунок 3.1 –Блок-схема алгоритма 45

Итак, рассмотрим основные части программного кода в среде разработки MATLAB и их предназначение. Опишем первую часть программы. На коде ниже представлены команды, которые очищают рабочее пространство, командную строку и закрывает все окна среды разработки: clc;clear;close;clearvars;close all; % очистка данных и закрытие окон tic; % начало отсчета На следующем фрагменте кода соответствует инициализация параметров алгоритма и создание матриц с нулевыми значениями: nCity = 50; % выбор кол-ва точек маршрута, от 3 до 50 age = [nCity*0.1 nCity*0.2 nCity*0.4 nCity*... 1.6 nCity*3.2 nCity*6.4]; % выбор кол-ва итераций (поколений) dist = zeros(nCity,nCity); % матрица расстояний returndist = zeros(nCity,nCity); % матрица обратных расстояний cities = rand(nCity,2)*100; % случайная генерация координат городов countage = nCity; % кол-во муравьев в поколении RANDperm = randperm(nCity); Матрица координат заполняется засчет функции генерации случайных чисел – rand, в интервале 0-100. У данной матрицы изменяется только количество строк – зависит от выбранного количества точек. Так как используется двухосевая система координат, в матрице только 2 столбца. Также в этой части программы заполняются данными нулевые матрицы расстояний и обратных расстояний: % заполнение матрицы расстояний и обратной матрицы расстояний for i = 1:nCity for j = 1:nCity dist(i,j)= sqrt((cities(i,1) - cities(j,1)... )^2 + (cities(i,2) - cities(j,2))^2); % вычисление дистанции if i ~= j returndist(i,j) = 1/dist(i,j); % вычисление обратной дистанции 46

end end end Матрица расстояний рассчитывается с помощью выведенной формулы из теоремы Пифагора, которая позволяет найти расстояние между двумя точками на плоскости [45]: S где  x2  x1    y2  y1  2 2 , (16) S – расстояние между двумя точками; x1 , x2 - координаты точек по первой оси; y1, y2 - координаты точек по второй оси. А матрица обратных расстояний наполняется за счет значений матрицы расстояний, в том же цикле. Она нужна для вероятностных вычислений в «теле» алгоритма. На следующем представленном коде отображены настройки для данного алгоритма: a = 1; % коэффициент запаха b = 4; % коэффициент расстояния ro = 0.5; % коэффициент испарения (память поколений) Q = 1; % количество выпускаемых феромонов elite = 1; % количество элитных муравьев ph = 0.01; % начальное значение феромон tao = ph*(ones(nCity,nCity)); % матрица начальных феромонов Они представлены в виде констант, которые подбирались как правило экспериментальным путем. Далее следующем фрагменте представлена инициализация матриц и массивов в основной части цикла алгоритма программы: ROUTEant = zeros(countage,nCity % матрица маршрута муравьев в одном поколении 47

DISTant = zeros(countage,1); % вектор расстояний муравьев в одном поколении ROUTE = zeros(1,nCity+1); % оптимальные маршруты P = zeros(1,nCity); % матрица вероятностей bestROUTE = zeros(1,nCity); % лучший маршрут DistAge = zeros(age(count),1); % хранение дистанций каждого поколения bestDIST = inf; % лучший начальный маршрут err = 0; % счетчик ошибок в вероятностях На фрагменте кода ниже соответствует 2 часть программы – работа алгоритма: for s = 2:nCity ir = ROUTEant(k,s-1); % индекс выбранной точки % заполнение матрицы вероятностей P = tao(ir,:).^a .*returndist(ir,:).^b; P(ROUTEant(k,1:s-1)) = 0; P = P./sum(P); % определение точки, куда был переход RANDONE = rand; getcity=find(cumsum(P)>=RANDONE,1,'first') % проверка на ошибку в вероятностях if isempty(getcity) == 1 err =+ 1;getcity = 1; end % s-ый точек -> путь k-ому муравью ROUTEant(k,s) = getcity; end Здесь определяется порядок следования каждого муравья по маршруту. А именно, вычисляется вероятность перехода муравья от одной точки к другой. Значимый параметр в этом моменте является tao. Это так называемый «феромон», который оставляет каждый виртуальный муравей на точке. 48

Чем больше значение феромона, тем больше вероятность, что эту точку муравьи будут предпочитать чаще, чем другие точки. Следующий фрагмент кода: ROUTE = [ROUTEant(k,1:end),ROUTEant(k,1)]; % маршрут k-ого муравья В переменную ROUTE записывается порядок следования муравья по точкам. Например, при маршруте из 5 точек может получится таким – 4,2,3,1,5,4. Первая и последняя цифра должны быть одинаковыми, так как маршрут должен быть кольцевым (замкнутым). Следующий цикл в фрагменте кода отвечает за подсчет суммарного значения расстояния текущего маршрута: for i = 1:nCity % вычисление маршрута k-ого муравья S = S + dist(ROUTE(i),ROUTE(i+1)); end С помощью матрицы расстояний и массива с порядком точек вычисляются соответствующие расстояния между точками. В последнем цикле сравнивается текущая дистанция с лучшей, и если первая меньше второй, то текущая будет лучшей на выполняемом цикле: % присвоение лучшего маршрута и S if DISTant(k) < bestDIST bestDIST = DISTant(k); % лучшая дистанция маршрута bestROUTE = ROUTEant(k,1:end); % порядок точек маршрута end В фрагменте ниже, текущий цикл отвечает за добавление/испарение значения феромона на каждой точке выбранного маршрута: % испарение феромонов "старого" пути tao = (1-ro)*tao; for u = 1:countage % получение маршрута u-ого муравья для каждой точки 49

for t = 1:nCity ROUTE = [ROUTEant(u,1:end),ROUTEant(u,1)]; x = ROUTE(t); y = ROUTE(t+1); % подсчет нового феромона if DISTant(u) ~= max(DISTant) % добавка феромона в зависимости от S tao(x,y) = tao(x,y) + Q/DISTant(u); else % усиление ребра лучшего пути tao(x,y)=tao(x,y)+(elite*Q)/... DISTant(u); end end end На следующем фрагменте реализованный код выводит рисунки с графиками, которые иллюстрируют кольцевой маршрут и его основные важные характеристики (количество точек, дистанция маршрута, количество итераций): bestDIST = round(bestDIST); % Вывод результатов и построение графиков figure(count); % создание график citiesOP(:,[1,2]) = cities(bestROUTE(:),[1,2]); % загрузка координат точек plot([citiesOP(:,1);citiesOP(1,1)],... [citiesOP(:,2);citiesOP(1,2)],... 'LineWidth',1,... 'Color','#b05612',... 'Marker','o',... 'MarkerFaceColor','red',... 'MarkerSize',8); % построение графика маршрута и настройка графика xlabel('X');ylabel('Y');grid on; % вывод подписей осей графиков title(['Точек: ', num2str(nCity),... ', Дистанция: ',num2str(bestDIST),... 50

', Итераций: ',num2str(age(count))]); % вывод строк над графиками set(findall(gcf,'type','axes'),'fontsize',10); % настройка размера шрифта set(findall(gcf,'type','text'),'fontSize',14); % настройка размера шрифта Результаты вывода представлены на дальнейших рисунках, например на рисунке 3.8. В последней 3 части программы происходит вывод времени работы текущего алгоритма: timerVal = toc; % фиксация времени работы программы disp("Общее затраченное время на расчет "... + "маршрута: "+ round(timerVal) +" сек."); % вывод потраченного времени Для более лучшего решения задачи подбирались оптимальные значения коэффициентов и параметров текущего алгоритма. По этой части были проведены многочисленные опыты, которые в дальнейшем анализировались для успешного выбора значений регулируемых коэффициентов. Некоторые результаты этих работ были опубликованы в научных статьях [4, 6]. Итак, были проведены предварительные вычислительные эксперименты для определения наилучшего количества итераций при различном числе городов. Под наилучшим понимается такое количество итераций, при котором длина кольцевого маршрута принимает минимальное значение. Варианты количеств точек приняли 10, 30 50. Стартовое значение коэффициентов запаха и расстояния соответственно –   1,   2 . Для каждого количества городов, при различных количествах итераций выполняли по три прогона (т.е. три опыта) алгоритма с отличным друг от друга расположением городов. Результаты построенных графиков представлены на рисунке 3.2. 51

Длина пути, усл. ед. Результаты расчетов при 10 точках Опыт №1 Опыт №2 Опыт №3 350 330 310 290 270 250 0 10 20 30 40 50 60 Количество итераций Рисунок 3.2 – График зависимости, расстояний и итераций При 15 итерациях расчетов алгоритма, оптимальный маршрут найден. Маршруту с 30 точками соответствует рисунок 3.3. Результаты расчетов при 30 точках Длина пути, усл. ед Опыт №1 Опыт №2 Опыт №3 520 510 500 490 480 470 460 450 440 0 20 40 60 80 100 120 140 160 180 200 Количество итераций Рисунок 3.3 – График зависимости, расстояний и итераций При 100 итерациях расчетов алгоритма, оптимальный маршрут найден. Маршруту с 50 точками соответствует рисунок 3.4. 52

Результаты расчетов при 50 точках Длина пути, усл. ед Опыт №1 Опыт №2 Опыт №3 700 650 600 550 500 0 50 100 150 200 250 300 Количество итераций Рисунок 3.4 – График зависимости, расстояний и итераций При 150 итерациях расчетов алгоритма, оптимальный маршрут найден. По ним можно сделать вывод, а именно какой минимальный порог итераций для оптимального решения задачи. Также были выполнены ряд экспериментов с изменением значений констант ,  . При каждом наборе рассматриваемых параметров и определенных количествах итераций, которые взяты с предыдущих исследованиях. Из полученных результатов были построены рисунки с графиками. Длина пути, усл. ед На рисунке 3.5 продемонстрирована диаграмма результатов при 10 точках. При 10 точках и 30 итерациях 500 400 300 200 100 0 α=0 β=1 α=1 α=2 β=2 α=3 β=3 β=4 α=4 α=5 β=5 Рисунок 3.5 – График зависимости, расстояний и коэффициентов ,  Постоянные результаты получаются при   1 и 2    5 . Результаты при 30 точках соответствует рисунок 3.6. 53

Длина пути, усл. ед При 30 точках и 200 итерациях 1000 800 600 400 200 0 α=0 β=1 α=1 α=2 β=2 α=3 β=3 β=4 α=4 α=5 β=5 Рисунок 3.6 – График зависимости, расстояний и коэффициентов ,  Стабильные результаты получаются при   2 и 3    5 . Результаты при Длина пути, усл. ед 50 точках соответствует рисунок 3.7. При 50 точках и 300 итерациях 500 400 300 200 100 0 α=0 β=1 α=1 α=2 β=2 α=3 β=3 β=4 α=4 α=5 β=5 Рисунок 3.7– График зависимости, расстояний и коэффициентов ,  Стабильные результаты получаются при   2 и   1 . Из всех полученных расчётов можно сделать следующие выводы о лучших значениях настраиваемых параметров: - среднее оптимальное значение параметра можно принять   1 ; - оптимальность расчёта при различных значениях параметра  зависит от ряда иных факторов (количество итераций и точек), можно принять, что оптимальное значение параметра   2,5 . 54

Для графического отображения получаемых решений были выполнены расчеты при 50 точках, но при разных количествах итераций. Результаты вывода программы представлены на рисунке 3.8. а) б) в) г) д) е) Рисунок 3.8 – Маршруты задачи коммивояжера для 50 городов, при   1,   4 (а – 5 итераций, б – 10 итераций, в – 20 итераций, г – 80 итераций, д – 160 итераций, е – 320 итераций) На графиках представлены кольцевые маршруты и их длина при соответствующем количестве итераций. 55

Из проведенных экспериментов можно сделать вывод, что популяция решений никогда не приводится к одному, общему решению для всех муравьев, а наоборот, алгоритм продолжает синтезировать новые, возможно наилучшие решения. Итак, подводим итог на данном этапе: чем сложней стоит поставленная задача (например, задача коммивояжёра) перед муравьиным алгоритмом, тем он находит более оптимальное решение задачи. 3.2 Метод имитационного отжига На рисунке 3.9 представлена упрощенная блок схема работы имитационного отжига. Рисунок 3.9 – Блок схема алгоритма Так как разработанные программы по всем алгоритмам имеют общую базу, соответственно у них есть одинаковые фрагменты, а то и части в коде. Чтобы не повторяться, будут описаны по аналогии с предыдущим пунктом, только характерные отличия. Итак, первое отличие заключается в настройках параметра алгоритма, которому соответствует фрагмент кода: 56

T_start = 1% начальная температура T_end = T_start/max(age); % конечная температура T = T_start; % начальная температура для вычислений Далее представлены формулы регулируемых параметров: Tstart  1 , Tend  Tstart / max  m  , где (17) Tstart – начальная температура; Tend – конечная расчетная температура; m – массив выбранных количеств итераций. На нижнем фрагменте кода выполняется приведение к одному виду массива transp с двумя случайными точками: % переворот вектора if transp(1) < transp(2) ROUTEp(transp(1):transp(2)) = ... fliplr(ROUTEp(transp(1):transp(2))) else ROUTEp(transp(2):transp(1)) = ... fliplr(ROUTEp(transp(2):transp(1))) end В следующей части происходит определение потенциального маршрута, а именно порядок точек следования: % если он меньше, то потенциальный маршрут -> основным if Sp < S S = Sp; ROUTE = ROUTEp; % иначе, определяется, был ли переход Else RANDONE = rand(1); % рандом от 0 до 1 Formul_M = exp((-(Sp - S)) / T); % формула Метрополиса Formul_B = 1/(1+exp((Sp - S) / T)); % формула Беркера if RANDONE <= Formul_M 57

S = Sp; ROUTE = ROUTEp; end end В следующей части кода выполняется проверка критерия выхода из цикла, т.е. решение для текущей итерации заканчивается и происходит переход к следующей: T = T_start / it; % уменьшение температуры % проверка условия выхода if T <= T_end break; end Из пункта 2.3 было взято две функции для моделирования решения имитационным отжигом: метод Метрополиса и критерий Баркера. Чтобы выбрать рабочую функцию было выполнено ряд экспериментов: для каждого количества точек при различном количестве итераций проводилось по 5 прогонов (т.е. пять опытов для каждого критерия/функции) алгоритма. Результаты опытов по функции Метрополиса и критерия Баркера продемонстрированы на следующих рисунках ниже. На рисунке 3.10 проиллюстрированы изображения с графиками, при установленных 10 точках. 58

0 500 1000 Длина пути, усл. ед. Длина пути, усл. ед. 600 550 500 450 400 350 300 250 200 500 450 400 350 300 250 200 0 Количество итераций Опыт №1 Опыт №2 Опыт №4 Опыт №5 а) 500 1000 Количество итераций Опыт №3 Опыт №1 Опыт №2 Опыт №4 Опыт №5 Опыт №3 б) Рисунок 3.10 – График зависимости, расстояний и итераций (а – функция Метрополиса, б – функция Беркера) Далее на рисунке 3.11 продемонстрированы результаты расчетов при 1800 1600 1400 1200 1000 800 600 400 0 500 1000 Длина пути, усл. ед. Длина пути, усл. ед. 30 точках. 1700 1500 1300 1100 900 700 500 0 Количество итераций Опыт №1 Опыт №2 Опыт №4 Опыт №5 а) Опыт №3 500 1000 Количество итераций Опыт №1 Опыт №2 Опыт №4 Опыт №5 Опыт №3 б) Рисунок 3.11 – График зависимости, расстояний и итераций (а – функция Метрополиса, б – функция Беркера) На рисунке 3.12 отображены результаты расчетов при 50 точках. 59

Длина пути, усл. ед. Длина пути, усл. ед. 2600 2100 1600 1100 600 0 500 1000 а) Опыт №2 Опыт №4 Опыт №5 0 500 1000 Количество итераций Количество итераций Опыт №1 2700 2500 2300 2100 1900 1700 1500 1300 1100 900 700 Опыт №3 Опыт №1 Опыт №2 Опыт №4 Опыт №5 Опыт №3 б) Рисунок 3.12 – График зависимости, расстояний и итераций (а – функция Метрополиса, б – функция Беркера) Из полученных данных выше, можно сделать вывод, что метод Метрополиса немного лучше и стабильнее справляется с поставленной задачей, чем так называемый критерий Баркера, потому что первому требуется меньше итераций для оптимального пути при приблизительном равном результате чем второму. В дальнейшем будет использоваться только функция Метрополиса. По рисунку 3.10, рисунку 3.11 и рисунку 3.12 можно сделать следующие выводы: - для достижения лучшего пути при 10 точках достаточно 100 итераций; - для достижения лучшего пути при 30 точках достаточно 600 итераций; - для достижения лучшего пути при 50 точках достаточно 800 итераций. Выведем результат работы алгоритма при 50 точках и 6 разных алгоритмах, которым соответствует рисунок 3.13. 60

а) б) в) г) д) е) Рисунок 3.13 – Графики моделирования маршрута имитационным отжигом (а – 50 итераций, б – 100 итераций, в – 200 итераций, г – 800 итераций, д – 1600 итераций, е – 3200 итераций) По проведенным экспериментам можно сделать вывод, что даже большое кол-во проведенных итераций имитационным отжигом не гарантирует нахождения оптимального маршрута, так как решение задачи может «застрять» в так называемом локальном минимуме. 61

3.3 Пчелиный алгоритм На рисунке 3.14 продемонстрирована блочная схема работы алгоритма. Рисунок 3.14 – Схема алгоритма пчелиного алгоритма По аналогии с пунктом 3.2, представлены только отличные части. В рассматриваемой программе используется дополнительная функция, которая находится в отдельном m-файле «ABC_Distances»: CostFunction = @(x) ABC_Distances(x); % целевая функция Она нужна для значительного сокращения кода в программе. Далее отображены параметра пчелиного алгоритма, которому соответствует фрагмент кода: nPop = max(age)*1.2; % размер колонии nOnlooker = nPop; % кол-во пчел-наблюдателей L = round(0.6*nVar*nPop); % параметр предела отмены (пробный предел) На следующем фрагменте кода выполняется создание начального эталонного решения: создание эталонной популяции for i=1:nPop pop(i).Position = randperm(nCity, nCity); % точки маршрута pop(i).Route = [pop(i).Position(1:end),... 62

pop(i).Position(1,1)]; % точки кольцевого маршрута pop(i).Cost = CostFunction(pop(i).Route); % дистанция маршрута % запись эталонного решения при условии if pop(i).Cost <= BestPop.Cost BestPop = pop(i); end end В следующем фрагменте исследуются маршруты завербованных пчел из которых выбираются потенциальные дистанции. % Перебор маршрутов завербованных пчел for i = 1:nPop k = randi(nPop); newbee.Position=pop(k).Position; % оценка newbee.Route = [newbee.Position(1:end),... newbee.Position(1,1)]; % точки кольцевого маршрута newbee.Cost = CostFunction(newbee.Route); % дистанция маршрута % сравнение расстояний if newbee.Cost <= pop(i).Cost pop(i) = newbee; else C(i) = C(i)+1; end end В следующем фрагменте кода выполняется конвертация текущего значения расстояния и расчет вероятности его выбора потенциальным: % Рассчет пробного значения и вероятности выбора F = zeros(nPop,1); MeanCost = mean([pop.Cost]); % рассчет средней дистанции 63

for i=1:nPop F(i) = exp(-pop(i).Cost/MeanCost); % конвертация расстояния end Для визуализации получаемых решений были выполнены расчеты при количестве точек (адресов) 50, но при разных количествах итераций. а) б) в) г) д) е) Рисунок 3.15 – Графики моделирования маршрута пчелиным алгоритмом (а – 5 итераций, б – 10 итераций, в – 20 итераций, г – 80 итераций, д – 160 итераций, е – 320 итераций) На рисунке 3.15 показан результат работы программы. 64

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

4 ПОСТРОЕНИЕ ОПТИМАЛЬНОГО КОЛЬЦЕВОГО МАРШРУТА НА КАРТЕ ГОРОДА БЛАГОВЕЩЕНСКА 4.1 Постановка задачи Для проверки работы алгоритма в так называемых «реальных» условиях, то есть вместо случайно рассчитанных данных, были использованы уже действительные географические данные адресов (координаты и расстояния между точками) города Благовещенска. Дистанции и координаты были предварительно извлечены из страниц поисково-информационной картографической службы Яндекс.Карты [46]. Ниже представлены скриншоты страниц сайта. Рисунок 4.1 показывает на примере адреса «Ленина, 174», с какой строки веб-страницы берутся его координаты (выделено красной рамкой). В данном случае координаты равны «50.261845,127.496460» - первое значение широта, а второе долгота. Рисунок 4.1 – Скриншот данных из ресурса Яндекс.Карты (широта и долгота адреса) Далее на рисунке 4.2. продемонстрирована веб-страница карты, из которой определяется расстояние между двумя точками. 66

Рисунок 4.2 – Скриншот данных из ресурса Яндекс.Карты (автомобильная дистанция между двумя адресами) По верхнему рисунку можно сказать, что расстояние (транспортное расстояние) между «Ленина, 174» и «Калинина, 130» равно 5.1 км. Выделено также красной рамкой на рисунке. Так как используемые значения дистанций имеют открытый доступ, было решено упростить процесс ручного сбора информации и соответственно автоматизировать работу, за счет компьютерного кода. И вот, для заполнения матрицы расстояний был использован автоматизированный HTML-парсинг интернет ресурса. Под парсингом HTML подразумеваем выборочное извлечение требуемого количества информации с интернет-ресурсов и ее последующая обработка. На языке Python 3.7 в интегрированной среде разработки программного обеспечения Microsoft Visual Studio была разработана программа «Distance Matrix». Результатом работы этой данной программы является матрица расстояний между выбранными точками на карте города Благовещенск. Вначале, для наглядной иллюстрации работы алгоритмов, были выбраны в случайном (не близко друг с другом) порядке следующие адреса города Благовещенска. 67

Координаты точек были взяты также с поисково-информационной картографической службы Яндекс.Карты [46]. Выбранные адреса и их данные показаны в таблице 4.1. Таблица 4.1 – Географические данные выбранных адресов № Адрес точки Широта Долгота 1 улица Ленина, 174 50.259558 127.495682 2 улица Ленина, 160 50.259424 127.500853 3 улица Ленина, 146 50.258526 127.514224 4 Рёлочный переулок, 4 50.258162 127.517827 5 улица Ленина, 130/1 50.258938 127.520566 6 Зейская улица, 212 50.261493 127.523526 7 Пионерская улица, 1 50.263215 127.530861 8 улица Ленина, 121 50.261909 127.541079 9 улица Ленина, 100 50.263509 127.544888 10 Театральная улица, 1 50.267231 127.549386 11 улица Фрунзе, 57/59 50.265087 127.558503 12 Первомайская улица, 19 50.264317 127.572498 13 Амурская улица, 3 50.272537 127.576786 14 Амурская улица, 20 50.274124 127.570614 15 улица Лазо, 53 50.272973 127.566703 16 Зейская улица, 63 50.270276 127.560655 17 Зейская улица, 89 50.267586 127.555666 18 Амурская улица, 102 50.269169 127.549856 19 улица Шимановского, 40 50.267687 127.541178 20 улица 50 лет Октября, 15 50.268487 127.535095 21 улица Шевченко, 35 50.265965 127.528898 22 улица Калинина, 52 50.268725 127.520615 23 Амурская улица, 236 50.275122 127.512198 24 Артиллерийская улица, 20 50.280887 127.503583 25 Батарейная улица, 26 50.286233 127.491961 26 Октябрьская улица, 236 50.292190 127.500949 27 улица Мухина, 82 50.298262 127.512262 28 улица Мухина, 64 50.305408 127.511705 68

Продолжение таблицы 4.1 29 улица Горького, 157 50.302783 127.525502 30 Красноармейская улица, 143 50.302554 127.532595 31 Красноармейская улица, 82 50.304711 127.540586 32 Кузнечная улица, 113/1 50.291884 127.550086 33 Красноармейская улица, 53А 50.298302 127.562505 34 улица Лазо, 101 50.305032 127.568715 35 Свободная улица, 33 50.302783 127.558676 36 Театральная улица, 170 50.295714 127.554142 37 Тенистая улица, 160 50.290959 127.522826 38 Студенческая улица, 19/1 50.285178 127.507082 39 Игнатьевское шоссе, 21 50.259558 127.510649 40 улица Воронкова, 26 50.259424 127.506885 41 Институтская улица, 15 50.258526 127.511795 42 Студенческая улица, 43 50.258162 127.518534 43 улица Воронкова, 8/А4 50.258938 127.526769 44 улица Калинина, 130 50.261493 127.525736 45 улица 50 лет Октября, 202 50.263215 127.543397 46 улица 50 лет Октября, 239 50.261909 127.546173 47 Кольцевая улица, 34 50.263509 127.550263 48 Театральная улица, 236 50.267231 127.558093 49 улица Чайковского, 175 50.265087 127.565734 50 Тенистая улица, 91 50.264317 127.541407 Итак, ниже рассматривается код данной программы, который написан на языке программирования Python (версия 3.7). Ниже продемонстрирован фрагмент кода, где подключаются все необходимые модули и библиотеки: import speech_recognition as SR # библиотека для генерации голоса import pyttsx3 # библиотека преобразования текста в речь на Python import os # функции для работы с операционной системой import subprocess # функции стандартных потоков ввода/вывода/ошибок import webbrowser # модуль для просмотра веб-документов import time # модуль для работы со временем 69

import random # функции для генерации случайных чисел и т.п. import Parsing_file # дополнительный файл для работы с данных import requests # осуществляет работу с HTTP-запросами import urllib.request # библиотека HTTP from bs4 import BeautifulSoup # библиотека для осуществления синтаксического разбора документов HTML from fake_useragent import UserAgent # модуль для генерации случайных данных браузера Инициализация массивов с входными данными выполняется в следующем фрагменте: proxy = Parsing_file.Proxy() # загрузка IP адреса https_proxy = proxy.get_array_proxy() coords = {} # массив географических координат для каждого адреса address = {} # массив наименование для каждого адреса coords[1] = "127.495682,50.261802" address[1] = "улица Ленина, 174" Массивы coords и address имеют размерность 50 элементов. Для сокращения места в скриншоте были отображены первые элементы массивов. Развернутый вариант программы находится в Приложении А. Данные элементов массива дублируются в таблице 4.1. В следующем фрагменте выполняется «сборка» нужного ссылка запроса (url адрес): url = "https://yandex.ru/maps/77/blagoveshchensk/?ll=127.512254,50.285279 &mode=routes&rtext=" + coords_i + "~" + coords_j + "&rtt=auto&ruri=ymapsbm1 ://geo?ll=" + coords[i] + &spn=0.001,0.001&text=Россия, Амурская область, Благовещенск, " + address[i] + "~ymapsbm1://geo?ll=" + coords[j] + "&spn=0.001 ,0.001&text=Россия, Амурская область, Благовещенск, " + address[j] + "&z=15.0" 70

За счет созданной ссылки, откроется путь к веб-странице сервиса Яндекса, в которой находится необходима информация, а именно дистанция между необходимыми адресами. Пример открываемой «ботом» ссылки показан на рисунке 4.2. А в следующих строках происходит обработка кода html-страницы и преобразование данных к нужному виду и формату: # обработка html-кода и извлечение информации о дистанции маршрута soup = BeautifulSoup(html, 'html.parser') obj = soup.find('div', attrs={'class': 'auto-route-snippet-view__route-subtitle'}) temp_s = obj.text.split(", ") distance = temp_s[0] temp_s = distance.split("\xa0") if temp_s[1] == "м": temp_d = float(distance.replace(',','.').replace('\xa0м','')) distance = round(temp_d / 1000, 1) elif temp_s[1] == "км": distance = float(distance.replace(',','.').replace('\xa0км','')) else: temp_d = float(distance.replace('\xa0000\xa0м','.0')) print("Точка: " + str(i) + "-" + str(j) + "\t->\t" + str(distance)) distance_all = distance_all + (str(distance) + "\t") При завершении программы происходит вывод итоговой информации на консоль и также сохраняется в txt-файл. На нижнем фрагменте продемонстрированно как это реализовано. f = open('card_data.txt', 'w') f.write("Расстояния, от одного пункта до другого пункта: \n" + distance_all) f.close() talk("Запись данных в блокнот успешно завершена") print("\n\n" + distance_all) 71

print("Время выполнения: %s минут или " % ((time.time() - start_time)//60) + "%s секунда" % ((time.time() - start_time)//1)) Для демонстрации программы была выполнена реализация на примере загрузки матрицы с размерностью 5x5 (не сильно громоздкая для демонстрации), поэтому для поставленной задачи она загружена с максимальной размерностью 50x50. Скриншот выведенной консоли показан на следующем рисунке 4.3. Рисунок 4.3 – Скриншот консоли Visual Studio Данная матрица построена так образом, что видно какое расстояние имеется от одной точки до других остальных точек. Значения нуля в матрице говорит, что от точки, например, А и до тоже самой точки, расстояние равно нулю. Полученные данные были добавляются в дополнительную функцию «ProgramData_new» ППП MATLAB, а именно матрица расстояний и координат. Ею уже пользуются все три программы алгоритмов. Листинг кода этой функции находится в Приложении Д. На основе ранее использованных программ в Разделе 3 в MATLAB были внесены коррективы: 72

- вместо случайного заполнения матрицы координат, загружаются реальные данные по точкам; - матрица расстояний не рассчитывается, а заполняется реальным дистанциями; - добавлен график динамики изменения дистанции маршрута от итераций; - добавлен вывод информации на консоль MATLAB - порядок точек маршрута, динамика оптимизации расстояний. После расчетов в данной программе уже получается массив с порядком следования по адресам (для удобства, все адреса пронумерованы). По полученному порядку следования по адресам и соответствующим им координатам (широта и долгота) формируются специальные ссылки, которые ведут на сайт ресурса (https://map.project-osrm.org/) [47], который работает на основе OSRM системы, где строятся автомобильные маршруты. Open Source Routing Machine или OSRM - это реализация C ++ высокопроизводительного механизма маршрутизации для кратчайших путей в дорожных сетях [47]. OSRM сочетает в себе сложные алгоритмы маршрутизации с открытыми и бесплатными данными дорожной сети проекта Open Street Map (OSM). Вычисление кратчайшего пути в сети континентального размера может занять до нескольких секунд, если оно выполняется без так называемой техники ускорения. Программное обеспечение использует реализацию иерархий сжатия и может вычислять и выводить кратчайший путь между любым источником и пунктом назначения в течение нескольких миллисекунд, в результате чего вычисление чистого маршрута занимает гораздо меньше времени. Большая часть усилий затрачивается на аннотирование маршрута и передачу геометрии по сети. Выбор данного интернет ресурса был обоснован тем, что в нем возможно строить маршруты с неограниченным количеством точек (у карт от Google и 73

Yandex стоит ограничение на свыше 10 точек) и грузит значительно быстрее аналоговых ресурсов. 4.2 Муравьиный алгоритм Результаты реализации муравьиного алгоритма представлены в виде графиков в ППП MATLAB. На рисунке 4.4 продемонстрирована динамика изменения маршрута при изменении количеств пройденных итераций. а) б) в) Рисунок 4.4 – Графики динамики оптимизации маршрутов (а – 10 адресов, б – 30 адресов, в – 50 адресов) По данным графикам можно сказать что: 1) оптимальный маршрут с 10 адресами найден за 12 итераций; 2) оптимальный маршрут с 30 адресами найден за 20 итераций; 3) оптимальный маршрут с 50 адресами найден за 100 итераций. Для маршрута с 50 адресами требуется значительное больше итераций по сравнению с остальными, так как чем больше адресов, тем больше хороших вариантов проходов по кольцевому маршруту. 74

На рисунке 4.5 показаны оптимальные лучшие маршруты в географической системе координат (широта и долгота), которые построены в ППП MATLAB. а) б) в) Рисунок 4.5 – Графики маршрутов в ППП MATLAB (а – 10 адресов, б – 30 адресов, в – 50 адресов) На примере маршрута с 10 адресами, на рисунке 4.6. показан вывод информации программы. Рисунок 4.6 – Скриншот консоли ППП MATLAB 75

Вся информация с консоли по всем точкам собрана и представлена далее в таблице 4.2. Таблица 4.2 –Данные с консоли ППП MATLAB Муравьиный алгоритм Кол-во Кол-во Порядок адресов Динамика адресов итераций маршрута оптимизации, км 10 100 10,9,8,7,5,3,2,1,4,6,10 11.4 -> 9.6 300 23,28,27,26,25,24,2,1,3,4, 29.1 -> 23.3 адресов 30 5,6,21,20,19,18,16,17,15,14, адресов 13,12,11,10,9,8,7,30,29,22,23 50 адресов 500 50,36,35,33,34,15,14,13,12, 66.2 -> 50.6 11,16,17,18,9,10,8,7,20,19, 31,30,29,22,23,28,27,26,25, 24,2,1,3,4,5,6,21,32,49,48,45, 46,47,43,42,41,40,39,38,44,37,50 Маршруту с 10 адресами соответствует рисунок 4.7: Рисунок 4.7 – Скриншот построенного маршрута в OSMR, 10 адресов с дистанцией маршрута 13.1 км 76

На рисунке ниже представлены рисунки с оптимальными маршрутами для каждого количества точек, которые уже построены с помощью интернет-сервиса OSRM. Рисунок 4.8 демонстрирует оптимальный маршрут с 30 адресами. Рисунок 4.8 – Скриншот построенного маршрута в OSMR, 30 адресов с дистанцией маршрута 28.5 км На рисунке 4.9 показан оптимально лучший вариант маршрута с 50 адресами. Рисунок 4.9 – Скриншот построенного маршрута в OSMR, 50 адресов с дистанцией маршрута 58.4 км 77

Вышеупомянутые 3 рисунка также представлены в Приложении Ж. Если сравнивать картографические маршруты с моделями маршрута (рисунок 4.5), то просматривается только схожесть расположений адресов(точек). Соединения же отличаются между адресами, так как в MATLAB точки соединяются прямой линией, в отличии OSRM – здесь соединения производятся на основе данных дорожной сети. Полноценный листинг программы муравьиного алгоритма находится в Приложении Б. 4.3 Метод имитационного отжига На рисунке 4.10 продемонстрирована динамика изменения маршрута при изменении количества пройденных итераций. а) б) в) Рисунок 4.10 – Графики динамики оптимизации маршрутов (а – 10 точек, б – 30 точек, в – 50 точек) По указанным графикам можно сказать что: 1) оптимальный маршрут с 10 адресами найден за 110 итераций; 78

2) оптимальный маршрут с 30 адресами найден за 2350 итераций; 3) оптимальный маршрут с 50 адресами найден за 4700 итераций. Из всего следует, что для имитационного отжига требуется гораздо больше итераций по сравнению с муравьиным алгоритмом. Рисунку 4.11 соответствуют оптимальные лучшие маршруты: а) б) в) Рисунок 4.11 – Графики маршрутов в ППП MATLAB (а – 10 точек, б – 30 точек, в – 50 точек) А на рисунке 4.12 соответствуют выводы данные алгоритма с консоли ППП MATLAB. 79

Рисунок 4.12 – Скриншот консоли ППП MATLAB Полная информация с консоли по всем точкам собрана и представлена далее в таблице 4.3. Таблица 4.3 –Данные с консоли ППП MATLAB Пчелиный алгоритм Кол-во Кол-во Порядок адресов Динамика адресов итераций маршрута оптимизации, км 10 1000 3,4,10,9,8,7,6,5,2,1,3 25.2->10.2 3000 26,24,2,1,3,4,5,6,21,7, 80.2->24.7 адресов 30 20,19,18,17,15,14,13,12,16,11, адресов 10,9,8,30,29,22,23,28,27,25,26, 50 5000 адресов 49,48,45,46,47,43,42,41,40,39, 227.2->52.9 38,44,37,50,36,32,33,34,15,14, 13,12,11,16,17,18,19,21,29,22, 28,27,26,25,24,2,1,23,3,4, 5,6,20,10,9,8,7,30,31,35,49, На следующих рисунках изображены построенные маршруты (с помощью сервиса OSRM) для каждого количества точек. Маршруту с 10 адресами соответствует рисунок 4.13: 80

Рисунок 4.13 – Скриншот построенного маршрута в OSMR, 10 адресов с дистанцией маршрута 11.7 км Следующий рисунок 4.14 относится к маршруту с 30 адресами. Рисунок 4.14 – Скриншот построенного маршрута в OSMR, 30 адресов с дистанцией маршрута 28.9 км Рисунок 4.15 соответствует лучшему маршруту с 50 адресами: 81

Рисунок 4.15 – Скриншот построенного маршрута в OSMR, 50 адресов с дистанцией маршрута 59.8 км Графики с маршрутами также показаны в Приложении К. А листинг самой программы имитационного отжига расположен в Приложении В. 4.4 Пчелиный алгоритм а) б) в) Рисунок 4.16 – Графики динамики оптимизации маршрутов (а – 10 точек, б – 30 точек, в – 50 точек) 82

По данным графикам можно сделать выводы: 4) оптимальный маршрут с 10 адресами найден за 72 итераций; 5) оптимальный маршрут с 30 адресами найден за 180 итераций; 6) оптимальный маршрут с 50 адресами найден за 480 итераций. Здесь также требуется значительно значительное больше итераций по сравнению для маршрута с максимальным количеством адресов (50), по сравнению с остальными алгоритмами/методами. На рисунке 4.16 продемонстрированы графики пчелиного алгоритма, которые показывают динамику изменения маршрута при изменении количества итераций. Рисунку 4.17 соответствуют построенные оптимальные маршруты. а) б) в) Рисунок 4.17 – Графики маршрутов в ППП MATLAB (а – 10 точек, б – 30 точек, в – 50 точек) 83

Рисунок 4.18 – Скриншот консоли ППП MATLAB Полная информация с консоли по всем точкам собрана и представлена в таблице 4.4. Таблица 4.4 –Данные с консоли ППП MATLAB Пчелиный алгоритм Кол-во Кол-во Порядок адресов Динамика адресов итераций маршрута оптимизации, км 10 100 10,9,8,7,5,3,2,1,4,6,10 11.4 -> 9.6 300 12,11,16,15,17,8,6,5,3,22, 42.9 -> 33 адресов 30 4,20,7,29,28,27,26,25,2,1, адресов 24,23,30,21,19,18,10,9,13,14,12 50 адресов 500 2,24,1,3,7,21,31,29,20,30, 85.8 -> 79.4 9,8,11,16,17,15,14,13,34,33, 32,10,12,18,5,6,27,28,23,22, 4,25,26,42,41,40,38,39,50,37, 45,47,46,43,44,36,48,49,35,19,2 Вывод информации с консоли MATLAB показана выше на рисунке 4.18. На следующих рисунках изображены построенные маршруты (с помощью сервиса OSRM) для каждого количества точек. Рисунок 4.19 соответствует построенному маршруту с 10 адресами. 84

Рисунок 4.19– Скриншот построенного маршрута в OSMR, 10 адресов с дистанцией маршрута 13.4 км Следующий рисунок 4.20 относится к маршруту с 30 адресами: Рисунок 4.20– Скриншот построенного маршрута в OSMR, 30 адресов с дистанцией маршрута 38.1 км На рисунке 4.21 представлен оптимально лучший вариант маршрута с 50 адресами. 85

Рисунок 4.21– Скриншот построенного маршрута в OSMR, 50 адресов с дистанцией маршрута 85.3 км Графики маршрутов также представлены в Приложении Л. Весь листинг программы пчелиного алгоритма расположен в Приложении Г. 4.5 Анализ результатов работы алгоритмов Проведем анализ полученных результатов главы 4. Сравнивая полученные данные показатели оптимальных маршрутов, которые были получены имитационным отжигом и муравьиным алгоритмом, можно сделать вывод, что алгоритм имитации отжига справляется гораздо хуже. Большое количество итераций данного метода не гарантирует получение оптимального маршрута. Самый главный плюс муравьиного алгоритма в поиске глобального оптимума: при бесконечном числе итераций вероятность нахождения глобального лучшего стремится к единице. Проведем анализ результатов, полученных выше. В таблице 4.5 представлены результаты работы алгоритмов. 86

Таблица 4.5 – Маршрутные данные трех алгоритмов (методов) Варианты проходов по итерациям Кол-во Муравьиный Имитационный Пчелиный точек алгоритм отжиг алгоритм 10 Iteration of method: 50 Iteration of method: 1000 Iteration of method: 100 MATLAB Dist: 10 км MATLAB Dist: 10 км MATLAB Dist: 10 км OSM Dist: 13.1 км OSM Dist: 11.7 км OSM Dist: 13.4 км Iteration of method: 60 Iteration of method: 3000 Iteration of method: 300 30 50 MATLAB Dist: 23.3 км MATLAB Dist: 25 км MATLAB Dist: 33 км OSM Dist: 28.5 км OSM Dist: 28.9 км OSM Dist: 38.1 км Iteration of method: 60 Iteration of method: 5000 Iteration of method: 500 MATLAB Dist: 51 км MATLAB Dist: 53 км MATLAB Dist: 79 км OSM Dist: 58.4 км OSM Dist: 59.8 км OSM Dist: 85.3 км Приняты следующие обозначения: Iteration of Method – количество итераций каждого метода при поиске оптимального маршрута, MATLAB Dist – длина маршрута, рассчитанная в программной среде MATLAB по имеющимся данным (км), OSM Dist – длина маршрута, рассчитанная в открытых данных дорожной сети (км). Сравнивая полученные результаты оптимальных маршрутов, которые были полученные муравьиным алгоритмом, имитационным отжигом и пчелиным алгоритмом, можно сделать следующие выводы: 1) алгоритм имитации отжига с увеличением количества точек будет справляться хуже в сравнении с представленными алгоритмами; значительное увеличение числа итераций метода не гарантирует получение лучшего пути; 2) пчелиный алгоритм работает гораздо лучше алгоритма отжига, но хуже муравьиного алгоритма; 3) муравьиный алгоритм справляется лучше всех. Главное его преимущество состоит в том, что при значительном увеличении числа итераций вероятность нахождения глобального минимального расстояния стремится к единице. 87

5 ИСПОЛЬЗОВАНИЕ РЕЗУЛЬТАТОВ МАГИСТЕРСКОЙ ДИССЕРТАЦИИ В ПЕДАГОГИЧЕСКОЙ ДЕЯТЕЛЬНОСТИ 5.1 Разработка лабораторной работы «Природные алгоритмы построения оптимального кольцевого маршрута» Цель работы: ознакомить студентов с решениям задач комбинаторной оптимизации с помощью трех разных природных алгоритмов. Данная работа посвящена задаче коммивояжера (кольцевого маршрута) и решению ее тремя алгоритмами: 1) Муравьиный алгоритм; 2) Метод имитационного отжига; 3) Пчелиный алгоритм. Реализация алгоритмов возможна уже по готовым кодам, которые созданы в ППП MATLAB. А также был разработан дополнительные программы на языке Python 3.7, которые упрощают процесс реализации алгоритмов. Ход работы: Получение с сервиса Яндекс.Карты матриц расстояний адресов г. Благовещенск. Изначально нам нужны точки(адреса) кольцевого маршрута выбранного города. Для лучшего восприятия работы алгоритмов точки были уже выбраны по 15 для каждого варианта. Адреса кольцевого маршрута перечислены в приложении ниже. Итак, нам понадобятся входные данные, которые представлены будут в виде матрицы расстояний. Она будет состоять из расстояний, которые определяют дистанцию от одного адреса до другого. Эти дистанции будут взяты с поисково-информационной картографической службы Яндекса. На рисунке 5.1 показано откуда извлекаются дистанции между двумя адресами. 88

Рисунок 5.1 – Скриншот интернет ресурса Яндекс.Карты Также, были взяты вручную для каждого адреса широта и долгота, как представлено на рисунке 5.2. Рисунок 5.2 – Скриншот интернет ресурса Яндекс.Карты Для значительного упрощения заполнения матрицы расстояний мы воспользуемся автоматизированным HTML парсингом ресурса Яндекс.Карты. Под парсингом HTML, подразумеваем выборочное извлечение большого количества информации с определенных сайтов и ее последующее использование. 89

Осуществление так называемого парсинга была выполнена на Python в среде Visual Studio. Программа состоит из двух файлов с расширением «.py» (main_yandex, Parsing_file) и текстовый документ со списком различных IPадресов (proxy.txt). Так как программа будет самостоятельно заходить на сайт и извлекать нужны нам данные, то по факту за нас будет работать интернет-бот, а от него как правило на крупных интернет ресурсах имеется защита, Яндекс.Карты, к сожалению, не исключение. Суть защиты заключается вот что, что из-за многократных и слишком быстрых (по сравнению с человеком) запросов, сервер сайта блокирует доступ к сайту по IP-адресу клиента, соответственно извлечение данных перестает быть возможным с этого IP. Для этого в программе была предусмотрена замена IP-адреса на другой в случае блокировке. На специальном сайте был импортирован список прокси серверов, как показано на рисунке 5.3. Рисунок 5.3 – Скриншот списка адресов 90

Листинг упомянутой программы (HTML парсинга) выведена в Приложение А. Результатом работы этой программы будет являться матрица расстояний, в данном случае с размерностью 15х15, которая представлена на рисунке 5.4: Рисунок 5.4 – Скриншот программы Выполнение реализаций алгоритмов осуществляется по готовым кодам программы, листинги которых расположены в указанных приложениях: - Муравьиный алгоритм – Приложение Б; - Метод имитационного отжига – Приложение В; - Пчелиный алгоритм – Приложение Г. А также имеется общая дополнительная функция в Приложении Д, которая содержит в себе матрицы расстояний и координат. При выполнении своего варианта работы нужно будет в данном файле вносить соответствующие изменения. Применение алгоритмов к матрицам расстояний будет осуществлена с помощью ППП MATLAB. В нем осуществляется поиск оптимального пути по имеющиеся матрице расстояний. После выполнения расчетов на выходе получается массив с порядком следования по адресам (для удобства, все адреса пронумерованы). 91

По полученным порядка следования по адресам и соответствующим им координатам (широта и долгота) были сформированы специальные ссылки, которые ведут на сайт ресурса (https://map.project-osrm.org/), который работает на основе OSRM, где строятся соответствующие маршруты. Open Source Routing Machine или OSRM - это реализация C ++ высокопроизводительного механизма маршрутизации для кратчайших путей в дорожных сетях. Далее представлены рисунок 5.5, рисунок 5.6, рисунок 5.7 с оптимальными маршрутами для каждого для алгоритма/метода. Рисунок 5.5 – Оптимальный маршрут (муравьиный алгоритм), 62.3 км 92

Рисунок 5.6 – Оптимальный маршрут (имитационный отжиг), 69.8 км Рисунок 5.7 – Оптимальный маршрут (пчелиный алгоритм), 61.9км Сравнение результатов работ алгоритмов. 93

Далее проведем анализ полученных результатов. Сравниваем полученные данные показатели оптимальных маршрутов, которые показаны в таблице 5.1. Таблица 5.1 – Маршрутные данные трех алгоритмов(методов) Варианты проходов по итерациям Муравьиный Имитационный Пчелиный алгоритм отжиг алгоритм Iteration: 60 Iteration: 700 Iteration: 150 MATLAB: 60.1 км MATLAB: 67.5 км MATLAB: 63.5 км OSRM: 61.9 км OSRM: 69.8 км OSRM: 65.3 км Вывод: Проведенные вычисления в ППП MATLAB показывают, что данный алгоритм находит хорошие маршруты коммивояжера значительно быстрее, чем точные методы комбинаторной оптимизации. Сравнивая полученные данные показатели оптимальных маршрутов, которые были получены имитационным отжигом, муравьиным алгоритмом и пчелиным алгоритмом, можно сделать вывод, что алгоритм имитации отжига справляется гораздо хуже. Самый главный плюс муравьиного алгоритма в поиске глобального оптимума: при бесконечном числе итераций вероятность нахождения глобального лучшего стремится к единице. Оформление отчета. 1. Титульный лист, содержащий информацию о студенте (группа, фамилия, номер варианта). 2. Результаты подготовки (матрица планирования эксперимента, выбранные по варианту значения экспериментальных данных). 3. Основные теоретические положения (используемые формулы). 4. Листинг программы. 5. Результат выполнения работы. 6. Выводы по лабораторной работе. 94

5.2 Варианты заданий для индивидуальной работы Таблица 5.2 – Варианты групп адресов для маршрутов Вар. Список адресов для кольцевого маршрута 1 2 3 4 5 6 7 8 9 10 Красноармейская, 300Бб; Больничная, 79а/1; Загородная, 169а; Мухина, 150; Пролетарская, 107; Мухина, 83/1; Мухина, 78/3; Горького, 231/1; Больничная, 32; Загородная, 56; Ленина, 261; Нагорная, 1а/1; Ленина, 194; Горького, 235; Северная, 163Б. Студенческая улица, 49; Студенческая ул., 43/3; улица Кантемирова, 6/2; Игнатьевское шоссе, 12/3; улица Калинина, 130/24; улица Калинина, 130/2; улица Калинина, 130/2; улица Калинина, 130/2; улица Калинина, 130/2; улица Калинина, 130/2; улица Калинина, 130/2; улица Калинина, 130/2; улица Калинина, 130/2; Новотроицкое шоссе, 10; Студенческая ул., 43. Студенческая ул., 43; Пионерская улица, 150/5; Пионерская улица, 150/54; улица Калинина, 141; улица Калинина, 1204; Комсомольская улица, 89; Пионерская улица, 150/1; Пионерская улица, 154; улица Богдана Хмельницкого, 101; Забурхановская улица, 102; улица Калинина, 116/1; Забурхановская улица, 98; улица Мухина, 118; Пионерская улица, 150; улица Шевченко, 134. Комсомольская улица, 89; улица Калинина, 103; улица Ломоносова, 154; улица 50 лет Октября, 62; улица Ломоносова, 158; улица Островского, 127; улица 50 лет Октября, 94; Забурхановская улица, 36; улица Богдана Хмельницкого, 96; улица Калинина, 116/4; ул. Мухина, 149; ул. Калинина, 141/3; Тенистая ул., 160; Промышленная улица, 6; Игнатьевское шоссе, 12/5 ул. Горького, 233; ул. Мухина, 64; Больничная ул., 45; Загородная ул., 35А; Больничная ул., 32; ул. Ленина, 192/9; ул. Ленина, 297/1; . Мухина, 18А; улица Горького, 247; Батарейная улица, 15; Загородная ул., 5; Новая улица, 2; Красноармейская улица, 164; Рёлочный пер., 15; Новая улица, 11. ул. Ленина, 146; ул. Мухина, 20; ул. Калинина, 52; Октябрьская ул., 197; ул. Шевченко, 85; улица Ломоносова, 145; ул. Горького, 129; улица Шевченко, 117; Красноармейская ул., 82; Красноармейская ул., 143; ул. 50 лет Октября, 61; Северная ул., 107; Октябрьская ул., 108А; Кузнечная ул., 113/1; Кузнечная улица, 147. ул. Чехова, 52; Свободная ул., 33; Октябрьская ул., 108Д; Северная ул., 107; ул. Лазо, 101; Конная улица, 104; Конная улица, 33; Театральная улица, 140; Северная ул., 57; Северная улица, 115; Октябрьская улица, 111; Красноармейская ул., 71; Амурская ул., 151; Амурская ул., 127; улица Чайковского, 108. Широкая ул., 61; Кольцевая ул., 30/2; Текстильная ул., 49А/1; Кольцевая ул., 45; Трудовая ул., 182; Тенистая ул., 91; Садовый переулок, 71; Тенистая улица, 103; Театральная ул., 170; ул. Шевченко, 85; ул. Калинина, 116/3; Трудовая улица, 96; Конная ул., 140; Литейная ул., 47; Театральная ул., 143. Институтская ул., 1; ул. Чайковского, 301; ул. Воронкова, 26; ул. Калинина, 130; Почтовая улица, 81; Широкая ул., 61; Перспективная ул., 53; Кольцевая ул., 45; Текстильная ул., 49А/1; Широкая улица, 53; Зелёная ул., 30; улица МуравьёваАмурского, 12; Трудовая улица, 235А; улица 50 лет Октября, 195/1; Кольцевая ул., 30/2. Красноармейская ул., 102; ул. Ломоносова, 154; Октябрьская ул., 108А; улица Ломоносова, 145; ул. Горького, 158; ул. Горького, 129; Кузнечная ул., 113/1; ул. Калинина, 22; Рёлочный пер., 15; ул. Мухина, 114; улица Калинина, 75; Красноармейская ул., 157; ул. Калинина, 103/1; ул. Ломоносова, 154; Свободная улица, 135. 95

ЗАКЛЮЧЕНИЕ Для выполнения научных исследований в рамках подготовки магистерской диссертации были рассмотрены природные алгоритмы решения комбинаторных задач. Также был затронут класс задач оптимизации в транспортной логистике. Были осуществлены научные исследования на тему природных алгоритмов для решения задачи построения кольцевого маршрута и их сравнение. В ходе работы по магистерской диссертации, были выполнены следующие задачи: 1) проведен обзор научной и методической литературы по теме исследования; 2) представлено описание и постановка математической модели задачи маршрутизации; 3) представлены описания муравьиного, пчелиного алгоритма и метода имитационного отжига; 4) осуществлено моделирование и тестирование решений задачи коммивояжера алгоритмами/методами в программе. Если сравнить полученные показатели оптимальных маршрутов каждого алгоритма, то можно сделать определенные выводы. При решении поставленной задачи, метод имитационного отжига работает хуже в сравнении с муравьиным алгоритмом, в особенности при больших количествах адресов (точек). При увеличении количества итераций не гарантируется получение маршрута столь близкого к оптимальному, так как метод имеет вероятностную природу, и в процессе поиска оптимального решения метода, он может как-бы «застрять» в локальном минимуме, не дойдя до глобального. От этих недостатков избавлен муравьиный алгоритм. Самое главное его достоинство при поиске глобального минимума заключается в том, что при значительно большом количестве итераций, вероятность нахождения оптимального маршрута будет близка к единице. Вопрос будет 96

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Corne D., Dorigo M., Glover F. New Ideas in Optimization. – New York: McGravHill – 1999. 2. Dorigo M. Optimization, Learning and Natural algorithms: Ph. D. Thesis / Dorigo M; Politecno di Milano. Milan, 1992 – P. 31-116. 3. Штовба, С. Д. Муравьиные алгоритмы / С. Д. Штовба // ExponentaPro. Математика в приложениях. – 2003. – Вып. 4 – С. 70–75. 4. Колтунов, Н. С. Реализация муравьиного алгоритма для исследования задачи построения кольцевого маршрута / Максимова Н. Н., Колтунов Н. С. // Вестник науки, сборник статей по материалам XIII международной научно-практической конференции “Инновации в науке и практике”, Часть 3(5), 26.12.2018, г. Барнаул, С. 17-21. 5. Колтунов, Н. С. Определение оптимальных значений параметров муравьиного алгоритма при решении задачи построения кольцевого маршрута/ Максимова Н. Н., Колтунов Н. С. // II всероссийская национальная научная конференция студентов, аспирантов и молодых ученых «Молодежь и наука: Актуальные проблемы фундаментальных и прикладных исследований», г. Комсомольскна-Амуре: Изд-во КнАГУ, 2019. Сборник Ч. 2. – С. 309-311. 6. Колтунов, Н.С. Построение оптимального кольцевого маршрута на карте г. Благовещенска/ Колтунов, Н. С. // Молодёжь XXI века: шаг в будущее материалы XX региональной научно-практической конференции. г. Благовещенск, 23 мая 2019 г. – Том 3 – С. 164-165. 7. Колтунов, Н. С. Реализация имитационного отжига для исследования задачи построения кольцевого маршрута (на примере карты г. Благовещенска / Н. С. Колтунов, Н. Н. Максимова // Научный журнал «Ученые заметки ТОГУ». – г. Хабаровск, 2020. – (в печати). 8. Колтунов, Н. С. Исследование задачи построения кольцевого маршрута природными алгоритмами (на примере карты г. Благовещенска) / Максимова Н. Н., Колтунов Н. С. // III всероссийская национальная научная конференция 98

студентов, аспирантов и молодых ученых «Молодежь и наука: Актуальные проблемы фундаментальных и прикладных исследований», г. Комсомольск-наАмуре, апрель 2020. – (в печати). 9. Колтунов, Н. С., Максимова Н. Н. Реализация имитационного отжига для исследования задачи построения кольцевого маршрута (на примере карты г. Благовещенска // Вестник АмГУ. Серия «Естественные и экономические науки»». – Благовещенск: АмГУ, 2020. – Вып. 89. – С. 16-21. 10. Леонов, А. В. Экспериментальная оценка возможности использования алгоритма муравьиной колонии AntHocNet для решения задачи маршрутизации в FANET // СПб: Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление – 2017. – Т. 10, Вып. 1 – С. 7–26. 11. Мудров, В. И. Задача о коммивояжёре. – М.: «Знание», 1969. – 62 с. 12. Скаков, Е. С. Методы и алгоритмы интеллектуальной поддержки принятия решений по оптимизации размещения элементов развивающихся информационных систем: диссертация на соискание ученой степени канд. физико-мат. наук: / Е. С. Скаков. – Липецк: Изд-во ФГБУ ВО «Липецкий государственный педагогический университет имени П.П. Семенова-Тян-Шанского», 2017. – 103 с. 13. Фомин, Г. П. Математические методы и модели в коммерческой деятельности: учебник: рек. Мин. обр. РФ / Г.П. Фомин. – 2-е изд., перераб. и доп. – М.: Финансы и статистика – 2005. – 616 с. 14. Ru.wikipedia.org: Венгерский алгоритм [Электронный ресурс]. Режим доступа: https://ru.wikipedia.org/wiki/Венгерский_алгоритм – 12.12. 2019. 15. Kuhn H. W. The Hungarian Method for the assignment problem – New York: McGravHill, 2008. – P. 83–97. 16. Ru.wikipedia.org: Алгоритм пчелиной колонии [Электронный ресурс]. Режим доступа: https://ru.wikipedia.org/wiki/Алгоритм_пчелиной_колонии – 12.12. 2019. 17. Чивилихин Д. С., Ульянцев В.И., Вяткин В.В., Шалыто А.А. Построение автоматных программ по спецификации с помощью муравьиного алгоритма 99

на основе графа мутаций // Научно-технический вестник информационных технологий, механики и оптики. 2014. №6 (94). 18. Abd Elmoniem A. M., Ibrahim, H.M., Mohamed M.H., Hedar A.-R. Ant Colony and Load Balancing Optimizations for AODV Routing Protcol // Int. J. Sens. Netw. DataCommun. – 2011. - Vol. 1. - P. 1–14. 19. Кажаров, А. А. Курейчик, В. М. Муравьиные алгоритмы для решения транспортных задач. // Известия РАН. Теория и системы управления. – 2010. – Вып. 1. – С. 32-45. 20. Bonavear E, Dorigo M. Swarm Intelligence: from Natural to Artificial Systems. – Oxford University Press. – 1999. – 307 p. 21. Долгова, О. Э. Муравьиные алгоритмы для решения задач маршрутизации транспорта: диссертация на соискание ученой степени канд. физико-мат. наук: / О.Э. Долгова. – Хабаровск: Изд-во ФГБУН ВЦ ДВО РАН, 2018. – 103 с. 22. Чураков, М. Якушев, А. Биологические принципы поведения муравьиной колонии. // Режим доступа: http://masters.donntu.org/2011/fknt/murzin/library/ docs/3.htm – 18.10.2019. 23. Blum C. Ant colony optimization: Introduction and recent trends // Phys. LifeRev. – 2005. – Vol. 2. No. 4. – P. 353–373. 24. Левитин, А. В. Глава 3. Метод грубой силы: Задача коммивояжёра // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. – С. 159–160. – 576 с. 25. McConnell J. Основы современных алгоритмов. М: Техносфера, перевед. – 2004. – 368 с. 26. Ладыженский, Ю.В. Мирецкая, В.А. Мирецкий, А.В. Применение муравьиных алгоритмов для решения задачи маршрутизации в компьютерных сетях // Научные Труды Донецкого Национального Технического Университета. – 2007. – Вып. 8(120) – С. 178–192. 27. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization // Reader for CEU Summer University Course «Complex System – Budapest: Central European University, 2001. – P. 1–38. 100

28. Cherix D. Note preliminaire sur la structure, la phenology et le regime alimentaire d'une super-colonie de Formicalugubris Zett. // Insects Sociaux 27 – 1980. – P. 226–236. 29. Cormen T. H., Leiserson C. I., Rivest R. L., Stein C. Алгоритмы: построение и анализ – Introduction to Algorithms. – Vol. 2. – Москва: «Вильямс», 2006. – 1296 p. 30. Sohabr.net: Введение в оптимизацию. Имитация отжига [Электронный ресурс]. Режим доступа: https://sohabr.net/post/209610/ – 12.12. 2018. 31. Caro G. D., Dorigo M. Anet: a Mobile Agents Approach toAdaptive Routing. Technical Report IRIDA 97-12. IRIDA–Universite Librede Brusseles – Brussels: Sretenie, 1997. – 27 p. 32. Reimann M. Ant Based Optimization in Good Transportation. PhD Thesis. University of Vienna. –Vienna, 2002. – 149 p. 33. Kirkpatrick S. Optimization by Simulated Annealing / S. Kirkpatrick, C.D. Gelatt Jr, M.P. Vecchi // Science. – 1983. – Vol. 220 – P. 671-680. 34. Алгоритм имитации отжига. // Wikipedia.org. Режим доступа: https://ru.wikipedia.org/wiki/Алгоритм_имитации_отжига: – 30.01.2020. 35. Устинов, С. М. Вычислительная математика / С.М. Устинов, В.А. Зимницкий. – СПб.: БХВ, 2009. – 336 с. 36. Gendreau M. Handbook of Metaheuristics (International Series in Operations Research and Management Science) / M. Gendreau, J. Y. Potvin. – Boston: Springer, 2010. – 675 p. 37. Szu H. H. Fast Simulated Annealing / H. H. Szu, R. L. Hartley// Physical Letters A. 122. – Boston: Springer, 2007 – P. 157-162. 38. Busetti F. Simulated annealing overview // Researchgate.net офиц. сайт. – Режим доступа: https://www.researchgate.net/publication/238690391_Simu- lated_annealing_ overview – 21.02.2020. 39. Лопатин, А. С. Метод отжига // Стохастическая оптимизация в информатике. СПб.: Изд-во СПбГУ, 2005. Вып. 1. – С. 133-149. 101

40. Karaboga D. An idea based on honey bee swarm for numerical optimization // Technical report - TR06, Erciyes University, Engineering Faculty – London: Routledge, 2005 г. – 10 p. 41. Pham D. T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M. The Bees Algorithm // Technical Note, Manufacturing Engineering Centre, Cardiff University – New York: Oxford University Press, 2005 г. – 6 p. 42. Тюхтина, А. А. Методы дискретной оптимизации: Часть 1: Учебнометодическое пособие. – Нижний Новгород: Нижегородский госуниверситет – 2014 г. – 62 с. 43. Гришин, А. А., Карпенко А. П. / Исследование эффективности метода пчелиного роя в задаче глобальной оптимизации // Машиностроение и компьютерные технологии. 2010. Вып. 8. Режим доступа: https://cyberleninka.ru /article/n/ issledovanie-effektivnosti-metoda-pchelinogo-roya-v-zadache-globalnoy- optimizatsii – 21.02.2020. 44. Habr.com: Сообщество IT-специалистов [Электронный ресурс]. Режим доступа: https://habr.com/ru/post/308960/ – 15.05. 2010. 45. Fxyz:ru: Интерактивный справочник формул [Электронный ресурс]. Режим доступа: https://www.fxyz.ru/формулы_по_математике/аналитическая_ геометрия/на_плоскости/точки_и_прямые_в_прямоугольной_системе_координат/расстояние_между_двумя_точками/ – 15.05. 2020. 46. Yandex.ru: Поисково-информационная картографическая служба Яндекса. Карта города Благовещенск [Электронный ресурс]. Режим доступа: https://yandex.ru/maps/ – 15.01.2019. 47. Map.project-osrm.org: OSRM. Карта города Благовещенск [Элек- тронный ресурс]. URL: https://map.project-osrm.org/ – 02.02. 2020. 102

ПРИЛОЖЕНИЕ А Листинг программы «Distance Matrix» на языке Python Файл « download_dist.py»: #!/usr/bin/env python # -*- coding: utf-8 -*# Author: Koltunov Nikolay Sergeevich # Position: undergraduate of AmSU 852 group # =========== Подключение библиотек и модулей =========== import speech_recognition as SR # библиотека для генерации голоса import pyttsx3 # библиотека преобразования текста в речь на Python def talk(words): engine = pyttsx3.init() engine.say(words) engine.runAndWait() talk("Инициализация программы") print("Загрузка ...") import os # функции для работы с операционной системой import subprocess # функции стандартных потоков ввода/вывода/ошибок import webbrowser # модуль для просмотра веб-документов import time # модуль для работы со временем import random # функции для генерации случайных чисел и т.п. import Parsing_file # дополнительный файл для обработки данных import requests # осуществляет работу с HTTP-запросами import urllib.request # библиотека HTTP from bs4 import BeautifulSoup # библиотека для осуществления синтаксического разбора документов HTML from fake_useragent import UserAgent # модуль для генерации случайных данных браузера UserAgent().firefox # =========== Инициализация данных =========== proxy = Parsing_file.Proxy() https_proxy = proxy.get_array_proxy() coords = {} # массив географ. координат для каждого адреса address = {} # массив наименование для каждого адреса coords[1] = "127.495682,50.261802" coords[2] = "127.500853,50.260975" coords[3] = "127.514224,50.259645" coords[4] = "127.517827,50.260643" coords[5] = "127.520566,50.258546" coords[6] = "127.523526,50.261361" coords[7] = "127.530861,50.258569" coords[8] = "127.541079,50.257364" coords[9] = "127.544888,50.255510" coords[10] = "127.549386,50.252979" coords[11] = "127.558503,50.253910" coords[12] = "127.572498,50.253657" coords[13] = "127.576786,50.259558" coords[14] = "127.570614,50.259424" coords[15] = "127.566703,50.258526" coords[16] = "127.560655,50.258162" coords[17] = "127.555666,50.258938" coords[18] = "127.549856,50.261493" coords[19] = "127.541178,50.263215" 103

Продолжение Приложения А Листинг программы «Distance Matrix» на языке Python coords[20] = "127.535095,50.261909" coords[21] = "127.528898,50.263509" coords[22] = "127.520615,50.267231" coords[23] = "127.512198,50.265087" coords[24] = "127.503583,50.264317" coords[25] = "127.491961,50.272537" coords[26] = "127.500949,50.274124" coords[27] = "127.512262,50.272973" coords[28] = "127.511705,50.270276" coords[29] = "127.525502,50.267586" coords[30] = "127.532595,50.269169" coords[31] = "127.540586,50.267687" coords[32] = "127.550086,50.268487" coords[33] = "127.562505,50.265965" coords[34] = "127.568715,50.268725" coords[35] = "127.558676,50.275122" coords[36] = "127.554142,50.280887" coords[37] = "127.522826,50.286233" coords[38] = "127.507082,50.292190" coords[39] = "127.510649,50.298262" coords[40] = "127.506885,50.305408" coords[41] = "127.511795,50.302783" coords[42] = "127.518534,50.302554" coords[43] = "127.526769,50.304711" coords[44] = "127.525736,50.291884" coords[45] = "127.543397,50.298302" coords[45] = "127.543397,50.298302" coords[46] = "127.546173,50.305032" coords[47] = "127.550263,50.302783" coords[48] = "127.558093,50.295714" coords[49] = "127.565734,50.290959" coords[50] = "127.541407,50.285178" # ====================================================== address[1] = "улица Ленина, 174" address[2] = "улица Ленина, 160" address[3] = "улица Ленина, 146" address[4] = "Рёлочный переулок, 4" address[5] = "улица Ленина, 130/1" address[6] = "Зейская улица, 212" address[7] = "Пионерская улица, 1" address[8] = "улица Ленина, 121" address[9] = "улица Ленина, 100" address[10] = "Театральная улица, 1" address[11] = "улица Фрунзе, 57/59" address[12] = "Первомайская улица, 19" 104

Продолжение Приложения А Листинг программы «Distance Matrix» на языке Python address[13] = "Амурская улица, 3" address[14] = "Амурская улица, 20" address[15] = "улица Лазо, 53" address[16] = "Зейская улица, 63" address[17] = "Зейская улица, 89" address[18] = "Амурская улица, 102" address[19] = "улица Шимановского, 40" address[20] = "улица 50 лет Октября, 15" address[21] = "улица Шевченко, 35" address[22] = "улица Калинина, 52" address[23] = "Амурская улица, 236" address[24] = "Артиллерийская улица, 20" address[25] = "Батарейная улица, 26" address[26] = "Октябрьская улица, 236" address[27] = "улица Мухина, 82" address[28] = "улица Мухина, 64" address[29] = "улица Горького, 157" address[30] = "Красноармейская улица, 143" address[31] = "Красноармейская улица, 82" address[32] = "Кузнечная улица, 113/1" address[33] = "Красноармейская улица, 53А" address[34] = "улица Лазо, 101" address[35] = "Свободная улица, 33" address[36] = "Театральная улица, 170" address[37] = "Тенистая улица, 160" address[38] = "Студенческая улица, 19/1" address[39] = "Игнатьевское шоссе, 21" address[40] = "улица Воронкова, 26" address[41] = "Институтская улица, 15" address[42] = "Студенческая улица, 43" address[43] = "улица Воронкова, 8/А4" address[44] = "улица Калинина, 130" address[45] = "улица 50 лет Октября, 202" address[46] = "улица 50 лет Октября, 239" address[47] = "Кольцевая улица, 34" address[48] = "Театральная улица, 236" address[49] = "улица Чайковского, 175" address[50] = "Тенистая улица, 91" # ====================================================== # i = s0 # переменная для цикла, строки j = s0 # переменная для цикла, столбцы N = len(coords) + 1 # кол-во адресов + 1 temp_i = "" # инициализация буферной переменной temp_j = "" # инициализация буферной переменной 105

Продолжение Приложения А Листинг программы «Distance Matrix» на языке Python temp_s = "" # инициализация буферной переменной temp_d = "" # инициализация буферной переменной distance = "" # строка для хранения одной дистанции distance_all = "" # строка для хранения всех дистанций length = 0 # счетчик использованных адресов прокси # =========== Выполнение программы =========== talk("Выполнение программы") start_time = time.time() # начало отсчет программы while i < N: # изменение порядка координат(Д,Ш) -> (Ш,Д), строки temp_i = coords[i].split(',') coords_i = str(','.join(temp_i[::-1])) while j < N: # Изменение порядка координат(Д,Ш) -> (Ш,Д), столбцы temp_j = coords[j].split(',') coords_j = str(','.join(temp_j[::-1])) if i != j: # формирование ссылки запроса url = "https://yandex.ru/maps/77/blagoveshchensk/?ll=127.512254,50.285279 &mode=routes&rtext=" + coords_i + "~" + coords_j + "&rtt=auto&ruri=ymapsbm1 ://geo?ll=" + coords[i] + &spn=0.001,0.001&text=Россия, Амурская область, Благовещенск, " + address[i] + "~ymapsbm1://geo?ll=" + coords[j] + "&spn=0.001 ,0.001&text=Россия, Амурская область, Благовещенск, " + address[j] + "&z=15.0" # установка данных о поисковой машине headers = { 'User-Agent': UserAgent().firefox } # установка IP-адреса прокси-сервера proxyDict = { 'https': 'https://{0}'.format(https_proxy[length]) } # проверка на успешность запроса try: r = requests.get(url, headers=headers, proxies=proxyDict) if r.status_code == 200: talk("Загрузка точек: " + str(i) + " и " + str(j)) else: print("Ошибка сервера" + str(r.status_code)) talk("Ошибка сервера") length += 1 continue html = r.text 106

Продолжение Приложения А Листинг программы «Distance Matrix» на языке Python # обработка исключений, т.е. ошибок except Exception: length += 1 if length >= len(https_proxy): print('proxy undefined') getch() #print("next proxy") talk("новый прокси") continue # обработка html-кода и извлечение информации о дистанции маршрута soup = BeautifulSoup(html, 'html.parser') obj = soup.find('div', attrs={'class': 'auto-route-snippet-view__route-subtitle'}) temp_s = obj.text.split(", ") distance = temp_s[0] temp_s = distance.split("\xa0") if temp_s[1] == "м": temp_d = float(distance.replace(',','.').replace('\xa0м','')) distance = round(temp_d / 1000, 1) elif temp_s[1] == "км": distance = float(distance.replace(',','.').replace('\xa0км','')) else: temp_d = float(distance.replace('\xa0000\xa0м','.0')) print("Точка: " + str(i) + "-" + str(j) + "\t->\t" + str(distance)) distance_all = distance_all + (str(distance) + "\t") else: distance_all = distance_all + "0\t" print("Точка: " + str(i) + "-" + str(j) + "\t->\t" + "0") j += 1 # запись дистанций в строку distance_all = distance_all + "\n" i += 1 j = s0 if (i < s0 and s0 == 0) else 1; # =========== Вывод загруженных данных =========== f = open('card_data.txt', 'w') f.write("Расстояния, от одного пункта до другого пункта: \n" + distance_all) f.close() talk("Запись данных в блокнот успешно завершена") print("\n\n" + distance_all) print("Время выполнения: %s минут или " % ((time.time() - start_time)//60) + "%s секунда" % ((time.time() - start_time)//1)) 107

Продолжение Приложения А Листинг программы «Distance Matrix» на языке Python Файл «Parsing_file.py»: import requests # библиотека для осуществления работы с HTTPзапросами import urllib.request # библиотека HTTP from lxml import html # библиотека для обработки разметки xml и html, импортируем только для работы с html from bs4 import BeautifulSoup # библиотека для осуществления синтаксического разбора документов HTML class Proxy: # создание класса proxy_url = 'http://www.ip-adress.com/ proxy_list/' # присвоение ссылки сайта, выставляющего проксисервера proxy_list = [] # пустой массив для заполнения def __init__(self): # функция конструктора класса с передачей параметра self r = requests.get(self.proxy_url) # http-запрос методом get, запрос нужно осуществлять только с полным url str = html.fromstring(r.content) # преобразование документа к типу lxml.html.HtmlElement ip = str.xpath( "//tbody/tr/td[1]/a/text()") # берем содержимое тега вместе с внутренними тегами для получение списка прокси count = len(ip) result = [] for i in range(0, count): proxy_tmp = ip[i] + ':' + str.xpath(f'//tbody/tr[{i + 1}]/td[1]/text()')[0] result.append(proxy_tmp) self.list = result # конструктору класса приравниваем прокси def get_proxy(self): # функция с передачей параметра self for proxy in self.list: # в цикле перебираем все найденные прокси proxy = proxy.replace('::', ':') url = f'https://{proxy}' return url def get_array_proxy(self): # функция для работы массивом прокси proxy_list = [] for proxy in self.list: proxy_list.append(str(proxy.replace('::', ':'))) return proxy_list 108

ПРИЛОЖЕНИЕ Б Листинг вычислительной программы «Ant Colony Algorithm» в ППП MATLAB %% РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА МУРАВЬИННЫМ АЛГОРИТМОМ clc;clear;close;clearvars;close all; % очистка данных и закрытие окон tic % начало отсчета %*********************************************************** %% I.ИНИЦИЛИЗАЦИЯ ВХОДНЫХ ДАННЫХ И ДРУГИХ ПАРАМЕТРОВ ProgramData_new(1); % функция с входными данными global points_to_50;global CitiesCoord; % глобальные переменные... global dist;global nCity;global osm; % ... с функции ProgramData % ВЫБОР кол-ва точек/адресов маршрута, максимум 50 nCity = 50; % ВЫБОР кол-ва итераций (поколений) age = nCity*10; countage = nCity; % кол-во муравьев в поколении RANDperm = randperm(nCity); % перестановка точек без повторений returndist = zeros(nCity,nCity); % матрица обратных расстояний temp(:,1) = CitiesCoord(:,2); % изменение формата на ... temp(:,2) = CitiesCoord(:,1); % ... (ш,д)->(д,ш) % Загрузка готовой матрицы расстояний dist = points_to_50; for i = 1:nCity for j = 1:nCity if i ~= j returndist(i,j) = 1/dist(i,j); end end end % ANT настройки a = 0; % коэффициент запаха, при 0 -> по кратчайшему пути b = 2; % бета - коэффициент расстояния, при 0 ориентируется по оставляемому запаху ro = 0.3; % коэффициент испарения (память поколений) Q = 1; % количество выпускаемых феромонов elite = 1; % кол-во элитных муравьев (увеличение лучшей дистанции в elite раз) ph = 0.01; % начальный феромон tao = ph*(ones(nCity,nCity)); % матрица начальных феромонов %% II.ОСНОВНАЯ ЧАСТЬ % Инициализация массивов ROUTEant = zeros(countage,nCity); % матрица маршрута муравьев в одном поколении DISTant = zeros(countage,1); % вектор расстояний муравьев в одном поколении ROUTE = zeros(1,nCity+1); % оптимальные маршруты P = zeros(1,nCity); % матрица вероятностей bestROUTE = zeros(1,nCity); % лучший маршрут DistAge = zeros(age,1); % хранение дистанций каждого поколения bestDIST = inf; % лучший начальный маршрут % кол-во муравьев в поколении 109

Продолжение Приложения Б Листинг вычислительной программы «Ant Colony Algorithm» в ППП MATLAB err = 0; % счетчик ошибок в вероятностях % Расчеты при разном количестве итераций for it = 1:age % муравьи (одно поколение) for k = 1:countage ROUTEant(k,1) = RANDperm(k); % начальное расположение муравьев % путь каждого муравья, со второго, т.к. 1 выбран for s = 2:nCity ir = ROUTEant(k,s-1); % индекс выбранного города P = tao(ir,:).^a .* returndist(ir,:).^b; P(ROUTEant(k,1:s-1)) = 0; P = P./sum(P); % вероятность перехода (сумма строк должна = 1) % определение города, куда перешел RANDONE = rand; getcity = find(cumsum(P)>=RANDONE,1,'first'); % проверка на ошибку в вероятностях if isempty(getcity) == 1 err =+ 1; getcity = 1; end ROUTEant(k,s) = getcity; % s-ый город -> путь k-ому муравью end ROUTE = [ROUTEant(k,1:end),ROUTEant(k,1)]; % маршрут k-ого муравья S = 0; % сброс длины for i = 1:nCity S = S + dist(ROUTE(i),ROUTE(i+1)); % вычисление маршрута k-ого муравья end DISTant(k) = S; % путь k-ого муравья, массив дистанций kых муравьев % присвоение лучшего маршрута и S if DISTant(k) < bestDIST bestDIST = DISTant(k); % лучшая дистанция маршрута bestROUTE = ROUTEant(k,1:end); % порядок точек маршрута end end % Изменение кол-ва феромонов tao = (1-ro)*tao; % испарение феромонов "старого" пути for u = 1:countage ROUTE = [ROUTEant(u,1:end),ROUTEant(u,1)]; % получение маршрута u-ого муравья % для каждого города for t = 1:nCity x = ROUTE(t); 110

Продолжение Приложения Б Листинг вычислительной программы «Ant Colony Algorithm» в ППП MATLAB y = ROUTE(t+1); % подсчет нового феромона if DISTant(u) ~= max(DISTant) % добавка феромона в зависимости от S tao(x,y) = tao(x,y) + Q/DISTant(u); else % << усиление ребра лучшего пути>> tao(x,y) = tao(x,y)+(elite*Q)/DISTant(u); end end end DistAge(it,1) = round(bestDIST,2); end bestROUTE; % оптимальная траектория [a, b, c,...] ROUTEend = [bestROUTE(1,1:end),bestROUTE(1,1)]; % длина опт-го маршрута [a, b, c,... a] bestDIST = 0; for i = 1:nCity bestDIST = bestDIST + dist(ROUTEend(i),ROUTEend(i+1)); end bestDIST = round(bestDIST); %% III. Вывод результатов и построение графиков ВЫВОД РЕЗУЛЬТАТОВ И ПОСТРОЕНИЕ ГРАФИКОВ % вывод на консоль основной информации о решении алгоритма fprintf(['<<< Муравьиный алгоритм >>>\n'... 'Кол-во точек маршрута:\t' num2str(nCity) '\n'... 'Кол-во итераций:.\t\t' num2str(age) '\n'... 'Порядок точек маршрута:\t' num2str(ROUTEend) '\n'... 'Динамика оптимизации:\t',num2str(DistAge(1,1)),... '->',num2str(DistAge(age,1)), '(км)\n',... 'Дистанция маршрута:\t\t' num2str(bestDIST) '(км)\n'... 'Кол-во ошибок в вероятностях:\t',num2str(err), '\n'... '********************************************\n']); figure(1); % график зависимости расстояний от итераций plot(DistAge,... '.m-',... 'Color','#b05612',... 'LineWidth',0.5); xlabel('Итерации');ylabel('Дистанция маршрута');grid on; title('Динамика оптимизации построения маршрута'); set(findall(gcf,'type','axes'),'fontsize',10); set(findall(gcf,'type','text'),'fontSize',15); figure(2); % график оптимального кольцевого маршрута citiesOP(:,[1,2]) = temp(bestROUTE(:),[1,2]); plot([citiesOP(:,1);citiesOP(1,1)],[citiesOP(:,2);citiesOP(1,2)],... 'LineWidth',1,... 'Color','#b05612',... 111

Продолжение Приложения Б Листинг вычислительной программы «Ant Colony Algorithm» в ППП MATLAB 'Marker','o',... 'MarkerFaceColor','red',... 'MarkerSize',8); xlabel('Долгота');ylabel('Широта');grid on; title(['Точек: ', num2str(nCity),... ', Дистанция: ',num2str(bestDIST),... ', Итераций: ',num2str(age)]); set(findall(gcf,'type','axes'),'fontsize',10); set(findall(gcf,'type','text'),'fontSize',15); % Построение маршрута на карте с помощью OSM за счет построения ссылки координатами(ш,д) url_str = join(string(CitiesCoord),"%2C"); for j = 1:nCity+1 url_Coords = url_str(ROUTEend(j)); if j == 1 url_base = osm; url = append(url_base,url_Coords); end url =append(url,url_Coords); if j ~= nCity+1 url = append(url,"&loc="); else url = append(url,"&hl=ru&alt=0"); end end web(url,'-new') % открытие в браузере Matlab %*********************************************************** timerVal = toc; % вывод времени работы скрипта disp("Общее затраченное время на расчет маршрута: "... + round(timerVal) +" сек."); 112

ПРИЛОЖЕНИЕ В Листинг вычислительной программы «Annealing Simulation Algorithm» в ППП MATLAB %% РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА ИМИТАЦИОННЫМ ОТЖИГОМ clc;clear;close;clearvars; % очистка данных tic % начало отсчета %*********************************************************** %% I.ИНИЦИЛИЗАЦИЯ ВХОДНЫХ ДАННЫХ И ДРУГИХ ПАРАМЕТРОВ ProgramData_new(1); % функция с входными данными global points_to_50;global CitiesCoord; % глобальные переменные... global dist;global nCity;global osm; % ... с функции ProgramData % ВЫБОР кол-ва точек/адресов маршрута, максимум 50 nCity = 50; % ВЫБОР кол-ва итераций (поколений) age = nCity*100; temp(:,1) = CitiesCoord(:,2); % изменение формата на ... temp(:,2) = CitiesCoord(:,1); % ...(ш,д)->(д,ш) % Загрузка готовой матрицы расстояний dist = points_to_50; % SA настройки T_start = 1; % начальная температура T_end = T_start/max(age); % конечная температура T = T_start; % начальная температура для вычислений S = inf; % расстояние %% II.ОСНОВНАЯ ЧАСТЬ % Инициализация массивов ROUTE = randperm(nCity); % создание случайного маршрута P = zeros(1,nCity); % матрица вероятностей bestROUTE = zeros(1,nCity); % лучший маршрут DistAge = zeros(age,1); % хранение дистанций каждого поколения % Рассчеты при разном количестве итераций for it = 1:age Sp = 0; % сброс потенциального расстояния % условие создания потенциальных маршрутов ROUTEp = ROUTE; % потенциальный маршрут transp = randperm(nCity,2); % два случайных города % переворот вектора, взяли два сгенерированных числа ... % ... transp и перевернули маршрут между ними if transp(1) < transp(2) ROUTEp(transp(1):transp(2)) = ... fliplr(ROUTEp(transp(1):transp(2))); else ROUTEp(transp(2):transp(1)) = ... fliplr(ROUTEp(transp(2):transp(1))); end % вычисление расстояния потенциального маршрута for i = 1:nCity-1 Sp = Sp + dist(ROUTEp(i),ROUTEp(i+1)); end Sp = Sp + dist(ROUTEp(1),ROUTEp(end)); 113

Продолжение Приложения В Листинг вычислительной программы «Annealing Simulation Algorithm» в ППП MATLAB % если он меньше, то потенц. маршрут становится основным if Sp < S S = Sp; ROUTE = ROUTEp; % иначе, определяется, был ли переход else RANDONE = rand(1); % рандом от 0 до 1 Formul_M = exp((-(Sp - S)) / T); % формула Метрополиса P = Formul_M; if RANDONE <= P S = Sp; ROUTE = ROUTEp; end end bestROUTE = ROUTE; DistAge(it,1) = round(S,2); T = T_start / it; % уменьшение температуры % проверка условия выхода if T <= T_end break; end end ROUTEend = [ROUTE(1,1:end),ROUTE(1,1)]; % длина опт-го маршрута [a, b, c,... a] bestDIST = 0; for i = 1:nCity bestDIST = bestDIST + dist(ROUTEend(i),ROUTEend(i+1)); end bestDIST = round(bestDIST); %% III.ВЫВОД РЕЗУЛЬТАТОВ И ПОСТРОЕНИЕ ГРАФИКОВ % вывод на консоль основной информации о решении алгоритма fprintf(['<<< Алгоритм имитационного отжига >>>\n'... 'Кол-во точек маршрута:\t' num2str(nCity) '\n'... 'Кол-во итераций:.\t\t' num2str(age) '\n'... 'Порядок точек маршрута:\t' num2str(ROUTEend) '\n'... 'Динамика оптимизации:\t',num2str(DistAge(1,1)),... '->',num2str(DistAge(age,1)), '(км)\n',... 'Дистанция маршрута:\t\t' num2str(bestDIST) '(км)\n'... '********************************************\n']); figure(1); % график зависимости расстояний от итераций plot(DistAge,... '.m-',... 'Color','#4512c7',... 'LineWidth',0.5); xlabel('Итерации');ylabel('Дистанция маршрута');grid on; title('Динамика оптимизации построения маршрута'); set(findall(gcf,'type','axes'),'fontsize',10); 114

Продолжение Приложения В Листинг вычислительной программы «Annealing Simulation Algorithm» в ППП MATLAB set(findall(gcf,'type','text'),'fontSize',15); figure(2); % график оптимального кольцевого маршрута citiesOP(:,[1,2]) = temp(bestROUTE(:),[1,2]); plot([citiesOP(:,1);citiesOP(1,1)],[citiesOP(:,2);citiesOP(1,2)],... 'LineWidth',1,... 'Color','#4512c7',... 'Marker','o',... 'MarkerFaceColor','blue',... 'MarkerSize',8); xlabel('Долгота');ylabel('Широта');grid on; title(['Точек: ', num2str(nCity),... ', Дистанция: ',num2str(bestDIST),... ', Итераций: ',num2str(age)]); set(findall(gcf,'type','axes'),'fontsize',10); set(findall(gcf,'type','text'),'fontSize',15); % Построение маршрута на карте с помощью OSM ... % ... за счет построения ссылки координатами(ш,д) url_str = join(string(CitiesCoord),"%2C"); for j = 1:nCity+1 url_Coords = url_str(ROUTEend(j)); if j == 1 url_base = osm; url = append(url_base,url_Coords); end url =append(url,url_Coords); if j ~= nCity+1 url = append(url,"&loc="); else url = append(url,"&hl=ru&alt=0"); end end web(url,'-new') % открытие в браузере Matlab %*********************************************************** timerVal = toc; % вывод времени работы скрипта disp("Общее затраченное время на расчет маршрута: "... + round(timerVal) +" сек."); 115

ПРИЛОЖЕНИЕ Г Листинг вычислительной программы «Bee Swarm Algorithm» в ППП MATLAB %% РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА ПЧЕЛИННЫМ АЛГОРИТМОМ clc;clear;close;clearvars;close all; % очистка данных и закрытие окон tic % начало отсчета %*********************************************************** %% I.ИНИЦИЛИЗАЦИЯ ВХОДНЫХ ДАННЫХ И ДРУГИХ ПАРАМЕТРОВ ProgramData_new(1); % функция с входными данными global points_to_50;global CitiesCoord; % глобальные переменные... global dist;global nCity;global osm; % ... с функции ProgramData % ВЫБОР кол-ва точек/адресов маршрута, максимум 50 nCity = 50; % ВЫБОР кол-ва итераций (поколений) age = nCity*10; CostFunction = @(x) ABC_Distances(x); % целевая функция countage = nCity; % кол-во муравьев в поколении RANDperm = randperm(nCity); % перестановка точек без повторений returndist = zeros(nCity,nCity); % матрица обратных расстояний temp(:,1) = CitiesCoord(:,2); % изменение формата на ... temp(:,2) = CitiesCoord(:,1); % ... (ш,д)->(д,ш) % Загрузка готовой матрицы расстояний dist = points_to_50; for i = 1:nCity for j = 1:nCity if i ~= j returndist(i,j) = 1/dist(i,j); end end end % ABC НАСТРОЙКИ nVar = age; % кол-во переменных решения VarSize = [1 nVar]; % размер матрицы переменных решения VarMin = 1; % переменные решения Нижняя граница VarMax = nCity; % переменные решения Верхняя граница nPop = nCity; % размер колонии nOnlooker = nPop; % кол-во пчел-наблюдателей L = round(5*nVar*nPop); % параметр предела отмены a = 1; % коэффициент ускорения, верхняя граница ph = 0.01; % начальный феромон tao = ph*(ones(nCity,nCity)); % матрица начальных феромонов d1 = size(a); % Инициализация массивов empty_bee.Position = []; % массив позиций пчелы empty_bee.Route = []; % массив маршрута пчелы empty_bee.Cost = []; % массив расстояние пчелы pop = repmat(empty_bee,nPop,1); % создание массива «населения» BestPop.Cost=inf; % инициализировать лучшее решение, когда-либо найденное % Создание начальной эталонной популяции 116

Продолжение Приложения Г Листинг вычислительной программы «Bee Swarm Algorithm» в ППП MATLAB for i=1:nPop pop(i).Position = randperm(nCity, nCity); % точки маршрута pop(i).Route = [pop(i).Position(1:end),pop(i)... .Position(1,1)]; % точки кольцевого маршрута pop(i).Cost = CostFunction(pop(i).Route); % дистанция кольцевого маршрута if pop(i).Cost <= BestPop.Cost BestPop = pop(i); % эталонное решение, с которым будет дальнейшие сравнение end end C = zeros(nPop,1); % счетчик отказов DistAge = zeros(age,1); % массив для хранения лучших значений расстояния %% I. ОСНОВНАЯ ЧАСТЬ % Рассчеты при разном количестве итераций ROUTEbee = zeros(nPop,nCity); % матрица маршрута пчел в одном поколении DISTbee = zeros(nPop,1); % расстояния пчел в одном поколении % Перебор всех итераций алгоритма for it = 1:age % 1)Перебор завербованных пчел for i = 1:nPop % Оценка newbee.Position = randperm(nCity, nCity); newbee.Route = [newbee.Position(1:end),newbee... .Position(1,1)]; % точки кольцевого маршрута newbee.Cost = CostFunction(newbee.Route); % Сравнение if newbee.Cost <= pop(i).Cost pop(i) = newbee; else C(i) = C(i)+1; end end % Рассчет фитнес-значения и вероятности выбора F = zeros(nPop,1); MeanCost = mean([pop.Cost]); for i=1:nPop F(i) = exp(-pop(i).Cost/MeanCost); % конвертирование !Стоимость в Фитнес! end P=F/sum(F); % 2)перебор пчелы-наблюдателей for m = 1:nOnlooker k = randi(nPop); newbee.Position=pop(k).Position; % новая позиция пчелы newbee.Route = [newbee.Position(1:end),newbee... 117

Продолжение Приложения Г Листинг вычислительной программы «Bee Swarm Algorithm» в ППП MATLAB .Position(1,1)]; % точки кольцевого маршрута newbee.Cost = CostFunction(newbee.Route); % Оценка newbee.Cost = CostFunction(newbee.Route); % Сравнение if newbee.Cost <= pop(i).Cost pop(i) = newbee; else C(i) = C(i)+1; end end % 3)Перебор пчел-разведчиков for i=1:nPop if C(i) >= L pop(i).Position = randperm(nCity, nCity); pop(i).Cost = CostFunction(pop(i).Route); C(i) = 0; end end % Обновление лучшего решения из когда-либо найденных for i=1:nPop if pop(i).Cost <= BestPop.Cost BestPop = pop(i); end end DistAge(it) = round(BestPop.Cost); % лучшее решение из когдалибо найденных end %Оптимальная траектория bestROUTE = BestPop.Route; % длина опт-го маршрута [a, b, c,... a] bestDIST = 0; for i = 1:nCity bestDIST = bestDIST + dist(bestROUTE(i),bestROUTE(i+1)); % вычисление расстояния опт-го маршрута end bestDIST = round(bestDIST); %% III. Вывод результатов и построение графиков ВЫВОД РЕЗУЛЬТАТОВ И ПОСТРОЕНИЕ ГРАФИКОВ % вывод на консоль основной информации о решении алгоритма fprintf(['<<< Алгоритм пчелиной колонии >>>\n'... 'Кол-во точек маршрута:\t' num2str(nCity) '\n'... 'Кол-во итераций:.\t\t' num2str(age) '\n'... 'Порядок точек маршрута:\t' num2str(bestROUTE) '\n'... 'Динамика оптимизации:\t',num2str(DistAge(1,1)),... '->',num2str(DistAge(age,1)), '(км)\n',... 'Дистанция маршрута:\t\t' num2str(bestDIST) '(км)\n'... '********************************************\n']); figure(1); % график зависимости расстояний от итераций 118

Продолжение Приложения Г Листинг вычислительной программы «Bee Swarm Algorithm» в ППП MATLAB plot(DistAge,... '.m-',... 'Color','#34ab27',... 'LineWidth',0.5); xlabel('Итерации');ylabel('Дистанция маршрута');grid on; title('Динамика оптимизации построения маршрута'); set(findall(gcf,'type','axes'),'fontsize',10); set(findall(gcf,'type','text'),'fontSize',15); figure(2); % график оптимального кольцевого маршрута citiesOP(:,[1,2]) = temp(bestROUTE(:),[1,2]); plot([citiesOP(:,1);citiesOP(1,1)],[citiesOP(:,2);citiesOP(1,2)],... 'LineWidth',1,... 'Color','#34ab27',... 'Marker','o',... 'MarkerFaceColor','green',... 'MarkerSize',8); xlabel('Долгота');ylabel('Широта');grid on; title(['Точек: ', num2str(nCity),... ', Дистанция: ',num2str(bestDIST),... ', Итераций: ',num2str(age)]); set(findall(gcf,'type','axes'),'fontsize',10); set(findall(gcf,'type','text'),'fontSize',15); % Построение маршрута на карте с помощью OSM ... % ... за счет построения ссылки координатами(ш,д) url_str = join(string(CitiesCoord),"%2C"); % формирование ссылки для сайта for j = 1:nCity+1 url_Coords = url_str(bestROUTE(j)); if j == 1 url_base = osm; url = append(url_base,url_Coords); end url =append(url,url_Coords); if j ~= nCity+1 url = append(url,"&loc="); else url = append(url,"&hl=ru&alt=0"); end end web(url,'-new') % открытие в браузере Matlab %*********************************************************** timerVal = toc; % вывод времени работы скрипта disp("Общее затраченное время на расчет маршрута: "... + round(timerVal) +" сек."); 119

Продолжение Приложения Г Листинг вычислительной программы «Bee Swarm Algorithm» в ППП MATLAB Функция «ABC_Distances»: function D = ABC_Distances(x) global nCity;global dist; D = 0; % сброс длины % вычисление маршрута i-ой пчелы for i = 1:nCity D = D + dist(x(i),x(i+1)); end end 120

ПРИЛОЖЕНИЕ Д Листинг дополнительной функции к программам «ProgramData_new» в ППП MATLAB function y = ProgramData_new(x) y = x; % Ввод обычной матрицы и обратной матрицы расстояний global osm; osm = "https://map.project-osrm.org/?z=13&center=50.293013%2C127.551098&loc="; global points_to_50;global CitiesCoord; points_to_50 = ... [0 0.4 1.3 1.7 1.9 2.2 2.6 4.2 4.5 4.9 5.4 6.2 6.5 5.9 5.5 5.0 5.3 4.6 3.8 3.2 2.9 2.6 1.8 1.0 2.4 2.2 2.4 2.1 3.5 3.8 4.3 5.1 5.8 6.6 6.4 6.6 4.6 5.3 6.0 7.2 6.8 6.5 7.3 6.2 7.2 8.0 8.2 8.4 8.5 5.9; 0.4 0 1.0 1.4 1.5 1.8 2.2 3.8 4.1 4.5 5.0 5.8 6.1 5.6 5.2 4.6 4.9 4.2 3.5 2.8 2.6 2.4 1.4 0.6 2.3 2.2 2.1 1.7 3.1 3.4 3.9 4.7 5.5 6.2 6.0 6.3 4.2 5.0 5.6 6.8 6.4 6.1 6.9 5.8 6.8 7.6 7.8 7.8 8.2 5.5; 1.3 1.0 0 0.4 0.5 0.9 1.2 2.9 3.1 3.5 4.1 4.8 5.1 4.6 4.2 3.6 3.9 3.2 2.5 1.9 1.5 1.4 0.9 1.2 3.0 2.6 1.8 1.5 2.2 2.4 2.9 3.7 4.5 5.2 5.0 5.3 3.9 4.7 5.3 6.6 6.8 5.8 7.2 5.5 6.7 7.5 7.6 7.1 7.2 4.6; 2.0 1.6 0.7 0 0.5 0.7 1.2 2.5 2.8 3.2 3.7 4.5 4.8 4.3 4.1 3.8 3.6 2.9 2.2 1.5 1.2 1.8 1.3 1.6 3.3 3.0 2.1 1.8 1.9 2.1 2.6 3.4 4.2 4.9 4.7 5.0 4.6 5.0 5.7 6.9 6.5 6.2 6.8 5.9 6.8 7.6 7.7 6.8 6.9 4.2; 1.9 1.5 0.5 0.9 0 0.6 0.9 2.6 2.8 3.2 3.8 4.5 4.8 4.3 3.9 3.3 3.6 2.9 2.2 1.6 1.2 1.9 1.4 1.7 3.5 3.2 2.3 2.0 1.9 2.1 2.6 3.4 4.2 4.9 4.7 5.0 4.4 5.2 5.8 7.0 6.6 6.3 7.1 6.0 6.8 7.6 7.8 6.7 6.9 4.2; 2.3 1.9 0.9 1.1 0.6 0 0.8 1.9 2.2 2.6 3.1 3.9 4.2 3.7 3.5 2.7 3.0 2.2 1.6 0.9 0.6 1.7 1.2 1.5 3.3 3.0 2.1 1.8 1.3 1.5 2.0 2.8 3.6 4.3 4.1 4.6 3.9 5.0 5.6 6.9 6.4 6.1 6.7 5.8 6.2 7.0 7.1 6.1 6.3 3.6; 2.6 2.2 1.2 1.6 0.9 1.0 0 1.6 1.9 2.3 2.8 3.6 3.9 3.4 3.2 2.4 2.3 1.9 1.3 0.6 0.8 2.1 2.0 2.3 4.2 3.9 3.0 2.7 1.4 1.2 1.7 2.5 3.3 4.0 3.8 4.1 4.1 5.9 6.5 7.8 6.7 7.0 6.4 6.8 6.3 7.8 7.3 5.9 6.0 3.3; 3.3 2.9 1.9 2.3 1.6 1.7 0.8 0 1.2 1.7 2.2 2.9 3.3 3.3 2.9 1.8 1.7 1.4 0.9 1.0 1.6 2.5 2.8 3.1 4.9 4.6 3.8 3.4 2.2 2.0 1.4 1.9 2.7 3.4 3.2 3.7 4.8 6.9 6.9 8.3 7.6 7.3 7.2 7.1 6.9 7.2 7.9 5.2 5.4 3.7; 4.4 4.0 3.1 3.2 2.8 2.4 1.9 0.5 0 0.5 1.3 2.0 2.9 2.4 2.0 1.4 1.4 0.8 1.4 1.5 2.1 3.4 3.4 3.7 5.5 5.1 4.4 3.9 2.8 2.5 2.0 1.6 3.1 3.1 2.8 3.1 5.4 8.5 8.3 9.6 8.9 8.6 8.0 8.4 6.1 6.8 7.1 4.9 5.0 4.1; 121

Продолжение Приложения Г Листинг дополнительной функции к программам «ProgramData_new» в ППП MATLAB 4.9 4.5 3.5 1.4 1.1 1.9 3.1 3.0 2.8 5.0 4.5; 5.4 5.0 4.0 0.9 1.6 2.4 2.2 2.1 2.9 4.6 5.0; 6.1 5.8 4.8 1.7 2.4 3.2 2.2 2.1 3.6 5.3 5.9; 6.4 6.0 5.1 1.7 2.0 3.2 1.8 1.8 3.3 5.0 5.4; 6.0 5.6 4.7 1.3 1.6 2.4 1.4 1.4 2.8 4.6 5.0; 5.5 5.1 4.2 1.1 1.4 2.6 1.2 1.2 2.6 4.4 4.8; 5.0 4.6 3.6 0.5 1.1 2.0 1.7 1.6 2.3 4.1 4.5; 4.9 4.5 3.6 0.9 1.7 2.0 1.9 2.1 3.1 4.3; 4.5 4.1 3.1 0.9 0 0.9 1.4 2.2 2.0 4.2 3.5; 3.9 3.5 2.6 1.6 0.8 0 1.9 2.7 2.4 4.7 2.8; 3.2 2.8 1.8 2.1 1.3 0.6 2.6 3.4 3.2 5.4 2.7; 3.6 3.2 2.9 2.3 1.0 0.5 0 1.0 2.0 2.9 2.3 2.0 1.4 2.0 2.6 3.9 3.8 4.1 5.9 5.6 4.8 4.4 3.2 3.0 2.4 2.0 3.3 5.8 8.5 8.2 9.5 8.9 8.6 7.9 8.4 6.1 6.8 7.1 4.9 4.1 3.7 3.4 2.8 1.5 1.3 0.9 0 1.1 2.0 1.5 1.1 0.5 2.5 3.1 4.4 4.4 4.7 6.4 6.1 5.3 4.9 3.7 3.5 2.9 2.5 3.8 6.3 9.0 8.8 10 9.4 9.1 8.5 8.9 6.6 7.3 7.6 5.4 5.2 4.5 4.1 3.6 2.3 2.0 2.0 1.1 0 1.0 0.9 1.1 1.3 3.3 4.0 5.1 5.1 5.5 7.2 6.9 6.1 5.7 4.5 4.3 3.7 3.3 4.6 7.1 9.8 9.5 11 10 10 9.2 9.7 7.4 8.1 8.3 6.2 5.8 4.8 4.4 3.9 3.1 2.9 2.9 2.0 1.0 0 0.7 1.0 1.5 3.2 3.6 4.8 4.8 5.5 6.8 6.5 5.6 5.3 4.2 3.9 3.3 2.9 4.2 6.7 9.4 9.2 10 9.8 9.7 8.9 9.3 7.0 7.7 8.4 5.9 4.7 4.3 4.0 3.4 2.7 2.5 2.5 1.6 0.8 0.5 0 0.6 1.1 2.8 3.2 4.4 4.4 5.1 6.4 6.1 5.2 4.9 3.7 3.5 2.9 2.5 3.8 6.3 9.0 8.8 10 9.4 9.3 9.0 8.9 6.6 7.3 7.6 5.4 4.3 3.9 3.5 3.0 2.3 2.0 2.0 1.1 1.1 1.0 0.6 0 0.6 2.6 3.0 4.2 4.1 4.8 6.2 5.9 5.1 4.7 3.5 3.3 2.7 2.3 3.6 6.1 8.8 8.6 9.8 9.2 8.9 8.8 8.7 6.4 7.1 7.8 5.2 3.7 3.3 3.0 2.5 1.7 1.5 1.5 0.6 1.3 1.5 1.0 0.8 0 2.1 2.7 3.9 3.8 4.3 5.9 5.6 4.7 4.4 3.2 3.0 2.4 2.0 3.3 5.8 8.5 8.2 9.5 8.9 8.8 7.9 8.4 6.5 6.8 7.5 4.9 3.6 3.3 2.9 2.3 1.6 1.4 1.4 1.0 1.7 1.8 1.3 1.1 0.5 0 2.5 3.7 3.6 4.2 5.7 5.4 4.6 4.2 3.0 2.8 2.2 1.8 1.1 5.6 8.3 8.1 9.3 8.7 8.5 8.3 8.2 5.9 6.6 7.3 4.7 3.8 3.2 2.8 2.5 1.9 1.1 0.8 1.1 1.6 2.4 2.1 1.6 1.4 1.1 1.3 1.7 2.9 2.8 3.6 4.9 4.6 3.7 3.4 2.2 2.0 1.4 1.0 2.6 4.8 7.6 7.4 8.7 8.0 7.8 7.7 7.5 5.7 6.0 6.2 4.0 2.6 2.3 1.9 1.4 1.1 1.3 1.8 2.3 3.1 2.7 2.2 2.1 1.8 0.7 1.1 2.1 2.3 3.0 4.2 3.8 3.0 2.6 1.5 1.2 0.6 1.2 2.7 4.1 6.7 6.5 7.4 6.8 6.5 6.4 6.3 6.1 6.4 7.1 4.5 1.9 1.5 1.2 0.7 1.3 1.6 1.9 2.5 3.3 3.3 2.8 2.6 2.1 0 0.9 1.9 1.8 2.5 4.2 3.6 2.8 2.4 1.2 1.0 1.1 1.9 3.5 3.9 6.5 6.0 7.2 6.6 6.4 6.2 6.1 6.4 7.1 7.1 5.2 122

Продолжение Приложения Г Листинг дополнительной функции к программам «ProgramData_new» в ППП MATLAB 2.9 2.4 3.0 5.7 2.6 3.5 3.5 6.2 1.8 3.6 4.1 6.9 1.0 4.2 5.1 7.8 2.4 5.7 5.7 7.8 2.2 5.4 4.8 8.1 2.4 4.5 4.0 6.2 2.1 4.2 4.1 7.7 2.9 3.2 3.2 5.9 3.7 2.8 2.7 4.9 4.1 2.2 2.2 4.4 2.5 1.5 1.7 1.0 3.7 3.5 3.0; 2.3 1.3 2.7 2.0 4.2 4.0 3.5; 1.4 0.9 2.8 2.1 4.9 4.7 4.2; 0.6 1.2 3.7 3.1 5.8 5.6 5.2; 2.4 3.0 5.0 4.2 5.9 5.7 5.2; 2.0 2.6 4.7 3.9 4.9 4.7 4.2; 2.1 1.8 3.7 3.0 4.1 3.9 3.4; 1.7 1.4 3.4 2.7 4.5 4.2 3.7; 2.6 1.6 2.4 1.7 3.8 3.6 3.1; 3.3 2.3 2.0 1.3 2.9 2.7 2.2; 3.7 2.8 1.5 0.7 2.5 2.3 2.1; 1.6 1.2 0.8 0.7 1.9 2.2 2.6 3.2 3.9 3.6 3.1 2.9 2.6 0.6 0 1.3 1.3 2.0 3.3 3.0 2.3 1.8 0.7 0.9 1.4 2.2 3.8 3.3 5.9 5.7 7.0 6.5 6.2 5.6 5.5 5.6 6.4 6.5 5.5 1.4 1.6 1.2 1.9 3.1 3.3 3.8 4.3 5.0 4.7 4.2 4.0 3.7 1.7 1.2 0 1.0 1.7 2.4 2.1 1.2 0.9 1.2 1.4 1.9 2.7 4.3 3.4 4.1 4.8 6.0 5.6 5.3 6.1 5.0 6.0 6.8 7.0 6.1 1.0 1.4 1.3 2.0 3.1 3.4 3.7 4.3 5.1 4.8 4.3 4.1 3.8 1.8 1.3 1.1 0 0.9 2.2 1.9 1.0 0.7 1.8 2.0 2.6 3.4 5.0 3.1 3.9 4.6 5.8 5.3 5.1 5.8 4.8 5.8 6.6 6.8 6.8 1.4 1.7 1.6 2.3 3.5 3.7 4.1 4.7 5.4 5.7 5.1 4.8 4.2 2.5 2.1 2.0 0.9 0 1.9 1.8 1.7 1.4 2.8 3.0 3.5 4.4 6.1 3.8 4.6 5.2 6.5 6.0 5.7 6.5 5.5 6.5 7.3 7.4 7.4 3.1 3.5 3.4 4.1 5.2 5.5 5.9 6.4 7.2 6.9 6.4 6.2 5.9 3.9 3.4 2.6 2.2 1.8 0 0.9 1.8 1.5 3.3 3.2 3.7 4.6 6.0 3.8 4.6 5.3 6.5 6.0 5.8 6.5 5.5 6.5 7.3 7.5 7.5 2.8 3.2 3.1 3.8 4.9 5.1 5.6 6.1 6.9 6.6 6.1 5.9 5.6 3.6 3.1 2.2 1.8 1.5 0.9 0 0.9 1.2 3.0 2.7 3.2 3.7 5.2 2.9 3.7 4.4 5.6 5.1 4.8 5.6 4.6 5.6 6.4 6.6 6.5 1.9 2.3 2.2 3.0 4.0 4.3 4.6 5.2 6.0 5.7 5.2 5.0 4.7 2.7 2.2 1.4 1.0 1.5 1.8 0.9 0 0.3 2.1 2.0 2.5 2.9 4.4 2.1 2.9 3.6 4.8 4.3 4.0 4.8 3.8 4.8 5.6 5.8 5.7 1.5 2.0 1.9 2.6 3.7 3.9 4.3 4.9 5.7 5.4 4.9 4.7 4.4 2.4 1.9 1.0 0.7 1.2 1.5 1.2 0.3 0 1.8 1.6 2.2 3.2 4.7 2.4 3.2 3.9 5.1 4.6 4.4 5.1 4.1 5.1 5.9 6.1 6.0 1.7 1.3 0.9 1.6 2.7 3.0 3.4 3.9 4.7 4.4 3.9 3.7 3.4 1.4 0.9 0.7 1.3 2.0 2.7 2.4 1.6 1.2 0 1.0 1.6 2.4 3.9 3.7 4.4 5.1 6.3 5.9 5.6 6.1 5.3 6.3 7.1 7.3 5.7 2.4 2.0 1.6 1.2 2.3 2.5 3.0 3.5 4.3 4.0 3.5 3.3 3.0 1.0 0.9 1.5 2.2 2.8 3.1 2.6 1.8 1.6 0.8 0 0.6 1.6 3.0 2.9 4.6 5.3 6.5 6.1 5.3 5.2 5.1 5.1 6.0 6.1 4.7 2.8 2.4 2.1 1.5 1.7 2.0 2.5 2.9 3.7 3.4 2.9 2.7 2.4 0.9 1.3 1.8 2.4 3.2 3.9 3.2 2.4 2.4 1.2 0.6 0 1.2 2.5 3.4 5.7 5.5 6.8 6.1 5.8 5.7 5.6 6.0 6.2 6.9 4.3 123

Продолжение Приложения Г Листинг дополнительной функции к программам «ProgramData_new» в ППП MATLAB 5.1 4.7 3.7 1.8 1.1 1.3 1.4 1.6 1.3 3.5 2.6; 5.8 5.5 4.5 1.1 1.4 2.0 0.8 1.5 2.7 3.7; 6.7 6.3 5.4 2.0 2.3 2.9 0.9 0 1.3 3.0 3.6; 6.4 6.0 5.5 2.1 2.0 2.5 1.5 1.6 0 2.3 2.3; 6.8 6.4 5.5 3.1 2.4 3.0 2.7 2.5 1.1 2.8 1.3; 4.7 4.3 4.0 5.6 4.9 4.1 4.9 5.0 3.6 5.3 1.3; 6.2 5.8 5.5 8.1 7.5 6.3 7.8 7.6 6.1 6.6 3.5; 5.9 5.5 5.2 7.8 7.1 6.0 7.5 7.2 5.8 6.3 3.2; 6.9 6.5 6.2 8.8 8.4 7.0 8.6 8.6 7.1 5.5 4.5; 6.7 6.3 6.1 8.6 8.0 6.9 8.0 8.1 6.7 6.0 4.1; 6.4 6.1 5.8 8.4 7.7 6.6 7.8 7.8 6.4 5.1 3.8; 3.8 3.4 3.1 2.5 1.8 1.6 2.0 2.5 3.5 3.2 2.5 2.3 2.0 1.9 2.3 2.8 3.4 4.2 4.5 3.7 2.9 3.2 2.2 1.6 1.1 0 1.6 3.9 7.0 6.8 8.0 7.5 7.3 6.5 6.9 4.6 5.3 6.0 3.4 4.6 4.2 3.8 3.3 3.3 3.1 3.1 2.2 2.2 1.9 1.4 1.2 1.7 2.6 3.0 3.6 4.2 4.9 5.7 4.8 4.0 4.3 2.9 2.8 2.2 1.2 0 5.0 7.7 7.5 8.7 8.1 7.9 7.2 7.6 5.3 6.0 5.8 4.9 3.4 5.4 5.1 4.7 4.1 3.4 3.2 3.2 2.3 2.3 2.0 1.5 1.3 1.8 3.5 3.9 4.5 5.1 5.8 6.0 5.1 4.3 4.6 3.8 3.0 2.5 1.7 2.3 4.8 7.5 7.3 8.5 8.0 7.7 7.0 7.4 5.1 5.8 6.1 3.9 5.1 4.7 4.4 3.8 3.1 2.9 2.9 2.9 3.6 3.3 2.8 2.6 2.4 3.2 3.6 4.1 4.9 5.5 5.6 4.7 4.0 4.3 3.5 2.7 2.1 1.3 1.1 3.6 6.3 6.1 7.3 6.9 6.6 5.8 6.2 4.4 4.6 4.9 2.7 5.5 5.1 4.8 4.2 3.5 3.3 3.3 3.8 4.6 4.3 3.8 3.6 3.3 3.6 4.0 4.6 5.3 5.9 6.1 5.2 4.4 4.7 3.9 3.2 2.6 1.8 0 2.6 5.4 5.2 6.4 5.9 5.6 5.4 5.3 3.0 3.7 4.4 1.8 4.1 5.3 4.0 4.4 5.1 5.3 5.7 6.2 7.0 6.7 6.3 6.0 5.8 3.8 3.3 3.6 3.2 3.8 4.0 3.1 2.3 2.6 3.2 2.9 3.4 3.8 2.5 0 2.7 2.5 3.7 3.3 3.0 2.7 2.6 2.7 3.5 3.7 3.7 5.6 6.0 6.0 6.7 8.6 8.3 8.3 8.8 9.6 9.3 8.8 8.6 8.3 6.0 5.9 5.1 4.7 5.3 5.4 4.5 3.8 4.1 5.9 5.6 5.6 6.8 4.7 2.7 0 1.0 2.2 1.8 1.5 2.7 2.5 3.2 4.1 4.3 5.0 5.3 5.7 5.6 6.4 8.2 8.0 8.0 8.5 9.2 8.9 8.4 8.3 8.0 5.7 5.2 4.8 4.4 4.9 5.1 4.2 3.4 3.7 5.5 5.2 5.3 6.5 4.4 2.3 0.9 0 1.3 1.1 1.2 2.3 2.1 2.9 3.7 3.9 4.7 6.3 6.8 6.7 7.5 9.3 9.1 9.1 9.5 10 10 9.5 9.3 9.1 6.7 6.7 5.8 5.4 6.0 6.2 5.3 4.5 4.8 6.6 6.3 6.4 7.5 5.4 3.6 2.2 1.2 0 0.5 1.2 1.7 2.7 2.9 3.1 3.2 4.6 6.1 6.6 6.5 7.3 9.1 8.9 8.9 9.4 10 9.8 9.3 9.2 8.9 6.5 6.0 5.6 5.3 5.8 6.0 5.1 4.3 4.6 5.9 6.1 6.2 7.4 5.2 3.2 1.8 1.2 0.8 0 0.8 2.0 2.3 2.5 3.4 3.6 4.4 5.9 6.3 6.2 7.0 8.8 8.6 8.6 9.1 9.8 9.5 9.0 8.9 8.6 6.3 6.2 5.4 5.0 5.5 5.7 4.8 4.0 4.3 5.6 5.8 5.9 7.1 5.0 2.9 1.5 1.3 1.5 0.8 0 1.3 2.0 2.2 2.7 2.9 4.2 124

Продолжение Приложения Г Листинг дополнительной функции к программам «ProgramData_new» в ППП MATLAB 7.1 6.7 6.4 6.5 6.9 6.8 6.9 8.7 8.5 8.5 8.2 7.6 6.5 6.2 5.6 6.0 5.6 6.2 6.3 5.4 7.6 7.7 5.8 4.8 2.8 2.7 2.4 2.2 2.0 1.3 4.0 3.7; 5.2 4.8 4.5 4.6 5.0 5.0 5.2 5.8 6.8 6.8 6.5 5.9 4.7 4.4 3.9 4.1 3.7 4.3 4.4 3.5 5.9 6.1 4.6 3.1 1.1 2.0 1.8 3.0 2.2 1.9 5.1 2.0; 7.2 6.8 6.5 6.6 6.8 6.7 7.0 6.3 6.1 6.1 5.8 5.2 5.8 6.0 5.5 5.9 5.7 6.3 6.4 5.5 5.7 5.4 3.9 4.0 2.9 3.2 2.9 3.2 2.5 2.2 3.5 3.7; 7.9 7.5 7.2 7.3 7.7 7.7 7.7 7.1 6.8 6.8 6.7 6.0 6.5 7.0 6.5 6.8 6.4 7.0 7.1 6.3 6.2 6.1 4.6 4.8 3.6 4.1 3.9 3.5 3.4 3.1 2.9 4.5; 9.7 9.3 8.3 8.5 8.0 7.7 7.2 6.5 6.2 6.2 6.0 5.3 5.9 6.5 6.9 7.5 6.8 7.4 8.6 6.6 5.5 5.5 4.0 4.2 4.0 5.1 4.9 4.3 3.6 3.4 2.3 5.1; 8.3 7.6 6.9 7.1 6.6 6.4 5.8 5.1 4.9 4.9 4.6 4.0 4.5 5.1 5.5 6.1 6.5 7.2 7.2 6.3 4.2 4.1 2.7 2.8 3.7 4.8 4.6 5.8 5.2 5.1 1.7 3.8; 8.5 8.2 7.2 7.3 6.9 6.5 6.0 5.3 5.0 5.0 3.8 4.2 4.7 5.3 5.8 6.3 6.9 7.8 7.8 6.9 3.4 3.3 2.3 2.8 5.4 6.4 6.2 7.5 5.8 5.1 4.0; 5.9 5.6 4.6 4.7 4.3 3.9 3.4 4.2 4.0 4.4 4.2 3.5 2.8 2.7 3.2 3.7 4.5 5.1 5.2 4.3 3.8 3.7 2.3 1.2 1.5 3.8 3.5 4.8 4.3 4.0 3.9 0.0]; %Ввод координат точек города CitiesCoord = ... [50.261802 127.495682 50.260975 127.500853 50.259645 127.514224 50.260643 127.517827 50.258546 127.520566 50.261361 127.523526 50.258569 127.530861 50.257364 127.541079 50.255510 127.544888 50.252979 127.549386 50.253910 127.558503 50.253657 127.572498 50.259558 127.576786 125 8.5 9.3 8.9 8.4 8.8 8.5 4.6 4.9 5.5 5.2 5.8 7.0 0 2.1 2.1 1.6 1.7 3.1 7.3 8.0 7.7 7.2 7.1 6.8 2.7 3.1 3.8 3.5 4.1 5.3 1.8 0 1.9 2.8 3.0 3.5 6.8 7.3 7.0 6.5 6.6 6.3 4.8 5.1 5.6 5.8 5.6 4.6 2.1 2.0 0 0.9 1.1 1.9 7.3 8.5 7.8 7.3 7.5 6.9 5.5 5.8 7.7 6.6 6.1 5.3 1.6 2.9 1.0 0 0.6 2.0 6.7 7.5 7.2 6.7 6.5 6.2 5.8 6.1 6.8 6.0 5.5 4.7 2.0 3.1 1.2 0.9 0 1.4 5.4 6.1 5.8 5.3 5.2 4.8 5.5 5.8 5.4 4.6 4.1 3.3 3.2 4.8 1.9 2.0 1.9 0 4.6 5.3 5.0 4.5 4.3 4.1 6.1 7.5 5.6 4.9 4.4 3.5 4.0 5.4 3.1 2.9 2.7 1.6 0 5.0 5.7 5.4 4.9 4.8 4.5 3.5 3.8 3.0 2.3 2.1 2.5 3.8 3.8 3.7 4.5 4.7 2.9

Продолжение Приложения Г Листинг дополнительной функции к программам «ProgramData_new» в ППП MATLAB 50.259424 50.258526 50.258162 50.258938 50.261493 50.263215 50.261909 50.263509 50.267231 50.265087 50.264317 50.272537 50.274124 50.272973 50.270276 50.267586 50.269169 50.267687 50.268487 50.265965 50.268725 50.275122 50.280887 50.286233 50.292190 50.298262 50.305408 50.302783 50.302554 50.304711 50.291884 50.298302 50.305032 50.302783 50.295714 50.290959 50.285178 127.570614 127.566703 127.560655 127.555666 127.549856 127.541178 127.535095 127.528898 127.520615 127.512198 127.503583 127.491961 127.500949 127.512262 127.511705 127.525502 127.532595 127.540586 127.550086 127.562505 127.568715 127.558676 127.554142 127.522826 127.507082 127.510649 127.506885 127.511795 127.518534 127.526769 127.525736 127.543397 127.546173 127.550263 127.558093 127.565734 127.541407]; end 126

ПРИЛОЖЕНИЕ Ж Оптимальные маршруты построенные в интернет сервисе OSRM, Муравьиный алгоритм Маршрут с 10 адресами 127

Продолжение Приложения Ж Оптимальные маршруты построенные в интернет сервисе OSRM, Муравьиный алгоритм Маршрут с 30 адресами 128

Продолжение Приложения Ж Оптимальные маршруты построенные в интернет сервисе OSRM, Муравьиный алгоритм Маршрут с 50 адресами 129

ПРИЛОЖЕНИЕ К Оптимальные маршруты построенные в интернет сервисе OSRM, Имитационный отжиг Маршрут с 10 адресами 130

Продолжение Приложения Ж Оптимальные маршруты построенные в интернет сервисе OSRM, Имитационный отжиг Маршрут с 30 адресами 131

Продолжение Приложения Ж Оптимальные маршруты построенные в интернет сервисе OSRM, Имитационный отжиг Маршрут с 50 адресами 132

ПРИЛОЖЕНИЕ Л Оптимальные маршруты построенные в интернет сервисе OSRM, Пчелиный алгоритм Маршрут с 10 адресами 133

Продолжение Приложения Ж Оптимальные маршруты построенные в интернет сервисе OSRM, Пчелиный алгоритм Маршрут с 30 адресами 134

Продолжение Приложения Ж Оптимальные маршруты построенные в интернет сервисе OSRM, Пчелиный алгоритм Маршрут с 50 адресами 135

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв

6315.12

Игорь Маслеников

и хорошего настроения

6315.12

Игорь Маслеников

удачи

6315.12

Игорь Маслеников

успехов в конкурсе

6315.12

Игорь Маслеников

Наверное было затрачено много времени и труда на работу

6315.12

Игорь Маслеников

Продолжай свое исследование

6315.12

Игорь Маслеников

Админам респект

6315.12

Игорь Маслеников

Красиво написанная работа

6315.12

Игорь Маслеников

Так держать

6315.12

Игорь Маслеников

Молодец

6315.12

Игорь Маслеников

Интересная работа!