Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Automatic Design of Ant Algorithms with Grammat...

Automatic Design of Ant Algorithms with Grammatical Evolution

Talk given at EuroGP in Málaga, Spain, April 13, 2012. The paper received the "Best Paper Award".

Jorge Tavares

April 17, 2012
Tweet

Other Decks in Research

Transcript

  1. Automatic Design of Ant Algorithms with Grammatical Evolution Jorge Tavares

    Francisco B. Pereira CISUC, University of Coimbra, Portugal
  2. “A man provided with paper, pencil, and rubber, and subject

    to strict discipline, is in effect a universal machine.” Alan Turing
  3. running the system Initial Population Access Fitness of Population Satisfactory

    Individual exist ? Select Individuals Make Random Changes Return Best Individual Ant Algorithms Run Ant Algorithm to solve a problem Best Ant Algorithm for the problem
  4. <aco> ::= (aco <parameters-init> <optimization-cycle>) <optimization-cycle> ::= (repeat-until <loop-ants> <update-trails>

    <daemon-actions>) <loop-ants> ::= (foreach-ant make-solution-with <decision-policy> (if <bool> (local-update-trails <decay>))) <decision-policy> ::= (roulette-selection) | (q-selection <q-value>) | (random-selection) <update-trails> ::= (progn <evaporate> <reinforce>) ... ...
  5. the system is able to generate all main Ant algorithms

    Ant System (AS), Elitist Ant System (EAS), Rank- Based Ant System (RAS), Ant Colony System (ACS), Max-Min Ant System (MMAS)
  6. test problem: traveling salesman problem selected instances from TSPLIB: learning:

    eil76, pr76, gr96 testing: att48, eil51, berlin52, kroA100, lin105, gr137, u159, d198, pr226, lin318
  7. 0! 0.05! 0.1! 0.15! 0.2! 0.25! 0.3! 0.35! 1! 5!

    9! 13! 17! 21! 25! Distance to optimum! Generations! median of best individuals
  8. 1) evolution is able to discover original architectures 2) best

    evolved strategies exhibit a good generalization capability 3) competitive with human-designed variants 4) hybrid architecture based on evolved strategies is effective conclusions
  9. “We can only see a short distance ahead, but we

    can see plenty there that needs to be done.” Alan Turing
  10. Thank you. Questions? Special thanks to Alex Wild for all

    the Ant pictures @alexanderwild.com