Интеллектуальная система управления эволюционными алгоритмами в дискретных задачах оптимизации

Полный текст

Введение

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

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

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

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

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

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

 Описание объекта исследования

Пусть дана дискретная задача оптимизации на графе согласно уравнению (1)

,

(1)

где n – размерность задачи.

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

.

(2)

Для автоматизации выбора стратегии решения вводится модель интеллектуального управления, которая:

• анализирует постановку задачи: преобразует данные в вектор признаков;
• прогнозирует оптимальную стратегию решения: , где – множество возможных конфигураций эволюционных алгоритмов, а  – обученная ИИ-модель;
• запускает решение задачи с выбранным методом;
• оценивает прогресс решения (например, при нужна смена алгоритма);
• адаптивно переключает используемые алгоритм и конфигурации.

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

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

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

Описание исходных данных

Для решения поставленной дискретной задачи оптимизации было выделено около 50 конфигураций следующих эволюционных алгоритмов: генетический [2, 3], пчелиный, муравьиный [4] и имитации отжига [5]. Краткое описание параметров эволюционных алгоритмов и их значений приведено в табл. 1 ниже.

 

Таблица 1. Описание параметров эволюционных алгоритмов и их значения

Наименование алгоритма	Диапазоны параметров
Муравьиный	: 0,5; 1,0  0,5; 1,0 q: 10,0; 100,0; 1000,0 p: 0,01; 0,1, 0,5 Кол-во акторов: 20, 50, 100
Пчелиный	Доля пчел-рабочих: 0,3; 0,5; 0,7 Методы поиска: Реверс подмножества, Смена индексов Кол-во акторов 20, 50, 100
Генетический	Шанс мутации: 0,01; 0,05 Метод мутации: Смена индексов, Реверс подмножества Метод отбора: Турнирный, Рулетка, Лучшие N Кол-во акторов 100; 200
Имитации отжига	Начальная температура: 500, 1000 Конечная температура: 1 Коэффициент охлаждения: 0,8; 0,95; 0,99 Метод мутации: Смена индексов, Реверс подмножества

 

 

В качестве признаков у обучающей выборки представлены нормализованные методом MinMax матрицы смежности. Каждому образцу соответствует метка, представляющая собой идентификационный номер конфигурации эволюционного алгоритма.

Набор данных был получен на основе вычислительного эксперимента, описанного в источнике [1]. Данные сгруппированы по постановкам задачи, выбраны те решения (и их алгоритмы), которые показали абсолютную наибольшую эффективность. В целях увеличения объема обучающей выборки набор данных был синтезирован при помощи метода SMOTE [6, 7]. В конечном итоге, для обучения представлено 245 тыс. образцов.

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

Для обучения интеллектуальной модели выбора алгоритма использовался метод «Анализ компонентов соседства» (далее – АКС). Данный метод является модификацией метода «k-ближайших соседей». Из основных особенностей данной модификации можно выделить следующие:

• вместо использования фиксированного расстояния (например, евклидова), АКС обучает линейное отображение пространства признаков, что позволяет более эффективно различать классы;
• обучает и сохраняет значения весов, что позволяет интегрировать модель в другие системы.

Пусть существует обучающая выборка  где  – входной вектор признаков,  – метка класса. Тогда, для установления степени «близости» между постановками, вычисляется расстояние между примерами в преобразованном пространстве согласно формуле (3)

(3)

где A – матрица линейного преобразования.

В отличие от классического «k-ближайших соседей», где выбирается k ближайших, АКС использует статистическую вероятность того, что объект i «выберет» j в качестве «соседа». Вероятность вычисляется в соответствии с формулой (4).

(4)

Таким образом, для каждого объекта i определяются вероятности , с которыми он «голосует» за другие точки j.

Целью АКС является максимизация вероятности правильной классификации. Для вычисления величины потерь вероятности  суммируются как показано в формуле (5)

(5)

Данная функция дифференцируема по параметрам A, поэтому обучение проводится градиентным методом.

Для обучения модели использовалась реализация АКС из библиотеки Scikit-learn с рядом параметров, подобранных в ходе эмпирических экспериментов. Первым из таких параметров было количество итераций в размере 1000, что позволило избежать преждевременной остановки в «застойных» периодах обучения. В качестве инициализации матрицы преобразования использовался метод главных компонент, что обеспечило эффективное начало процесса обучения. В качестве порога точности была выбрана величина .

Для минимизации потерь использовался метод L-BFGS [8]. Выбор в пользу данного метода обусловлен стабильностью и скоростью сходимости на имеющемся объеме данных. В ряде экспериментов использовался стохастических градиентный спуск (скорость обучения 0,01), однако результаты оказались менее стабильными.

Размерность признакового пространства после линейного преобразования была ограничена значением 50. Это компромисс между сохранением достаточной информации о данных и снижением вычислительной нагрузки.

Результаты обучения

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

На рис. 1 показана динамика точности и потерь в процессе обучения моделей. По оси X отложен номер итерационного шага, по осям Y – точность (шкала слева) и величина потерь (шкала справа). Динамика потерь на графике обозначена пунктирной линией.

На начальных этапах обучения (до 100 итерации) наблюдается стремительный рост точности до 75 %, сопровождаемый резким снижением потерь с 2,9 до 1,1. Это указывает на быструю адаптацию матрицы преобразования к структуре обучающих данных. Далее процесс обучения обретает более «плавный» вид и достигает значения около 89 %, а потери снижаются к уровню 0,5 и ниже. Таким образом, в результате обучения модели удалось достигнуть монотонной сходимости без переобучения. Это подтверждает, что выбранные гиперпараметры являются оптимальными для текущих объема и структуры данных.

 

Рис. 1. График точности и потерь в процессе обучения по итерациям

 Принцип интеллектуального выбора алгоритмов

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

 

Рис. 2. Схема интеллектуального решения дискретной задачи оптимизации

 

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

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

Заключение

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

Разделение выбора на «быстрые» и «качественные» обеспечивает как оперативную стартовую сходимость, так и стабильное улучшение решений. Механизм мониторинга динамики решения позволяет системе своевременно переключаться между алгоритмами, что гарантирует высокую устойчивость при изменении сложных целевых функций.

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

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

___________________________________

© Баранов Д.А., Барабанов В.Ф., 2025

Об авторах

Дмитрий Алексеевич Баранов

Воронежский государственный технический университет

Автор, ответственный за переписку.
Email: oblivvion333@gmail.com

аспирант

Россия, 394006, Россия, г. Воронеж, ул. 20-летия Октября, 84

Владимир Федорович Барабанов

Воронежский государственный технический университет

Email: bvf@list.ru

д-р техн. наук, профессор

Россия, 394006, Россия, г. Воронеж, ул. 20-летия Октября, 84

Список литературы

Дополнительные файлы