FitnessProp should warn on minimization problems

[SigmaX]

Our shiny new ops.proportional_selection() operator is great, but could easily lead to bugs when applied to minimization problems. I tossed this operator into a script to minimize a spheroid, and it cheerfully maximized it for me!

We should consider adding a check to see if the problem has a maximize attribute (hasattr(maximize)), and issue a warning to the logger if maximize=False.

[thomashopkins32]

Should we somehow try to support minimization?

I can think of reflecting the values over the zero-point and then lowering the zero point.

For example (with offset=0 and maximize=False):

population_fitness = [-100, 3, 1000]
reflected_fitness = [100, -3, -1000]
new_fitness = reflected_fitness + 1000 (for each element)
new_fitness = [1100, 997, 0]

[SigmaX]

My feeling is that logic for converting a minimization problem to a maximization problem belongs in the Problem, not in the operator. So we can leave that to the user to worry about.

There are several ways to turn a minimization problem into a maximization problem (ex. taking the negative, or taking the reciprocal). At some point we could provide a fitness function wrapper to apply these strategies (in the spirit of problem.AverageFitnessProblem and real_rep.problems.TranslatedProblem).

@piprrr , any opinions?

[markcoletti]

The literature covers this case. John Grefenstette in the Handbook of Evolutionary Computation says in C2.2:2:

... one fitness function that might be used when the goal is to minimize the objective function is:

𝜱(ai) = fmax - f(ai(t))

where fmax is the maximum value of the objective function. If the global maximum value of the objective function is unknown, an alternative is:

𝜱(ai) = fmax(t) - f(ai(t))

Where fmax(t) is the maximum observed value of the objective function up to time t.

Since we will almost never know the global maximum, we're going to have to go with the second approach and do some bookkeeping to remember the current running maximum observed fitness. I suggest using a function closure to keep a running maximum as selection happens. Also, when doing selection, you can determine if you're minimizing by looking at the boolean individual.problem.maximize.

(As an aside, Siggy, there's apparently a TeX Chrome extension for adding TeX math to gmail. Spiffy!)

Sorry for slow responses today. I'm in meetings and am chasing a poster deadline for today.

On Thu, Jun 17, 2021 at 9:45 AM SigmaX @.***> wrote:

My feeling is that logic for converting a minimization problem to a maximization problem belongs in the Problem, not in the operator. So we can leave that to the user to worry about.

There are several ways to turn a minimization problem into a maximization problem (ex. taking the negative, or taking the reciprocal). At some point we could provide a fitness function wrapper to apply these strategies (in the spirit of problem.AverageFitnessProblem and real_rep.problems.TranslatedProblem).

@piprrr https://github.com/piprrr , any opinions?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/AureumChaos/LEAP/issues/146#issuecomment-863252690, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABZHWSGZTUOZAJQAEHKFC6LTTH4AFANCNFSM462U3F6Q .

-- @.***

[thomashopkins32]

To add on to this, I realize that if the population all has 0 fitness we'll have a divide by zero error on the line:

proportions = values / population_total

This converts the values to an array of nan and issues a warning. Selection still works after this though.

This could be fixed by offset=1 and changing the behavior of offset='pop-min' to shift the lowest value to 1 instead of 0. Then raise an error for any non-positive fitness.

This case would be pretty rare but should it select individuals uniformly random then?

[markcoletti]

That scenario may be indicative of some problems on the practitioner's behalf. ;) But, I can see gracefully reverting to uniform selection may be the least astonishing thing to happen, especially given that it's known in the EC community that that's sorta the normal end-of-run behavior for fitness proportional selection. I.e., the "lack of killer instinct" mentioned in texts.

BTW, in case you didn't know about The Principle of Least Astonishment: https://en.wikipedia.org/wiki/Principle_of_least_astonishment. On occasion we wrestle with that very thing with LEAP's design!

On Fri, Jun 18, 2021 at 9:47 AM Thomas Hopkins @.***> wrote:

To add on to this, I realize that if the population all has 0 fitness we'll have a divide by zero error on the line:

proportions = values / population_total

This could be fixed by offset=1 and changing the behavior of offset='pop-min' to shift the lowest value to 1 instead of 0. Then raise an error for any non-positive fitness.

This case would be pretty rare but should it select individuals uniformly random then?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/AureumChaos/LEAP/issues/146#issuecomment-864052035, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABZHWSCVO3R7BNY4OGQLP5DTTNFAXANCNFSM462U3F6Q .

-- @.***

[thomashopkins32]

Running this bit of code runs into the divide by zero error mentioned above:

prop_file = open('./proportional_stats.csv', 'w')
prop_stats_probe = probe.FitnessStatsCSVProbe(stream=prop_file, context=context)
for i in tqdm(range(100)):
    ea = generational_ea(max_generations=MAX_GEN, pop_size=POP_SIZE,
                         problem=StepProblem(maximize=True),
                         representation=Representation(
                             individual_cls=Individual,
                             initialize=create_real_vector(bounds=[[-5.12, 5.12]]*2)
                         ),
                         pipeline=[
                             ops.proportional_selection(offset='pop-min'),
                             ops.clone,
                             ops.uniform_crossover,
                             mutate_gaussian(std=0.5, expected_num_mutations='isotropic'),
                             ops.evaluate,
                             ops.pool(size=POP_SIZE),
                             prop_stats_probe
                         ])
    list(ea);
prop_file.close()

It issues this warning:

LEAP/leap_ec/ops.py:558: RuntimeWarning: invalid value encountered in true_divide
  proportions = values / population_total