Grammatical Swarm Evolution

From Robowiki
Jump to navigation Jump to search

Grammatical swarm is an evolutionary method based on combination of Grammatical Evolution and Particle Swarm Optimization (PSO). In Robocode context it is used to evolve partial or full robot programs. Evolution is realized outside of Robocode and only final robot programs are tested against specified set of robots in the Robocode. Results of testing are used in the evolution process as fitness values.

Inispiration

Works:

  • [1] GP-Robocode: Using Genetic Programming to Evolve Robocode Players by Yehonatan Shichel, Eran Ziserman, and Moshe Sipper
  • [2] Grammatical Swarm: The generation of programs by social by Michael O`Neill and Anthony Brabazon

Robots:

  • geep.mini.GPBotA: MiniRumble ‒ APS: 52.57% (267th), PL: 283-255 (252nd), Survival: 46.05%
  • dggp.haiku.gpBot_0: NanoRumble ‒ APS: 50.18% (152nd), PL: 99-131 (146th), Survival: 45.3%

How it works

Steps:

  1. PSO - updates particles (based on fitness value) with proper vectors that are used to search in the solution space
  2. Grammatical Evolution - transforms particle vectors to full or partial robot programs
  3. BNF Grammar - grammar that is specifying possibilities of robot programs generating
  4. Output - robot programs
  5. Target Function - quality criteria of robots that is calculated from robot tests (e.g. based on score against set of robots) which is used to assign fitness values to robots (particles)

http://robocode.hmark.eu/gswarm.png

Regression methods

Regression methods used for generating robot programs:

  • Behavioral regression - final program is represented by sequence of orders or statements defined by grammar
  • Parametric regression - aimed to generate set of constants that are applied in manually defined programs
  • Symbolic regression - aimed to generate math formulas

Experiments

hlavko.nano.Phoenix: NanoRumble ‒ APS: 54.06% (130th), PL: 115-115 (128th), Survival: 50.39%

  • robot generated with behavioral regression (grammar is similar to GP-Bot grammar)
  • using radar locking

hlavko.nano.Ringo 1.0: NanoRumble ‒ APS: 57.36% (94th), PL: 133-97 (100th), Survival: 55.09%

  • movement and wall smoothing parameters are generated with parametric regression
  • using wall smoothing movement and heads-on targeting

hlavko.nano.Ringo 2.0: NanoRumble ‒ APS: 59.23% (80th), PL: 143-87 (83rd), Survival: 60.25%

  • same as hlavko.nano.Ringo 1.0 but added fire formula generated with symbolic regression

hlavko.micro.Flex 1.5: MicroRumble ‒ APS: 75.68% (17th), PL: 338-66 (47th), Survival: 79.89%

  • one of the control strategies is generated with parametric regression
  • fire formula is same as in the hlavko.nano.Ringo 2.0 (generated by symbolic regression)
  • using set of strategies that controls movement and targeting