automated timetable using php and genetic algorithms
Moderator: General Moderators
automated timetable using php and genetic algorithms
This is a final year project, I have tried to understand the concept of ga and hard constraint and the soft constraint required in a normal ga application, But u don't know how to go about it to create a timetable application in php. Please help me
Re: automated timetable using php and genetic algorithms
In a nutshell (the kind of reply you should, in all honesty, be expecting from random people on the internet):
GA is about taking some input, modifying it in a somewhat random way, doing that a number of times, and then deciding which of those outputs (one or more) you use to repeat the process. Keep going until you like what you have.
A hard constraint is something you have to observe (eg, no scheduling conflicts) while a soft constraint is something you want to observe but are willing to be flexible on (eg, minimizing time wasted between appointments).
1. Find a way to express the specification for the timetable in a simple manner. Serialization, in a sense. The typical example is a single string but you don't have to do it that way.
2. Then come up with a way to rate the fitness of a timetable. Example rule: a schedule that creates conflicts should never be "more fit" than one that does not create conflicts.
3. Then you need a mutator. It takes the specification and makes random changes to it. Maybe it picks a different appointment time. Maybe it takes more than one input and mixes their parts together to get hybrids. Maybe it freaks out and completely rewrites parts. Maybe all of those. Keep in mind that the output should remain close to the input - can't just redo the whole thing, otherwise you're merely making random guesses.
Start with an input, however bad it may be. Mutate it. Repeatedly. Then rate the fitness of all the outputs to decide which ones are best and repeat the process with those. Keep going until you find a good timetable... or you want to give up.
Fun fact: if I remember my math correctly, a student picking 5 out of 20 possible courses, each at 4 different locations and times, is 15.8M distinct combinations. At 1ms to evaluate each combination via brute force, though I doubt any PHP code would actually be that slow, that's a worst case (ie, no suitable timetables) of more than 4 hours running.
GA is about taking some input, modifying it in a somewhat random way, doing that a number of times, and then deciding which of those outputs (one or more) you use to repeat the process. Keep going until you like what you have.
A hard constraint is something you have to observe (eg, no scheduling conflicts) while a soft constraint is something you want to observe but are willing to be flexible on (eg, minimizing time wasted between appointments).
1. Find a way to express the specification for the timetable in a simple manner. Serialization, in a sense. The typical example is a single string but you don't have to do it that way.
2. Then come up with a way to rate the fitness of a timetable. Example rule: a schedule that creates conflicts should never be "more fit" than one that does not create conflicts.
3. Then you need a mutator. It takes the specification and makes random changes to it. Maybe it picks a different appointment time. Maybe it takes more than one input and mixes their parts together to get hybrids. Maybe it freaks out and completely rewrites parts. Maybe all of those. Keep in mind that the output should remain close to the input - can't just redo the whole thing, otherwise you're merely making random guesses.
Start with an input, however bad it may be. Mutate it. Repeatedly. Then rate the fitness of all the outputs to decide which ones are best and repeat the process with those. Keep going until you find a good timetable... or you want to give up.
Fun fact: if I remember my math correctly, a student picking 5 out of 20 possible courses, each at 4 different locations and times, is 15.8M distinct combinations. At 1ms to evaluate each combination via brute force, though I doubt any PHP code would actually be that slow, that's a worst case (ie, no suitable timetables) of more than 4 hours running.
Re: automated timetable using php and genetic algorithms
Thanks so much for the reply. But can you pls give some sample codes in php to buttress you explanation.
Re: automated timetable using php and genetic algorithms
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).
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.
Step 3: mutator. I'll vary each coefficient by +/- 10%.
Starting with an input,
mutate it repeatedly,
rate fitness, and choose the best ones.
I then average the original and the two best selections to get my new selection, and rate it.
Keep going until I'm satisfied.
The coefficients of the actual function are [1.22, 2.44, 4.66].
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.06Code: Select all
2x**2 + 3x + 4 => [2, 3, 4]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;
}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;
}Code: Select all
$coeff = array(10, 10, 10); // 10x**2 + 10x + 10
do {Code: Select all
$coeffs = array();
for ($i = 0; $i < 20; $i++) {
$coeffs[] = mutator($coeff);
}Code: Select all
usort($coeffs, function($a, $b) {
return fitness($a) - fitness($b);
});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);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.027310Re: automated timetable using php and genetic algorithms
Thanks for your prompt response. I really appreciate. I will go through it and get back to you asap.
Re: automated timetable using php and genetic algorithms
Hey did you finish the project. i am working in the same project for my final year project i could use some help