GA (genetic algorithm) moves away from better values

I am running a ga-optimization and I often get results like this one:

                                Best           Mean      Stall
Generation      f-count        f(x)           f(x)    Generations
    1           932     -9.372e+005      1.231e+010        0
    2          1398     -1.514e+005      7.911e+009        1
    3          1864      7.705e+004     -3.975e+017        2
    4          2330     -2.988e+004     -1.812e+015        0
    5          2796     -2.988e+004     -1.135e+007        1
    6          3262     -2.988e+004     -9.866e+007        2
    7          3728          -563.1     -3.495e+007        3
    8          4194          -563.1     -8.067e+006        4
    9          4660          -563.1     -2.998e+007        5
   10          5126          -563.1     -7.216e+006        6
   11          5592          -563.1     -7.953e+006        7
   12          6058          -288.2     -3.525e+006        8
   13          6524           51.32     -3.823e+005        9
   14          6990          -40.55     -1.176e+005        0
   15          7456           19.38        2.5e+004        1
   16          7922           14.31            9165        0
   17          8388           14.31            8330        1
   18          8854           6.788            6995        0
   19          9320           6.788            8568        1
   20          9786           5.907            8970        0
   21         10252           1.453      1.218e+004        0

i wonder how (with an elite count set to 40 out of a population of 466) the algorithm moves to worse values first. How can this be improved? Thanks a lot for your answers!

[Sean de Wolski]

highly non-linear behavior? What does your fitness function look like?

[Hans]

You can see the function below. I just do not get why it doesnt at least keep the good individuals. I just thought I kind of use a "shotgun" and throw a larger number of individuals at it so i dont get lost in minor "valleys". Can you recommend any change in the settings or so?

function ll=bbva(param)

given=[0.9018585500777736 0.0054652585568056855 0.006730395774728828 -0.08559786078631593];

L=0.45;

theta=given(1);

mu=given(2);

sigma=given(3);

p=param(1);

q=param(2);

v=param(3);

s=param(4);

l=param(5);

m=param(6);

sigmacc=param(7);

a1=param(8);

b1=param(9);

lambdar=given(4);

lambdac=param(10);

lambdab=param(11);

Data = xlsread('bbva-spain');

r=Data(:,3);

k=Data(:,1);

f=Data(:,2);

%col=Data(:,4);

%cou=Data(:,5);

Brc=zeros(length(k),1);

Arc=zeros(length(k),1);

Brb=zeros(length(f),1);

Arb=zeros(length(f),1);

Bc=zeros(length(k),1);

Ac=zeros(length(k),1);

Bb=zeros(length(f),1);

Ab=zeros(length(f),1);

hcdach=zeros(length(k),1);

hbdach=zeros(length(f),1);

singleliker=zeros(length(k),1);

singleliker(1)=0;

singlelikec=zeros(length(k),1);

singlelikec(1)=0;

singlelikeb=zeros(length(k),1);

singlelikeb(1)=0;

singlelike=zeros(length(k),1);

singlelike(1)=0;

for i=1:length(k);

Brc(i)=(1/theta)*(1-exp(-theta*k(i)));

Arc(i)=exp((mu-sigma^2/2*theta^2)*(Brc(i)-k(i))-sigma^2*Brc(i)^2/4*theta);

Brb(i)=(1/theta)*(1-exp(-theta*f(i)));

Arb(i)=exp((mu-sigma^2/2*theta^2)*(Brb(i)-f(i))-sigma^2*Brb(i)^2/4*theta);

Bc(i)=(1/p)*(1-exp(-p*k(i)));

Ac(i)=exp((q-v^2/(2*p^2))*(Bc(i)-k(i))-(v^2*Bc(i)^2)/(4*p));

Bb(i)=(1/s)*(1-exp(-s*f(i)));

Ab(i)=exp((l-m^2/(2*s^2))*(Bb(i)-f(i))-(m^2*Bb(i)^2)/(4*s));

hcdach(i)=1/(L*Bc(i))*(log(Ac(i))-log(Data(i,4))+log(Arc(i))+(1+L*a1)*Brc(i)*r(i));

hbdach(i)=1/(L*Bb(i))*(log(Ab(i))-log(Data(i,5))+log(Arb(i))+(1+L*b1)*Brb(i)*r(i));

