Friday, 29 April 2016

Paretto frontiers

Last Thursday professor El-Ghazali Talbi from Lille University hold a talk about metaheuristic classification and his unified framework ParadisEO to deal with it on the Elx University Miguel Hernandez CIO, and after the talk (I enjoyed it a lot and learn things a was supposed to already know and some more!) I had a little time to explain my latest fractal methods and show some of the videos I had been producing about them.

There was some debate after the talks about the classification itself and the Pareto frontier way of working on multi objective optimisation problems.

Basically, actual approaches try to maximise all the functions at the same time, if possible, and if not, then obtain the optimum solution for any weighted combination of those functions, so for any possible combination you get a point, and all those points form the "Pareto Frontier" of the problem.

It is true that, if you know the Pareto frontier, it is then easy to find the solution for your function combination of choice, but, in my opinion, trying to find this frontier prior to setting those weigths is making the problem quite more complex than it was initially.
Why? Having a frontier is far more powerful that finding a single point in it! Yep, but frontiers are dangerous geometric objects as Mandelbrot showed us: if you try to get the frontier of the Mandelbrot set using Pareto based approaches, you will probably fail, or you will need thousand of CPU working together, just to find out the frontier can be too fuzzy to decide on it.

Non fractal problems also can (and use to) have complex Pareto frontiers, just consider hundreds of mundane functions to be maximised, and you will be into some serious troubles: how to mix them, how to find the frontier... all this get really hard.

Consider instead using directly the formula that generates this frontier to sheek for the point on it that maximises your combination of functions: quite simpler and faster. In the case of Mandelbrot, this is just a line of code. The difference in complexity from the formula itself to the frontier it generates, is just immense, but more important, the difficulty of solving the same problem one way or the other can also be immense.

The actual problem with that is we don't have a model that, using the "generating formula" of the frontier, can properly scan the state space seeking for the optimum directly, and finding it (this point is important!). Then we break the problem into parts we can deal with and combine them somehow to find the general solution, the Pareto frontier of the problem.

The lack of such a method is actually forcing us to try to solve a quite more complex problem, a problem I think is only academic, in with several functions needs to be maximised at he same time.

Thinking on real problems, you always can pinpoint a single functions that really extract the thing to be maximised, at least I can always imagine one.

For instance, imagine a company hires you to optimise it robotic factory.You can break the problem into a set of different problems, where all of them needs to be maximised: keep energy cost low, keep robot repairs low, keep production high... if you stop here your analysis, you can think you have a multi-objective problem that needs a Pareto frontier to be calculated before going any further.

But none of those are the company goal, the company what to have profits, so the profit is the only goal in the real world, and all the other sub-goals are only academic.

A method that used only the long term profit after taking a given decision to ponder witch option to take at every moment, a continuous decision maker, is needed but nonexistent to the date.

Can all problems been considered as single-function optimisation? I think so. Consider your brain: for every problem it faces, it always uses a single function to maximise while deciding: how good I would feel in the future. The feeling is make makes us want to go up and work, as having money and being useful make us feel better in the long term as compared to staying at bed. As simplistic as it may sound, we only have one goal in life!

I think my fractal (well, it is really a vitamined evolutionary algorithm, but "fractal" or "entropic" are far better namings!) can fill that hole and be used as a tool to directly seek for the solution without any a priori study of the problem (such as finding an aproximate Paretto frontier).

The small problem here is my method doesn't fit professor Talbi classification exactly (I think it amazed him a little), it is a little "out of the box", but not for that much, so I plan to integrate the fractal algorithm (the most simple one, no multi-agent for instance) on his ParadisEO framework for metaheuristic, so we can really find out if it will fill any hole.


  1. Hi Sergio,

    I think you are not right that you can always transform you multi-objective optimization problem into a classical optimization problem. Form example, when you study the sustainability of a process you should understand the cost, the environmental impact and the social effects. The three items are completely unrelated and in some cases you have huge problems just to reduce the problem to a 3 objectives optimization problem.

    In this case, you can try to summary the 3 objectives in one (for example, in economic terms) but as there isn't a "unambiguously" way of doing that you are just setting a weight to every category and this is a completely different problem.

    1. Nice example cruzki, sustainability is one of the usually considered "another different goal" while it is not.

      In one sense you are right: if your time horizon is short, the outcomes of the decision are too uncertain to you and you basically can not foresight them, so the only thing you can do is keep the option you take in the Pareto frontier, seeking for some balance between the three goals.

      But it is just because of your time scale being too short for the problem.

      Imagine your problem is about a forest used to obtain wood. You need to keep money flowing for the company, you also need to keep the process sustainability on the long term, and you need the process to be "human friendly", all at the same time.

      But sustainability is only a word for "we need the business to be profitable also in 50 years, not only 1 year", so, if you think with a time horizon of 50 years, both goals melt into only one: keep profit in the long term, not only in the short term.

      Social benefits, in this case, could mean people want to walk on the forest and have clean air on the zone, so if the business is optimized for 50 years, it is mandatory that the forest is still there after this time, so again, just trying to maximie profit in the long term can balance the three goals aoutatically.

      So, if you can change the scale of time at with you are casting the outcome of your decision, the three objetives will become one.

      If you think only on profit in the short term, you will chop all the trees in the forest and convert into oney you can enjoy.

      If now you think in a longer term, in one week there will be no more trees and you will be broken, so, it is smarter (better for your mind term profits) to keep the a portion of the trees untouched so they can produce more trees for the mid term profit not to fall down, so you decide to keep 50% of the trees and chop them in the next year.

      But if you do so, in 2 years there will be no more trees again, and you will be broken one more time.

      If you think 10 years in advance, you will find that choping only 1/3 of the trees each years is better, because your profits will be similar during those 10 years.

      So, thinking at 20 years time horizon, melted profit and sustainability in one single goal.

      This is why I think optimising on several objetives is just a sign telling us he time horizon used was not long enougt for the problem being solved.

      All decisions humanity could take should be pondered for 1000 years time horizon, and with only one goal: keep humanity healthy, with lots of people living nice lifes.

      Sumatory of hapinnes of all the peopley in the world IS the only real goal we are always, as society, trying to maximise, but it wont work unless you are capable of proyecting your forecasts above the century scale.

      Did you read the Assimov "Foundation" books? This foundation was able to cast predictions up to thousand of years to come, and the foundation was trying to influence in the world history so those outcomes were as "good for humanity as a whole".

      As they could foresight the outcomes of decisions for so long, they didn't need to balance objetives or find Pareto frontier: just take the decison tha maximise the "humanity health" in a 1000 years time horizon.