[Math] Specific fitness function for genetic algorithm

algorithmsfunctions

I have a program that assign students to different courses using a genetic algorithm.
To get the best assignation I have a fitness function that evaluates the distribution of the students and their priority.

The ideal scenario is where all students get assigned with the best priority (option), but usually some students don't get a place or get a lower priority. In numbers this would look like this:

Total students: 307
Not assigned: 7

Assigned students: 300
Assigned to first option: 143
Assigned to second option: 121
Assigned to third option: 36

For fitness I concatenate the numbers so the bigger the better, like this:

300,143,121,036 (a big integer formed with the previous values)

Being the best possible

307,307,000,000 (all assigned to the first option)

So different assigns give you different integers that I can sort and keep the best. As you can see I'm not calculating anything, just ordering.

There are some options that I find more suitable than other that are better (but only because they are bigger numbers). Because the genetic algorithm evolves giving some evolutionary jumps, I get finesses like this:

nth generation:   200,120,060,020 
nth+1 generation: 201,121,020,060

The second has a bigger score (it's a bigger number), but I prefer the first one, because a small change in the first option it's not worth if the second option looses so many students. So, for the second number I would need some kind of transformation so it gives a number smaller that the first one as a result.

The question: is there a formula that given the values above (total assigned, first option, second, etc.) would give me a more cushioned value for the fitness? The number can be anything but it has to be bigger for better assignments, my function is too lineal to work (I do a ln of the value for ease of use later).

I hope I was clear, I can clarify.

Thanks,
R.

Best Answer

The problem is with your fitness function. The fitness function is supposed to assign higher values to qualities you want (so the configurations you don't like receives a lower score).

Perhaps a more suitable function is:

  • +1 point for student getting his first choice
  • 0 points for student getting his second choice
  • -2 points for student getting his third choice

That way, a configuration like (120,20,60) gets penalized heavily.

Related Question