Обзор алгоритмов построения оптимального маршрута

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

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

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

· вычисление верхней границы значений целевой функции, либо на множестве, либо на некотором его подмножестве (оценивание);

· постепенное разбиение множества на подмножества (ветвления);

· пересчет оценок при постепенном разбиении множеств;

· нахождение конкретных вариантов решения;

· проверка вариантов на оптимальность;

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

Рисунок 1.1. График сравнения методов

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

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

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

· Задается число итераций (температура) и случайное начальное решение;

· Случайным образом меняются местами две точки;

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

· Пройдя все итерации, последний найденный путь считается наилучшим;

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

Генетический алгоритм.Подход генетического алгоритма начинается с генерации популяции (множества маршрутов), затем к элементам(особям) популяции применяются операции скрещивания и мутации [5]. Скрещивание из выбранных маршрутов формирует дочерний. Скрещивание бывает двух видов:

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

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

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

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

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

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

Муравьиный алгоритм имеет несколько вариантов модификации, которые увеличивают шанс нахождения оптимального маршрута быстрее или позволяют найти куда более короткие маршруты за N повторений. Среди таких алгоритмов: Элитарная муравьиная система, Система муравьиной колонии (ACS), Max-Min муравьиная система (MMAS), Выпрямление.

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

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

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

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

Рисунок 1.2. Сравнение сходимости MMAS с ACS

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

Рисунок 1.3. Результат применения модификации выпрямления

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

Начальное расположение колонии. Существуют несколько вариантов расположения муравьиной колонии:

· Расположение всей колонии в одной точке

· Случайное расположение всей колонии в одной точке на каждой итерации

· Равномерное распределение колонии по точкам

· Случайное распределение колонии по точкам (где-то больше, где-то меньше)

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

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

Таблица 1.1

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

Число заказчиков	Муравьиный алгоритм	Генетический алгоритм
Длина маршрута для лучшего решения	Время решения, мин	Длина маршрута для лучшего решения	Время решения, мин
	6460,98	7,13	6460,98	1,04
	586,87	139,27	596,89	14,32
	1007,07	32,55	1018,74	39,33
	927,27	158,93	933,74	78,5
	1834,79	239,47	1946,55	210,42

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