Welcome to the documentation for Pants!¶
A Python3 implementation of the Ant Colony Optimization Meta-Heuristic.
Pants provides you with the ability to quickly determine how to visit a collection of interconnected nodes such that the work done is minimized. Nodes can be any arbitrary collection of data while the edges represent the amount of “work” required to travel between two nodes. Thus, Pants is a tool for solving traveling salesman problems.
The world is built from a list of nodes and a function responsible for returning the length of the edge between any two given nodes. The length function need not return actual length. Instead, “length” refers to that the amount of “work” involved in moving from the first node to the second node - whatever that “work” may be. For a silly, random example, it could even be the number of dishes one must wash before moving to the next station at a least dish-washing dish washer competition.
Solutions are found through an iterative process. In each iteration, several ants are allowed to find a solution that “visits” every node of the world. The amount of pheromone on each edge is updated according to the length of the solutions in which it was used. The ant that traveled the least distance is considered to be the local best solution. If the local solution has a shorter distance than the best from any previous iteration, it then becomes the global best solution. The elite ant(s) then deposit their pheromone along the path of the global best solution to strengthen it further, and the process repeats.
You can read more about Ant Colony Optimization on Wikipedia.
World module¶
-
class
pants.world.
Edge
(start, end, length=None, pheromone=None)[source]¶ This class represents the link between starting and ending nodes.
In addition to start and end nodes, every
Edge
has length and pheromone properties. length represents the static, a priori information, whereas pheromone level represents the dynamic, a posteriori information.Parameters:
-
class
pants.world.
World
(nodes, lfunc, **kwargs)[source]¶ The nodes and edges of a particular problem.
Each
World
is created from a list of nodes, a length function, and optionally, a name and a description. Additionally, eachWorld
has a UID. The length function must accept nodes as its first two parameters, and is responsible for returning the distance between them. It is the responsibility of thecreate_edges()
to generate the requiredEdge
s and initialize them with the correct length as returned by the length function.Once created,
World
objects convert the actual nodes into node IDs, since solving does not rely on the actual data in the nodes. These are accessible via thenodes
property. To access the actual nodes, simply pass an ID obtained fromnodes
to thedata()
method, which will return the node associated with the specified ID.Edge
s are accessible in much the same way, except two node IDs must be passed to thedata()
method to indicate which nodes start and end theEdge
. For example:ids = world.nodes assert len(ids) > 1 node0 = world.data(ids[0]) node1 = world.data(ids[1]) edge01 = world.data(ids[0], ids[1]) assert edge01.start == node0 assert edge01.end == node1
The
reset_pheromone()
method provides an easy way to reset the pheromone levels of everyEdge
contained in aWorld
to a given level. It should be invoked before attempting to solve aWorld
unless a “blank slate” is not desired. Also note that it should not be called between iterations of theSolver
because it effectively erases the memory of theAnt
colony solving it.Parameters: -
create_edges
()[source]¶ Create edges from the nodes.
The job of this method is to map node ID pairs to
Edge
instances that describe the edge between the nodes at the given indices. Note that all of theEdge
s are created within this method.Returns: a mapping of node ID pairs to Edge
instances.Return type: dict
-
data
(idx, idy=None)[source]¶ Return the node data of a single id or the edge data of two ids.
If only idx is specified, return the node with the ID idx. If idy is also specified, return the
Edge
between nodes with indices idx and idy.Parameters: Returns: the node with ID idx or the
Edge
between nodes with IDs idx and idy.Return type: node or
Edge
-
nodes
¶ Node IDs.
-
reset_pheromone
(level=0.01)[source]¶ Reset the amount of pheromone on every edge to some base level.
Each time a new set of solutions is to be found, the amount of pheromone on every edge should be equalized to ensure un-biased initial conditions.
Parameters: level (float) – amount of pheromone to set on each edge (default=0.01)
-
Ant module¶
-
class
pants.ant.
Ant
(alpha=1, beta=3)[source]¶ A single independent finder of solutions to a
World
.Each
Ant
finds a solution to a world one move at a time. They also represent the solution they find, and are capable of reporting which nodes and edges they visited, in what order they were visited, and the total length of the solution.Two properties govern the decisions each
Ant
makes while finding a solution: alpha and beta. alpha controls the importance placed on pheromone while beta controls the importance placed on distance. In general, beta should be greater than alpha for best results.Ant
s also have a uid property that can be used to identify a particular instance.Using the
initialize()
method, eachAnt
must be initialized to a particularWorld
, and optionally may be given an initial node from which to start finding a solution. If a starting node is not given, one is chosen at random. Thus a few examples of instantiation and initialization might look like:ant = Ant() ant.initialize(world)
ant = Ant().initialize(world)
ant = Ant(alpha=0.5, beta=2.25) ant.initialize(world, start=world.nodes[0])
Note
The examples above assume the world has already been created!
Once an
Ant
has found a solution (or at any time), the solution may be obtained and inspected by accessing itstour
property, which returns the nodes visited in order, or itspath
property, which returns the edges visited in order. Also, the total distance of the solution can be accessed through itsdistance
property.Ant
s are even sortable by their distance:ants = [Ant() for ...] # ... have each ant in the list solve a world ants = sorted(ants) for i in range(1, len(ants)): assert ants[i - 1].distance < ants[i].distance
Ant
s may be cloned, which will return a shallow copy while not preserving the uid property. If this behavior is not desired, simply use thecopy.copy()
orcopy.deepcopy()
methods as necessary.The remaining methods mainly govern the mechanics of making each move.
can_move()
determines whether all possible moves have been made,remaining_moves()
returns the moves not yet made,choose_move()
returns a single move from a list of moves,make_move()
actually performs the move, andweigh()
returns the weight of a given move. Themove()
method governs the move-making process by gathering the remaining moves, choosing one of them, making the chosen move, and returning the move that was made.-
choose_move
(choices)[source]¶ Choose a move from all possible moves.
Parameters: choices (list) – a list of all possible moves Returns: the chosen element from choices Return type: node
-
clone
()[source]¶ Return a shallow copy with a new UID.
If an exact copy (including the uid) is desired, use the
copy.copy()
method.Returns: a clone Return type: Ant
-
initialize
(world, start=None)[source]¶ Reset everything so that a new solution can be found.
Parameters: - world (World) – the world to solve
- start (Node) – the starting node (default is chosen randomly)
Returns: self
Return type: Ant
-
make_move
(dest)[source]¶ Move to the dest node and return the edge traveled.
When dest is
None
, an attempt to take the final move back to the starting node is made. If that is not possible (because it has previously been done), thenNone
is returned.Parameters: dest (node) – the destination node for the move Returns: the edge taken to get to dest Return type: Edge
-
move
()[source]¶ Choose, make, and return a move from the remaining moves.
Returns: the Edge
taken to make the move chosenReturn type: Edge
-
node
¶ Most recently visited node.
-
path
¶ Edges traveled by the
Ant
in order.
-
tour
¶ Nodes visited by the
Ant
in order.
-
weigh
(edge)[source]¶ Calculate the weight of the given edge.
The weight of an edge is simply a representation of its perceived value in finding a shorter solution. Larger weights increase the odds of the edge being taken, whereas smaller weights decrease those odds.
Parameters: edge (Edge) – the edge to weigh Returns: the weight of edge Return type: float
-
Solver module¶
-
class
pants.solver.
Solver
(**kwargs)[source]¶ This class contains the functionality for finding one or more solutions for a given
World
.Parameters: - alpha (float) – relative importance of pheromone (default=1)
- beta (float) – relative importance of distance (default=3)
- rho (float) – percent evaporation of pheromone (0..1, default=0.8)
- q (float) – total pheromone deposited by each
Ant
after each iteration is complete (>0, default=1) - t0 (float) – initial pheromone level along each
Edge
of theWorld
(>0, default=0.01) - limit (int) – number of iterations to perform (default=100)
- ant_count (float) – how many
Ant
s will be used (default=10) - elite (float) – multiplier of the pheromone deposited by the elite
Ant
(default=0.5)
-
aco
(colony)[source]¶ Return the best solution by performing the ACO meta-heuristic.
This method lets every
Ant
in the colony find a solution, updates the pheromone levels according to the solutions found, and returns the Ant with the best solution.This method is not meant to be called directly. Instead, call either
solve()
orsolutions()
.Parameters: colony (list) – the Ants to use in finding a solution Returns: the best solution found Return type: Ant
-
create_colony
(world)[source]¶ Create a set of
Ant
s and initialize them to the given world.If the ant_count is less than 1,
round_robin_ants()
are used and the number ofAnt
s will be equal to the number of nodes. Otherwise,random_ants()
are created instead, and the number ofAnt
s will be equal to the ant_count.Parameters: world (World) – the world from which the Ant
s will be given starting nodes.Returns: list of Ant
sReturn type: list
-
find_solutions
(ants)[source]¶ Let each
Ant
find a solution.Makes each
Ant
move until each can no longer move.Parameters: ants (list) – the ants to use for solving
-
global_update
(ants)[source]¶ Update the amount of pheromone on each edge according to the fitness of solutions that use it.
This accomplishes the global update performed at the end of each solving iteration.
Note
This method should never let the pheromone on an edge decrease to less than its initial level.
Parameters: ants (list) – the ants to use for solving
-
local_update
(edge)[source]¶ Evaporate some of the pheromone on the given edge.
Note
This method should never let the pheromone on an edge decrease to less than its initial level.
Parameters: edge (Edge) – the Edge
to be updated
-
random_ants
(world, count, even=False)[source]¶ Returns a list of
Ant
s distributed to the nodes of the world in a random fashion.Note that this does not ensure at least one
Ant
begins at each node unless there are exactly as manyAnt
s as there are nodes. This method is used to create theAnt
s before solving if ant_count is not0
.Parameters: - world (World) – the
World
in which to create the ants. - count (int) – the number of
Ant
s to create - even (bool) –
True
ifrandom.random()
should avoid choosing the same starting node multiple times (default isFalse
)
Returns: the
Ant
s initialized to nodes in theWorld
Return type: - world (World) – the
-
reset_colony
(colony)[source]¶ Reset the colony of
Ant
s such that eachAnt
is ready to find a new solution.Essentially, this method re-initializes all
Ant
s in the colony to theWorld
that they were initialized to last. Internally, this method is called after each iteration of theSolver
.Parameters: colony (list) – the Ant
s to reset
-
round_robin_ants
(world, count)[source]¶ Returns a list of
Ant
s distributed to the nodes of the world in a round-robin fashion.Note that this does not ensure at least one
Ant
begins at each node unless there are exactly as manyAnt
s as there are nodes. However, if ant_count is0
then ant_count is set to the number of nodes in theWorld
and this method is used to create theAnt
s before solving.Parameters: Returns: the
Ant
s initialized to nodes in theWorld
Return type:
-
solutions
(world)[source]¶ Return successively shorter paths through the given world.
Unlike
solve()
, this method returns one solution for each improvement of the best solution found thus far.Parameters: world (World) – the World
to solveReturns: successively shorter solutions as Ant
sReturn type: list
-
solve
(world)[source]¶ Return the single shortest path found through the given world.
Parameters: world (World) – the World
to solveReturns: the single best solution found Return type: Ant
-
trace_elite
(ant)[source]¶ Deposit pheromone along the path of a particular ant.
This method is used to deposit the pheromone of the elite
Ant
at the end of each iteration.Note
This method should never let the pheromone on an edge decrease to less than its initial level.
Parameters: ant (Ant) – the elite Ant