ant colony optimization

Оптимизация муравьиной колонии

Пакет Python для поиска кратчайшего пути в графе с использованием Ant Colony Optimization (ACO).

➡️ Подробное описание можно найти в моей статье на Medium.

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

Эта реализация алгоритма ACO использует графовую среду NetworkX.

Начиная

Чтобы установить пакет непосредственно из PyPi:

$ pip install aco_routing

Использование

Посмотрите: example.py

Импортируйте все зависимости:

 из aco_routing импортировать ACOimport networkx как nx

Создайте объект NetworkX.Graph с узлами и ребрами:

 G = nx.DiGraph()G.add_edge("A", "B", Cost=2)G.add_edge("B", "C", Cost=2)G.add_edge("A", "H" , Cost=2)G.add_edge("H", "G", Cost=2)G.add_edge("C", "F", Cost=1)G.add_edge("F", "G", стоимость =1)G.add_edge("G", "F", Cost=1)G.add_edge("F", "C", Cost=1)G.add_edge("C", "D", Cost=10)G.add_edge("E", "D" ", Cost=2)G.add_edge("G", "E", Cost=2)

Используйте ACO, чтобы найти кратчайший путь и стоимость между source и destination :

 aco = ACO(G, ant_max_steps=100, num_iterations=100, ant_random_spawn=True)aco_path, aco_cost = aco.find_shortest_path(source="A",destination="D",num_ants=100,
)

Выход:

ACO path: A -> H -> G -> E -> D
ACO path cost: 8.0

Содержание

Муравей

aco_routing.Ant

• Ant , пересекающий граф.

АКО

aco_routing.ACO

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

Содействие

• Публикуйте любые проблемы и предложения на странице проблем GitHub.

• Чтобы внести свой вклад, разветвите проект, а затем создайте запрос на включение обратно в мастер.