Minimum score goes up rather than down sometimes

[gwd]

I'm trying to use your library, but I'm getting some really strange results sometimes. For certain models, the population seems to be getting worse (fitness function going up) as time goes on rather than better.

Here's one configuration I used:

        ga = gago.GA {
            NewGenome: ScheduleFactory,
            NPops:     2,
            PopSize:   200,
            Model: gago.ModMutationOnly {
                NChosen: 50,
                Selector: gago.SelElitism { },
                Strict: true,
            },
        }

And here is some sample output from the log:

schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-42968.000000 max=-30081.000000 avg=-37780.345000 std=2289.283752
schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-43257.000000 max=-30794.000000 avg=-38022.870000 std=2217.460431
schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-40642.000000 max=-30794.000000 avg=-37369.045000 std=1836.562951
schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-42115.000000 max=-30081.000000 avg=-37158.315000 std=1909.202324
schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-40086.000000 max=-29913.000000 avg=-36747.050000 std=1707.612365
schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-41925.000000 max=-30081.000000 avg=-36540.960000 std=1655.269854
schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-39933.000000 max=-29913.000000 avg=-36240.105000 std=1729.159343
schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-38890.000000 max=-30081.000000 avg=-36017.890000 std=1539.559852
schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-38513.000000 max=-29207.000000 avg=-35519.680000 std=1576.155255
schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-39357.000000 max=-29246.000000 avg=-35797.325000 std=1668.239338
schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-37953.000000 max=-28815.000000 avg=-34964.755000 std=1669.453927
schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-37595.000000 max=-29246.000000 avg=-35396.215000 std=1585.120926
schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-37417.000000 max=-28293.000000 avg=-34983.050000 std=1591.166527
schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-37705.000000 max=-27978.000000 avg=-34526.410000 std=1685.592140
schedule.go 2018/06/01 10:26:09 pop_id=IJN min=-37663.000000 max=-27978.000000 avg=-34086.300000 std=1585.385521
schedule.go 2018/06/01 10:26:09 pop_id=UIe min=-37050.000000 max=-28293.000000 avg=-34562.515000 std=1506.342066
schedule.go 2018/06/01 10:26:10 pop_id=UIe min=-36376.000000 max=-28293.000000 avg=-34127.960000 std=1417.550041
schedule.go 2018/06/01 10:26:10 pop_id=IJN min=-36434.000000 max=-27978.000000 avg=-33659.550000 std=1565.961796
schedule.go 2018/06/01 10:26:10 pop_id=UIe min=-35553.000000 max=-27834.000000 avg=-33776.890000 std=1439.687274
schedule.go 2018/06/01 10:26:10 pop_id=IJN min=-35779.000000 max=-27978.000000 avg=-33276.435000 std=1571.765547

[snip]

schedule.go 2018/06/01 10:26:37 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13105.810000 std=569.072591
schedule.go 2018/06/01 10:26:37 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13208.310000 std=622.588318
schedule.go 2018/06/01 10:26:37 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13090.395000 std=564.413234
schedule.go 2018/06/01 10:26:37 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13067.800000 std=570.242484
schedule.go 2018/06/01 10:26:37 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13205.330000 std=620.816141
schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13187.325000 std=620.124810
schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13044.520000 std=574.277441
schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13041.195000 std=569.691186
schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13176.480000 std=618.033826
schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13031.840000 std=566.920034
schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13164.640000 std=617.818768
schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13132.580000 std=628.239830
schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-13024.580000 std=564.373736
schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-12997.095000 std=570.329112
schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13126.275000 std=624.070653
schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-12983.905000 std=583.783818
schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13120.270000 std=623.693280
schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-12973.925000 std=579.498947
schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13110.700000 std=627.804500
schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-12954.475000 std=586.226440
schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14797.000000 max=-9746.000000 avg=-13108.250000 std=626.450770
schedule.go 2018/06/01 10:26:38 pop_id=UIe min=-14752.000000 max=-9746.000000 avg=-13091.415000 std=630.471350
schedule.go 2018/06/01 10:26:38 pop_id=IJN min=-14602.000000 max=-10808.000000 avg=-12931.535000 std=578.849565

As you can see, the minimum fitness (with random starting points) started around -42k, and ended around -14k 30 seconds later. Regardless of how I implement the Genome interface, I don't see how this should be possible.

[MaxHalford]

Hey,

The minimum fitness you're seeing is not the best obtained fitness. It's the minimum fitness inside the population. The HallOfFame property will give you the best obtained solutions, along with their

However, it is a bit weird that the populations fitness is going up. If you can share the code I can look into why this is happening. To be totally honest I haven't battle-tested gago.ModMutationOnly so it might have a bug.

[gwd]

Thanks for the quick response!

Yes, I understand that HallOfFame is where to look for the "best seen so far"; but what I'm finding is that the "best seen so far" in this case is always one of the initial, randomly-chosen populations: further evolution with ModMutationOnly never results in any better results. And when I looked into it, the reason was pretty obvious -- the actual population keeps getting worse instead of better! :-)

I don't see this effect with ModGenerational or ModDownToSize, but for some reason the results are still not very good -- I wrote an alternate search function that literally just generates random solutions, and it usually outperforms the genetic search, which is why I started exploring other options, and noticed this effect. (I think one of the other ones I tried had a similar effect -- maybe ModSteadyState.)

Regarding code, it's hard to share less than the whole thing in this case. I made a branch that reproduces this problem. The main repo is http://github.com/gwd/session-scheduler , and the branch name is out/ModMutationOnly-repro/v1. Once you've built it, run the following commands:

mkdir data
./session-scheduler -count=-500 testpopulate
./session-scheduler testinterest

That will generate a bunch of random users, a bunch of random discussion sessions, and set the "interest" of users in attending various sessions between 0 and 100. At that point, we just need to generate a schedule that maximizes happiness, as calculated by the sum of 'interest' when a user is able to attend the sessions they want to.

To run the genetic algorithm scheduler, just run:

./session-scheduler schedule

This will run the search for 30s, and compare the results to to a "heuristic" scheduler (greedy first-fit), and choose the best one. If you want more data about what's going on, add the -sched-debug flag (before the schedule command). (You probably want to pipe to a file in that case.) You can try various things I've tried: -searchalgo=random will use the completely random method I mentioned above; -crossover=false will cause the crossover function to return without doing anything, and so on. All the actual scheduling happens in schedule.go.

I realize this is a lot, so if you don't have time to dig into this, don't worry; my 'random' scheduler will do well enough for the time being. I mainly just wanted to let you know there might be a bug (and/or see if I'm doing something obviously wrong, like using arbitrarily large negative scores).

[MaxHalford]

Okay cheers for linking the code. I'm a bit busy at the moment but I should be able to free some time over the weekend. Hang tight!

[MaxHalford]

Hey,

I went through the code and noticed that the mutants would replace the initial individual if the fitness was higher, which is not the intended behaviour. I've corrected this and pushed the fix to GitHub.

Can you try it again and tell me if it works?

[gwd]

That seemed to do the trick. Thanks!

[MaxHalford]

Awesome! Closing this. Tell me if you have any other questions!