Constraint handling - assessing feasibility

[fmder]

By cmd-ntrf

Currently, DEAP handles constraints by checking that bounds are respected through either specialized operators like mutPolynomialBounded and cxSimulatedBinaryBounded or decorators such as staticLimit (gp) and checkBounds (see example ga/kurswafct.py). Through these mechanisms, we ensure that every individuals produced and evaluated will be valid, respecting constraints.

It is however not always possible to restrict the generated individuals to the feasible domain. In which case, it is required to assess the feasibility of solutions. While the concept of fitness evaluation is well defined, it is less clear how the concept of feasibility assessment can be integrated in DEAP's examples and algorithms.

Kurpati et al. (2002) list three assumptions on constraints handling in a multi-objective context, : (i) In a given population, feasible solutions are preferred over infeasible solutions, i.e. feasible solutions should have a better rank than the infeasible ones. (ii) The amount of infeasibility (or the extent of constraint violation) is an important piece of information and should not be ignored while handling constraints. (iii) The number of violated constraints is also an important piece of information and should be taken into consideration while handling constraints.

These guidelines could serve as design principles for integration of feasibility assessment in DEAP.

Kurpati, A. and Azarm, S. and Wu, J. "Constraint handling improvements for multiobjective genetic algorithms", Struct Multidisc Optim 23, pp. 204–213, 2002

[fmder]

by cmd-ntrf

Some more food for thoughts, Coello Coello (2002) has written a survey on constraint-handling techniques used in evolutionary algorithms.

He lists 5 major approaches.

• Penalty functions (i.e., static, dynamic, annealing, adaptive, co-evolutionary, and death penalties)
• Special representations and operators (preserving feasibility at all times and decoders and transforming the shape of the search space)
• Repair algorithms (make valid (or feasible) individuals through the application of a certain heuristic)
• Separation of objectives and constraints (i.e.: usage of multiobjective optimization techniques)
• Hybrid methods (Lagrangian multipliers, fuzzy logic, the use of cultural algorithms or the immune system)

While some of the approaches might never be implemented in the core, it could be appropriate to write a tutorial on constraint-handling which covers the basics of each approach and how to implement them in DEAP.

Coelle Coello, C. A. "Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art". Computer Methods in Applied Mechanics and Engineering 191, 11–12, 1245–1287, 2002.

[fmder]

By chrisonian

I successfully implemented constraints for DEAP's NSGS-II routines by only modifying the Fitness class (see attached file). Basically I added 'n_constraints' and 'cvalues' properties, added a 'feasible' routine, and modified the 'dominates' routine to check for feasibility according to the scheme mentioned about (Kurpati) and also mentioned in Deb's original NSGA-II paper (2002). A solution is feasible if all 'cvalues' are greater than zero.

[fmder]

By heelijo

Hi. chrisonian

I'm trying to solve constraintd pareto optimization problem with DEAP's NSGA-II

I read your modification on class fitness. and could you give me a instruction of some examples giving constraint to this fitness class in frontend interface of nsga2.py ?

like in deap-1.0.0/examples/ga/nsga2.py

def constraint_ftn() toolbox.register("constraint", constraint_ftn)

[fmder]

Hi heel...

I attached a working example with the plot. It also needs the fitness_with_constraints.py file attached in my above comment. Essentially the evaluation function (in this case TNK, from the Deb 2002 paper) returns two tuples:

def TNK(individual): x1=individual[0] x2=individual[1] objectives = (x1, x2) constraints = (x12+x22-1.0 - 0.1_cos(16_atan(x1/x2)), 0.5-(x1-0.5)2-(x2-0.5)2 ) return (objectives, constraints)

and the constraints (cvalues) are set in one place at the evaluation:

fitnesses = toolbox.map(toolbox.evaluate, invalid_ind) for ind, fit in zip(invalid_ind, fitnesses): ind.fitness.values = fit[0] ind.fitness.cvalues = fit[1]

This was the simplest way for me to add this functionality without changing anything else in DEAP.

• Chris

[fmder]

Work has started for adding constraint handling to deap see the Constraint Handling Tutorial

[FabioMunaretto]

Hi there,

I just wanted to point out that multi objectives problems along with contraints on fitnesses (for example with the DeltaPenality class) are still tricky to deal with in deap (even in 1.1).

To be clear, in my case, I added an attribute to the individuals that stores fitnesses of my population which is computed by an external simulation code before calling a fake evaluation method decorated with constraints.

If I want to set a distance function which returns something different depending on my multiple fitnesses (means after computation of the external simulation code) and their distance to a valid solution, it is not handled by the current code (line 52 to 54 of constraints.py in master):

if self.dist_fct is not None:
    dist = self.dist_fct(individual)
return tuple(d - w * dist for d, w in zip(self.delta, weights))

In my opinion, this issue could be tackled simply by adding dist to zip and managing the fact that dist is potentially an iterable (different for each fitness) or a single element (identical to every fitness):

if self.dist_fct is not None:
    dists = self.dist_fct(individual)
if not isinstance(dist, Sequence):
    dists = repeat(dists)
return tuple(d - w * dist for d, w, dist in zip(self.delta, weights, dists))

What do you reckon?

Cheers.

Fabio.

[fmder]

That looks like a good solution, can you provide PR with the modification? At first sight, I don't see any down side to those using the original version.

Best regards,

2016-10-26 8:37 GMT-04:00 FabioMunaretto notifications@github.com:

Hi there,

I just wanted to point out that multi objectives problems along with contraints on fitnesses (for example with the DeltaPenality class) are still tricky to deal with in deap (even in 1.1).

To be clear, in my case, I added an attribute to the individuals that stores fitnesses of my population which is computed by an external simulation code before calling a fake evaluation method decorated with constraints.

If I want to set a distance function which returns something different depending on my multiple fitnesses (means after computation of the external simulation code) and their distance to a valid solution, it is not handled by the current code (line 52 to 54 of constraints.py in master):

if self.dist_fct is not None: dist = self.dist_fct(individual)return tuple(d - w * dist for d, w in zip(self.delta, weights))

In my opinion, this issue could be tackled simply by adding dist to zip and managing the fact that dist is potentially an iterable (different for each fitness) or a single element (identical to every fitness):

if self.dist_fct is not None: dists = self.dist_fct(individual)if not isinstance(dist, Sequence): dists = repeat(dists)return tuple(d - w * dist for d, w, dist in zip(self.delta, weights, dists))

What do you reckon?

Cheers.

Fabio.

— You are receiving this because you were assigned. Reply to this email directly, view it on GitHub https://github.com/DEAP/deap/issues/30#issuecomment-256334447, or mute the thread https://github.com/notifications/unsubscribe-auth/AA6rwqXlnbEDoQ_Tg4W7C6rRL4JiCiDYks5q30mjgaJpZM4B9uP6 .

[FabioMunaretto]

Yes, this is the PR https://github.com/DEAP/deap/pull/156 Btw, thanks for your amazing job on deap ;)