Disclaimer: I just hacked this out without putting too much thought into it. Obviously you should put thought into yours.
Example: I have five data points that plot an unknown quadratic function. I want to discover the function using GA (rather than solve it immediately and precisely using math).
Code: Select all
-10 => 102.26
-5 => 22.96
0 => 4.66
5 => 47.36
10 => 151.06
Step 1: serialization. Since it's a quadratic function I can serialize the necessary data as an array with three numbers representing the coefficients.
Step 2: fitness. I'm going to sum the squares of the differences between the observed data points and what my coefficients calculate. R-squared would probably be better but I don't care.
Code: Select all
function fitness($coeff) {
static $observed = array(-10 => 102.26, -5 => 22.96, 0 => 4.66, 5 => 47.36, 10 => 151.06);
$fitness = 0;
foreach ($observed as $x => $y) {
$fitness += pow($y - ($coeff[0] * $x * $x + $coeff[1] * $x + $coeff[2]), 2);
}
return $fitness;
}
Step 3: mutator. I'll vary each coefficient by +/- 10%.
Code: Select all
function mutator($coeff) {
$keys = array_rand($coeff, mt_rand(1, 3));
if (!is_array($keys)) $keys = array($keys);
foreach ($keys as $k) {
$coeff[$k] += (abs($coeff[$k]) < 0.5 ? 1 : $coeff[$k]) * (mt_rand(90, 110) - 100) / 100;
}
return $coeff;
}
Starting with an input,
Code: Select all
$coeff = array(10, 10, 10); // 10x**2 + 10x + 10
do {
mutate it repeatedly,
Code: Select all
$coeffs = array();
for ($i = 0; $i < 20; $i++) {
$coeffs[] = mutator($coeff);
}
rate fitness, and choose the best ones.
Code: Select all
usort($coeffs, function($a, $b) {
return fitness($a) - fitness($b);
});
I then average the original and the two best selections to get my new selection, and rate it.
Code: Select all
$coeff[0] = ($coeff[0] + $coeffs[0][0] + $coeffs[1][0]) / 3;
$coeff[1] = ($coeff[1] + $coeffs[0][1] + $coeffs[1][1]) / 3;
$coeff[2] = ($coeff[2] + $coeffs[0][2] + $coeffs[1][2]) / 3;
$f = fitness($coeff);
Keep going until I'm satisfied.
Code: Select all
printf("%+.4fx**2 %+.4fx %+.4f => fitness %.6f\n", $coeff[0], $coeff[1], $coeff[2], $f);
flush();
usleep(100e3);
} while ($f > 0.05);
Code: Select all
+9.3333x**2 +9.6333x +10.0667 => fitness 1433821.493556
+8.8044x**2 +9.3764x +9.5969 => fitness 1253252.907026
+8.2468x**2 +9.4077x +9.3410 => fitness 1077940.072763
+7.7520x**2 +9.6899x +9.0296 => fitness 934186.787451
+7.2869x**2 +9.7545x +9.3005 => fitness 809714.223125
+6.8983x**2 +9.4944x +9.5795 => fitness 711686.324781
+6.4844x**2 +9.7159x +10.0585 => fitness 616503.789552
+6.0737x**2 +9.6188x +10.3938 => fitness 527577.429821
+5.8307x**2 +9.3623x +9.7701 => fitness 475643.737275
+5.5392x**2 +9.4871x +10.2261 => fitness 421021.257730
+5.1699x**2 +9.7717x +10.2261 => fitness 356127.019499
+4.8770x**2 +9.7066x +9.9193 => fitness 307140.054980
+4.5843x**2 +9.8036x +9.9193 => fitness 263066.188372
+4.3093x**2 +10.0978x +9.6217 => fitness 225250.759649
+4.1513x**2 +10.0978x +9.6538 => fitness 204692.416633
+3.9022x**2 +10.1987x +9.7503 => fitness 174882.542250
+3.6811x**2 +10.2667x +9.7503 => fitness 150416.909984
+3.4725x**2 +9.9929x +9.7503 => fitness 127939.881429
+3.2410x**2 +9.8597x +10.0103 => fitness 106105.578594
+3.0465x**2 +9.6954x +9.8101 => fitness 88890.251456
+2.8739x**2 +9.4368x +9.6793 => fitness 74641.705855
+2.7015x**2 +9.5941x +9.5825 => fitness 63200.318588
+2.5844x**2 +9.2104x +9.8061 => fitness 54660.756666
+2.4810x**2 +9.0261x +9.7408 => fitness 47967.792085
+2.3404x**2 +8.9961x +10.0330 => fitness 40576.074887
+2.2624x**2 +8.5163x +10.0664 => fitness 35284.955930
+2.1116x**2 +8.2324x +9.8651 => fitness 27735.887236
+1.9990x**2 +8.0403x +9.8651 => fitness 22897.851945
+1.8924x**2 +7.8795x +9.3718 => fitness 18698.336986
+1.8230x**2 +7.4593x +9.3094 => fitness 15533.899910
+1.7257x**2 +7.0863x +9.5266 => fitness 12181.292604
+1.6337x**2 +6.7792x +9.2725 => fitness 9404.650013
+1.5357x**2 +6.4629x +9.5507 => fitness 7055.057529
+1.4743x**2 +6.2690x +9.7099 => fitness 5808.451081
+1.4153x**2 +6.1645x +9.3539 => fitness 4846.821217
+1.3823x**2 +5.9590x +9.0421 => fitness 4106.863851
+1.2947x**2 +5.8200x +8.5297 => fitness 3194.109332
+1.2559x**2 +5.5678x +8.6718 => fitness 2625.518072
+1.2517x**2 +5.3079x +8.9320 => fitness 2236.543440
+1.2141x**2 +5.0072x +8.6938 => fitness 1717.835966
+1.1777x**2 +4.6733x +8.5489 => fitness 1278.347739
+1.1856x**2 +4.3618x +8.6059 => fitness 958.426718
+1.1856x**2 +4.2164x +8.6059 => fitness 824.004404
+1.1579x**2 +4.0196x +8.8067 => fitness 662.974696
+1.1579x**2 +3.9124x +8.5719 => fitness 579.015829
+1.1579x**2 +3.7429x +8.5719 => fitness 461.383777
+1.1772x**2 +3.5183x +8.6576 => fitness 323.978627
+1.1850x**2 +3.3072x +8.7442 => fitness 226.008069
+1.1732x**2 +3.2190x +8.7442 => fitness 186.098376
+1.1693x**2 +3.0474x +8.6276 => fitness 124.974195
+1.1810x**2 +2.9051x +8.5125 => fitness 85.491207
+1.1810x**2 +2.7986x +8.3990 => fitness 61.460128
+1.1810x**2 +2.6773x +8.3150 => fitness 41.924824
+1.1810x**2 +2.5346x +8.1487 => fitness 27.380966
+1.1810x**2 +2.4670x +7.8228 => fitness 20.846378
+1.1810x**2 +2.4670x +7.6403 => fitness 18.800957
+1.1810x**2 +2.4423x +7.6912 => fitness 19.157730
+1.1810x**2 +2.4423x +7.4605 => fitness 16.931397
+1.1889x**2 +2.3935x +7.2366 => fitness 14.225202
+1.1889x**2 +2.3935x +6.9472 => fitness 11.693448
+1.1928x**2 +2.4014x +6.6461 => fitness 8.802997
+1.1928x**2 +2.4014x +6.5132 => fitness 8.057922
+1.1928x**2 +2.4094x +6.3395 => fitness 7.212269
+1.1968x**2 +2.4094x +6.1705 => fitness 5.558920
+1.2008x**2 +2.4175x +6.3350 => fitness 5.908466
+1.2008x**2 +2.4094x +6.2717 => fitness 5.583147
+1.2008x**2 +2.4094x +6.3135 => fitness 5.863993
+1.2008x**2 +2.4174x +6.2714 => fitness 5.474609
+1.2008x**2 +2.4174x +6.1042 => fitness 4.526544
+1.2008x**2 +2.4094x +6.0838 => fitness 4.537415
+1.2008x**2 +2.4013x +5.8810 => fitness 3.943327
+1.2008x**2 +2.4013x +5.8026 => fitness 3.770086
+1.2008x**2 +2.4174x +5.7252 => fitness 3.414110
+1.2008x**2 +2.4335x +5.7443 => fitness 3.318331
+1.2048x**2 +2.4416x +5.6103 => fitness 2.205824
+1.2048x**2 +2.4497x +5.4420 => fitness 2.051466
+1.2048x**2 +2.4497x +5.5327 => fitness 2.111853
+1.2048x**2 +2.4579x +5.4589 => fitness 2.112866
+1.2048x**2 +2.4579x +5.4043 => fitness 2.106935
+1.2088x**2 +2.4415x +5.2602 => fitness 1.106067
+1.2088x**2 +2.4415x +5.2251 => fitness 1.098100
+1.2088x**2 +2.4415x +5.1555 => fitness 1.118756
+1.2088x**2 +2.4822x +5.1898 => fitness 1.547053
+1.2128x**2 +2.4574x +5.0687 => fitness 0.537873
+1.2128x**2 +2.4574x +5.0518 => fitness 0.530809
+1.2128x**2 +2.4574x +5.1529 => fitness 0.615559
+1.2128x**2 +2.4574x +5.1014 => fitness 0.559581
+1.2128x**2 +2.4328x +5.0673 => fitness 0.474680
+1.2128x**2 +2.4328x +5.0842 => fitness 0.484359
+1.2169x**2 +2.4328x +5.1859 => fitness 0.781438
+1.2169x**2 +2.4490x +5.1513 => fitness 0.667016
+1.2169x**2 +2.4653x +5.1342 => fitness 0.751231
+1.2169x**2 +2.4653x +4.9801 => fitness 0.380310
+1.2169x**2 +2.4407x +4.8639 => fitness 0.097001
+1.2169x**2 +2.4570x +4.8802 => fitness 0.177852
+1.2169x**2 +2.4570x +4.9615 => fitness 0.262834
+1.2169x**2 +2.4242x +4.8623 => fitness 0.158476
+1.2169x**2 +2.4404x +4.7488 => fitness 0.108388
+1.2169x**2 +2.4241x +4.6538 => fitness 0.280830
+1.2169x**2 +2.4564x +4.6538 => fitness 0.284978
+1.2169x**2 +2.4482x +4.5763 => fitness 0.390655
+1.2209x**2 +2.4482x +4.6373 => fitness 0.027310
The coefficients of the actual function are [1.22, 2.44, 4.66].