Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 0 down vote accepted

A fitness function that looks like

A * (Assigned first) + B * (Assigned second) + C * (Assigned third) + D * (Not assigned) + E

for some suitable values of A, B, C, D, E may provide a more intuitive ranking of the final results (in fact E is unnecessary, but I've included it to make a comparison with your current fitness function). Your current fitness function is of this form, with:

  • A = 1,000,000
  • B = 1,000
  • C = 1
  • D = -1,000,000,000
  • E = 307,000,000,000

So you see that at present, you are very strongly penalizing schemes where any students aren't assigned a course (because D is large and negative), and privileging schemes which manage to assign students to their first choice (because A is large and positive).

If you chose different values for A, B, C, D (eg the other answer suggests A = 1, B = 0, C = -2, D = 0) you may get more sensible results. I suspect that you may always want to choose A > B > C > D, with D significantly lower than all of the other three.

share|improve this 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.