API Documentation¶
acopy package¶
acopy.ant module¶
-
class
acopy.ant.
Ant
(alpha=1, beta=3)[source]¶ Bases:
object
An ant.
Ants explore a graph, using alpha and beta to guide their decision making process when choosing which edge to travel next.
Parameters: - alpha (float) – how much pheromone matters
- beta (float) – how much distance matters
-
alpha
¶ How much pheromone matters. Always kept greater than zero.
-
beta
¶ How much distance matters. Always kept greater than zero.
-
choose_destination
(graph, current, unvisited)[source]¶ Return the next node.
Parameters: - graph (
networkx.Graph
) – the graph being solved - current – starting node
- unvisited (list) – available nodes
Returns: chosen edge
- graph (
-
choose_node
(choices, scores)[source]¶ Return one of the choices.
Note that
scores[i]
corresponds tochoices[i]
.Parameters: - choices (list) – the unvisited nodes
- scores (list) – the scores for the given choices
Returns: one of the choices
-
get_scores
(graph, current, destinations)[source]¶ Return scores for the given destinations.
Parameters: - graph (
networkx.Graph
) – the graph being solved - current – the node from which to score the destinations
- destinations (list) – available, unvisited nodes
Returns: scores
Return type: list
- graph (
-
get_starting_node
(graph)[source]¶ Return a starting node for an ant.
Parameters: graph ( networkx.Graph
) – the graph being solvedReturns: node
-
get_unvisited_nodes
(graph, solution)[source]¶ Return the unvisited nodes.
Parameters: - graph (
networkx.Graph
) – the graph being solved - solution (
Solution
) – in progress solution
Returns: unvisited nodes
Return type: list
- graph (
-
initialize_solution
(graph)[source]¶ Return a newly initialized solution for the given graph.
Parameters: graph ( networkx.Graph
) – the graph to solveReturns: intialized solution Return type: Solution
-
score_edge
(edge)[source]¶ Return the score for the given edge.
Parameters: edge (dict) – the edge data Returns: score Return type: float
-
tour
(graph)[source]¶ Find a solution to the given graph.
Parameters: graph ( networkx.Graph
) – the graph to solveReturns: one solution Return type: Solution
acopy.solvers module¶
-
class
acopy.solvers.
Solution
(graph, start, ant=None)[source]¶ Bases:
object
Tour for a graph.
Parameters: - graph (
networkx.Graph
) – a graph - start – starting node
- ant (
Ant
) – ant responsible
- graph (
-
class
acopy.solvers.
Solver
(rho=0.03, q=1, top=None, plugins=None)[source]¶ Bases:
object
ACO solver.
Solvers control the parameters related to pheromone deposit and evaporation. If top is not specified, it defaults to the number of ants used to solve a graph.
Parameters: - rho (float) – percentage of pheromone that evaporates each iteration
- q (float) – amount of pheromone each ant can deposit
- top (int) – number of ants that deposit pheromone
- plugins (list) – zero or more solver plugins
-
add_plugin
(plugin)[source]¶ Add a single solver plugin.
If plugins have the same name, only the last one added is kept.
Parameters: plugin ( acopy.plugins.SolverPlugin
) – the plugin to add
-
find_solutions
(graph, ants)[source]¶ Return the solutions found for the given ants.
Parameters: - graph (
networkx.Graph
) – a graph - ants (list) – the ants to use
Returns: one solution per ant
Return type: list
- graph (
-
global_update
(state)[source]¶ Perform a global pheromone update.
Parameters: state ( State
) – solver state
-
optimize
(graph, colony, gen_size=None, limit=None)[source]¶ Find and return increasingly better solutions.
Parameters: - graph (
networkx.Graph
) – graph to solve - colony (
Colony
) – colony from which to source eachAnt
- gen_size (int) – number of
Ant
s to use (default is one per graph node) - limit (int) – maximum number of iterations to perform (default is unlimited so it will run forever)
Returns: better solutions as they are found
Return type: iter
- graph (
-
solve
(*args, **kwargs)[source]¶ Find and return the best solution.
Accepts exactly the same parameters as the
optimize()
method.Returns: best solution found Return type: Solution
-
class
acopy.solvers.
SolverPlugin
(**kwargs)[source]¶ Bases:
object
Solver plugin.
Solver plugins can be added to any solver to customize its behavior. Plugins are initialized once when added, once before the first solver iteration, once after each solver iteration has completed, and once after all iterations have completed.
Implementing each hook is optional.
-
initialize
(solver)[source]¶ Perform actions when being added to a solver.
Though technically not required, this method should be probably be idempotent since the same plugin could be added to the same solver multiple times (perhaps even by mistake).
Parameters: solver ( acopy.solvers.Solver
) – the solver to which the plugin is being added
-
name
= 'plugin'¶ unique name
-
on_finish
(state)[source]¶ Perform actions once all iterations have completed.
Parameters: state ( acopy.solvers.State
) – solver state
-
on_iteration
(state)[source]¶ Perform actions after each iteration.
Parameters: state ( acopy.solvers.State
) – solver state
-
on_start
(state)[source]¶ Perform actions before the first iteration.
Parameters: state ( acopy.solvers.State
) – solver state
-
-
class
acopy.solvers.
State
(graph, ants, limit, gen_size, colony)[source]¶ Bases:
object
Solver state.
This class tracks the state of a solution in progress and is passed to each plugin hook. Specially it contains:
Attribute Description graph
graph being solved colony
colony that generated the ants ants
ants being used to solve the graph limit
maximum number of iterations gen_size
number of ants being used solutions
solutions found this iteration best
best solution found this iteration is_new_record
whether the best is a new record record
best solution found so far previous_record
previously best solution Parameters: - graph (
networkx.Graph
) – a graph - ants (list) – the ants being used
- limit (int) – maximum number of iterations
- gen_size (int) – number of ants to use
- colony (
Colony
) – source colony for the ants
-
best
¶
- graph (
acopy.utils package¶
acopy.utils.data module¶
acopy.utils.general module¶
acopy.utils.plot module¶
The plot utility works with the StatsRecorder plugin to generate interesting plots of solver iterations.
-
class
acopy.utils.plot.
Plotter
(stats)[source]¶ Bases:
object
Utility for plotting iteration data using matplotlib.
This is meant to be used in combination with the
StatsRecorder
plugin which collects stats about solutions and pheromone levels on each iteration.Parameters: stats (dict) – map of stats by name