Source code for pants.solver

"""
.. module:: solver
    :platform: Linux, Unix, Windows
    :synopsis: Provides functionality for finding a complete solution to a 
               world.

.. moduleauthor:: Robert Grant <rhgrant10@gmail.com>

"""

import random
from copy import copy

from .world import World
from .ant import Ant

[docs]class Solver: """This class contains the functionality for finding one or more solutions for a given :class:`World`. :param float alpha: relative importance of pheromone (default=1) :param float beta: relative importance of distance (default=3) :param float rho: percent evaporation of pheromone (0..1, default=0.8) :param float q: total pheromone deposited by each :class:`Ant` after each iteration is complete (>0, default=1) :param float t0: initial pheromone level along each :class:`Edge` of the :class:`World` (>0, default=0.01) :param int limit: number of iterations to perform (default=100) :param float ant_count: how many :class:`Ant`\s will be used (default=10) :param float elite: multiplier of the pheromone deposited by the elite :class:`Ant` (default=0.5) """ def __init__(self, **kwargs): self.alpha = kwargs.get('alpha', 1) self.beta = kwargs.get('beta', 3) self.rho = kwargs.get('rho', 0.8) self.q = kwargs.get('Q', 1) self.t0 = kwargs.get('t0', .01) self.limit = kwargs.get('limit', 100) self.ant_count = kwargs.get('ant_count', 10) self.elite = kwargs.get('elite', .5)
[docs] def create_colony(self, world): """Create a set of :class:`Ant`\s and initialize them to the given *world*. If the *ant_count* is less than `1`, :func:`round_robin_ants` are used and the number of :class:`Ant`\s will be equal to the number of nodes. Otherwise, :func:`random_ants` are created instead, and the number of :class:`Ant`\s will be equal to the *ant_count*. :param World world: the world from which the :class:`Ant`\s will be given starting nodes. :return: list of :class:`Ant`\s :rtype: list """ if self.ant_count < 1: return self.round_robin_ants(world, len(world.nodes)) return self.random_ants(world, self.ant_count)
[docs] def reset_colony(self, colony): """Reset the *colony* of :class:`Ant`\s such that each :class:`Ant` is ready to find a new solution. Essentially, this method re-initializes all :class:`Ant`\s in the colony to the :class:`World` that they were initialized to last. Internally, this method is called after each iteration of the :class:`Solver`. :param list colony: the :class:`Ant`\s to reset """ for ant in colony: ant.initialize(ant.world)
[docs] def aco(self, colony): """Return the best solution by performing the ACO meta-heuristic. This method lets every :class:`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 :func:`solve` or :func:`solutions`. :param list colony: the `Ant`\s to use in finding a solution :return: the best solution found :rtype: :class:`Ant` """ self.find_solutions(colony) self.global_update(colony) return sorted(colony)[0]
[docs] def solve(self, world): """Return the single shortest path found through the given *world*. :param World world: the :class:`World` to solve :return: the single best solution found :rtype: :class:`Ant` """ world.reset_pheromone(self.t0) global_best = None colony = self.create_colony(world) for i in range(self.limit): self.reset_colony(colony) local_best = self.aco(colony) if global_best is None or local_best < global_best: global_best = copy(local_best) self.trace_elite(global_best) return global_best
[docs] def solutions(self, world): """Return successively shorter paths through the given *world*. Unlike :func:`solve`, this method returns one solution for each improvement of the best solution found thus far. :param World world: the :class:`World` to solve :return: successively shorter solutions as :class:`Ant`\s :rtype: list """ world.reset_pheromone(self.t0) global_best = None colony = self.create_colony(world) for i in range(self.limit): self.reset_colony(colony) local_best = self.aco(colony) if global_best is None or local_best < global_best: global_best = copy(local_best) yield global_best self.trace_elite(global_best)
[docs] def round_robin_ants(self, world, count): """Returns a list of :class:`Ant`\s distributed to the nodes of the world in a round-robin fashion. Note that this does not ensure at least one :class:`Ant` begins at each node unless there are exactly as many :class:`Ant`\s as there are nodes. However, if *ant_count* is ``0`` then *ant_count* is set to the number of nodes in the :class:`World` and this method is used to create the :class:`Ant`\s before solving. :param World world: the :class:`World` in which to create the :class:`Ant`\s :param int count: the number of :class:`Ant`\s to create :return: the :class:`Ant`\s initialized to nodes in the :class:`World` :rtype: list """ starts = world.nodes n = len(starts) return [ Ant(self.alpha, self.beta).initialize( world, start=starts[i % n]) for i in range(count) ]
[docs] def random_ants(self, world, count, even=False): """Returns a list of :class:`Ant`\s distributed to the nodes of the world in a random fashion. Note that this does not ensure at least one :class:`Ant` begins at each node unless there are exactly as many :class:`Ant`\s as there are nodes. This method is used to create the :class:`Ant`\s before solving if *ant_count* is **not** ``0``. :param World world: the :class:`World` in which to create the ants. :param int count: the number of :class:`Ant`\s to create :param bool even: ``True`` if :func:`random.random` should avoid choosing the same starting node multiple times (default is ``False``) :return: the :class:`Ant`\s initialized to nodes in the :class:`World` :rtype: list """ ants = [] starts = world.nodes n = len(starts) if even: # Since the caller wants an even distribution, use a round-robin # method until the number of ants left to create is less than the # number of nodes. if count > n: for i in range(self.ant_count // n): ants.extend([ Ant(self.alpha,self.beta).initialize( world, start=starts[j]) for j in range(n) ]) # Now (without choosing the same node twice) choose the reamining # starts randomly. ants.extend([ Ant(self.alpha, self.beta).initialize( world, start=starts.pop(random.randrange(n - i))) for i in range(count % n) ]) else: # Just pick random nodes. ants.extend([ Ant(self.alpha, self.beta).initialize( world, start=starts[random.randrange(n)]) for i in range(count) ]) return ants
[docs] def find_solutions(self, ants): """Let each :class:`Ant` find a solution. Makes each :class:`Ant` move until each can no longer move. .. todo:: Make the local pheromone update optional and configurable. :param list ants: the ants to use for solving """ # This loop occurs exactly as many times as there are ants times nodes, # but that is only because every ant must visit every node. It may be # more efficient to convert it to a counting loop... but what # flexibility would we loose in terms of extending the solver class? ants_done = 0 while ants_done < len(ants): ants_done = 0 for ant in ants: if ant.can_move(): edge = ant.move() self.local_update(edge) else: ants_done += 1
[docs] def local_update(self, edge): """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. :param Edge edge: the :class:`Edge` to be updated """ edge.pheromone = max(self.t0, edge.pheromone * self.rho)
[docs] def global_update(self, ants): """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. :param list ants: the ants to use for solving """ ants = sorted(ants)[:len(ants) // 2] for a in ants: p = self.q / a.distance for edge in a.path: edge.pheromone = max( self.t0, (1 - self.rho) * edge.pheromone + p)
[docs] def trace_elite(self, ant): """Deposit pheromone along the path of a particular ant. This method is used to deposit the pheromone of the elite :class:`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. :param Ant ant: the elite :class:`Ant` """ if self.elite: p = self.elite * self.q / ant.distance for edge in ant.path: edge.pheromone += p