Software & Systems

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

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

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

Широкое применение при решении таких задач получили недетерминированные многоагентные алгоритмы, в том числе бионические. В данной статье рассматриваются генетический алгоритм (ГА) [1], муравьиный алгоритм (Ant Colony Opti­mization, ACO) [2], алгоритм умных капель (Intelli­gent Water Drops, IWDs) [3], эвристика Лина–Кер­нигана [4] и авторские адаптивные ГА и АСО.

Описание алгоритмов

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

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

Алгоритм IWDs основан на имитации поведения потоков (множеств капель) в реке [3]. Для каждого множества капель река является окружающей средой, которая влияет на него, но в то же время и это множество влияет на реку. То есть как капли влияют на маршрут реки, так и путь реки влияет на маршрут каждой отдельной капли. Большое влияние на движение реки оказывают тип грунта и его сопротивление потоку, так как от него зависит скорость капель. Таким образом, река представляет собой результат противоборства множества капель воды и сопротивления окружающей среды. Можно также заметить, что все реки в природе имеют множество изгибов и поворотов, так как под действием силы тяжести, выбирая путь наименьшего сопротивления, вода движется по направлению к самой низкой точке.

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

На основании рассмотренных выше свойств Шах-Хоссейни в 2007 году предложил алгоритм умных капель [3]. Каждая умная капля воды (IWD) имеет два важных свойства: количество грунта (soil), который она несет, и скорость (velocity), с которой она двигается. Эти свойства могут изменять то, как движется капля в окружающей среде.

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

Одним из классических методов решения за- дачи коммивояжера, как и задач оптимизации, является локальный спуск, в частности алгоритм 3-за­мена, или эвристика Лина–Кернигана [4]. При построении алгоритмов локального поиска основным является определение окрестности. Для за- дачи коммивояжера обычно используются окрестности типа k-замены: два обхода лежат в такой окрестности, если они могут быть получены друг из друга удалением и заменой k ребер. Алгоритм локального поиска перебирает элементы окрестности текущего решения до обнаружения улучшения. Если улучшение находится, то соответствующее решение становится центром окрестности и алгоритм продолжает поиск, в противном случае текущее решение и есть локальный оптимум. В своих работах Лин показал, что 3-оптимальные решения намного лучше 2-оптимальных, а 4-опти­мальные лучше 3-оптимальных, но не настолько, чтобы были оправданы дополнительные вычислительные затраты [4]. Именно поэтому в данной работе рассматривается алгоритм 3-замены, являющийся частным случаем k-замены.

ГА основывается на заимствовании из природы идеи естественной эволюции [1]. В связи с этим решение задачи является хромосомой индивида в популяции (множество решений). В своей работе ГА использует несколько операторов, итерационно следующих друг за другом: селекция, рекомбинация (порождение потомков), мутация, селекция выживших, формирование следующего поколения. В связи с тем, что представление решения в виде хромосомы при решении задачи коммивояжера отличается от стандартной бинарной строки (представляет собой перестановку n чисел), стандартные генетические операторы видоизменены. Однако сохраняется большое количество настраиваемых параметров, таких как вероятность мутации, тип селекции – турнирная (с выбором размера турнира), пропорциональная и ранговая (с линейным или экспоненциальным ранжированием), тип скрещивания и т.д. Авторы экспериментально проверяли взаимодействие типов селекции и уровней мутации, приняв остальные параметры неизменными. Это привело к необходимости проверки 24 вариантов настройки алгоритма.

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

Суть предлагаемого подхода для ГА в следующем. Для каждого оператора выбор его варианта осуществляется отдельно. Пусть z – число вариантов данного оператора. Например, если варианты оператора селекции турнирная с размерами турнира 2, 4 и 8 и пропорциональная, то z=4.

В начале работы алгоритма вероятности выбора всех вариантов оператора одинаковы: p=1/z. На каждом поколении производится оценка эффективности каждого варианта оператора следующим образом:  i=1, 2, …, z, где ni – количество индивидов, полученных с применением i-го варианта оператора; fij – пригодность j-го индивида, полученного i-м вариантом оператора; averagefitnessi – средняя пригодность потомков, порожденных i-м вариантом оператора.

