ant colony optimization

Ant Colony Optimization

A Python package to find the shortest path in a graph using Ant Colony Optimization (ACO).

➡️ Check out my Medium article for a detailed walkthrough

The Ant colony Optimization algorithm is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs (source).

This implementation of the ACO algorithm uses the NetworkX graph environment.

Getting Started

To install the package directly from PyPi:

$ pip install aco_routing

Usage

Check out: example.py

Import all the dependencies:

from aco_routing import ACOimport networkx as nx

Create a NetworkX.Graph object with nodes and edges:

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", cost=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)

Use ACO to find the shortest path and cost between the source and 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,
)

Output:

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

Contents

Ant

aco_routing.Ant

• An Ant that traverses the graph.

ACO

aco_routing.ACO

• The traditional Ant Colony Optimization algorithm that spawns ants at various nodes in the graph and finds the shortest path between the specified source and destination (pseudo code).

Contributing

• Post any issues and suggestions on the GitHub issues page.

• To contribute, fork the project and then create a pull request back to master.