Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

ACO implementations in Java

Three ACO Algorithms in Java language

Solve Travel Salesman Problem

Data Structures

ACO implemetation

  • program runs for some interations
  • at each interation every Ant constructs a tour
  • updates the pheromone trails

Tour construction

combines

  • how much pheromone there is between two points
  • how close the points are

Pheromone update

some of the old pheromones evaporate

and some are added

different Variations

  • simple AS

  • Elite Ant (EAS)

  • MinMax (MMAS)

all Ants deposit pheromone between the points they have been through

a certain amount of extra pheromone is added between the points of the best-iteration-tour

Only the Ant that found the best tour deposits pheromone

aim: avoid biast tours

pheromones has lower and upper limits

if not a best tour found after a number of interations pheromone values are reinitialized

Local Optimizations (2-Opt, 2.5-Opt)

after every tour construction

changes the order of some cities in the tour to decrease its length

Programm run expectations

Conclusion

Fulfilled goals

Knowledge gained

Unique experience

TSP

  • Find the shortest tour
  • Shortest amount of time

ACO

Artificial imitation of one specific behavior based on natural instinct and capacities of Ants:

Find the optimal tour by communicating with pheromones

Artificial Ant->Ant Class Objects

  • conctruct tours

AsTSP->Main Class

create Ants

  • make them construct tours in parallel (Ant threads)
  • updates the pheromones

Aristeidis Stroumpos

ACO implementation in Java

June 14th 2011

Oral Presentation

Learn more about creating dynamic, engaging presentations with Prezi