Difference between revisions of "Grammatical Swarm Evolution"
(Created page with "Grammatical swarm is an evolutionary method based on combination of [http://en.wikipedia.org/wiki/Grammatical_evolution Grammatical Evolution] and [http://en.wikipedia.org/wiki/P...") |
(Remove categories as it is not strictly a movement or targeting strategy) |
||
| (8 intermediate revisions by one other user not shown) | |||
| 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 | + | # Target Function - quality criteria of robots which is calculated in robot tests (e.g. based on score against set of robots) and used to assign fitness values to robots (particles) |
http://robocode.hmark.eu/gswarm.png | http://robocode.hmark.eu/gswarm.png | ||
== Regression methods == | == Regression methods == | ||
| − | + | ==== '''Behavioral regression''' ==== | |
| − | + | Final program is represented by sequence of orders or statements defined by grammar. | |
| − | * '''Parametric regression''' | + | |
| − | * '''Symbolic regression''' | + | ''Grammar example:''<br/> |
| + | <code><!EXP> = <!IFF> | <!LOG><br/> | ||
| + | <!LOG> = <!OPP> | <!VAR> | <!CON><br/> | ||
| + | <!IFF> = ((<!LOG> > <!LOG>) ? (<!EXP>) : (<!EXP>))<br/> | ||
| + | <!OPP> = <!LOG> + <!LOG> | <!LOG> - <!LOG> | <!LOG> * <!LOG> | Math.abs(<!LOG>) | Math.cos(Math.PI * <!LOG>) | (-(<!LOG>)) | ||
| + | <!VAR> = (Math.random() * 2 - 1) | e.getDistance() / 300.0D | e.getBearingRadians() | e.getHeadingRadians() - getHeadingRadians() | e.getVelocity() / 300.0D | e.getEnergy() / 100.0D | getEnergy() / 100.0D<br/> | ||
| + | <!CON> = (- Math.PI / 2) | (-Math.PI / 4) | (Math.PI / 4) | (Math.PI / 2)</code> | ||
| + | <br/><br/> | ||
| + | ''Robot example:''<br/> | ||
| + | <code>turnGunLeftRadians(robocode.util.Utils.normalRelativeAngle(((getY() > ((fireBullet(3)==null) ? 0.0 : 0.0)) ? (((Math.abs(getWidth()) > getGunHeadingRadians()) ? (Math.sin(0.0)) : (getHeadingRadians()))) : (e.getEnergy()))));</code> | ||
| + | <br/> | ||
| + | ==== '''Parametric regression''' ==== | ||
| + | Aimed to generate set of constants that are applied in manually defined programs. | ||
| + | |||
| + | ''Grammar example:''<br/> | ||
| + | <code><!EXP> = goAhead((wallDistance() / 15) * <!CON> + (e.getDistance() / 15) * <!CON>) + northStickSensor() * <!CON><br/> | ||
| + | <!CON> = -1.00 | -0.80 | -0.60 | -0.40 | -0.20 | 0.00 | 0.20 | 0.40 | 0.60 | 0.80 | 1.00</code><br/><br/> | ||
| + | ''Robot example:''<br/> | ||
| + | <code>double turnRightRadians = robocode.util.Utils.normalRelativeAngle(goAhead((wallDistance() / 15) * -0.60 + (e.getDistance() / 15) * -0.4) + northStickSensor() * 0.2);</code> | ||
| + | <br/> | ||
| + | ==== '''Symbolic regression''' ==== | ||
| + | Aimed to generate math formulas. | ||
| + | |||
| + | ''Grammar example:''<br/> | ||
| + | <code><!EXP> = 1 / (<!VAL>)<br/> | ||
| + | <!VAL> = <!VAL> <!OPP> <!VAL> | <!VAR><br/> | ||
| + | <!OPP> = + | - | * | /<br/> | ||
| + | <!VAR> = e.getEnergy() | getEnergy() | e.getDistance()</code><br/><br/> | ||
| + | ''Robot example:''<br/> | ||
| + | <code>setFire(enemyEnergy + getEnergy() / getEnergy() * getEnergy() / e.getDistance() + e.getEnergy() - e.getEnergy());</code> | ||
== Experiments == | == Experiments == | ||
'''hlavko.nano.Phoenix''': {{RumbleStatsDefault|link=http://literumble.appspot.com/BotDetails?game=nanorumble&name=hlavko.nano.Phoenix%201.0|rumble=NanoRumble|scorelabel=APS|score=54.06|rank=130th|win=115|loss=115|plrank=128th|glicko2=N/A|pwin=50|vote=0|anpp=60.46|score2label=Survival|score2=50.39}}<br /> | '''hlavko.nano.Phoenix''': {{RumbleStatsDefault|link=http://literumble.appspot.com/BotDetails?game=nanorumble&name=hlavko.nano.Phoenix%201.0|rumble=NanoRumble|scorelabel=APS|score=54.06|rank=130th|win=115|loss=115|plrank=128th|glicko2=N/A|pwin=50|vote=0|anpp=60.46|score2label=Survival|score2=50.39}}<br /> | ||
| − | * robot generated with behavioral regression | + | * robot generated with behavioral regression (grammar is similar to GP-Bot grammar) |
* using radar locking | * using radar locking | ||
| Line 40: | Line 69: | ||
* same as hlavko.nano.Ringo 1.0 but added fire formula generated with symbolic regression | * same as hlavko.nano.Ringo 1.0 but added fire formula generated with symbolic regression | ||
| − | '''hlavko.micro.Flex 1.5''': {{RumbleStatsDefault|link=http://literumble.appspot.com/BotDetails?game=microrumble&name=hlavko.micro.Flex%201.5|rumble=MicroRumble|scorelabel=APS|score=75.68|rank=17th|win=338|loss=66|plrank=47th|glicko2=N/A|pwin=83.66|vote=0.99|anpp=83.9|score2label=Survival|score2=79.89}}<br /> | + | [[Flex|'''hlavko.micro.Flex 1.5''']]: {{RumbleStatsDefault|link=http://literumble.appspot.com/BotDetails?game=microrumble&name=hlavko.micro.Flex%201.5|rumble=MicroRumble|scorelabel=APS|score=75.68|rank=17th|win=338|loss=66|plrank=47th|glicko2=N/A|pwin=83.66|vote=0.99|anpp=83.9|score2label=Survival|score2=79.89}}<br /> |
* one of the control strategies is generated with parametric regression | * 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) | * 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 | * using set of strategies that controls movement and targeting | ||
| − | |||
| − | |||
Latest revision as of 06:14, 21 August 2017
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.
Contents
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 which is calculated in robot tests (e.g. based on score against set of robots) and used to assign fitness values to robots (particles)
http://robocode.hmark.eu/gswarm.png
Regression methods
Behavioral regression
Final program is represented by sequence of orders or statements defined by grammar.
Grammar example:
<!EXP> = <!IFF> | <!LOG>
<!LOG> = <!OPP> | <!VAR> | <!CON>
<!IFF> = ((<!LOG> > <!LOG>) ? (<!EXP>) : (<!EXP>))
<!OPP> = <!LOG> + <!LOG> | <!LOG> - <!LOG> | <!LOG> * <!LOG> | Math.abs(<!LOG>) | Math.cos(Math.PI * <!LOG>) | (-(<!LOG>))
<!VAR> = (Math.random() * 2 - 1) | e.getDistance() / 300.0D | e.getBearingRadians() | e.getHeadingRadians() - getHeadingRadians() | e.getVelocity() / 300.0D | e.getEnergy() / 100.0D | getEnergy() / 100.0D
<!CON> = (- Math.PI / 2) | (-Math.PI / 4) | (Math.PI / 4) | (Math.PI / 2)
Robot example:
turnGunLeftRadians(robocode.util.Utils.normalRelativeAngle(((getY() > ((fireBullet(3)==null) ? 0.0 : 0.0)) ? (((Math.abs(getWidth()) > getGunHeadingRadians()) ? (Math.sin(0.0)) : (getHeadingRadians()))) : (e.getEnergy()))));
Parametric regression
Aimed to generate set of constants that are applied in manually defined programs.
Grammar example:
<!EXP> = goAhead((wallDistance() / 15) * <!CON> + (e.getDistance() / 15) * <!CON>) + northStickSensor() * <!CON>
<!CON> = -1.00 | -0.80 | -0.60 | -0.40 | -0.20 | 0.00 | 0.20 | 0.40 | 0.60 | 0.80 | 1.00
Robot example:
double turnRightRadians = robocode.util.Utils.normalRelativeAngle(goAhead((wallDistance() / 15) * -0.60 + (e.getDistance() / 15) * -0.4) + northStickSensor() * 0.2);
Symbolic regression
Aimed to generate math formulas.
Grammar example:
<!EXP> = 1 / (<!VAL>)
<!VAL> = <!VAL> <!OPP> <!VAL> | <!VAR>
<!OPP> = + | - | * | /
<!VAR> = e.getEnergy() | getEnergy() | e.getDistance()
Robot example:
setFire(enemyEnergy + getEnergy() / getEnergy() * getEnergy() / e.getDistance() + e.getEnergy() - e.getEnergy());
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
