Parallelizing the ant colony algorithm for solving the knapsack problem as an example using Python

Full Text

Введение

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

Метод исследования

Допустим, что в колонии 40 муравьев. Обычно для их работы запускается один цикл длиной 40 итераций, где каждый муравей поочередно строит свой маршрут и вносит вклад в общий процесс оптимизации. Но можно поступить и иначе: один большой цикл разбить на ряд малых. Например, на 4 цикла по 10 муравьев каждый. Принцип работы алгоритма не изменится: все 40 муравьев все равно обойдут свое пространство решений, а феромоны будут обновлены только после окончания всех 4 циклов. То есть последовательный процесс можно дробить на более мелкие части, которые могут выполняться независимо друг от друга. Это естественным образом ведет нас к идее распараллеливания, когда запуск всех 4 циклов одновременно в 4 параллельных потоках вместо их последовательного выполнения значительно ускорит процесс решения задачи.

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

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

def model(n, range_v=(100, 500), range_w=(30, 100)):

 np.random.seed(42)

 v = np.random.randint(range_v[0], range_v[1], size=n)

 w = np.random.randint(range_w[0], range_w[1], size=n)

 return v, w

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

def select_item(probabilities):

 return np.random.choice(len(probabilities), p=probabilities)

def ant_solution(pheromones, w, v, s, alpha, beta):

 num_items = len(w)

 selected_items = []

 current_weight = 0

 available_items = list(range(num_items))

 while available_items:

 pheromone = pheromones[available_items]

 heuristic = v[available_items] / (w[available_items] + 1e-10)

 probabilities = (pheromone ** alpha) * (heuristic ** beta)

 probabilities /= probabilities.sum()

 item = available_items.pop(select_item(probabilities))

 if current_weight + w[item] <= s:

 selected_items.append(item)

 current_weight += w[item]

 return selected_items

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

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

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

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

def ant_colony_opt(pheromones, w, v, s, alpha, beta, rho, Q, iter, ants, proc):

 best_solution = None

 best_value = float('-inf')

 for i in range(iter):

 t0 = time.time()

 # Создание пула процессов

 pool = multiprocessing.Pool(processes=proc)

 results = []

 # Распараллеливание обработки муравьев

 for group_id in range(proc):

 result = pool.apply_async(process_group,

 args=(pheromones, w, v, s, alpha, beta, Q, ants, group_id, proc)

 )

 results.append(result)

 pool.close()

 pool.join()

 # Сбор и обработка результатов

 local_pheromones = np.zeros(len(w))

 for result in results:

 solution, value, group_pheromones = result.get()

 if value > best_value:

 best_solution = solution

 best_value = value

 local_pheromones += group_pheromones

 pheromones = (1 - rho) * pheromones + local_pheromones

 tk = time.time()

 print(f"Итерация {i+1}, Решение: {best_value}, t={tk-t0:.2f} сек")

 return best_solution, best_value

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

Внутри цикла для каждой группы муравьев, используя метод apply_async объекта multiprocessing.Pool, асинхронно вызывается функция process_group. Она будет обрабатывать группу муравьев, генерировать решения и обновлять локальные феромоны. Список results хранит все асинхронные задачи для последующего получения их результатов.

После запуска всех задач метод pool.close() закрывает пул процессов для новых задач, а метод pool.join() блокирует основной поток выполнения до тех пор, пока все процессы в пуле не завершат свою работу.

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

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

def process_group(pheromones, w, v, s, alpha, beta, Q, ants, group_id, proc):

 local_pheromones = np.zeros(len(w))

 local_best_solution = None

 local_best_value = float('-inf')

 ants_per_group = ants // proc

 for _ in range(ants_per_group):

 solution = ant_solution(pheromones, w, v, s, alpha, beta)

 value = np.sum(v[solution])

 weight = np.sum(w[solution])

 if value > local_best_value and weight <= s:

 local_best_solution = solution

 local_best_value = value

 for item in solution:

 local_pheromones[item] += Q / value

 print(f"----- Процесс {group_id} Решение группы - {local_best_value}")

 return local_best_solution, local_best_value, local_pheromones

На этапе инициализации определяются: local_pheromones - массив для хранения феромонов, обновляемых внутри этого процесса, local_best_solution - локальное лучшее решение, найденное в данном процессе, и local_best_value - значение лучшего решения. Значение ants_per_group определяет количество муравьев, обрабатываемых в рамках данного процесса. Общее число муравьев в АСО делится между всеми доступными процессами (proc).

Для каждой муравьиной итерации вызывается функция ant_solution, которая строит решение на основе текущих феромонов, весов, ценностей и других параметров. Вычисляются ценность (value) и вес (weight) найденного решения. Если найденное решение лучше локального лучшего решения и его вес не превышает ограничения, оно сохраняется как лучшее решение для данного процесса.

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

def main():

 n = 100

 v, w = model(n)

 s = 500

 ants = 100 # Количество муравьев

 proc = 4 # Количество процессов для параллелизма

 alpha = 1.0 # Влияние феромонов

 beta = 2.0 # Влияние эвристической информации

 rho = 0.5 # Коэффициент испарения феромонов

 Q = 100 # Константа для обновления феромонов

 iter = 10 # Количество итераций

 pheromones = np.ones(len(w))

 # Запуск оптимизации муравьиной колонии

 start_time = time.time()

 best_solution, best_value = ant_colony_optimization(

 pheromones, w, v, s, alpha, beta, rho, Q, iter, ants, proc )

 print(f"Лучшее решение: {best_solution}; Общая цена: {best_value}")

 print(f"Общее время выполнения: {time.time() - start_time:.2f} секунд")

Результат исследования

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

 

Рис. 1. Одно- и четырехпоточное решение задачи о рюкзаке

