Genetic algorithm - Thousands of variables

Hello,

I am using Matlab's Genetic Algorithm from the Global Optimisation Toolbox to solve a multi-period Non-Linear constrained problem.

Let me try and give you a bit of a background for the problem: Basically, I have the heat and electricity demand of a building for 8760 hours of a year. I have 5 (or more) pieces of kit that can supply this demand and depending on the pricing I would like to find out what is the most optimal use of each technology for each single hour of the year. The objective is to minimize the annual cost.

So, for a single hour I would have 5 variables corresponding to the consumption of each piece of kit. However, as I said this problem is multi-period which means that the number of variables is actually multiplied by 8760 => reaching the number of 43800.

My question therefore is:

Can I somehow define these variables in any other form other than a single vector? For instance a matrix of 8760x5 would be much easier to comprehend and use to construct equations.

I know for instance that when using fmincon data can be passed as a matrix, taking some care of the A, Aeq matrices etc. Something that is very nicely illustrated here: http://www.mathworks.ch/matlabcentral/newsreader/view_thread/323075

Is there something equivalent I can do?

Note: I want to use the GA toolbox, because I will be extending the model by adding a few integer variables in future formulations. Hence, I cannot move to fmincon.

Thanks in advance,

George

Answer 1

[Alan Weiss]

I think that you are unlikely to obtain a satisfactory answer from GA with that many variables. GA is a random search algorithm, and searching more than a few hundred variables takes a long time. You would need to take a population of at least twice the size as the number of variables, and that alone will cause the iterations to be very slow. Furthermore, the GA nonlinear constraint algorithm takes a large number of iterations for constraint satisfaction, making the problem seem to me to be unlikely to yield a satisfactory result in a reasonable time.

I wonder if you can formulate the problem for fmincon, and then, if you have just a few integer-constrained variables, do an exhaustive search over the possible values of the integer variables.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Georgios Mavromatidis]

Firstly, Alan, I have to say thank you for such a prompt reply. Simply a few more questions to elaborate a bit more.

If time was not a constraint, how much confidence could I have in such a solution from GA?

Moreover, assuming that there was no computational issue, with regards to the single-vector-variable definition issue, can it be solved/tackled somehow?

Thanks again,

George

[Alan Weiss]

GA has no guarantees regarding the quality of its solutions. None, not even that it produces a local minimum.

You can formulate your problem however you like, with arrays of any size and dimensionality. Suppose you have X, 3-by-4-by-12, and Y, 15-by-3-by-2-by-20. Combine them as [X(:);Y(:)]' (one big row vector). Later you can take the answer apart and reshape the components.

I see that you are really interested in a binary programming problem. The only solver MathWorks has dealing with these problems, other than GA, is bintprog, but bintprog is for linear objective functions only. Quite often, you can formulate a nonlinear-looking integer-constrained problem as a binary linear program. But if you cannot, then I am afraid that our solvers will not be satisfactory for you.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[Walter Roberson]

Do I understand correctly that you have 5 pieces of equipment each of which can be turned on or off independently? If so, then what interrelationships are there between the time periods and the choices? Why not just optimize period by period, and calculate the totals yearly?

For example, do you have "momentum" effects? Such as a particular piece of kit heats at such-and-such a rate, and cools at this-and-that rate, so if it had been on at hour #1, and off for hour #2, that it might be more economical to switch back to it because the cost to re-heat from 1-hour cooled, plus the cost to run for the hour, would be less than the cost to heat something else from multi-hour cooled plus the cost to run that other device for the hour?

But even that kind of momentum effect would surely call for a fuzzy logic controller or a small state-space controller optimizing based upon current temperature gauges for the various devices, together with some near-term automated forecast of conditions, rather than upon something that needs to GA over an entire year of data?

Are there wear-and-tear to take into account? "Don't switch on Kit #3 because although it is more responsive in adjusting heat, the forecast wear on it under these conditions would implicitly increase overall expense compared to using this other kit that costs slightly more in fuel but would wear less expensively" ?

If you are trying to decide between which subset combination of devices would be most cost effective over the 5 year period, then if you do not take maintenance or time-to-refill-reserves or the like into account, it is not clear to me that you want GA over so many variables. More like a linear optimization question than a GA question, it seems to me.

[Georgios Mavromatidis]

Hello Walter,

First, let me thank you for your thorough reply. I didn't explicitly describe the nature of my problem because not everyone knows the details involved in energy modelling, which clearly you do.

What I want to do is called "energy hub optimal layout". An energy hub is a modelling concept or a multi-energy carrier management scheme in which multiple energy carriers and conversion devices are combined to allow for optimal power dispatch and flexibility.

What I want to do is define a big set of these devices and then using binary integer variables (0 or 1) define which subset of these devices should be chosen in order to minimize the annual operating cost. Since energy storage will probably be part of it, the need for hourly resolution arises. More info can be found here (on page 5): http://www.eeh.ee.ethz.ch/uploads/tx_ethpublications/PowerTech_07_Geidl_Andersson.pdf

So, overall the use of these integer binary variables in conjunction with the hourly energy production from each piece of kit makes my problem automatically a MINLP. This is the reason why I am looking into going GA.

The original developers of the concept utilised and MINLP solver from TOMLAB, namely minlpBB. Since I don't have access to that, I thought I should try GA.

Would you have any other suggestions?