Ant Colony Optimization



Download 11,6 Kb.
Date conversion28.12.2016
Size11,6 Kb.

Ant Colony Optimization

  • Theresa Meggie
  • Barker von Haartman
  • IE 516 Spring 2005

Overview

ACO Concept

  • Ants (blind) navigate from nest to food source
  • Shortest path is discovered via pheromone trails
    • each ant moves at random
    • pheromone is deposited on path
    • ants detect lead ant’s path, inclined to follow
    • more pheromone on path increases probability of path being followed

ACO System

  • Virtual “trail” accumulated on path segments
  • Starting node selected at random
  • Path selected at random
    • based on amount of “trail” present on possible paths from starting node
    • higher probability for paths with more “trail”
  • Ant reaches next node, selects next path
  • Continues until reaches starting node
  • Finished “tour” is a solution

ACO System, cont.

  • A completed tour is analyzed for optimality
  • “Trail” amount adjusted to favor better solutions
    • better solutions receive more trail
    • worse solutions receive less trail
    • higher probability of ant selecting path that is part of a better-performing tour
  • New cycle is performed
  • Repeated until most ants select the same tour on every cycle (convergence to solution)

ACO System, cont.

  • Often applied to TSP (Travelling Salesman Problem): shortest path between n nodes
  • Algorithm in Pseudocode:
    • Initialize Trail
    • Do While (Stopping Criteria Not Satisfied) – Cycle Loop
      • Do Until (Each Ant Completes a Tour) – Tour Loop
      • Local Trail Update
      • End Do
      • Analyze Tours
      • Global Trail Update
    • End Do

Background

  • Discrete optimization problems difficult to solve
  • “Soft computing techniques” developed in past ten years:
    • Genetic algorithms (GAs)
      • based on natural selection and genetics
    • Ant Colony Optimization (ACO)
      • modeling ant colony behavior

Background, cont.

  • Developed by Marco Dorigo (Milan, Italy), and others in early 1990s
  • Some common applications:
    • Quadratic assignment problems
    • Scheduling problems
    • Dynamic routing problems in networks
  • Theoretical analysis difficult
    • algorithm is based on a series of random decisions (by artificial ants)
    • probability of decisions changes on each iteration

Implementation

Ant Algorithms

  • Ant Algorithms

Implementation

  • Can be used for both Static and Dynamic Combinatorial optimization problems
  • Convergence is guaranteed, although the speed is unknown
    • Value
    • Solution

The Algorithm

  • Ant Colony Algorithms are typically use to solve minimum cost problems.
  • We may usually have N nodes and A undirected arcs
  • There are two working modes for the ants: either forwards or backwards.
  • Pheromones are only deposited in backward mode.

The Algorithm

  • The ants memory allows them to retrace the path it has followed while searching for the destination node
  • Before moving backward on their memorized path, they eliminate any loops from it. While moving backwards, the ants leave pheromones on the arcs they traversed.

The Algorithm

  • The ants evaluate the cost of the paths they have traversed.
  • The shorter paths will receive a greater deposit of pheromones. An evaporation rule will be tied with the pheromones, which will reduce the chance for poor quality solutions.

The Algorithm

  • At the beginning of the search process, a constant amount of pheromone is assigned to all arcs. When located at a node i an ant k uses the pheromone trail to compute the probability of choosing j as the next node:
  • where is the neighborhood of ant k when in node i.

The Algorithm

  • When the arc (i,j) is traversed , the pheromone value changes as follows:
  • By using this rule, the probability increases that forthcoming ants will use this arc.

The Algorithm

  • After each ant k has moved to the next node, the pheromones evaporate by the following equation to all the arcs:
  • where is a parameter. An iteration is a completer cycle involving ants’ movement, pheromone evaporation, and pheromone deposit.

Steps for Solving a Problem by ACO

  • Represent the problem in the form of sets of components and transitions, or by a set of weighted graphs, on which ants can build solutions
  • Define the meaning of the pheromone trails
  • Define the heuristic preference for the ant while constructing a solution
  • If possible implement a efficient local search algorithm for the problem to be solved.
  • Choose a specific ACO algorithm and apply to problem being solved
  • Tune the parameter of the ACO algorithm.

