Selection is not so easy

[Lipsum]

As says the title, selection is not so easy.
I added statistics to show how many machines are halted after a run of the population.
In fact most machines are halted. I think this is because the selection function keep machines who don't run too far.
But with these machines, we loose diversity and the population do not evolve (and new machines created by mutations and crossover seems to be often quickly discarded).
I tried to use an uniform selection method in early_dead function (uniform) but then it is hard to balance between mutation rate (which is close to a creation rate) and the ceil in early dead : the extremal cases are too much deletion -> population size goes to 0 and too much creation -> population size goes to infinity, and my computer blow up.

[emmmile]

I actually thought that was good to have only halted machines in the population (because these are more "safe").. And in fact I wrote a fitness function that highly penalize non halted machines!

I saw that you modified the fitness function.. And I think it's ok to penalize only if the machine has passed the upper bound.
The point is that, as you said, the sigmoid penalizes too much individuals that are low in the ranking (the sigmoid in the tails is practically 1, so the individual dies for sure).

For the uniform selection the right threshold for having on average M individuals in the population, is (N - M) / N, where N is the current population size.
Of course N must be > M, otherwise you don't want to remove any individual. In this case, for every individual you have (N - M) / N probability to remove it, that means (N-M) total removed individuals, that means the populations size shrinks from N to M (because N - (N-M) == M).

But I also think that a uniform function is not that good because all individuals are treated in the same manner. For this reason, at the moment I implemented this:

1. define a certain number of "safe" machines (elitism)
2. if the population exceeds the maximum, remove uniformly as above an average of (N-M) individuals, but only from the "unsafe" individuals.

This seems to keep a certain number of non-halting machines in the population, but for making it work I had to high the importance of the halting machines (multiply the fitness of them by 10), otherwise in the first generations the non-halting machines dominates the other, and the algorithm seems to get stuck.

Anyway I don't know if now is working better than before because I didn't tested that much, what do you think?

[emmmile]

This implementation (elitism + uniform selection on the other machines) seems to work also on the ackley problem..

[Lipsum]

I don't know, we have to run tests.

However, I started to change things (selection, fitness) because when
running the program on machines with 2 symbols and 4 states, one
(halted) machine is the best after (for instance) 10000 generations and
it never change in the following generations.

So I thought that it may be good to crossover early halting machines
(i.e. non BB halting machines) with looping machines who contains
patterns in their transition tables what makes them run longer.
But this is only intuition and I have no rigorous proof of it.

Le Sun, 27 May 2012 16:25:44 -0700,
Emilio Del Tessandoro
reply@reply.github.com
a écrit :

I actually thought that was good to have only halted machines in the
population (because these are more "safe").. And in fact I wrote a
fitness function that highly penalize non halted machines!

I saw that you modified the fitness function.. And I think it's ok to
penalize only if the machine has passed the upper bound. The point is
that, as you said, the sigmoid penalizes too much individuals that
are low in the ranking (the sigmoid in the tails is practically 1, so
the individual dies for sure).

For the uniform selection the right threshold for having on average M
individuals in the population, is (N - M) / N, where N is the current
population size. Of course N must be > M, otherwise you don't want to
remove any individual. In this case, for every individual you have (N

• M) / N probability to remove it, that means (N-M) total removed
  individuals, that means the populations size shrinks from N to M
  (because N - (N-M) == M).

But I also think that a uniform function is not that good because all
individuals are treated in the same manner. For this reason, at the
moment I implemented this: 1) define a certain number of "safe"
machines (elitism) 2) if the population exceeds the maximum, remove
uniformly as above an average of (N-M) individuals, but only from the
"unsafe" individuals.

This seems to keep a certain number of non-halting machines in the
population, but for making it work I had to high the importance of
the halting machines (multiply the fitness of them by 10), otherwise
in the first generations the non-halting machines dominates the
other, and the algorithm seems to get stuck.

Anyway I don't know if now is working better than before because I
didn't tested that much, what do you think?

---

Reply to this email directly or view it on GitHub:
#7 (comment)

[emmmile]

That's why I increased the fitness value for the halting machines, because in the early stages they didn't survive (non halting can have fitness = 1)..
Multiplying by 10 the fitness of a halting machine can help to let her survive, since it will have a fitness around 1 too also if maybe the number of shifts is very low.

EDIT: you wrote (halted) machine, so maybe I didn't understood the point..