Авторы: Семенкина О.Е.
Источник:
Сибирский журнал науки и технологий. 2012. Выпуск № 4(44).
[Ссылка]
Рассматриваются алгоритм муравьиной колонии, генетический алгоритм и параллельные версии этих методов для решения задачи коммивояжёра.
Ключевые слова: генетический алгоритм, алгоритм муравьиной колонии, задача коммивояжёра, параллелизация.
Одними из наиболее интересных и актуальных методов решения задач оптимизации являются стохастические алгоритмы, работающие одновременно со многими актуальными решениями. В данной статье рассматриваются алгоритм муравьиной колонии [1] и генетический алгоритм [2], а также распараллеленные версии этих методов. Эти алгоритмы могут быть очень полезны для поиска приближённых решений в сложных оптимизационных задачах. Оба алгоритма являются вдохновлённой природой метаэвристикой оптимизации, при этом муравьиные алгоритмы основываются на поведении и организации колонии муравьев, касающихся поиска пищи, а генетические алгоритмы – на некоторых принципах эволюции.
Исследование эффективности муравьиных и генетических алгоритмов проводилось путём решения известной задачи комбинаторной оптимизации, а именно задачи коммивояжёра. Программная реализация этих алгоритмов была реализована на языке C++, а для распараллеливания использовалась библиотека MPICH2.
В генетическом алгоритме для задачи коммивояжёра хромосома представлена как перестановка n чисел (номеров городов). Вот почему некоторые стандартные операции содержат определённые изменения, но в генетическом алгоритме имеется множество чувствительных параметров, таких как вероятность мутации, тип селекции – турнирный отбор (параметр – размер турнира), пропорциональный и ранговый отбор (линейное или экспоненциальное ранжирование), размер популяции и число эпох. Решения в муравьиных алгоритмах также представлены как перестановка n городов, и муравьи выбирают следующий город, ориентируясь на каждом этапе на табу-список городов и матрицу феромонов. Так же, как и генетические, муравьиные алгоритмы имеют довольно чувствительные параметры: размер колонии муравьёв (m), количество итераций, скорость испарения феромона (ρ), коэффициент важности предыдущего опыта поиска (α) и коэффициент важности расстояния между городами (β).
Сначала была исследована эффективность каждого алгоритма на тестовом задании (сетка городов размером 5 на 5) и выявлены закономерности зависимости эффективности алгоритмов от их параметров. Муравьиный алгоритм показывает лучшие результаты при следующих настройках: α = 1, β = 10, ρ ∈ [0.5, 0.7] и количество муравьев приблизительно равно количеству городов. Лучшие настройки для генетического алгоритма – турнирная селекция с небольшим размером турнира и низкой или очень низкой вероятностью мутации. При решении тестового задания муравьиный алгоритм показал лучшие результаты, чем генетический, поскольку он полагается на расстояние между городами при инициализации и начинает работать с уже довольно неплохим маршрутом, в то время как генетический алгоритм начинается с абсолютно случайной последовательности городов. Следовательно, муравьиный алгоритм требует значительно меньше вычислительных ресурсов для решения задач с большим количеством вершин. Поэтому надёжность алгоритмов была исследована на более сложной тестовой задаче с количеством городов равным 30, которая называется Оливер30. После завершения работы алгоритмов локальный поиск был применён к лучшим решениям. Обоим алгоритмам было предоставлено одинаковое количество вычислений, а именно 30 особей (муравьёв) и 10000 поколений (итераций).
Надёжность алгоритмов была рассчитана путём усреднения результатов после 30 запусков каждого из них. Генетический алгоритм нашел самый короткий маршрут хотя бы один раз для всех вариантов настроек, в то время как муравьиный не нашел лучший маршрут во всех случаях. Средняя длина маршрута для генетического алгоритма варьировалась в интервале от 429.172 до 459.028, тогда как для муравьиного она была в интервале от 423.8171 до 490,5966. Это означает, что муравьиный алгоритм имеет широкий разброс надёжности и более чувствителен к параметрам. По сравнению с генетическим алгоритмом, муравьиный может найти как значительно лучший маршрут, так и значительно худший при неудачном подборе параметров. Таким образом, можно сказать, что для этой задачи генетический алгоритм работает лучше, чем муравьиный, потому что он более постоянен и предсказуем для своих различных параметров.
Оба алгоритма показывают хорошую надёжность при достаточной вычислительной мощности, но ресурсоёмкость, а, следовательно, и время работы алгоритмов быстро растут с увеличением размерности задачи. Одним из решений этой проблемы является распараллеливание.
Существует много различных вариантов распараллеливания, но в этой статье рассматривается наиболее интересный тип – крупнозернистые эволюционные алгоритмы [3]. В этом случае на каждое ядро процессора приходится несколько независимых популяций. Они периодически обмениваются несколькими особями, и этот процесс называется миграцией. Вот почему необходимы два дополнительных параметра – интервал обмена и количество мигрирующих особей. Параллельные эволюционные алгоритмы этого типа очень популярны, но достаточно сложны для понимания, потому что последствия миграции изучены не полностью. В данном исследовании была выбрана топология обмена индивидами.
Надёжность алгоритмов была исследована при различных настройках параметров и при различном количестве ядер и, соответственно, популяций. Интервал между обменом особей был установлен на 10 эпох, и в каждой популяции мигрировала одна лучшая особь. При увеличении количества ядер, т.е. отдельных популяций, надёжность алгоритмов существенно не изменилась, хотя некоторые изменения надёжности для различных настроек наблюдались, кроме того, время работы алгоритмов было существенно сокращено. Использование одного ядра для генетического алгоритма занимает около 30 секунд за один прогон, для двух ядер – около 16 секунд, а для четырех – около 8 секунд. Для муравьиного алгоритма эти значения составляют 0,55, 0,27 и 0,16 секунды соответственно. То есть, распараллеленный алгоритм может значительно сократить время работы без потери надёжности. Таким образом, можно сказать, что при достаточной скорости миграции распараллеливание алгоритмов как минимум не уменьшает их эффективность. Однако, необходимо более точно определить скорость миграции, при которой алгоритмы работают лучше всего.
Для сетки городов размером 5 на 5 с фиксированным количеством ресурсов рассматривалась эффективность обоих алгоритмов с использованием различных параметров и различных интервалах обмена лучшей особью на 4 ядрах. При увеличении интервала между миграциями надёжность увеличивалась до определённого предела, а затем начинала снижаться. Это можно объяснить несколькими факторами. При низком уровне миграции популяции на ядрах становятся практически изолированными и работают независимо друг от друга. В то же время, если уровень миграций высокий, нет существенной разницы по сравнению с одной большой популяцией. Кроме того, в генетике известен принцип: благоприятные признаки распространяются быстрее, когда сообщества маленькие, чем когда они большие. Таким образом, можно сделать вывод, что распараллеливание существенно сокращает время работы алгоритмов, не снижая и не увеличивая надёжность при правильном подборе параметров.
Как часть будущих планов можно рассмотреть поиск более эффективных методов распараллеливания для ускорения работы алгоритма благодаря эффективному взаимодействию различных популяций, разрабатываемых на разных ядрах и разных топологиях, разделяющих индивидов, и различных топологий, разделяющих индивидов.