ant colony optimization

Otimização de colônia de formigas

Um pacote Python para encontrar o caminho mais curto em um gráfico usando Ant Colony Optimization (ACO).

➡️ Confira meu artigo no Medium para um passo a passo detalhado

O algoritmo Ant Colony Optimization é uma técnica probabilística para resolver problemas computacionais que pode ser reduzida a encontrar bons caminhos através de grafos (fonte).

Esta implementação do algoritmo ACO usa o ambiente gráfico NetworkX.

Começando

Para instalar o pacote diretamente do PyPi:

$ pip install aco_routing

Uso

Confira: exemplo.py

Importe todas as dependências:

 de aco_routing importar ACOimport networkx como nx

Crie um objeto NetworkX.Graph com nós e arestas:

 G = nx.DiGraph()G.add_edge("A", "B", custo=2)G.add_edge("B", "C", custo=2)G.add_edge("A", "H" , custo=2)G.add_edge("H", "G", custo=2)G.add_edge("C", "F", custo=1)G.add_edge("F", "G", custo=1)G.add_edge("G", "F", custo=1)G.add_edge("F", "C", custo=1)G.add_edge("C", "D", custo= 10)G.add_edge("E", "D", custo=2)G.add_edge("G", "E", custo=2)

Use ACO para encontrar o caminho e custo mais curto entre a source e 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,
)

Saída:

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

Conteúdo

Formiga

aco_routing.Ant

• Uma Ant que percorre o gráfico.

ACO

aco_routing.ACO

• O algoritmo tradicional de otimização de colônia de formigas que gera formigas em vários nós do gráfico e encontra o caminho mais curto entre a origem e o destino especificados (pseudocódigo).

Contribuindo

• Publique quaisquer problemas e sugestões na página de problemas do GitHub.

• Para contribuir, bifurque o projeto e crie uma solicitação pull de volta ao master.