ПРОГРАММНАЯ ПОДСИСТЕМА ДЛЯ РЕШЕНИЯ NP-СЛОЖНЫХ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ

Аннотация

Работа посвящена созданию программной подсистемы для решения NP- трудных и NP-сложных комбинаторно-логических задач на графах. В статье приведено описание комбинаторно-логических задач на графах. Для эффективного их решения предлагаются новые многоуровневые архитектуры поиска, такие как простая комбинированная, парал- лельная комбинированная, двухуровневая, интегрированная и гибридная. Данные архитек- туры основаны на методах, инспирированных природными системами. Ключевым отличием данных архитектур является разделение поиска на два или три уровня и применение на них различных алгоритмов эволюционного моделирования и биоинспирированного поиска. Это позволяет получать наборы квазиоптимальных решений выполнять параллельную обработку и частично устранять проблему преждевременной сходимости. В статье при- ведено подробное описание разработанной программной подсистемы и ее модулей. В каче- стве модулей в подсистеме имеется пять разработанных архитектур и набор разрабо- танных алгоритмов эволюционного моделирования и биоинспирированного поиска, таких как эволюционный, генетический, пчелиный, муравьиный, светлячковый и обезьяний. Благо- даря модульной структуре в подсистеме имеется возможность конструировать более 50 различных вариантов комбинаций поиска. Это позволяет использовать все достоинства методов биоинспирированной оптимизации для эффективного решения NP-сложных ком- бинаторно-логических задач на графах. Для подтверждения эффективности разработан- ной программной подсистемы был проведен вычислительный эксперимент на тестовых примерах. Проведенные серии тестов и экспериментов показали преимущество использо- вания программного продукта для решения комбинаторно-логических задач на графах большой размерности, по сравнению с известными алгоритмами, что говорит о перспек- тивности применения такого подхода. Временная сложность разработанных алгоритмов в лучшем случае O(nlogn), в худшем случае – О(n3).