What can I do to make a GA spread the intial population over a larger area

Dear community,

I am currently optimising the size of a combination of a chp unit and an auxiliary boiler. I feed the algorithm with all sorts of information about investment costs, fuel efficiencies, o&m costs and so on. As a start, I am looking at 12 timesteps only, in which the combination of chp unit and the boiler jointly have to supply heat to a city quarter. So I have chp unit power from 1:12, boiler power from 13:24 and at 25 and 26 the rated power of the two. The rated power of both chp unit and boiler is the final result.

For instance the needed heat supply is 20kW in all 12 timesteps. So chp unit power and boiler power have to meet this request. There are billions of combinations possible but my ga goes for quite a narrow range as for instance:

CHP Power [kW] 19.5 19.4 19.6 19.7. 19.65 .... Boiler [kW] 0.5 0.6 0.4 0.3 0.35 ....

The ga creates an intial population from which he starts optimisation. The algorithm ends up in a local minimum that is not the global minimum. The reason for this is that the genetics of its initial population is simply not different enough. With other words my individuals are too similar to each other.

However if I provide the ga with an initial population with a combination of a optimal solution from linprog and of the initial population that it usually comes up with, it finds the same solution as linprog and also as fmincon. You might now wonder, why I want to use ga in the first place...the answer is that I want to do multiobjective programming next, so I need my ga to work first...

Do you have any suggestions as to how to spread the gene variation further?

Thanks in advance,

Mathias

Answer 1

[Alan Weiss]

The documentation has suggestions about setting the initial diversity. I suggest that you put bounds on all your variables, and then ga uses those bounds to set its initial population. You might also need to take a larger-than-default population size, or to use the @gacreationlinearfeasible creation function.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Mathias Tholey]

Hi Alan,

I had already set bounds on all my variables. I tried to implement the population initial range, but for some reason the algorithm simply does not react to it. I have set up a vector with 2 rows and nvars columns. But the algorithm neglects my 'PopInitRange',P0. I could just as well delete it from the options again...is there a well known reason for this behaviour?

Changing the population size doesn't change this behaviour of emphazising the chp unit. Even if I double the amount of population size there is not the slightest difference in behaviour.

Thanks again for your help!

Mathias

[Alan Weiss]

What happened when you tried the @gacreationlinearfeasible creation function?

Alan Weiss

MATLAB mathematical toolbox documentation

[Mathias Tholey]

Hi Alan,

I might not have mentioned that I have been using linear constraints all along, so @gacreationlinearfeasible should have been default anyway, shouldn't it? That's why I don't know what you mean by "What happened when you tried the @gacreationlinearfeasible creation function".

I have just read in the documentation that @gacreationlinearfeasible ignores Initial range (PopInitRange). This is exactly what I described yestday...Do you have any recommendations as to how to avoid this?

Is there a way to change the @gacreationlinearfeasible function so that the inital population is further spread? I think it is quite difficult to come up with a custom creation function that takes all the constraints into account...not to say impossible (for me).

Best wishes and many thanks,

Mathias

[Alan Weiss]

As this example shows, @gacreationlinearfeasible creates a diverse population that not only satisfies bounds, but is biased to lie on the linear boundaries. You won't get a more dispersed feasible population using any other creation function.

But if you want a LESS dispersed population, you could write a custom creation function that takes, say, half the population from gacreationlinearfeasible and then creates half the population using convex combinations of the existing population, to fill in the middle region better.

I also think that you probably need to take a much larger population size.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Mathias Tholey]

Hi Alan,

I have studied all the links that you sent me. I have seen the example and I just don't understand why it is not the same with my programme. I certainly don't want a LESS dispersed population. My problem is that the population is by far not diverse enough. I have uploaded my code on Dropbox. Maybe you can check yourself...

https://www.dropbox.com/sh/yce7fl1pwhkmyw0/AAAcovt_9_i1Dm3E4NU2zrUWa?dl=0

If you put a breakpoint into the fitness function, you can see the initial population I guess. There you can see that it is not diverse at all. The first 24 columns account for the chp unit, column 25-48 auxiliary boiler. 49-72 storage tank power, 73 rated power chp unit, 74 rated power boiler, 75 storage tank volume. CHP unit and boiler should show very similar values, which they don't. CHP unit is far higher than boiler.

On the other hand, creating a far bigger population will increase the computing time rediculously. I have tripled it to 600 and it already took quite some time for only two hours of observation. T = 105120/365/12 == 12*5min*8760h/365d/12h

Does anyone understand where the problem lies? I am desperate...

Best wishes,

Mathias

[Mathias Tholey]

I have found out that the reason why there are basically only the first 24 columns used in my programm is that eqnsolv deep down in the GA decides to choose an XBASIC solution instead of the minnormstep. As one cannot change this code I have to accept this situation but then I don't understand why even with this rather undispersed solution, the ga does not manage to evolve into other directions...

I know this is quite a complex question but maybe there is someone out there who can help me!

Best wishes,

Mathias

[Alan Weiss]

It is possible that the creation function gacreationlinearfeasible is getting stuck near the initial feasible point that it creates. So perhaps the best thing to do is to give ga a new creation function, based on gacreationlinearfeasible, that works as follows: Instead of generating one feasible point and then looking for feasible directions from that point, instead solve a number of linear programming problems using linprog. Each linear programming problem has the same linear constraints and bounds as your original problem.

The new feature is to take f, the linprog objective function vector, to be randn(1,nvars), where nvars is the number of variables in your problem. For better scaling you could even take f to be f/norm(f).

This linear programming problem has a solution that is a vertex of the constraint simplex, chosen in a random direction. As you generate your initial population you could even discard points that have already been found, while being careful not to halt the generation entirely by getting stuck if you have already generated all feasible vertices.

To implement this function, you can create a new function, say called gacreatelinear2. In that file, copy over the code from gacreationlinearfeasible, and replace the block of code starting at line 97:

 if directionCounter > maxDirections

and ending at line 160, with the linprog calls.

If you don't want to write your own creation function like this, you could generate an initial population by running the linprog code yourself several times, and then taking a few convex combinations of the resulting vertices, as your initial population.

Whatever you choose to do, be sure to either pass in the custom creation function, or the custom initial population, to your ga options.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation