Эволюционный алгоритм на графическом процессоре в 10 раз ускорил планирование работы химического производства
Сотрудник Института математики им. С.Л. Соболева СО РАН (Новосибирск) создал алгоритм для составления расписания работы химического завода, который решает эту задачу более чем в 10 раз быстрее аналогичных вычислительных инструментов.
Новый алгоритм помогает эффективно распределять задачи между оборудованием и точно рассчитывать объёмы выпускаемых продуктов. Разработка будет полезна крупным предприятиям, производящим десятки и сотни различных типов продукции. Результаты исследования, поддержанного грантом Российского научного фонда (РНФ), опубликованы в Journal of Heuristics.
Современное химическое производство — это сложная система, в которой десятки установок работают с сотнями различных веществ. Чтобы выпустить нужное количество продукции за определённое время, важно составить точное расписание: определить, какие реакции когда проводить, на каком оборудовании и в каких объёмах. Это позволит избежать простоя оборудования и реактивов и тем самым произвести максимальное количество продукта в сжатые сроки, получив наибольшую выгоду от продаж. Поэтому производствам нужны быстрые и точные алгоритмы планирования.
Уже существуют инструменты для составления расписаний, например, метод ветвей и границ. Это алгоритм, который представляет все возможные варианты расписаний в виде деревьев и многогранников. Алгоритм последовательно «проходит» по ветвям дерева и вершинам многогранника, отбрасывая заведомо плохие варианты, математически рассчитывает, где решение лучше, и в результате находит оптимальное. Однако встречаются задачи, в которых поиск хотя бы не оптимального, но достаточно хорошего решения может занимать несколько часов и даже дней, из-за чего метод оказывается не всегда удобным.
Разработик предложил более быстрый эволюционный алгоритм, который проводит вычисления на графическом процессоре. В отличие от центрального процессора, графический процессор содержит тысячи простых ядер, которые параллельно выполняют множество математических операций. Эта архитектура идеально подходит для эволюционных алгоритмов, которые используют принципы природной эволюции (например, механизмы естественного отбора и мутаций).
Схема работы параллельного эволюционного алгоритма
Разработанный алгоритм сначала случайным образом создаёт некоторый набор возможных расписаний. Затем он оценивает каждое решение по нескольким критериям (общее время завершения всех работ, равномерность загрузки оборудования и другие). Программа отбирает лучшие варианты и вносит в них поправки — меняет местами операции или корректирует количество задействованных установок. Процесс повторяется тысячи раз, постепенно улучшая расписание. При этом за счёт того, что графический процессор позволяет параллельно проводить тысячи вычислений на своих ядрах, это занимает в десятки раз меньше времени, чем метод ветвей и границ.
При тестировании разработки алгоритму поручили составить расписание для реального химического предприятия, которое ежемесячно выпускает более ста видов продукции. По скорости и точности решения сложных задач алгоритм превзошел не только известный промышленный программный продукт Gurobi, но и другие аналогичные инструменты, например, cuOpt от NVIDIA.
Было также показано, что использование более мощных графических процессоров позволяет ещё сильнее ускорить алгоритм, поэтому с развитием аппаратного обеспечения метод будет становиться все более эффективным.
«В дальнейшем мы планируем продолжить работу по ускорению алгоритма, а также его адаптации к другим задачам, например, к составлению расписаний в вычислительных системах или планированию доставки продукции потребителям», — рассказывает Павел Борисовский, кандидат физико-математических наук, старший научный сотрудник лаборатории дискретной оптимизации Омского филиала ИМ СО РАН.
Источник: пресс-служба РНФ.
