First prototypes
Contents |
[edit] First prototype
parrot-lgp params:
- population size: 50.000
- max generations: 50
- max individual length: 50 "bytes" (e.g. 25 two byte length instructions)
- input/output dataset
- input registers: I0, I1, I2
- output registers: I3
- dataset:
[ [ 3, 2, 1 ], [ 11 ] ],
[ [ 3, 3, 1 ], [ 12 ] ],
[ [ 3, 3, 3 ], [ 14 ] ],
[ [ 9, 5, 3 ], [ 22 ] ],
---------- ----
| |
input output
(I0,I1,I2) (I3)
- allowed instructions
496, // 20 ... abs_i: i(io) 498, // 21 ... abs_i_i: i(o), i(i) 503, // 22 ... add_i_i: i(io), i(i) 507, // 23 ... add_i_i_i: i(o), i(i), i(i) 519, // 25 ... dec_i: i(io) 522, // 26 ... div_i_i: i(io), i(i) 526, // 27 ... div_i_i_i: i(o), i(i), i(i) 550, // 30 ... inc_i: i(io) 563, // 33 ... mul_i_i: i(io), i(i) 567, // 34 ... mul_i_i_i: i(o), i(i), i(i) 583, // 37 ... sub_i_i: i(io), i(i) 587, // 38 ... sub_i_i_i: i(o), i(i), i(i) 810, // 39 ... exchange_i_i: i(io), i(io) 814, // 40 ... set_i_i: i(o), i(i) 917, // 41 ... null_i: i(o) 1, // 27 .. noop 16 // 28 .. ret
E.g. add_i_i means "Increase $1 by the amount in $2.". See Parrot instructions/opcodes.
- fitness function
- step 1) minimalize SUM( (correct_output-actual_individual_output)^2 )
- step 2) minimalize individual_length
The goal of parrot-lgp is to find the best (by fitness function) program (individual, symbolic regresion function) whitch compute output data from input data (for all rows in dataset) usign allowed instructions.
After 2 minutes on 2GHz, 512 MB RAM computer, if you are lucky, you get output similar to:
... gen 49, fights 12250000 ( max gen 50, max fights 12500000 ) gen 50, fights 12500000 ( max gen 50, max fights 12500000 ) run [ok] this run best indi: inum=31336, fitness=0, len=18, code: 0 +2 0 147e674 550 inc_i I1 1 +2 2 147e67c 550 inc_i I0 2 +2 4 147e684 550 inc_i I0 3 +2 6 147e68c 550 inc_i I2 4 +2 8 147e694 550 inc_i I2 5 +3 10 147e69c 503 add_i_i I0, I1 6 +4 13 147e6a8 507 add_i_i_i I3, I2, I0 7 +1 17 147e6b8 16 ret
The best individual is, after rewrited to math by hand, regression function I0 + I1 + I2 + 5. See dataset
[ [ 3, 2, 1 ], [ 11 ] ], # 3 + 2 + 1 + 5 = 11 [ [ 3, 3, 1 ], [ 12 ] ], # 3 + 3 + 1 + 5 = 12 [ [ 3, 3, 3 ], [ 14 ] ], # 3 + 3 + 3 + 5 = 14 [ [ 9, 5, 3 ], [ 22 ] ], # 9 + 5 + 3 + 5 = 22
[edit] Algorithm and speed
- initialization compute fitness for all randomly generated indviduals, it means evaluate each individual for each input set and compute fitness function from results
- 50.000 population size * 50 generations / 115 seconds (parrot-lgp r79) = cca 21.700 runs/second
each run contains of:
- randomly select 4 individuals from population
- sort them by fitness, indi0 is the worst, indi3 is the best (smaller fitness value)
- mutate indi2
- if mutated indi2 is better than indi0 then replace indi2 with new mutated indi2
- isn't new indi2 better then best_indi
- mutate indi3
- if mutated indi3 is better than indi1 then replace indi3 with new mutated indi3
- isn't new indi3 better then best_indi
So, each run do 2 fitness evaluation. When we add another from initialization, then 2 * 21.700 + ( 50.000 / 115 ) = 43.400 + 430 =
44.260 individual evaluation per second
- on Intel Pentium M, 1.86 GHz, 512 MB RAM
- each evaluation for full dataset (4 data rows)
- max individual length 50 bytes, population size 50.000
[edit] Another runs results
Some solutions founded in different runs:
Fitness 0:
this run best indi: inum=2387, fitness=0, len=18, code: 0 +2 0 93acfc 550 inc_i I1 1 +2 2 93ad04 550 inc_i I0 2 +2 4 93ad0c 550 inc_i I2 3 +2 6 93ad14 550 inc_i I1 4 +2 8 93ad1c 550 inc_i I0 5 +3 10 93ad24 503 add_i_i I0, I1 6 +4 13 93ad30 507 add_i_i_i I3, I0, I2 7 +1 17 93ad40 16 ret this run best indi: inum=19826, fitness=0, len=18, code: 0 +2 0 1003e64 550 inc_i I0 1 +2 2 1003e6c 550 inc_i I0 2 +2 4 1003e74 550 inc_i I1 3 +2 6 1003e7c 550 inc_i I1 4 +2 8 1003e84 550 inc_i I1 5 +4 10 1003e8c 507 add_i_i_i I3, I0, I2 6 +3 14 1003e9c 503 add_i_i I3, I1 7 +1 17 1003ea8 16 ret this run best indi: inum=31680, fitness=0, len=18, code: 0 +2 0 14a0ab4 550 inc_i I1 1 +4 2 14a0abc 507 add_i_i_i I3, I1, I2 2 +2 6 14a0acc 550 inc_i I3 3 +2 8 14a0ad4 550 inc_i I3 4 +2 10 14a0adc 550 inc_i I3 5 +2 12 14a0ae4 550 inc_i I3 6 +3 14 14a0aec 503 add_i_i I3, I0 7 +1 17 14a0af8 16 ret this run best indi: inum=2414, fitness=0, len=18, code: 0 +4 0 93d804 507 add_i_i_i I3, I1, I2 1 +3 4 93d814 503 add_i_i I3, I0 2 +2 7 93d820 550 inc_i I3 3 +2 9 93d828 550 inc_i I3 4 +2 11 93d830 550 inc_i I3 5 +2 13 93d838 550 inc_i I3 6 +2 15 93d840 550 inc_i I3 7 +1 17 93d848 16 ret
Fitness 0, length 20:
this run best indi: inum=16672, fitness=0, len=20, code: 0 +2 0 ec9bb4 550 inc_i I0 1 +2 2 ec9bbc 550 inc_i I2 2 +2 4 ec9bc4 550 inc_i I1 3 +3 6 ec9bcc 503 add_i_i I2, I0 4 +3 9 ec9bd8 503 add_i_i I1, I2 5 +2 12 ec9be4 550 inc_i I1 6 +3 14 ec9bec 810 exchange_i_i I1, I3 7 +2 17 ec9bf8 550 inc_i I3 8 +1 19 ec9c00 16 ret
Fitness 1, length 23:
this run best indi: inum=23092, fitness=1, len=23, code: 0 +2 0 1149394 550 inc_i I3 1 +2 2 114939c 550 inc_i I1 2 +3 4 11493a4 503 add_i_i I3, I0 3 +3 7 11493b0 503 add_i_i I3, I1 4 +3 10 11493bc 503 add_i_i I3, I1 5 +3 13 11493c8 522 div_i_i I2, I0 6 +3 16 11493d4 503 add_i_i I3, I2 7 +3 19 11493e0 503 add_i_i I3, I2 8 +1 22 11493ec 16 ret
Fitness 3, length 14:
this run best indi: inum=1625, fitness=3, len=14, code: 0 +2 0 8eee8c 550 inc_i I1 1 +2 2 8eee94 550 inc_i I1 2 +3 4 8eee9c 810 exchange_i_i I1, I3 3 +3 7 8eeea8 503 add_i_i I0, I3 4 +3 10 8eeeb4 503 add_i_i I3, I0 5 +1 13 8eeec0 16 ret
[edit] ChangeLog
[edit] revison 44
- reduction operator now implemented
- bug fixes
[edit] revison 48
- insertion operator implemented
num of results found: 50 fitness mean: 0.000 length mean: 18.480
[edit] revison 59
- code refactoring and cleanup
[edit] revison 62
- divide by zero exceptions
- added new ops
514, // 26 ... div_i_i: i(io), i(i) 518, // 27 ... div_i_i_i: i(o), i(i), i(i)
[edit] revision 72-74
- more cleanups and docs
[edit] revision 79 (23.7.2008)
- updated to Parrot r29697
- save and restore removed
- code cleanup
