ant colony optimization

Optimisation des colonies de fourmis

Un package Python pour trouver le chemin le plus court dans un graphique à l'aide de Ant Colony Optimization (ACO).

➡️ Consultez mon article Medium pour une présentation détaillée

L'algorithme d'optimisation des colonies de fourmis est une technique probabiliste permettant de résoudre des problèmes informatiques qui peuvent être réduits à trouver de bons chemins à travers des graphiques (source).

Cette implémentation de l'algorithme ACO utilise l'environnement graphique NetworkX.

Commencer

Pour installer le package directement depuis PyPi :

$ pip install aco_routing

Usage

Découvrez : exemple.py

Importez toutes les dépendances :

 à partir de aco_routing importer ACOimport networkx en tant que nx

Créez un objet NetworkX.Graph avec des nœuds et des arêtes :

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

Utilisez ACO pour trouver le chemin le plus court et le coût entre la source et 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,
)

Sortir:

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

Contenu

Fourmi

aco_routing.Ant

• Une Ant qui traverse le graphique.

ACO

aco_routing.ACO

• L'algorithme traditionnel d'optimisation des colonies de fourmis qui génère des fourmis à différents nœuds du graphique et trouve le chemin le plus court entre la source et la destination spécifiées (pseudo-code).

Contribuer

• Publiez tous les problèmes et suggestions sur la page des problèmes GitHub.

• Pour contribuer, créez le projet, puis créez une pull request vers le maître.