В Корее разработали ИИ, создающий «реализуемые планы» - от маршрутов доставки и производственных планов до графика работы

Корреспондент Ким Кван У

- Технология позволяет получить реализуемые планы без помощи внешних программ оптимизации

- Показала 100%-ую успешность на 5 тестовых наборах данных (бенчмарках), скорость обучения - в 14,7 раз выше

Корреспондент-автор Ким Мин Су, профессор факультета информатики KAIST (слева направо), и первый автор Ли Тхэ Хун, аспирант [Фото предоставлено KAIST]

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

Корейский институт передовых технологий (KAIST) сообщил 3 августа, что исследовательская группа под руководством профессора факультета информатики Ким Мин Су разработала технологию «RL-SPH (Reinforcement Learning-based Start Primal Heuristic)», позволяющую ИИ самостоятельно обучаться созданию реализуемых планов без помощи внешних специализированных программ оптимизации.

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

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

Существующие системы ИИ, даже предлагая планы, позволяющие сократить затраты или время, зачастую нарушали реальные ограничения, такие как грузоподъёмность транспортных средств, рабочее время персонала и пропускная способность оборудования. Из-за этого на заключительном этапе специализированные программы оптимизации, такие как «Gurobi» или «SCIP», должны были исправлять ошибки в планах, предложенных ИИ. Одним лишь ИИ было сложно завершить процесс планирования.

Разработанная исследовательской группой система RL-SPH вместо того, чтобы сразу предсказать правильный ответ, поэтапно корректирует текущий план, подобно тому, как это делает человек. Она решает задачу ограничений, поочередно изменяя переменные — количество персонала, транспортных средств, объем производства и т. д. — и обучается на полученных результатах.

Рисунок 1. Сравнение примальных эвристик на основе сквозного обучения (E2EPH), стартовых примальных эвристик (SPH) и предложенного нами подхода.

Рисунок 2. Обзор метода RL-SPH.

Рисунок 3. Обучение с подкреплением для задачи ILP.

Рисунок 4. Архитектура ILP-GT.

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

Для этого сначала находится «осуществимое решение», удовлетворяющее всем ограничениям, а затем применяется двухэтапная стратегия поиска, направленная на сокращение затрат и времени.

Помимо этого команда разработала модель искусственного интеллекта «ILP-GT», обучающаяся взаимосвязям между переменными и ограничениями. Эффективность вычислений была повышена за счет применения «стратегии поиска с распознаванием выполнимости», которая в первую очередь корректирует переменные, которые оказывают существенное влияние в решении задач.

В ходе оценки RL-SPH исследовательской группой на пяти тестовых наборах данных (бенчмарках) был найден практически применимый план в 100 % случаев для всех задач. Такая же производительность сохранялась даже при решении сложных задач, содержащих обычные целочисленные переменные.

По сравнению с существующими технологиями «примальный разрыв», отражающий отклонение от оптимального решения, улучшился в среднем в 28,6 раза, а «примальный интеграл», оценивающий качество и скорость поиска, — в 2,6 раза. Время, необходимое для нахождения первого выполнимого плана, сократилось в среднем в 2,5 раза.

Даже при сравнении с новейшими технологиями искусственного интеллекта, такими как PAS, DDIM и DiffILO, только RL-SPH на всех тестах на 100 % нашла выполнимые планы. Время обучения составило в среднем 30 минут, что в 14,7 раза быстрее, чем у существующих технологий, и примерно в 34 раза быстрее, чем у технологий, основанных на ненадзорном обучении.

В международном тестовом наборе задач по оптимизации «MIPLIB» система стабильно находила выполнимые планы как для задач, размер которых превышал предыдущие в 67 раз, так и для новых задач, с которыми не сталкивалась в процессе обучения.

Таблица 1. Сравнение производительности с базовыми методами SPH на пяти наборах данных. Жирным шрифтом и подчеркиванием выделены лучший и второй по эффективности методы среди тех, у которых FR (доля тех задач, на которые были найдены "реализуемые" решения) составляет 100 %. Улучшения усреднены по парам «набор данных — базовый метод» с FR 100 %.

Рисунок 5. Иллюстрация значений целевой функции сравниваемых методов во времени (в секундах). Линии обозначают действительные усреднённые значения текущей целевой функции, которые вычисляются только в том случае, если для всех экземпляров в данной временной точке существует текущее значение целевой функции. Пунктирные линии указывают, что FR не равен 100%, и усреднение включает только те экземпляры, для которых было найдено хотя бы одно реализуемое решение.

Таблица 2. Сравнение производительности с репрезентативными методами E2EPH на наборах SC, CA и IS, которые представляют собой пересечение тестовых наборов, использованных в DDIM, DiffILO и нашем исследовании. Поскольку PAS не предоставляет гиперпараметров для тестового набора SC, мы исключаем его из данного эксперимента. Пометка «fail» указывает, что метрики не могут быть вычислены, поскольку не было получено ни одного реализуемого решения (т. е. FR = 0 %). Временное ограничение установлено на 300, 300 и 30 секунд для SC, CA и IS соответственно.

Рисунок 6. Иллюстрация значений целевой функции сравниваемых методов во времени (в секундах). Отображаются только случаи с FR = 100%.

Таблица 4. Межзадачная производительность RL-SPH.

«В реальной жизни более важен план, который можно реализовать на практике, чем самый лучший ответ» - отметил профессор Ким, добавив: «Этот результат демонстрирует, что ИИ может самостоятельно создавать выполнимые планы без помощи специализированных программ оптимизации».

Также он выразил надежду, что данная технология «станет ключевой для внедрения ИИ-основанного принятия решений в различных отраслях, таких как логистика, производство, выпуск полупроводников и управление персоналом».

В данном исследовании в качестве первого автора участвовал аспирант факультета информатики KAIST Ли Тхэ Хун. Профессор Ким выступил в качестве корреспондентского автора.

Результаты исследования представлены на прошедшей в прошлом месяце Международной конференции по машинному обучению (ICML). Исследование было проведено при поддержке Министерства науки и ИКТ Южной Кореи, Института планирования и оценки ИКТ и Корейского фонда научных исследований.

woo@heraldcorp.com

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