Эволюционный алгоритм на графическом процессоре в 10 раз ускорил планирование работы химического производства

Ученый создал алгоритм для составления расписания работы химического завода, который решает эту задачу более чем в 10 раз быстрее аналогичных вычислительных инструментов. Новый алгоритм помогает эффективно распределять задачи между оборудованием и точно рассчитывать объемы выпускаемых продуктов. Разработка будет полезна крупным предприятиям, производящим десятки и сотни различных типов продукции. Результаты исследования, поддержанного грантом Российского научного фонда (РНФ), опубликованы в Journal of Heuristics.

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

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

Исследователь из Института математики имени С.Л. Соболева СО РАН (Новосибирск) предложил более быстрый эволюционный алгоритм, который проводит вычисления на графическом процессоре. В отличие от центрального процессора, графический процессор содержит тысячи простых ядер, которые параллельно выполняют множество математических операций. Эта архитектура идеально подходит для эволюционных алгоритмов, которые используют принципы природной эволюции (например, механизмы естественного отбора и мутаций).

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

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

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

«В дальнейшем мы планируем продолжить работу по ускорению алгоритма, а также его адаптации к другим задачам, например, к составлению расписаний в вычислительных системах или планированию доставки продукции потребителям», — рассказывает участник проекта, поддержанного грантом РНФ, Павел Борисовский, кандидат физико-математических наук, старший научный сотрудник лаборатории дискретной оптимизации Омского филиала Института математики имени С.Л. Соболева СО РАН.