Introduction

The normal procedure of a genetic algorithm is:

1. Generate an initial solution. Say with N candidates or individuals. In GA we will call this a population. One individual consists in our timetabling problem of many TimeInterval's. So a gene is here a TimeInterval.
2. Recombination of the best ones, to 'produce' some children.
3. Mutate some individuals: Change the TimeInterval's of them only slightly (e.g. different start time).
4. Evaluate the changed individuals to 'sort' them and make the next step easier:
5. Select the best and repeat with 2.

See here for one possible implementation in the timetabling area.

Parameter Optimization

In revision 167 (and 168) I tried to find the best parameter combination: Which one will lead us within 2minutes to the smallest evaluation?
I tried this one two different computers only 3 values for each parameter (=> 7^3), but even with that the duration was approx. 5 days!
Every combination I tried 3 times and calculated the Meanvalue and RMS-error of the evaluation. I used a fixed 'new Random(12345)' to better compare the result, but so we don't see how 'stable' the solution was. We should set Random(12345) only for the first try.

Enhancements

Through the book "Evolutionäre Algorithmen" from Karsten Weicker I get the following ideas, which could be useful for the GA of gstpl:

• Parallelize the algorithm through:
  1. global parallelization: put expensive evaluation (or mutation) on several processors.
  2. 'small part' parallelization: take only some genes and possible overlapping, but many individuals
  3. 'big part' parallelization: take some genes, but less indivduals
  4. 'merge' parallelization: take a main individual. put clones on different processors. Make separate evolution. Define a merge operator to merge the best solution of the different processors and prevent segregation.
• Try different parameter-evolutions:
  1. Parameters like mutations rate could be introduced as a variable of each individual, to evolve the parameters too. (Selfadoption) Only global borders for those parameters exist. Other possible parameters could be number of children, #parents, ...
  2. Use the standard deviation (sigma) of gaus, which is used for the mutation and look how many children of the last generation was better through mutation. If more than 20% increase their evaluation then we are far away from the optimum and we should increase sigma.
  3. Optimize starting parameters through testing them and statistically evaluate them: Start with 100 different parameter sets and evaluate the evolution.
• Try a different Recombination:
  1. Merge into a new child with the TimeInterval's, which are the same in both parents, but if they are different choose the TimeInterval's with better evaluation.
  2. Create 30% of the children only with mutation.
  3. Create 2 children from 2 parents: parent A consist of A1 and A2 (parent B the same) then produce: Child A1+B2 and child A2+B1.
• Combine with Local Search technics: tabu search seems to be a clever algorithm. (memetic algorith, SAGA??) Other would be Hill Climbing or Simulated Annealing.
• Increase penalty for collision if many individuals have many collisions or if the meancollision does not decrease or if you want to end the algorithm.
• Mutate start time of TimeInterval through the gaussian distribution.
• Algorithm could concentrate on difficult genes (e.g. where the evaluation is significantly lower then elsewhere. Every single TimeInterval could get its evaluation.
• Iterative solution where user can interact with computer algorithm
• Minimax solution for the problem to generate a good compomise for several weeks where the TimeInterval's must be evaluated
• Instead of sorting for 'selection' we could try a priorityqueue to get the best individual.
• Diploide individuals (two genes, one is recessive one is dominant) to preserve populationdiversity.
• Try GA without recombination or without mutation to better understand them.

Please look here (in German!) for a list of additional improvements of the GA.

Our very next steps are:

• Parameter-Evolution through 1. and manual statistical evaluating them.
• Try GA without recombination or without mutation to better understand them and to understand the Recombination in detail.
• Parallelize through 4.
• Tabu Search

Already done experiments:

• Evaluation of parameter combination.