Implementation of the ant pollinator algorithm with a matrix structure of the optimisation goal function
Implementation of the ant pollinator algorithm with a matrix structure of the optimisation goal function
Abstract
The article is devoted to the development of a method for constructing interpretable survival analysis models. An extended Cox model is used as a basis, where the dependence between traits is specified by a polynome. To solve the problem of optimising the polynomial structure, a modification of the ant-pollinator algorithm is suggested. A key feature is the matrix representation of the goal function, which combines accuracy criteria (c-index), the number of features, and model complexity. Unlike classical approaches, the pheromone in the algorithm is deposited at the vertices of the trait graph. The method was tested on data about critical malfunctions in 5,000 cars. During the experiment, the algorithm demonstrated its effectiveness, accurately restoring the specified dependence of the risk function on features with an average number of iterations of 6.09. The results confirm that the proposed approach allows to simultaneously build accurate predictive models and select significant features, ensuring high interpretability of the results. The prospects for further work are related to the development of a matrix representation of pheromones and testing on real data.
1. Введение
Прогнозирование наступления терминальных событий, таких как отказ технических систем, является критически важной задачей в инженерии, анализе надежности, а также в медицине . Широко распространенная модель Кокса , несмотря на свою интерпретируемость, опирается на предположение о линейной зависимости между признаками и функцией риска, что часто нарушается на практике . Хотя методы машинного обучения способны определять нелинейные зависимости, их результаты часто представляют собой «черный ящик», что затрудняет их практическое использование специалистами. В связи с этим актуальной является разработка методов, сочетающих высокую адаптивность к сложным данным и прозрачность получаемых моделей.
Объектом исследования является расширенная модель Кокса. Предметом исследования — метод построения расширенной модели Кокса. Цель работы заключается в возможности построения точной и интерпретируемой модели анализа выживаемости за счет разработки модификации алгоритма муравьев-опылителей, оперирующего матричным представлением целевой функции.
Научная новизна заключается в следующем. Предложена модификация алгоритма муравьев-опылителей, в которой целевая функция представлена в виде оптимизируемой матрицы, что позволяет эффективно решать многокритериальную задачу построения модели. Разработанный метод позволяет одновременно решать задачу построения точной прогностической модели и отбора наиболее значимых признаков. Для проверки эффективности предложенного метода был использован синтетический набор данных, содержащий параметры эксплуатации и время до выхода из строя для 5000 автомобилей. Использование искусственно сгенерированных данных с заранее известной зависимостью позволило объективно оценить способность алгоритма к воспроизведению истинных функциональных связей.
2. Методы и принципы исследования
2.1. Расширенная модель Кокса
Широко используемой моделью анализа выживаемости
является регрессионная модель пропорциональных рисков Кокса. Одним из достоинств модели является то, что функция риска этой модели содержит две компоненты — параметрическую, зависящую от параметров, и не параметрическуюгде
Регрессионная модель Кокса, включающая параметрический и непараметрический компоненты, позволяет получить более согласованные оценки в широком диапазоне условий по сравнению с параметрическими моделями и более точные оценки по сравнению с непараметрическими методами .
Использовав иную, нелинейную зависимость
Функция (2) является обобщением функции (1).
В данной работе такой функцией является полином специального вида: он является суммой одночленов, каждый из которых является произведением признаков, при том степень каждого признака в одночлене не превосходит единицы.
2.2. Постановка задачи
Признанным способом оценки точности моделей анализа выживаемости является c-индекс (индекс согласованности)
. В его основе лежит ранговая корреляция между фактическим временем выживания и прогнозами модели. Он представляет точность ранжирования прогнозов модели выживаемости, показывая, насколько хорошо модель упорядочивает объекты по вероятности выживания . Является величиной, принимающей значения от нуля до единицы, где 1 — идеальное соответствие, 0.5 — соответствие уровню случайного угадывания.Задачей является построение модели по набору данных. Так как моделью в данном исследовании является расширенная модель Кокса, необходимо построить полином, с-индекс которого, был бы наибольшим, а количество признаков — минимальным. Также для повышения интерпретируемости модели и для борьбы с ошибкой переобучения имеет смысл ввести показатели сложности построенного полинома, которые также необходимо минимизировать.
2.3. Матричное представление целевой функции
Исходя из постановки задачи, введены четыре критерия, которые будут оптимизированы.
Первый критерий — точность модели
Таким образом, с учетом введенных критериев задача оптимизация заключается в поиске полинома при условиях
Система условий (3) порождает многокритериальную задачу оптимизации. Для ее решения предложено рассмотрение условий в виде матрицы:
Тогда определитель матрицы (4) сводит задачу к одномерной оптимизации.
2.4. Метод муравьев-опылителей
Решение задачи оптимизации осуществляется с помощью метаэвристического гибридного метода муравьев-опылителей
. Алгоритм состоит из трех этапов: муравьиный, генетический и этап опыления. Основное структурное отличие от классических муравьиных алгоритмов заключается в том, что процесс оптимизации происходит не на полном графе путей, а на графе признаков, где феромон откладывается на вершинах, а не на дугах. Это позволяет алгоритму оценивать и отбирать наиболее важные с точки зрения признаки и их взаимодействия.Основные понятия алгоритма:
1. Цветок (вершина графа) — элементарная единица модели, соответствующая моному полинома. Исходное множество вершин инициализируется множеством признаков объекта.
2. Путь муравья — упорядоченный набор вершин (мономов), формирующий полиномиальную целевую функцию.
3. Феромон — числовая мера, связанная с каждой вершиной, которая динамически обновляется и отражает важность признака в построенных решениях.
4. Мера пути: Значение целевой функции, вычисленное для модели с полиномом, соответствующему пройденному пути. Значением является определитель матрицы (4).
Алгоритм является итерационным и состоит из трех последовательно выполняемых этапов.
2.4.1. Муравьиный этап
На данном этапе популяция агентов-«муравьев» осуществляет поиск оптимального пути — набора вершин-мономов, формирующего полином. Каждый муравей строит путь, стохастически выбирая вершины для добавления в свой полином. Вероятность выбора вершины зависит от уровня феромона, связанного с ней. После оценки целевой функции для всех построенных полиномов (путей) происходит обновление феромона на вершинах. Вершины, входящие в лучшие решения, получают прирост феромона. Одновременно моделируется процесс его испарения на всех вершинах для избегания преждевременной сходимости алгоритма.
2.4.2. Генетический этап
Этап используется для оптимизации ключевых параметров муравьиного алгоритма для повышения эффективности поиска решения. Оптимизируются параметры: чувствительность муравьев к феромону, чувствительность муравьев к эвристической информации, количество откладываемого феромона. Особи в генетическом алгоритме представляют собой векторы параметров муравьиного алгоритма. Над популяцией особей применяются стандартные генетические операторы: выбора (селекция на основе приспособленности, определяемой качеством работы муравьиного этапа с данными параметрами), кроссинговера (рекомбинация параметров) и мутации (случайное возмущение значений параметров).
2.4.3. Этап опыления
Данный этап отвечает за эволюцию самого множества вершин-мономов, обеспечивая адаптацию модели к данным. Этап реализует динамическое обновление множества цветков путем добавления новых перспективных мономов и удаления неэффективных. Эффективность вершины-монома определяется накопленным на ней уровнем феромона. Этап представляет собой последовательное применение операторов: селекции (отбор наименее эффективных вершин для удаления), кроссбридинга (умножение мономов), лайнбридинга (случайное добавление монома, состоящего из одного признака), старения (механизм планомерного уменьшения феромона на вершинах, который позволяет постепенно исключать устаревшие или неперспективные мономы из рассмотрения)
Совместная работа трех этапов образует метаэвристический механизм, который формирует структуру полиномиальной модели, обеспечивая как высокую точность, так и интерпретируемость результата.
3. Основные результаты
Метод муравьев-опылителей реализован в виде программы, написанной на языке программирования Python3. Использована библиотека Lifelines, предназначенная для работы с моделями и методами анализа выживаемости
. Она предоставляет интерфейс и реализацию основных моделей анализа выживаемости, в том числе модель пропорциональных рисков Кокса. Одним из преимуществ интерфейса является возможность создание собственных моделей и конструирование функции риска .Для проведения вычислительного эксперимента сгенерирован набор данных о неисправностях автомобилей. Искусственная генерация данных позволила задать аналитическую форму зависимости времени до наступления терминального события от признаков. Это дало возможность оценить способность алгоритма к воспроизведению истинных функциональных зависимостей, скрытых в данных. Сгенерированный набор данных включает параметры эксплуатации и время выхода из строя для 5000 автомобилей. Набор данных содержит 10 признаков и время эксплуатации. Полином, использующийся для генерации данных:
Таблица 1 - Описание признаков тестируемого набора данных
Признак | Полное название | Значение |
mileage | Пробег автомобиля | Числовой |
age | Возраст автомобиля | Числовой |
offroad_ratio | Доля поездок по бездорожью | Числовой |
maintenance_reg | Техническое обслуживание | 0 — присутствует 1 — отсутствует |
engine_temp | Температура двигателя | Числовой |
tire_pressure | Давление в шинах | Числовой |
battery_health | Состояние аккумулятора | Числовой |
color | Цвет автомобиля | 0 — белый 1 — серый 2 — черный 3 — другой |
fuel_type | Вид топлива | 0 — бензин 1 — дизель 2 — газ |
Таким образом, для синтетического набора данных значимыми являются 2 признака из 10.
В проведенном эксперименте использован следующий набор параметров:
1. Исходная чувствительность муравьев к феромону
2. Исходная чувствительность муравьев к эвристической информации
3. Исходное количество откладываемого феромона
4. Испарение
5. Количество муравьев
6. Вероятность кроссинговера
7. Вероятность мутации
Вычислительный эксперимент состоял из 100 запусков алгоритма. Во всех случаях алгоритм успешно идентифицировал полином, соответствующий функции
4. Обсуждение
Проведенное исследование демонстрирует, что предложенная модификация алгоритма муравьев-опылителей является работоспособным и эффективным инструментом для построения расширенных моделей Кокса. Высокая частота успешного нахождения целевого полинома и низкое среднее число итераций (6.09) свидетельствуют о хорошей сходимости метода и адекватности предложенного матричного подхода для решения многокритериальной задачи, позволяющего сводить критерии оптимизации в скалярную целевую функцию. Эти результаты подтверждают, что переход от оптимизации на графе путей к оптимизации на графе признаков с откладыванием феромона на вершинах является результативным для задач структурного синтеза моделей.
Основным преимуществом гибридного подхода является объединение его трех этапов. Муравьиный этап эффективно исследует пространство возможных полиномов, генетический алгоритм адаптивно настраивает параметры этого поиска, а этап опыления динамически обогащает и очищает словарь мономов, предотвращая стагнацию. Одновременная оптимизация структуры модели и ее параметров позволяет алгоритму успешно решать задачу отбора признаков и построения интерпретируемой нелинейной зависимости.
Вместе с тем, текущая реализация метода имеет области для потенциального улучшения. Использование определителя матрицы критериев, хотя и доказало свою эффективность, является по сути линейной сверткой, которая может нивелировать сложные взаимоотношения между отдельными целевыми функциями. Это ограничение открывает путь для дальнейших исследований, направленных на разработку более совершенных механизмов агрегирования, таких как матричное представление не только целевой функции, но и самой структуры феромона.
5. Заключение
В данной работе успешно решена задача разработки метода построения точной и интерпретируемой модели анализа выживаемости. Цель работы достигнута за счет модификации алгоритма муравьев-опылителей, ключевой особенностью которой является матричное представление целевой функции. Это представление позволило свести многокритериальную задачу максимизации точности и минимизации сложности модели к задаче однокритериальной оптимизации.
Метод решает не только задачу аппроксимации, но и проблему отбора признаков, что важно для повышения интерпретируемости итоговой модели. Практическая значимость подтверждена результатами вычислительного эксперимента на синтетических данных, где алгоритм стабильно и быстро находил заданную зависимость, демонстрируя свою робастность и эффективность.
Таким образом, работа вносит вклад в область интеллектуального анализа данных и анализа выживаемости, предлагая современный инструмент для построения прогностических моделей, сочетающих высокую адаптивность и прозрачность. Перспективы дальнейших исследований включают апробацию метода на реальных наборах данных, а также развитие предложенной матричной парадигмы, в частности, во внедрении матричного феромона и соответствующих матричных операций для его обновления, что может существенно повысить универсальность алгоритма.