Re: Issue 28 in deap: Constraint handling - assessing feasibility

[de...@googlecode.com]

Updates:
Summary: Constraint handling - assessing feasibility
Status: Started

Comment #2 on issue 28 by felix.antoine.fortin: Constraint handling -
assessing feasibility
http://code.google.com/p/deap/issues/detail?id=28

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.


--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings

[de...@googlecode.com]

Comment #3 on issue 28 by chrison...@gmail.com: Constraint handling -
assessing feasibility
http://code.google.com/p/deap/issues/detail?id=28

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.

Attachments:
fitness_with_constraints.py 7.1 KB

[de...@googlecode.com]

Comment #4 on issue 28 by heel...@gmail.com: Constraint handling -
assessing feasibility
http://code.google.com/p/deap/issues/detail?id=28

Hi. chrison...@gmail.com

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)

pleas help me. my address is hee...@gmail.com

[de...@googlecode.com]

Comment #5 on issue 28 by chrison...@gmail.com: Constraint handling -
assessing feasibility
http://code.google.com/p/deap/issues/detail?id=28

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 = (x1**2+x2**2-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

Attachments:
nsga2_constrained.py 5.4 KB
TNK.png 61.3 KB

[de...@googlecode.com]

Comment #6 on issue 28 by daniel.s...@gmail.com: Constraint handling -
assessing feasibility
http://code.google.com/p/deap/issues/detail?id=28

Thanks for this submission Chris. I tested it and it also works for me with
the following minor changes:

* the name of the class Fitness must coincide with the name
FitnessWithConstraints in
line 38 of nsga2_constrained
* also in line 38 of nsga2_constrained.py, length(weights) must be equal to
# objectives = 2

Best,

Dani