Examples of problem solving by GP

topics :  GP examples from Koza's book ch. 7

Artificial Ant, Symbolic regression, 11-Mux.  and ch. 8  Effort

Artificial Ant shows how to cope with problem scale up.  The Los Altos trail is much bigger than Santa Fe trail.  The parameters that have to be adjusted are , the max. no. of operations (time for execution) from 400 to 3000, population size from 300 to 2000.  Notable is the convergence curve that shows the worst of generation to diverge.

Symbolic regression shows that the solution discovered by GP is unlikely to be of "good-form", i.e. there are several "surplus" in the solution such as ' cos ( x - x ) ' which is equivalent to ' 1' .  However this can be minimize using parsimoneous (penalize for large size in fitness function).  It also shows how to find fitness cases, in this case the random pair of (x,y).  The 'curve fitting' ability is very useful especially that GP can discovered the "form" of the equation which traditionaly must be provided as a priori.  Although the function set must be select a priori but the choice can rather arbitrarily (with in reason).  GP will choose the function in the solution which is best suite for the problem (for example, it does not use sin, exp, rlog).

11-Mux shows how GP solve a search in large space (the 11-mux possible solutions are huge as it is one of the possible truth table of the size 2^11, that is it is 2^2^11).  The function set includes 'if' which is a mux.  GP exploits the hierarchical structure of the solution (building a large mux from smaller mux).  This problem is a "good" case of simple structure.  It is interesting to see if GP can find Adder given a complete set of gates eg. {AND, OR, NOT} or { XOR, NOT} etc.  and whether some property can be included such as searching for the faster Adder (Von Neuman)  or the cheapest (in terms of gates) Adder (which should give us ripple carry adder).

Effort curve gives the "best possible" figure, i.e. the min. value of the number of individual to be processed.  (the lower bound)   The other alternative can be using the centroid of the area under I(m,n,z) curve which should give "average" figure.

Some comment on the students result on the timetabling assignment

Tepakorn Sirivan 41652132 , does not obtain the good solution when incorporating soft constrain.  His parameters :  pop 10,000, gmax 1,000, cross 0.85, mutate 0.2.   This is rather strange as the population size is large enough to converge.  And also using only hard constraint is successful (however from his report, I suspect that the successful run is by chance).  There are several things need to be clarify.  I suspect the size of tournament selection, the coding scheme.  He used a realistic schedule which is rather complicated.

Songpol Chitanes 41652140, uses simple scheme of encoding, tuple of (subject, room, time) and works well.  His parameters :  pop 100, gmax 3000, cross 700, mutate 1.  This is a small population.  The convergence is also fast, it reaches a steady state around generation 500.  It uses simple GA.

Chakorn Chanta-u-rai 41652082, reports several interesting experiments.
1) small population size is better than large.  ranking best size 100, 50, 500, 1000
this is also a surprise.
2) at pop 100, the convergence of cross 0.5 is similar to 0.2 is better than 0.8
3) at pop 100, cross 0.5, the convergence of mutate 0.01 is significantly better than 0.05 and 0.1

Vutichai Piyapanwong 41652306, using very small pop 20, gmax 10, cross 0.4.  The solution converges (but didn't reach min).  His finding is that his population lost diversity very quickly (in g 20).  I suspect that because he used "repair" very heavily on every individual.  It depends on how his "repair" really work.  Also pop size is too small to maintain diversity.

Tuan Rasa 41652124, uses pop 20, gmax 100, with MATHLAB and GA module he can produce the result easily (but slowly, upto half an hour).

Ekapol Jeeransuwan 41652462, reports several experiments which show the large population is better than small population.  pop 1000, gmax 1000.  the convergence ranking of pop size 1000, 500, 200, 50.

Duangpen Jetpipatpong 41652108, small pop 20 and 40 , similar set up with Tuan, reports good result, gmax 400.

Tanatep Pansuwankit 41652165, using coding in binary (room, time, day).  His parameters : pop 100, gmax 40, cross 0.6, mutate 0.033.  The solution does not converge.  I suspect some problem in programming error.

Aswit Pungsema 4165244, use PGApack report good result, varying crossover rate indicates that  too much leads to divergence (1.0),  0.1 and 0.5 leads to local min, 0.3 is best.  I can understand why 1.0 is not good as the good solution is not preserved but for other value the result is not explainable except some value give good result (0.3).
His parameters : pop 100, gmax 500.  He observed that the best schedule resulted in using one room for all classes of the same year (rather intuitive, which is good).  He also used PGApack, the most difficult part is to write fitness function.
(aswit.htm, timetable.c)

General comments

There are contradicted finding such as the population size is small or large better?  A number of report say small is good.  There is more report supporting small than supporting large.  Why some experiment does not converge?   To know the answer the implemented code must be carefully inspected.  Many students did not check the solution whether it is really a correct one.  Observing fitness value can only indicate the 'trend' of the solution (how fast it converge) but fitness value is the 'estimate' of the goodness of the solution it does not say if the solution is correct.  As GA is probabilistic in nature, running the experiment only once doesn't give any meaningful result.  To have a reliable result, the conclusion must be made based on statistics.  Running the experiment a large number of time is necessary (law of large number).

Moral of the story :  It is not easy to understand the result from evolutionary experiment.  (it is also not easy to know if the code is correctly implemented!)