Вероятность варианта оператора с наибольшим значением averagefitness (то есть наиболее эффективного) увеличивается на ((z–1)∙K)/(z∙N), тогда как вероятности всех остальных операторов уменьшаются на K/(z∙N), где N – число прошедших поколений работы алгоритма; K – константа, обычно равная 2. Кроме того, устанавливается порог снижения вероятности, так как ни в одном из вариантов оператора эта вероятность не может быть равна нулю. При достижении минимально возможного значения вероятности такой вариант оператора перестает отдавать свою долю в пользу лучшего. Сумма вероятностей для всех вариантов одного оператора всегда равна единице. Таким образом, распределение вероятностей выбора варианта оператора постепенно смещается в сторону более эффективных за счет менее эффективных вариантов.

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

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

В данной работе адаптивный ACO располагал шестнадцатью вариантами настроек (по четыре для каждого из параметров), а именно 1, 2, 5, 10. Адаптивный ГА имел 8 вариантов селекции: турнирная с размером турнира 2, 4 и 8, ранговая с линейным ранжированием, ранговая с экспоненциальным ранжированием с параметром λ, равным 0,95, 0,8 и 0,5, и пропорциональная, а также 5 вариантов мутации: очень низкая, низкая, средняя, высокая и очень высокая.

Анализ работы бионических алгоритмов комбинаторной оптимизации

Описанные выше алгоритмы были реализованы на языке программирования С++ в виде программной системы решения комбинаторных задач оптимизации на перестановках. Эффективность работы этих алгоритмов сравнивалась на двух широко известных тестовых задачах – Eil51 и Oliver30 [5], число городов в которых равно соответственно 51 и 30.

На задаче Oliver30 алгоритм 3-замены для сходимости в среднем требовал 52 800 вычислений целевой функции, поэтому всем остальным алгоритмам давалось такое же количество ресурсов (30 индивидов, 1 760 итераций). Усреднение проводилось по 100 прогонам, оптимальное решение этой задачи имеет длину 423,741.

На задаче Eil51 алгоритм 3-замены в среднем требовал 342 210 вычислений целевой функции, поэтому количество ресурсов, выделяемое остальным алгоритмам, – 51 индивид, 6 710 поколений. Усреднение на данной задаче проводилось по 50 прогонам, а оптимальное решение имеет длину 426.

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

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

Таблица 1

Эффективность работы алгоритмов на задачах Oliver30 и Eil51

Поскольку эффективность бионических алгоритмов на конкретной задаче существенно различается в зависимости от настроек, более реалистичным будет предположение, что при однократном решении задачи, что и ожидается на практике, эффективность применяемых алгоритмов будет более близка к средней на этой задаче, а не к наилучшей. Такое сравнение на задаче Oliver30 приведено в таблице 2, где три строки для каждого алгоритма (GA, ACO, IWDs) содержат значения целевой функции, найденные при наилучших и наихудших настройках, а также усредненные по всем настройкам, а столбцы содержат усреднение по прогонам и СКО.

Таблица 2

Сравнение эффективности алгоритмов при различных настройках

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

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

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

Литература

1.     Гуменникова А.В., Емельянова М.Н., Семенкин Е.С., Сопов Е.А. Об эволюционных алгоритмах решения сложных задач оптимизации // Вестн. СибГАУ. 2003. № 4. С. 14–23.

2.     Dorigo М., Gambardella L.M., Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, Vol. 1, Is. 1, 1997, pp. 53–66.

3.     Shah-Hosseini H., Optimization with the Nature-Inspired Intelligent Water Drops Algorithm, Evolutionary Computation, Vienna, InTech, 2009, pp. 299–319.

4.     Lin Sh., Kernighan B.W., An Effective Heuristic Algorithm for the Traveling-Salesman Problem, Operations Research, 1973, no. 21 (2), pp. 498–516.

5.     Oliver I.M., Smith D.J., Holland J.R.C., A study of permutation crossover operators on the travelling salesman problem, Proc. 2nd Intern. Conf. on Genetic Algorithms and their application, 1987, pp. 224–230.

References

1.     Gumennikova A.V., Emelyanova M.N., Semenkin E.S., Sopov E.A., Vestnik SibGAU [Bulletin of the SibSAU], 2003, no. 4, pp. 14–23.

2.     Dorigo М., Gambardella L.M., IEEE Transactions on Evolutionary Computation, Vol. 1, iss. 1, 1997, pp. 53–66.

3.     Shah-Hosseini H., Evolutionary Computation, Vienna, InTech, 2009, pp. 299–319.

4.     Lin Sh., Kernighan B.W., Operations Research, 1973, no. 21 (2), pp. 498–516.

5.     Oliver I.M., Smith D.J., Holland J.R.C., Proc. of the 2nd Int. Conf. on Genetic Algorithms and their application, 1987, pp. 224–230.