search

vsariola / pakettic

TIC-80 cartridge packer
MIT License
19 stars 4 forks source link

To check with original algorithm as described in paper #7

Closed ilmenit closed 1 year ago

ilmenit commented 1 year ago

In this line https://github.com/vsariola/pakettic/blob/c2f0a73187779a90ee265b53e72daf46b74f779f/pakettic/optimize.py#L293 shouldn't N be initialized back to list_length? N = list_length

won't N = history.count(cost_max) make N too small? Or you did it on purpose because cost_max will be repeating and count going then to list_length?

vsariola commented 1 year ago

I think it's correct. N is the number of entries in the array that have the current maximum cost. Later in the paper: "Variables Φmax and N in Fig. 2 are respectively always equal to the maximum value in the fitness array and the number of occurrences of that value in the array."

vsariola commented 1 year ago

Note that this is computed after updating the history list. And if N <= 0 then that means we just updated the last item in the list with the maximum cost. And we thus recompute a) the new maximum cost; b) how many times this new maximum cost appears in the list.

vsariola commented 1 year ago

I'm closing this as I think the code is working as it should. If this is not accurate, let's reopen this issue.

ilmenit commented 1 year ago

After reading it again I think you are correct, sorry for your time wasted :-(

vsariola commented 1 year ago

No worries! It's still nice to hear people find the time to study the code with such detail!