Оптимизация Ant Colony для поиска подмножеств с суммой ~0
У меня есть множество A = [x1, x2...xn], где xi в R (вещественное). Мне нужно найти все непересекающиеся подмножества с суммой подмножеств ~0.
Поскольку в наборе могут быть ненулевые действительные числа, я решил использовать Ant Colony Optimization для этой проблемы. Я реализовал это в Python, и программа имеет тенденцию быть немного медленной (словари Python для графа). Это займет около 60 секунд для 100 муравьев за одну итерацию. Алгоритм выглядит так:
- Создать график со всем списком действительных чисел (полностью подключен)
- Инициализировать ребра графа с помощью w0
- Каждая вершина имеет ассоциированное значение
- Инициализировать положение муравьев в случайных узлах
- Муравьи выбирают следующие узлы на основе веса ребер
- После того, как муравей завершит обход - сумма всех значений вершин> пороговое значение 1 (1000000) или <пороговое значение 2 (~ 0,1), веса пути обновляются на основе суммы пути и глобальных обновлений пути (испарение феромона) после этого
У меня есть вопросы:
- Здесь уместно использование ACO?
- Как я могу импровизировать скорость реализации?