View Forum Topic

Forums
CS4635
fitness target

Author Message

Author	Message
rmedina0531 Posts: 19	Posted 18:51 Apr 18, 2020 \| I'm having trouble understanding what fitness target is supposed to do. Best guess right now is that it is a value that the model is trying to surpass, but I don't see it being compared to any other fitness values in any generation. Running it with example 1 it returns 16. It adds the first three elements in the list, then removes that third element and only adds value according to the percentage weight that is available in the bag. What does the model do with this value?
rabbott Posts: 1649	Posted 21:14 Apr 18, 2020 \| When running a knapsack problem, you normally don't know what the right answer is. The `fitness_target` is an estimate of an upper bound. If an Individual can achieve that value, it can't be beaten. It's computed whenever a Problem is selected and read into the system. (After it's computed it's copied to `GA_World.fitness_target`.) It's defined as the greedy solution if the items were divisible--just as you described it. In other words, it's as many items (in density order) as will fit given the capacity (weight) constraint plus whatever fraction of the next item can be added within the capacity. Of course, we are not allowed to take fractional parts of items, which is why it's an optimistic estimate. It gets the actual right answer for problems 2 and 4 and overestimates for the others. Last edited by rabbott at 21:26 Apr 18, 2020.

rmedina0531

Posts: 19

Posted 18:51 Apr 18, 2020 |

I'm having trouble understanding what fitness target is supposed to do. Best guess right now is that it is a value that the model is trying to surpass, but I don't see it being compared to any other fitness values in any generation.

Running it with example 1 it returns 16. It adds the first three elements in the list, then removes that third element and only adds value according to the percentage weight that is available in the bag. What does the model do with this value?

rabbott

Posts: 1649

Posted 21:14 Apr 18, 2020 |

When running a knapsack problem, you normally don't know what the right answer is. The fitness_target is an estimate of an upper bound. If an Individual can achieve that value, it can't be beaten.

It's computed whenever a Problem is selected and read into the system. (After it's computed it's copied to GA_World.fitness_target.)

It's defined as the greedy solution if the items were divisible--just as you described it. In other words, it's as many items (in density order) as will fit given the capacity (weight) constraint plus whatever fraction of the next item can be added within the capacity. Of course, we are not allowed to take fractional parts of items, which is why it's an optimistic estimate.

It gets the actual right answer for problems 2 and 4 and overestimates for the others.

Last edited by rabbott at 21:26 Apr 18, 2020.