priorities in multiobjectives

[kaustubh.patil]

Hi,

First of all thanks for the wonderful library.

I want to know if there is any way one could assign priorities to the
objectives in a multiobjective task?

best regards

[Aaron Garrett]

Can you give an example so that I can understand better what you want to do?


Aaron Garrett, Ph.D.
Assistant Professor
Computer Science
Jacksonville State University
Jacksonville, AL  36265
agar...@jsu.edu
256-782-5364
http://mcis.jsu.edu/faculty/agarrett

--
You received this message because you are subscribed to the Google Groups "Evolutionary Computations in Python" group.
To post to this group, send email to ec...@googlegroups.com.
To unsubscribe from this group, send email to ecspy+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/ecspy?hl=en.

[jelle feringa]

Are you mean a weightening of the objective?

[kaustubh.patil]

Hi Aaron,

Thanks for reply. Here is an example;

Imagine I have three objectives A, B and C, all of them should be
minimized. But for me A is more important than B and C and B is more
important than C, imposing an order A > B > C. Therefore, B should not
be minimized at the expense of A and C should not be minimized at the
expense of B or A.

A relevant publication is;

http://www.aaai.org/Papers/JAIR/Vol18/JAIR-1806.pdf

I didnt go through the whole article but seems to be in the same
direction.

best regards

On Mar 14, 3:46 pm, Aaron Garrett <aaron.lee.garr...@gmail.com> wrote:
> Can you give an example so that I can understand better what you want to do?
>
> Aaron Garrett, Ph.D.
> Assistant Professor
> Computer Science
> Jacksonville State University
> Jacksonville, AL  36265

> agarr...@jsu.edu
> 256-782-5364http://mcis.jsu.edu/faculty/agarrett

[kaustubh.patil]

hi jelle,

Its not really weighting of the objective components but rather
imposing order such that more important objective component is not
compromised for less important component.

best

[Mike Vella]

Hi Kaustbuh,

You may be a bit confused about terms here. I think you need to understand multi objective optimization a bit better. I suggest you read up on Pareto Fronts in wikipedia.

Mike

[kaustubh.patil]

Hi Mike,

That might be possible as I dont really work in this field but just
use it :) and please excuse me for any confusion.

I have basic ideas about Pareto optimality. When I try to optimize a
three objective functions (all to be minimized) using NSGA2 this is
what I get;

ngen:0 neval:50 best:[0.77502170660866987, 0.019886221342636037,
0.56663760706218347] worst:[0.73023004247608148, 0.020102329673084882,
0.58742085723617565]
ngen:1 neval:100 best:[0.77502170660866987, 0.019886221342636037,
0.56663760706218347] worst:[0.75620845590828067, 0.021433623662428115,
0.58955293072983994]
ngen:2 neval:150 best:[0.76533658928756998, 0.019933482008048137,
0.58871141287541717] worst:[0.76575034485640481, 0.02044345671707699,
0.56835320154475399]
ngen:100 neval:5050 best:[0.61303715153669391, 0.020791973957471233,
0.46833355468136462] worst:[0.66800040173070496, 0.018338133099019081,
0.45358593235442141]
ngen:200 neval:10050 best:[0.73917747061984018, 0.015282120924892022,
0.45743167136084528] worst:[0.58654518945658141, 0.020189569671711663,
0.46825962076581207]
ngen:300 neval:15050 best:[0.73917747061984018, 0.015282120924892022,
0.45743167136084528] worst:[0.63924910665167567, 0.017541907644333072,
0.42645382850501784]

Here my first objective is more important than second and second than
third, therefore I dont want to compromise the first to minimize
others as happens at generation 200.

Is there any way I can address this?

best regards

On Mar 14, 11:46 pm, Mike Vella <vellam...@gmail.com> wrote:
> Hi Kaustbuh,
>
> You may be a bit confused about terms here. I think you need to understand
> multi objective optimization a bit better. I suggest you read up on Pareto
> Fronts in wikipedia.
>
> Mike

[Aaron Garrett]

Yes, you can do it. What you're describing is called "lexicographic" ordering of the objectives. You just need to make a class for it so the comparison goes down the way you intend. For example, something like this should work for you:

import functools

@functools.total_ordering

class Lexicographic(object):

    def __init__(values=None):

        if values is None:

            values = []

        self.values = values

    def __lt__(self, other):

        for v, o in zip(self.values, other):

            if v < o:

                return True

        return false

    def __eq__(self, other):

        return (self.values == other.values)

Note that I haven't tested this code. I'm just throwing it out here to give you the idea. Your mileage may vary.

You can use it as follows:

