Full support for elitism

[beniz]

'elitism' reinjects selected candidates into the population in order to foster the search toward those candidates (e.g. best visited candidate so far). This is a follow up to #77.

In other discussions, it was proposed that at least three strategies of 'elitism' be pursued (see #77 and #102):

• [x] elitist: always (re-)inject the best-ever seen solution
• [x] initial elitism: (re-)inject X0 as long as it has not been improved upon
• [x] initial elitism on restart: as above, but not for the first run, using the best-ever seen solution from previous run (already implemented by #77)

Following #77, a solution is (re-)injected until the population median exceeds its fitness. If some alternative strategies (e.g. always (re)inject) are of interest, they could be studied here as well.

[nikohansen]

A natural alternative for initial elitism: inject X0 iff X0 is better than the best solution in the current iteration, independently of history. It seems to well reflect the underlying goal.

[beniz]

@nikohansen are there any testbed functions that you especially recommend to assess elitism strategies ? I had collected at least one from a ticket a few months ago. Thanks.

[nikohansen]

I have no specific testbed in mind. It is however possible to construct an example where this should perform exceptionally well compared to the default: e.g. on the 20-D Rastrigin function with x0 = 0.1, sigma0 = 2.

[beniz]

This is now available for testing on branch 'elitism_103', with a slight difference to the 'initial elitism on restart', which applies only if the best seen candidate is not within the three final search steps' candidates.

It can be used with option -elitist to test_functions, with 0 for no elitism, 1 for best seen reinjection, 2 for initial elitism and 3 for initial elitism on restart.

Early results are mitigated. The one current oddity I am looking into are cases in which elitist (-elitist 1) does yield a poorer result than no elitism. To reproduce one of these:

./test_functions -fname rastrigin -ftarget 1e-8 -dim 20 -sigma0 2 -x0 0.1 -seed 34612 -initial_fvalue

which returns f-value=26.8638743902426 and

./test_functions -fname rastrigin -ftarget 1e-8 -dim 20 -sigma0 2 -x0 0.1 -seed 34612 -initial_fvalue -elitist 1

which yields f-value=45.7679701194505.

Once I've ruled out or fixed a potential bug, results on a larger base, such as multi-modal functions from BBOB would be on the menu.

[nikohansen]

Just checked again with cma.py, the first result is what I see as well. With initial elitism (second case) I reach the target value with high probability in a single trial within about 3000 evaluations.

[beniz]

Just checked again with cma.py, the first result is what I see as well.

So on my side, it was a bug, at least in the case above. There's an option to compute the initial objective function value, that is otherwise unneeded. When this option is on, elitism should not be worst than initial elitism, while when it is off, it may happen. I've fixed this, though a final improvement could be to compute the initial objective function value whenever elitism is activated.

With initial elitism (second case) I reach the target value with high probability in a single trial within about 3000 evaluations.

Yes, observing the same behavior. Note that I am still using the median to trigger reinjection, so it should be a little more 'pushy' than what you suggest in https://github.com/beniz/libcmaes/issues/103#issuecomment-71215473.

[beniz]

Added computation of initial objective function value whenever elitism is activated, thus avoiding the pitfall mentioned earlier.

I believe this is ready for integration into the main dev branch.

[beniz]

Merged into 'dev' branch, closing for now.