Difference between revisions of "Grammatical Swarm Evolution"
| Line 15: | Line 15: | ||
# PSO - updates particles (based on fitness value) with proper vectors that are used to search in the solution space | # PSO - updates particles (based on fitness value) with proper vectors that are used to search in the solution space | ||
# Grammatical Evolution - transforms particle vectors to full or partial robot programs | # Grammatical Evolution - transforms particle vectors to full or partial robot programs | ||
| − | # BNF Grammar - grammar that | + | # BNF Grammar - grammar that is specifying possibilities of robot programs generating |
# Output - robot programs | # Output - robot programs | ||
# 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) | # 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) | ||
Revision as of 19:24, 5 May 2013
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:
- PSO - updates particles (based on fitness value) with proper vectors that are used to search in the solution space
- Grammatical Evolution - transforms particle vectors to full or partial robot programs
- BNF Grammar - grammar that is specifying possibilities of robot programs generating
- Output - robot programs
- 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