Applications

  • Efficiently Solves NP hard Problems
  • Routing
    • TSP (Traveling Salesman Problem)
    • Vehicle Routing
    • Sequential Ordering
  • Assignment
    • QAP (Quadratic Assignment Problem)
    • Graph Coloring
    • Generalized Assignment
    • Frequency Assignment
    • University Course Time Scheduling
  • 4
  • 3
  • 5
  • 2
  • 1

Applications

  • Scheduling
    • Job Shop
    • Open Shop
    • Flow Shop
    • Total tardiness (weighted/non-weighted)
    • Project Scheduling
    • Group Shop
  • Subset
    • Multi-Knapsack
    • Max Independent Set
    • Redundancy Allocation
    • Set Covering
    • Weight Constrained Graph Tree partition
    • Arc-weighted L cardinality tree
    • Maximum Clique

Applications

  • Other
    • Shortest Common Sequence
    • Constraint Satisfaction
    • 2D-HP protein folding
    • Bin Packing
  • Machine Learning
    • Classification Rules
    • Bayesian networks
    • Fuzzy systems
  • Network Routing
    • Connection oriented network routing
    • Connection network routing
    • Optical network routing

Advantages and Disadvantages

Advantages and Disadvantages

  • For TSPs (Traveling Salesman Problem), relatively efficient
    • for a small number of nodes, TSPs can be solved by exhaustive search
    • for a large number of nodes, TSPs are very computationally difficult to solve (NP-hard) – exponential time to convergence
  • Performs better against other global optimization techniques for TSP (neural net, genetic algorithms, simulated annealing)
  • Compared to GAs (Genetic Algorithms):
    • retains memory of entire colony instead of previous generation only
    • less affected by poor initial solutions (due to combination of random path selection and colony memory)

Advantages and Disadvantages, cont.

  • Can be used in dynamic applications (adapts to changes such as new distances, etc.)
  • Has been applied to a wide variety of applications
  • As with GAs, good choice for constrained discrete problems (not a gradient-based algorithm)

Advantages and Disadvantages, cont.

  • Theoretical analysis is difficult:
    • Due to sequences of random decisions (not independent)
    • Probability distribution changes by iteration
    • Research is experimental rather than theoretical
  • Convergence is guaranteed, but time to convergence uncertain

Advantages and Disadvantages, cont.

  • Tradeoffs in evaluating convergence:
    • In NP-hard problems, need high-quality solutions quickly – focus is on quality of solutions
    • In dynamic network routing problems, need solutions for changing conditions – focus is on effective evaluation of alternative paths
  • Coding is somewhat complicated, not straightforward
    • Pheromone “trail” additions/deletions, global updates and local updates
    • Large number of different ACO algorithms to exploit different problem characteristics

Sources

  • Dorigo, Marco and Stützle, Thomas. (2004) Ant Colony Optimization, Cambridge, MA: The MIT Press.
  • Dorigo, Marco, Gambardella, Luca M., Middendorf, Martin. (2002) “Guest Editorial,” IEEE Transactions on Evolutionary Computation, 6(4): 317-320.
  • Thompson, Jonathan, “Ant Colony Optimization.” http://www.orsoc.org.uk/region/regional/swords/swords.ppt, accessed April 24, 2005.
  • Camp, Charles V., Bichon, Barron, J. and Stovall, Scott P. (2005) “Design of Steel Frames Using Ant Colony Optimization,” Journal of Structural Engineeering, 131 (3):369-379.
  • Fjalldal, Johann Bragi, “An Introduction to Ant Colony Algorithms.” http://www.informatics.sussex.ac.uk/research/nlp/gazdar/teach/atc/1999/web/johannf/ants.html, accessed April 24, 2005.

Questions?



The database is protected by copyright ©sckool.org 2016
send message

    Main page