Finding best weights for multiobjective optimization

[Jaime RG]

Hi!

I am using your wonderful project, together with UCSF Chimera, to write my master thesis in Bioinformatics. So far, it's been straight-forward experience and we're very glad with the results and performance. A couple of days with no prior knowledge of GA has been enough to achieve a 'beta-ish' status!

My scoring function has three components, so I am using a three-objective GA, with weights 1.0, -1.0, -1.0, since I want to maximize the first param, and minimize the other two. However, we don't know how much each component contributes to the final behaviour in real life.

My guess is that, since you have chosen floats to represent the optimization type, can we tune them to find a better fitting score function? For example, if I feel that the third parameter won't be as important as the first two, could I use these weights: 1.0, -1.0, -0.5?

I have run a couple of tests, and DEAP doesn't complain about it, but I don't know if the change is having any effect. Anyway, if I am right, what would be the best way to find a better set of weights?

Thanks in advance,

Jaime.

[Marc-André Gardner]

Hi Jaime,

Thanks for the kind words, it's always great to see what people are able to achieve with DEAP.

I do not have the time the answer about the (very complex) issue about finding the best set of weights -- and others knows far better than me about that -- but just to confirm your thoughts : you can indeed pass any real number to the weights parameter, as stated in the documentation (http://deap.gel.ulaval.ca/doc/default/tutorials/basic/part1.html#fitness), including numbers higher than 1. DEAP will just use them as a multiplication factor to their relevant objective.

Have fun with DEAP,

Marc-André

[Marc-André Gardner]

Oh BTW, I forget that in my previous post : some of the selection operators (say for instance a tournament) will not care about those weights, because of the way fitness are compared. For instance, if you have a set of weights : (-1.0, 1.0, 0.5), and two individuals with fitness values like (3, 2, 6) and (2, 2, 5), then DEAP will just multiply the values and the weights, giving (-3, 2, 3) and (-2, 2, 2.5). When the two individuals are compared, the default way to do so is to use a lexicographic approach : if the first value of an individual is better than the other, than the first is set to be better. If this first value is equal, then we go to the second value, and so on. So in this case, your weights will not change anything, except for the minimization/maximization part.

You have to use specific selection operators in order to make use of this weight information. In any other case, those values will be, in a way, ignored.

I hope it's a bit more clear.

Marc-André

[François-Michel De Rainville]

In short, the weights are useful in the crowding distance computation for NSGA2. If you have objectives that are not scaled, the weights serve to put or remove emphasis on a subset. Other than that they are of no use. I'm not aware of any study on that subject however.

Cheers,
François-Michel

[Félix-Antoine Fortin]

Hi Jaime,

If you plan to do multi-objective optimization and you do not have prior knowledge on the importance of each objective, you should stay away from aggregating function and instead use a multi-objective selection algorithm that is based on the concept of dominance, and most commonly Pareto dominance. Linear aggregating function, such as the weighted sum, have a well known limitation of being unable to generate non-convex portions of the Pareto front [1].

DEAP currently includes two multi-objective selection operator NSGA-II and SPEA2. However, in order for these operators' elitism to work properly, you have to use an algorithm that will expand your population: algorithms.eaMuPlusLambda. There are many examples of usage in the example folder, here is a short list:
- Discrete optimization with NSGA-II : GA Knapsack
- Discrete optimization with NSGA-II : GA Evolutionary KNN
- Continuous optimization with NSGA-II : GA Kursawe
- Discrete optimization with NSGA-II + custom algorithm: GA Evolutionary Sorting Network 

NSGA-II, as François-Michel mentioned, can use the weights via the crowding-distance computation to normalize the objective. Although, it would be preferable to do the normalization in the evaluation function, as it can be more complex than a simple a multiplication. Ideally, each objective should be defined on the same range of values.

Regards,
Félix-Antoine

[1] Das, I. and Dennis, J.E. "A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems", Structural optimization, vol. 14, no 1., pp. 63-69, 1997.

On Monday, March 31, 2014 4:04:49 AM UTC-4, Jaime RG wrote:

Hi! Thanks for your time. That was quick!

I think I've understood most of the concepts, but I would like to ask a couple of questions to confirm my thoughts.

Since the score is compared lexicographically in the tournaments, would it be acceptable to clone that function and edit the comparison part to, for example, the weighted sum of the fitnesses? In your example, Marc-andré, I'd try something like this: (rough draft)

https://gist.github.com/enoyx/2f1ae960bf1d6bad5f83

If that's not recommendable, maybe I should rearrange the fitness scores in my evaluation function? Presumably important components first, then the rest?

Thanks again,
Jaime.

[Jaime RG]

Wow, totally missed this answer! 

Thanks for such a thorough explanation. I am so new to Python and GA, but I am slowly getting it! I will take a look at those papers and examples, but I think it's clear now. Thanks again!

[Wanli Ma]

Hi, Antoine,

Thank you for your thorough explanation about NSGA-II, which is quite helpful!

Maybe it's too old question, but I stll got confused when applying NSGA-II to my situation. Hope these are not silly questions. cause I searched quite a few.

1. " However, in order for these operators' elitism to work properly, you have to use an algorithm that will expand your population: algorithms.eaMuPlusLambda." Why is this? The individual in my case is OrderedDict, with self-defined mutation and crossover functions. I use multi-objectives with 8 weights, selected by tools.selNSGA2. The evolution algorithm is eaSimple, with both VarOr and VarAnd. Should it work, or not? Why? I paste my code at the bottom.

2. NSGA2 with different weights could be useful for crowding, according to your statement. The thing is, I know what does every objective stand for, but they may be different in order of magnitudes and significance. How should I assign weights for them?

    def model(self):

        creator.create("Fitness", base.Fitness, weights=(-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0))

        creator.create("Individual", OrderedDict, fitness=creator.Fitness)

        toolbox = base.Toolbox()

        toolbox.register("individual", tools.initIterate, creator.Individual, generate_od())

        toolbox.register("population", tools.initRepeat, list, toolbox.individual)

        toolbox.register("evaluate_new", fitness_func())

        toolbox.register("mate", tools.cxTwoPointOrderedDict)

        toolbox.register("mutate", tools.mutOrderedDict)

        toolbox.register("select", tools.selNSGA2)

        stats_fit = tools.Statistics(lambda ind: ind.fitness.values)

        mstats = tools.MultiStatistics(fitness=stats_fit)

        mstats.register("avg", np.nanmean)

        mstats.register("std", np.nanstd)

        mstats.register("min", np.nanmin)

        mstats.register("max", np.nanmax)

        pop = toolbox.population(n=self.num_pop)

        hof = tools.ParetoFront()

        pop, log = algorithms.eaSimple(pop, toolbox, self.mate_prob, self.mute_prob,\

                    self.num_gen, stats=mstats, halloffame=hof, verbose=True)

        return pop, log, hof

在 2014年3月31日星期一 UTC+8下午11:35:05，Félix-Antoine Fortin写道：