Source code for acopy.ant

# -*- coding: utf-8 -*-
import sys
import itertools
import bisect
import random

from .utils import positive
from .solvers import Solution

[docs]class Ant: """An ant. Ants explore a graph, using alpha and beta to guide their decision making process when choosing which edge to travel next. :param float alpha: how much pheromone matters :param float beta: how much distance matters """ def __init__(self, alpha=1, beta=3): self.alpha = alpha self.beta = beta @property def alpha(self): """How much pheromone matters. Always kept greater than zero.""" return self._alpha @alpha.setter def alpha(self, value): self._alpha = positive(value) @property def beta(self): """How much distance matters. Always kept greater than zero.""" return self._beta @beta.setter def beta(self, value): self._beta = positive(value) def __repr__(self): return f'Ant(alpha={self.alpha}, beta={self.beta})'
[docs] def tour(self, graph): """Find a solution to the given graph. :param graph: the graph to solve :type graph: :class:`networkx.Graph` :return: one solution :rtype: :class:`~acopy.solvers.Solution` """ solution = self.initialize_solution(graph) unvisited = self.get_unvisited_nodes(graph, solution) while unvisited: node = self.choose_destination(graph, solution.current, unvisited) solution.add_node(node) unvisited.remove(node) solution.close()
return solution
[docs] def initialize_solution(self, graph): """Return a newly initialized solution for the given graph. :param graph: the graph to solve :type graph: :class:`networkx.Graph` :return: intialized solution :rtype: :class:`~acopy.solvers.Solution` """ start = self.get_starting_node(graph)
return Solution(graph, start, ant=self)
[docs] def get_starting_node(self, graph): """Return a starting node for an ant. :param graph: the graph being solved :type graph: :class:`networkx.Graph` :return: node """
return random.choice(list(graph.nodes))
[docs] def get_unvisited_nodes(self, graph, solution): """Return the unvisited nodes. :param graph: the graph being solved :type graph: :class:`networkx.Graph` :param solution: in progress solution :type solution: :class:`~acopy.solvers.Solution` :return: unvisited nodes :rtype: list """ nodes = [] for node in graph[solution.current]: if node not in solution: nodes.append(node)
return nodes
[docs] def choose_destination(self, graph, current, unvisited): """Return the next node. :param graph: the graph being solved :type graph: :class:`networkx.Graph` :param current: starting node :param list unvisited: available nodes :return: chosen edge """ if len(unvisited) == 1: return unvisited[0] scores = self.get_scores(graph, current, unvisited)
return self.choose_node(unvisited, scores)
[docs] def get_scores(self, graph, current, destinations): """Return scores for the given destinations. :param graph: the graph being solved :type graph: :class:`networkx.Graph` :param current: the node from which to score the destinations :param list destinations: available, unvisited nodes :return: scores :rtype: list """ scores = [] for node in destinations: edge = graph.edges[current, node] score = self.score_edge(edge) scores.append(score)
return scores
[docs] def choose_node(self, choices, scores): """Return one of the choices. Note that ``scores[i]`` corresponds to ``choices[i]``. :param list choices: the unvisited nodes :param list scores: the scores for the given choices :return: one of the choices """ total = sum(scores) cumdist = list(itertools.accumulate(scores)) + [total] index = bisect.bisect(cumdist, random.random() * total)
return choices[min(index, len(choices) - 1)]
[docs] def score_edge(self, edge): """Return the score for the given edge. :param dict edge: the edge data :return: score :rtype: float """ weight = edge.get('weight', 1) if weight == 0: return sys.float_info.max pre = 1 / weight post = edge['pheromone']
return post ** self.alpha * pre ** self.beta
[docs]class Colony: """Colony of ants. Effectively this is a source of :class:`~acopy.ant.Ant` for a :class:`~acopy.solvers.Solver`. :param float alpha: relative factor for edge pheromone :param float beta: relative factor for edge weight """ def __init__(self, alpha=1, beta=3): self.alpha = alpha self.beta = beta def __repr__(self): return (f'{self.__class__.__name__}(alpha={self.alpha}, ' f'beta={self.beta})')
[docs] def get_ants(self, count): """Return the requested number of :class:`~acopy.ant.Ant` s. :param int count: number of ants to return :rtype: list """
return [Ant(**vars(self)) for __ in range(count)]