def my_evaluator(candidates, args):

    fitness = []

    for candidate in candidates:

        f = objective_1_calculation()

        g = objective_2_calculation()

        h = objective_3_calculation()

        fitness.append(Lexicograhic([f, g, h])

    return fitness

Now, if you do this, you normally wouldn't use NSGA to solve it. It's essentially a single-objective problem now. So just using a normal EC on your problem should be fine. If you're still confused, let me know and I can give you a little more direction. I'm just pressed for time at the moment.

Aaron Garrett, Ph.D.
Assistant Professor
Computer Science
Jacksonville State University
Jacksonville, AL  36265
agar...@jsu.edu
256-782-5364
http://mcis.jsu.edu/faculty/agarrett

[kaustubh.patil]

Hi Aaron,

Thanks a lot I will try that out.

best

On Mar 15, 12:20 am, Aaron Garrett <aaron.lee.garr...@gmail.com>
wrote:

> agarr...@jsu.edu
> 256-782-5364http://mcis.jsu.edu/faculty/agarrett

[Aaron Garrett]

OK. Now that I have a little more time, here's a bit more thorough implementation. Does it match what the functionality you wanted?

import functools

@functools.total_ordering

class Lexicographic(object):

    def __init__(self, values=None, maximize=True):

        if values is None:

            values = []

        self.values = values

        try:

            iter(maximize)

        except TypeError:

            maximize = [maximize for v in values]

        self.maximize = maximize

    def __len__(self):

        return len(self.values)

    

    def __getitem__(self, key):

        return self.values[key]

        

    def __iter__(self):

        return iter(self.values)

        

    def __lt__(self, other):

        for v, o, m in zip(self.values, other.values, self.maximize):

            if m:

                if v < o:

                    return True

                elif v > o:

                    return False

            else:

                if v > o:

                    return True

                elif v < o:

                    return False

        return False

    def __eq__(self, other):

        return (self.values == other.values and self.maximize == other.maximize)

    def __str__(self):

        return str(self.values)

        

    def __repr__(self):

        return str(self.values)

    

if __name__ == '__main__':

    a = Lexicographic([1, 2, 3], maximize=True)

    b = Lexicographic([1, 3, 2], maximize=True)

    c = Lexicographic([2, 1, 3], maximize=True)

    d = Lexicographic([2, 3, 1], maximize=True)

    e = Lexicographic([3, 1, 2], maximize=True)

    f = Lexicographic([3, 2, 1], maximize=True)

    

    u = Lexicographic([1, 2, 3], maximize=False)

    v = Lexicographic([1, 3, 2], maximize=False)

    w = Lexicographic([2, 1, 3], maximize=False)

    x = Lexicographic([2, 3, 1], maximize=False)

    y = Lexicographic([3, 1, 2], maximize=False)

    z = Lexicographic([3, 2, 1], maximize=False)

    

    for p in [a, b, c, d, e, f]:

        for q in [a, b, c, d, e, f]:

            print('%s < %s : %s' % (p, q, p < q))

    print('----------------------------------------')

    for p in [u, v, w, x, y, z]:

        for q in [u, v, w, x, y, z]:

            print('%s < %s : %s' % (p, q, p < q))

Aaron Garrett, Ph.D.
Assistant Professor
Computer Science
Jacksonville State University
Jacksonville, AL  36265

agar...@jsu.edu
256-782-5364
http://mcis.jsu.edu/faculty/agarrett

[kaustubh.patil]

Hi Aaron,

Thanks for the code, I had something similar coded up, without the
implici maximize though.

This servers the prupose, thanks again.

I have another question. In multiobjective components is it possible
to assign weights? For examples if I have objectives A, B and C, can I
assign weight alpha to C? I want to use it for parameter tuning, e.g.
controling complexity of the solution using norm and find a good value
of alpha via cross-validation.

best

> agarr...@jsu.edu
> 256-782-5364http://mcis.jsu.edu/faculty/agarrett

[Aaron Garrett]

I'm not entirely clear on what you're wanting to do. What is the weight for? Do you want the evolution to care about it, or is it for some other purpose independent of the evolution?

Aaron Garrett, Ph.D.
Assistant Professor
Computer Science
Jacksonville State University
Jacksonville, AL  36265

agar...@jsu.edu
256-782-5364
http://mcis.jsu.edu/faculty/agarrett

[kaustubh.patil]

Individual solution is a vector of real numbers and using the weight I
want to control its sparsity. So one of my objective function is L1
norm of the solution. Thus by assigning higher weight to this function
should result in more sparse solutions.

An example of this is SVM where the solution is the weight vector and
one objective is its norm, and I want to find the "optimal" weight for
this objective. Makes sense?

best

On Mar 15, 5:30 am, Aaron Garrett <aaron.lee.garr...@gmail.com> wrote:
> I'm not entirely clear on what you're wanting to do. What is the weight
> for? Do you want the evolution to care about it, or is it for some other
> purpose independent of the evolution?
>
> Aaron Garrett, Ph.D.
> Assistant Professor
> Computer Science
> Jacksonville State University
> Jacksonville, AL  36265

> agarr...@jsu.edu
> 256-782-5364http://mcis.jsu.edu/faculty/agarrett
>
> On Wed, Mar 14, 2012 at 11:27 PM, kaustubh.patil

> ...
>
> read more »

[Aaron Garrett]

If I understand you correctly, then I would say that you could certainly add a constant weighting factor to your calculation of the L1 norm. But from your previous message, it sounded like you wanted to use the evolution to find an optimal value for your weighting factor. If that's the case, then it needs to be a part of your candidate solution because it's no longer a constant.

I'm not sure how much experience you've had with using these kinds of optimization algorithms, so forgive me if I'm saying things that you already understand... 

When you have an optimization problem, then your candidate solutions (the chromosomes, if you prefer, that will be evolved) are the elements of your problem that you want to optimize. They are the independent variables. The fitness that comes out of the evaluation function should be a function of those variables that somehow provides a measure of optimality. The evolution absolutely will not care how that function was generated or how it works. And the evolution will do whatever it takes to produce candidate solutions that optimize that value. It will "cheat" if it can find a way to do so (by exploiting some property of your fitness measure that you didn't intend, for example). So the fitness measure is a black box to the evolution. If it has some weighting internally, that's perfectly valid and the evolution will be none the wiser.

When you do lexicographic ordering, all you're doing is redefining how the candidates are compared to one another. It is essentially a single-objective problem again because you only care about one objective (the first one) unless the two candidates match on it, in which case you only care about one objective (the second one), and so on. This is similar to the use of weighting factors on the objectives (which may be what you're thinking about above). For instance, I may have 3 objectives, x, y, and z, and I may measure the fitness as 0.25x + 0.25y + 0.5z. (The weights need not be probabilities.) So this would mean that objective z has twice the impact of either x or y in terms of total fitness. And individuals would be compared based on their value for this linear combination of objectives. I should mention that, while the weight vector approach is still fairly popular (because it turns a mulitobjective problem into a single objective problem), it was mathematically proven quite a while back that such an approach is unable to produce all non-dominated solutions if the Pareto front is concave or discontinuous. That means that there may be a very good solution to your problem that the EC simply can't reach because of your particular choice (or any choice) of weight values.

A more robust approach is to use an EMO algorithm that can operate in an environment where "non-dominated" is a well-defined concept. Algorithms like NSGA produce a set of near-optimal solutions, rather than a single solution. (You need to look in the EC's "archive" variable for this set, by the way. The final population will be of little use to you. I think there's an example of that in the documentation. If not, I can get you an example.) A solution u is dominated by another solution v if it v is no worse than u in any objective and strictly better than u in at least one objective. For example, suppose you and I share two competitive hobbies. If we always tie on one of them but you always beat me on the other, then we would say that you "dominate" me. (Obviously, if you beat me on both, then you also dominate.) But what if I always win one and you always win the other? In that case, we are both "non-dominated". And the EMO algorithms produce a set of solutions that are all non-dominated. So, in your case if your priorities are A > B > C, then you can still use an EMO. Then you can just pick the elements from the final archive that match those inequalities. But you may also find trade-offs that you are comfortable with that don't necessarily fit your inequalities. For instance, what if there is a solution in the final set where A is 0.1% worse than B, but B is 500% better than any other solution in the set? Is that a trade-off that you'd be willing to make? 

For instance, what if we're optimizing ... product quality (max) and production cost (min). Those are two things that would require a trade-off. And what if we care mostly about cost. So your inequality would be Cost > Quality. But what if the EMO algorithm produced a solution like the one mentioned above? Would you be willing to sacrifice one-tenth of one percent of the cost to get a five-fold increase in the quality? I would expect so. But that solution would not be found using lexicographic ordering because the higher cost would be out-competed by lower cost solutions.

I don't know if any of that helps you. You may have already been clear on it. If so, I apologize for having wasted your time. :-)

Aaron Garrett, Ph.D.
Assistant Professor
Computer Science
Jacksonville State University
Jacksonville, AL  36265

agar...@jsu.edu
256-782-5364
http://mcis.jsu.edu/faculty/agarrett

[kaustubh.patil]

Hi Aaron,

I have some experience with such optimization but a rminder is always
good :)

