Использование дополнительной информации в задачах дискретной оптимизации типа многих коммивояжеров
Для реальных систем актуальной является проблема анализа и синтеза оптимальных потоков различной природы: ресурсных, информационных и других. В качестве математических моделей используются сети – графовые структуры, вершинам и дугам которых приписаны некоторые величины. Возникает многообразие классов задач дискретной оптимизации (ДО), как правило, NP-трудных. Естественный учет информации, связанной с данными задачами ДО, позволяет строить алгоритмы (приближенные, эвристические), пригодные для сложных задач большой размерности. Характерными и тестовыми являются задачи маршрутизации, задачи типа многих коммивояжеров. С ними связаны задачи построения кратчайшего пути, гамильтонова контура, вершинно-реберных преобразований, максимального разреза и другие. В реальных ситуациях возникают экстремальные постановки задач, для которых важны как точные, так и приближенные решения. Приближенные решения базируются на комбинациях локальных и эвристических алгоритмов. В экстремальных задачах анализа и синтеза на графах необходимо учитывать знания, факты, прецеденты и другую релевантную информацию. Разнообразие задач диктуется классами графов, моделирующих ресурсные сети; структурой графов, их размерностью, возможностью декомпозиции; характером целевых функций и полнотой информации о коэффициентах критериев; возможностью представления знаний об ограничениях на сети в виде дизъюнктивных нормальных форм. Использование дополнительной информации (знаний) по обязательным ограничениям усложняют задачу и требуют адаптации существующих алгоритмов.
В работе, используя знаниеориентированный подход, приведен обзор существующих результатов по задачам ДО типа коммивояжера с ограничениями и получены новые постановки задач, предложены алгоритмы их решения. Приведена предварительная классификация. Показано, что учет знаний о структуре сети, целях коммивояжеров, запретах приводит к декомпозиционным (кластерным) алгоритмам. Дальнейшее развитие связывается с подходом, основанным на использовании управляемых интеллектуальных агентов (в частности, агентов-коммивояжеров). Рассмотрены обобщенные многоагентные задачи типа коммивояжера, в которых для интеллектуального управления учитывается разнообразная информация, необходимая для интеллектуального управления агентами, и локального управления, осуществляемого самим агентом, алгоритмы декомпозиции, кластеризации, анализа и синтеза сети. Предварительные численные расчеты подтверждают необходимость создания широкого комплекса алгоритмов, участвующих в оптимальной композиции метаэвристик и наполняющих системы управления.
Ключевые слова: задачи типа многих коммивояжеров, знаниеориентированные модели, приближенные алгоритмы.