Fig. 1. One- and four-stream solution of the knapsack problem

 

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

 

Рис. 2. Загрузка 4 ядер при решении задачи о рюкзаке

Fig. 2. Loading of 4 cores when solving the knapsack problem

 

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

 

Рис. 3. Задача о рюкзаке: 100 предметов, 10 итераций и 100 муравьев

Fig. 3. Knapsack problem: 100 items, 10 iterations and 100 ants

 

Для более обоснованного вывода по качеству разработанного Python-кода было выполнено дополнительное тестирование на увеличенном наборе данных. Цель тестирования на наборе из 1000 предметов со 100 муравьями и 20 итерациями заключается в следующем:

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

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

В табл. 1 приведен анализ работы параллельного и простого алгоритмов муравьиной колонии при решении задачи о рюкзаке с увеличенным до 1000 набором предметов, который выполнили 100 муравьев за 20 итераций.

 

Таблица 1. Сравнительный анализ работы параллельного и простого АСО

Table 1. Comparative analysis of the operation of parallel and simple ACO

100 муравьев, 20 итераций, 1000 предметов
Параллельный алгоритм АСО	Простой алгоритм АСО
Iteration 1, Best Value: 4724, Time: 22.62 сек. Iteration 2, Best Value: 4848, Time: 19.08 сек. Iteration 3, Best Value: 5035, Time: 20.03 сек.   Iteration 18, Best Value: 7000, Time: 23.97 сек. Iteration 19, Best Value: 7000, Time: 19.40 сек. Iteration 20, Best Value: 7000, Time: 18.45 сек. Лучшее найденное решение: [718, 957, 918, 538, 190, 646, 639, 200, 533, 337, 520, 318, 70, 797, 759] с общей ценностью 7000   Общее время выполнения: 397.23 секунд	Iteration 1, Time: 70.61 сек. Best Value: 4867 Iteration 2, Time: 74.44 sec, Best Value: 5027 Iteration 3, Time: 70.47 сек. Best Value: 5174  . . . . . Iteration 18, Time: 69.23 сек. Best Value: 6972 Iteration 19, Time: 68.30 сек. Best Value: 6972 Iteration 20, Time: 68.71 сек. Best Value: 6972 Лучшее найденное решение: [318, 918, 639, 823, 957, 190, 646, 249, 70, 759, 797, 538, 819, 337, 522] с общей ценностью 6972   Общее время выполнения: 1414.94 секунд

 

Из анализа полученных результатов следует, что параллельный алгоритм АСО значительно быстрее. Общее время выполнения составило 397 секунд по сравнению с 1415 секундами у простого алгоритма. То есть распараллеливание существенно сократило время выполнения задачи, особенно для больших наборов данных. Кроме этого, время выполнения одной итерации у параллельного алгоритма занимает от 18.45 до 23.97 секунд, что значительно меньше по сравнению с от 68.30 до 74.44 секундами у простого алгоритма. Это показывает более равномерную и эффективную обработку задач в параллельной реализации.

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

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

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

 

Рис. 4. Загрузка 4 ядер процессора при 1000 предметах

Fig. 4. Loading of 4 processor cores with 1000 items

 

Все это подтверждает эффективность использования параллельных вычислений для задач с высокой вычислительной сложностью.

Переход от последовательного выполнения к параллельному логично вытекает из понимания независимости муравьев в ACO и открывает новые возможности для решения сложных задач. Проведенное тестирование показало, что АСО может быстро находить решения, близкие к оптимальным, даже при малом количестве итераций. Это делает его полезным инструментом в условиях, когда время расчета играет критическую роль, и позволяет его использовать при решении широкого круга траекторных задач [4, 5, 6] или задач маршрутизации в беспроводных сетях [7]. По сравнению с точными методами типа динамического программирования ACO показал значительное сокращение времени выполнения при приемлемом уровне отклонения от оптимального решения.

Выводы

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

1. Распараллеливание позволяет одновременно запускать множество муравьев на разных процессорах, что значительно сокращает время поиска оптимального решения по сравнению с последовательным выполнением алгоритма.
2. При использовании распараллеливания алгоритм максимально задействует доступные вычислительные ресурсы (ядра процессора), что особенно важно при работе с большими наборами данных или сложными проблемами, требующими значительных вычислительных ресурсов.
3. Распараллеливание позволяет исследовать большее количество возможных решений за определенное время, что приводит к повышению вероятности нахождения более точного решения по сравнению с последовательным алгоритмом.
4. Распараллеливание делает алгоритм муравьиной колонии более устойчивым к случайным колебаниям в поведении муравьев. Благодаря тому, что муравьи работают независимо друг от друга на разных процессорах, ошибки одного муравья не влияют на других.
5. Библиотека multiprocessing в Python позволяет эффективно распараллелить алгоритм муравьиной колонии, что делает распараллеливание доступным для разработчиков любого уровня.

About the authors

Marsel R. Vagizov

St. Petersburg State Forestry Engineering University named after S.M. Kirov

Author for correspondence.
Email: bars-tatarin@yandex.ru
ORCID iD: 0000-0003-4848-1619
SPIN-code: 4811-8943

Candidate of Technical Sciences, Head of the Department of Information Systems and Technologies

Russian Federation, 194021, St. Petersburg, 5 Institutsky lane

Sergey P. Khabarov

St. Petersburg State Forestry Engineering University named after S.M. Kirov

Email: Serg.Habarov@mail.ru
ORCID iD: 0000-0003-1337-0150
SPIN-code: 4365-2033

Candidate of Technical Sciences, Associate Professor of the Department of Information Systems and Technologies

Russian Federation, 194021, St. Petersburg, 5 Institutsky lane

References

Supplementary files