Sorry for my previous confusing message. Here I am explaining again
what I want to do;

I want to tune a hyper-parameter "alpha" using cross-validation so I
get some generalization over the learned function. In additive
objective function I do it like this;

obj = f1(x) + alpha*f2(x)

Then I run the optimization for different valies of alpha in cross-
validatoin setup; i.e. leaving out some part of the data to validate.
The validation objective is only f1(x). Then I choose the alpha for
which there was minimum validation error and then run the final
optimization using it.

Now my question is, can this be achieved in multioobjective
optimization procedure where I want to add aother objectibe f3(x)? One
way I can see is to keep the additive objective and add the new one
and use either lexicographic or non-dominated optimization over this.
Is there any other way than this?

best

> agarr...@jsu.edu
> 256-782-5364http://mcis.jsu.edu/faculty/agarrett
>
> On Wed, Mar 14, 2012 at 11:36 PM, kaustubh.patil
> <kaustubh.pa...@gmail.com>wrote:

> ...
>
> read more »

[Aaron Garrett]

Sorry it took me so long to respond. 

When you add another objective in a non-dominated setup, your choosing of the alpha with "minimum validation error" will not be very well defined. So that is going to be an issue for you.

Aaron Garrett, Ph.D.
Assistant Professor
Computer Science
Jacksonville State University
Jacksonville, AL  36265

agar...@jsu.edu
256-782-5364
http://mcis.jsu.edu/faculty/agarrett

> ...
>
> read more »