end

Vr=(sigma^2)/(2*theta)*(1-exp(-2*theta));

Vc=(v^2)/(2*p)*(1-exp(-2*p));

Vb=(m^2)/(2*s)*(1-exp(-2*s));

Varcou=Vb-(v*m*sigmacc)^2/Vc;

for i=2:length(k);

singleliker(i)=-1/(2*log(Vr))-(1/(2*Vr))*(r(i)-mu-(lambdar*sigma)/theta-(r(i-1)-mu-(lambdar*sigma)/theta)*exp(-theta))^2;

singlelikec(i)=-1/(2*log(Vc))-(1/(2*Vr))*(hcdach(i)-q-(lambdac*v)/p-((hcdach(i-1)-q-(lambdac*v)/p))*exp(-p))^2;

singlelikeb(i)=-1/(2*log(Varcou))-(1/(2*Varcou))*(hbdach(i)-l-(lambdab*m/s)-(hbdach(i-1)-l-(lambdab*m)/s)*exp(-s)-(sigmacc*v*m)/Vb*(hcdach(i)-q-(lambdac*v/p)-(hcdach(i-1)-q-(lambdac*v)/p)*exp(-p)))^2;

singlelike(i)=singleliker(i)+singlelikec(i)+singlelikeb(i);

end

ll=-(sum(singlelike)+(3/2)*(length(k)-1)*(2*pi));

end

[Hans]

Could it be due to complex results (there are some logarithms in the function to be minimized)? Let's say MATLAB displays some result a, then there's actually a result a+ib with a lower absolute value or lower [minus absolue value] than one of the older results. Could that be it?

[Hans]

I am trying again now with constraints preventing complex results. However, the algorithm is still moving away(only two generations so far becasue it needs 26500 function evaluations per generation) but still..

Answer 1

[Richard Crozier]

But only the mean gets worse, the best improves with every generation, and this is all that matters surely?

Random combinations with nonlinear responses can easily throw up huge values which distort the mean, while not affecting the overall progress of the search.

For example, imagine the following with a population of 7:

Gen 1 scores: 100, 100, 150, 140, 111, 100, 119

best score: 100

mean score: 117.14

Gen2 scores: 87, 66, 167, 1000000000000, 55, 98, 206

best score: 55

mean score: 1.4286 x 10^11

The really bad individual would have a very low chance of passing its genes to the next generation so it's ok.

[Hans]

Thank you for your reply but I do NOT see overall progress in the search. The "best f(x)" gets worse.

If you look at the best results which (and you're right about that) is all that matters, you will see that for example in generation in 4 there is a worse "best f(x)" value than in generation 1. In fact, in the above example, the first generation has the best individual of all generations. The best f(x) also gets better later but does not get as good as in the beginning.

[Richard Crozier]

I've obviously misunderstood, I've assumed you are trying to get as close to zero as possible (rather than minimizing) so that -9.372e+005 is not as good as -2.988e+004, being 40 time smaller in magnitude. Are you sure you have not somehow told the GA to do this? This is what seems to be happening, it looks to me to be converging on zero.

[Hans]

I don't think so, I used normal settings, no constraints. Could it be due to complex results (there are some logarithms in the function to be minimized)? Let's say MATLAB displays some result a, then there's actually a result a+ib with a lower absolute value or lower [minus absolue value] than one of the older results. Could that be it? I'm trying again now with constraints that prevent that.

[Hans]

I did as I said, now the algorithm is running (has been running for 8 hours) and I'm getting the following result:

Best max Stall

Generation f-count f(x) constraint Generations

1 26500 -0.00245613 0 0

2 52500 -0.00055561 0 0

So: Still the algorithm moves away from the better (the first generation) value..

[Richard Crozier]

It still looks like it's moving towards zero? Another way to test your theory would be to modiy your function to return a poor score for complex results (e.g. 10000 * real(ll) if ll is complex or something like this) instead of the actual value of the function.

What GA are you using, is it the Matlab GA toolbox (which I haven't used) or some other one? You could try the problem out in the GA Toolbox from the University of Sheffield available here: http://www.shef.ac.uk/acse/research/ecrg/gat to see if you get the same behaviour.

[Richard Crozier]

or actually abs(10000 * real(ll) ) would be better.