РЕШЕНИЕ ЗАДАЧИ РАЗБИЕНИЯ ОРИЕНТИРОВАННОГО АЦИКЛИЧЕСКОГО ГРАФА МОДИФИЦИРОВАННЫМ АЛГОРИТМОМ ИСКУССТВЕННОЙ ИММУННОЙ СИСТЕМЫ С КЛОНАЛЬНОЙ СЕЛЕКЦИЕЙ

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

• Иванченко А.Н.
• Нгон Нгуен

• Прикладные науки. Медицина. Технология

• Технические науки. Промышленность