API Documentation

acopy package

acopy.ant module

class acopy.ant.Ant(alpha=1, beta=3)

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)

Return the next node.

Parameters:

• graph (networkx.Graph) – the graph being solved
• current – starting node
• unvisited (list) – available nodes

Returns:

chosen edge

choose_node(choices, scores)

Return one of the choices.

Note that scores[i] corresponds to choices[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)

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

get_starting_node(graph)

Return a starting node for an ant.

Parameters:graph (networkx.Graph) – the graph being solved Returns:node

get_unvisited_nodes(graph, solution)

Return the unvisited nodes.

Parameters:

• graph (networkx.Graph) – the graph being solved
• solution (Solution) – in progress solution

Returns:

unvisited nodes

Return type:

list

initialize_solution(graph)

Return a newly initialized solution for the given graph.

Parameters:graph (networkx.Graph) – the graph to solve Returns:intialized solution Return type:Solution

score_edge(edge)

Return the score for the given edge.

Parameters:edge (dict) – the edge data Returns:score Return type:float

tour(graph)

Find a solution to the given graph.

Parameters:graph (networkx.Graph) – the graph to solve Returns:one solution Return type:Solution

class acopy.ant.Colony(alpha=1, beta=3)

Bases: object

Colony of ants.

Effectively this is a source of Ant for a Solver.

Parameters:

• alpha (float) – relative factor for edge pheromone
• beta (float) – relative factor for edge weight

get_ants(count)

Return the requested number of Ant s.

Parameters:count (int) – number of ants to return Return type:list

acopy.solvers module

class acopy.solvers.Solution(graph, start, ant=None)

Bases: object

Tour for a graph.

Parameters:

• graph (networkx.Graph) – a graph
• start – starting node
• ant (Ant) – ant responsible

add_node(node)

Record a node as visited.

Parameters:node – the node visited

close()

Close the tour so that the first and last nodes are the same.

get_easy_id(sep=' ', monospace=True)

get_id()

Return the ID of the solution.

The default implementation is just each of the nodes in visited order.

Returns:solution ID Return type:tuple

trace(q, rho=0)

Deposit pheromone on the edges.

Note that by default no pheromone evaporates.

Parameters:

• q (float) – the amount of pheromone
• rho (float) – the percentage of pheromone to evaporate

class acopy.solvers.Solver(rho=0.03, q=1, top=None, plugins=None)

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)

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

add_plugins(*plugins)

Add one or more solver plugins.

find_solutions(graph, ants)

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

get_plugins()

Return the added plugins.

Returns:plugins previously added Return type:list

global_update(state)

Perform a global pheromone update.

Parameters:state (State) – solver state

optimize(graph, colony, gen_size=None, limit=None)

Find and return increasingly better solutions.

Parameters:

• graph (networkx.Graph) – graph to solve
• colony (Colony) – colony from which to source each Ant
• 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

solve(*args, **kwargs)

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)

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)

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)

Perform actions once all iterations have completed.

Parameters:state (acopy.solvers.State) – solver state

on_iteration(state)

Perform actions after each iteration.

Parameters:state (acopy.solvers.State) – solver state

on_start(state)

Perform actions before the first iteration.

Parameters:state (acopy.solvers.State) – solver state

class acopy.solvers.State(graph, ants, limit, gen_size, colony)

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

acopy.utils package

acopy.utils.data module

acopy.utils.data.get_demo_graph()

acopy.utils.data.get_formats()

acopy.utils.data.read_graph_data(path, format_)

acopy.utils.data.read_json(path)

acopy.utils.data.read_tsplib95(path)

acopy.utils.general module

acopy.utils.general.is_plot_enabled()

Return true if plotting is enabled.

Plotting requires matplotlib and pandas to be installed.

Returns:indication of whether plotting is enabled Return type:bool

acopy.utils.general.looper(limit)

Return an optionally endless list of indexes.

acopy.utils.general.positive(value)

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)

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

extract_ant_distances()

plot()

Create and show the plot.