Skip to content
This repository has been archived by the owner on Jul 23, 2020. It is now read-only.

Implementation of the Ant Colony Optimization algorithm (python)

Notifications You must be signed in to change notification settings

pjmattingly/ant-colony-optimization

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

21 Commits
 
 
 
 
 
 
 
 

Repository files navigation

ant-colony-optimization

Implementation of the Ant Colony Optimization algorithm (python)

#Usage: import ant_colony

//given some nodes, and some locations...
test_nodes = {0: (0, 7), 1: (3, 9), 2: (12, 4), 3: (14, 11), 4: (8, 11)
	5: (15, 6), 6: (6, 15), 7: (15, 9), 8: (12, 10), 9: (10, 7)}

//...and a function to get distance between nodes...
def distance(start, end):
	x_distance = abs(start[0] - end[0])
	y_distance = abs(start[1] - end[1])
	
	//c = sqrt(a^2 + b^2)
	import math
	return math.sqrt(pow(x_distance, 2) + pow(y_distance, 2))

//...we can make a colony of ants...
colony = ant_colony(test_nodes, distance)

//...that will find the optimal solution with ACO
answer = colony.mainloop()

#Discussion:

Ant Colony Optimization is intended to solve combinatoric optimization problems (like the Traveling Salesman Problem, or the Knapsack Problem). Simply feed the constructor a dict mapping your node names to coordinates of those nodes and give it a distance function call back that can take the coordinates and it will solve it using the ACO algorithm as described.

An effort has been made to initialize the algorithm's variables (alpha, beta, Q, etc) to sensible defaults. But your TSP problem may differ significantly from the testing set (see test directory) and may perform more poorly than optimal.

The latest release is multithreaded.

A full description of the behavior of the algorithm can be found here: https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms#Example_pseudo-code_and_formula

Note: Tests that implement finding actual optimal paths may fail occasionally, as this algorithm is semi-random. The default configuration should make this a rare occurance.

About

Implementation of the Ant Colony Optimization algorithm (python)

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages