Constraint-Handling in Nature-Inspired Optimization
Efrén Mezura-Montes
Artificial Intelligence Research Center
University of Veracruz, MEXICO
emezura@uv.mx
http://www.uv.mx/personal/emezura2017 IEEE Congress on Evolutionary Computation
Donostia - San Sebastián, SPAIN, June 5th, 2017

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

1 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

2 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

2 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

2 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

2 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

3 / 156

Problem statement
Constrained numerical optimization problem (CNOP)
Find ~x which minimizes f (~x )subject to:gi (~x )  0, i = 1, . . . , mhj (~x ) = 0, j = 1, . . . , p~x 2 IRn is the vector of solutions ~x = [x1 , x2 , . . . , xn ]T .

Each xk , k = 1, ..., n is bounded by lower and upper limits
Lk  xk  Uk which define the search space S.

F comprises the set of all solutions which satisfy the constraintsof the problems and it is called the feasible region.
To handle equality constraints they are transformed into inequality
constraints as follows: hj (~x )"  0.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

4 / 156

Problem statement
Constrained numerical optimization problem (CNOP)
Find ~x which minimizes f (~x )subject to:gi (~x )  0, i = 1, . . . , mhj (~x ) = 0, j = 1, . . . , p~x 2 IRn is the vector of solutions ~x = [x1 , x2 , . . . , xn ]T .

Each xk , k = 1, ..., n is bounded by lower and upper limits
Lk  xk  Uk which define the search space S.

F comprises the set of all solutions which satisfy the constraintsof the problems and it is called the feasible region.
To handle equality constraints they are transformed into inequality
constraints as follows: hj (~x )"  0.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

4 / 156

Problem statement
Constrained numerical optimization problem (CNOP)
Find ~x which minimizes f (~x )subject to:gi (~x )  0, i = 1, . . . , mhj (~x ) = 0, j = 1, . . . , p~x 2 IRn is the vector of solutions ~x = [x1 , x2 , . . . , xn ]T .

Each xk , k = 1, ..., n is bounded by lower and upper limits
Lk  xk  Uk which define the search space S.

F comprises the set of all solutions which satisfy the constraintsof the problems and it is called the feasible region.
To handle equality constraints they are transformed into inequality
constraints as follows: hj (~x )"  0.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

4 / 156

Problem statement
Constrained numerical optimization problem (CNOP)
Find ~x which minimizes f (~x )subject to:gi (~x )  0, i = 1, . . . , mhj (~x ) = 0, j = 1, . . . , p~x 2 IRn is the vector of solutions ~x = [x1 , x2 , . . . , xn ]T .

Each xk , k = 1, ..., n is bounded by lower and upper limits
Lk  xk  Uk which define the search space S.

F comprises the set of all solutions which satisfy the constraintsof the problems and it is called the feasible region.
To handle equality constraints they are transformed into inequality
constraints as follows: hj (~x )"  0.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

4 / 156

Constrained numerical optimization problem
Constrained search space

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

5 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

6 / 156

Feasible global optimum

In the following definitions we will assume minimization (without loss ofgenerality). ~x ⇤ = [x1⇤ , x2⇤ , . . . , xn⇤ ]T refers to the feasible optimum point
and its corresponding value of the objective function f (~x ⇤ ) is called thefeasible optimum value. The pair ~x ⇤ and f (~x ⇤ ) is called feasible
optimum solution.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

7 / 156

Feasible global minimum

A function f (~x ) defined on a set S attains its feasible global minimum
at a point ~x ⇤ 2 F ✓ S if and only if: f (~x ⇤ )  f (~x ), 8~x 2 F ✓ S.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

8 / 156

Kuhn-Tucker Conditions

Kuhn and Tucker developed the necessary and sufficient
optimality conditions for the CNOP assuming that the functions f ,gi , and hj , are differentiable or twice-differentiable.
These optimality conditions, commonly known as the Kuhn-Tucker
conditions (KTC) consist of finding a solution to a system ofnonlinear equations.
However, it is quite difficult that KTC hold for real-world problems.
Therefore, the CNOP is an open-problem.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

9 / 156

Kuhn-Tucker Conditions

Kuhn and Tucker developed the necessary and sufficient
optimality conditions for the CNOP assuming that the functions f ,gi , and hj , are differentiable or twice-differentiable.
These optimality conditions, commonly known as the Kuhn-Tucker
conditions (KTC) consist of finding a solution to a system ofnonlinear equations.
However, it is quite difficult that KTC hold for real-world problems.
Therefore, the CNOP is an open-problem.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

9 / 156

Kuhn-Tucker Conditions

Kuhn and Tucker developed the necessary and sufficient
optimality conditions for the CNOP assuming that the functions f ,gi , and hj , are differentiable or twice-differentiable.
These optimality conditions, commonly known as the Kuhn-Tucker
conditions (KTC) consist of finding a solution to a system ofnonlinear equations.
However, it is quite difficult that KTC hold for real-world problems.
Therefore, the CNOP is an open-problem.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

9 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

10 / 156

Two categories

They usually require just one solution which is improved during
the process.
Two categories:
Direct Methods.
Indirect Methods.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

11 / 156

Two categories

They usually require just one solution which is improved during
the process.
Two categories:
Direct Methods.
Indirect Methods.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

11 / 156

Direct methods

These methods use only the information of the objective function tofind search directions.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

12 / 156

Indirect methods

These methods require that the objective function is differentiable ortwice differentiable so as to use such information to guide the search.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

13 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

14 / 156

Motivation

Despite the large number of mathematical programming methods
developed, several optimization problems present characteristics thatmake them difficult to solve using this kind of algorithms.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

15 / 156

Difficulties foundProblems with non-differentiable objective functions and/or
non-differentiable constraints.
Problems with disjoint feasible regions
Problems with objective function and/or constraints not available inalgebraic form.
Problems in which the Kuhn-Tucker conditions for optimality do not
hold.
Problems where no mathematical programming technique canguarantee convergence to the global optimum.
Huge search spaces.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

16 / 156

Difficulties foundProblems with non-differentiable objective functions and/or
non-differentiable constraints.
Problems with disjoint feasible regions
Problems with objective function and/or constraints not available inalgebraic form.
Problems in which the Kuhn-Tucker conditions for optimality do not
hold.
Problems where no mathematical programming technique canguarantee convergence to the global optimum.
Huge search spaces.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

16 / 156

Difficulties foundProblems with non-differentiable objective functions and/or
non-differentiable constraints.
Problems with disjoint feasible regions
Problems with objective function and/or constraints not available inalgebraic form.
Problems in which the Kuhn-Tucker conditions for optimality do not
hold.
Problems where no mathematical programming technique canguarantee convergence to the global optimum.
Huge search spaces.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

16 / 156

Difficulties foundProblems with non-differentiable objective functions and/or
non-differentiable constraints.
Problems with disjoint feasible regions
Problems with objective function and/or constraints not available inalgebraic form.
Problems in which the Kuhn-Tucker conditions for optimality do not
hold.
Problems where no mathematical programming technique canguarantee convergence to the global optimum.
Huge search spaces.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

16 / 156

Difficulties foundProblems with non-differentiable objective functions and/or
non-differentiable constraints.
Problems with disjoint feasible regions
Problems with objective function and/or constraints not available inalgebraic form.
Problems in which the Kuhn-Tucker conditions for optimality do not
hold.
Problems where no mathematical programming technique canguarantee convergence to the global optimum.
Huge search spaces.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

16 / 156

Difficulties foundProblems with non-differentiable objective functions and/or
non-differentiable constraints.
Problems with disjoint feasible regions
Problems with objective function and/or constraints not available inalgebraic form.
Problems in which the Kuhn-Tucker conditions for optimality do not
hold.
Problems where no mathematical programming technique canguarantee convergence to the global optimum.
Huge search spaces.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

16 / 156

Nature-inspired algorithms (NIAs)

Evolutionary algorithms (EAs) and swarm intelligence algorithms(SIAs) (grouped as NIAs) are popular meta-heuristics approaches
used to solve complex optimization problems.
NIAs are designed to deal with unconstrained search spaces.
The design and addition of a constraint-handling techniques into a
NIA to deal with a constrained search space is an open problem.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

17 / 156

Nature-inspired algorithms (NIAs)

Evolutionary algorithms (EAs) and swarm intelligence algorithms(SIAs) (grouped as NIAs) are popular meta-heuristics approaches
used to solve complex optimization problems.
NIAs are designed to deal with unconstrained search spaces.
The design and addition of a constraint-handling techniques into a
NIA to deal with a constrained search space is an open problem.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

17 / 156

Nature-inspired algorithms (NIAs)

Evolutionary algorithms (EAs) and swarm intelligence algorithms(SIAs) (grouped as NIAs) are popular meta-heuristics approaches
used to solve complex optimization problems.
NIAs are designed to deal with unconstrained search spaces.
The design and addition of a constraint-handling techniques into a
NIA to deal with a constrained search space is an open problem.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

17 / 156

Main components of a nature-inspired algorithm

1

Solution encoding.

2

Fitness function.

3

Initial population.

4

Parent selection.

5

Variation operators (crossover & mutation).

6

Replacement.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

18 / 156

Why the search must change?
Unconstrained optimization problem
Min: f (~x ) = (x12 + x2

11)2 + (x1 + x22 )2

Taken from Deb, K., Opt. for Eng. Design, Algorithms and Examples, Prentice-Hall, 1995.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

19 / 156

Why the search must change?
Unconstrained optimization problem

Taken from Deb, K., Opt. for Eng. Design, Algorithms and Examples, Prentice-Hall, 1995.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

20 / 156

Why the search must change?
Constrained optimization problem
Min: f (~x ) = (x12 + x2 11)2 + (x1 + x22 )2
subject to:(x1 5)2 + x22 26 0

Taken from Deb, K., Opt. for Eng. Design, Algorithms and Examples, Prentice-Hall, 1995.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

21 / 156

Why a constraint-handling technique?

The initial population (usually generated at random) may containseveral (if not all) infeasible solutions, and it may be difficult togenerate only feasible solutions from the beginning.
The information about feasibility must be incorporated into thefitness function to bias the search to the feasible region.
The parent selection and/or replacement must distinguishbetween feasible and infeasible solutions.
The variation operators are blind with respect to the constraints of
the optimization problem.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

22 / 156

Why a constraint-handling technique?

The initial population (usually generated at random) may containseveral (if not all) infeasible solutions, and it may be difficult togenerate only feasible solutions from the beginning.
The information about feasibility must be incorporated into thefitness function to bias the search to the feasible region.
The parent selection and/or replacement must distinguishbetween feasible and infeasible solutions.
The variation operators are blind with respect to the constraints of
the optimization problem.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

22 / 156

Why a constraint-handling technique?

The initial population (usually generated at random) may containseveral (if not all) infeasible solutions, and it may be difficult togenerate only feasible solutions from the beginning.
The information about feasibility must be incorporated into thefitness function to bias the search to the feasible region.
The parent selection and/or replacement must distinguishbetween feasible and infeasible solutions.
The variation operators are blind with respect to the constraints of
the optimization problem.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

22 / 156

Why a constraint-handling technique?

The initial population (usually generated at random) may containseveral (if not all) infeasible solutions, and it may be difficult togenerate only feasible solutions from the beginning.
The information about feasibility must be incorporated into thefitness function to bias the search to the feasible region.
The parent selection and/or replacement must distinguishbetween feasible and infeasible solutions.
The variation operators are blind with respect to the constraints of
the optimization problem.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

22 / 156

Constraint-handling over the years

Two classifications were proposed: one by Michalewicz andSchoenauer [96] and another one by Coello [18].
Both taxonomies agreed on penalty functions as a particular class.
This new classification for earlier methods is based on
constraint-handling mechanisms, whereas the search algorithm
employed is discussed as a separate issue.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

23 / 156

Constraint-handling over the years

Two classifications were proposed: one by Michalewicz andSchoenauer [96] and another one by Coello [18].
Both taxonomies agreed on penalty functions as a particular class.
This new classification for earlier methods is based on
constraint-handling mechanisms, whereas the search algorithm
employed is discussed as a separate issue.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

23 / 156

Constraint-handling over the years

Two classifications were proposed: one by Michalewicz andSchoenauer [96] and another one by Coello [18].
Both taxonomies agreed on penalty functions as a particular class.
This new classification for earlier methods is based on
constraint-handling mechanisms, whereas the search algorithm
employed is discussed as a separate issue.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

23 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

24 / 156

Penalty functions
Definition
Based on mathematical programming approaches, where a CNOP istransformed into an unconstrained numerical optimization problem,
NIAs have adopted penalty functions, whose general formula is thefollowing:(~x ) = f (~x ) + p(~x )where (~x ) is the expanded objective function to be optimized, andp(~x ) is the penalty value that can be calculated as follows:p(~x ) =

m
X
i=1

2

ri · max(0, gi (~x )) +

p
X
j=1

cj · |hj (~x )|where ri and cj are positive constants called “penalty factors”.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

25 / 156

Penalty functions
Pros and cons
The aim is to decrease the fitness of infeasible solutions.
Unlike mathematical programming approaches, where interior andexterior penalty functions are employed, NIAs have mainly
focused on the last ones.
Their implementation is quite simple ... but,
Penalty functions require a careful fine-tuning of their penalty
factors.
Such values usually are highly problem-dependent.
Different approaches have been proposed to tackle thisshortcoming.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

26 / 156

Penalty functions
Pros and cons
The aim is to decrease the fitness of infeasible solutions.
Unlike mathematical programming approaches, where interior andexterior penalty functions are employed, NIAs have mainly
focused on the last ones.
Their implementation is quite simple ... but,
Penalty functions require a careful fine-tuning of their penalty
factors.
Such values usually are highly problem-dependent.
Different approaches have been proposed to tackle thisshortcoming.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

26 / 156

Penalty functions
Pros and cons
The aim is to decrease the fitness of infeasible solutions.
Unlike mathematical programming approaches, where interior andexterior penalty functions are employed, NIAs have mainly
focused on the last ones.
Their implementation is quite simple ... but,
Penalty functions require a careful fine-tuning of their penalty
factors.
Such values usually are highly problem-dependent.
Different approaches have been proposed to tackle thisshortcoming.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

26 / 156

Penalty functions
Pros and cons
The aim is to decrease the fitness of infeasible solutions.
Unlike mathematical programming approaches, where interior andexterior penalty functions are employed, NIAs have mainly
focused on the last ones.
Their implementation is quite simple ... but,
Penalty functions require a careful fine-tuning of their penalty
factors.
Such values usually are highly problem-dependent.
Different approaches have been proposed to tackle thisshortcoming.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

26 / 156

Penalty functions
Pros and cons
The aim is to decrease the fitness of infeasible solutions.
Unlike mathematical programming approaches, where interior andexterior penalty functions are employed, NIAs have mainly
focused on the last ones.
Their implementation is quite simple ... but,
Penalty functions require a careful fine-tuning of their penalty
factors.
Such values usually are highly problem-dependent.
Different approaches have been proposed to tackle thisshortcoming.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

26 / 156

Penalty functions
Pros and cons
The aim is to decrease the fitness of infeasible solutions.
Unlike mathematical programming approaches, where interior andexterior penalty functions are employed, NIAs have mainly
focused on the last ones.
Their implementation is quite simple ... but,
Penalty functions require a careful fine-tuning of their penalty
factors.
Such values usually are highly problem-dependent.
Different approaches have been proposed to tackle thisshortcoming.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

26 / 156

Penalty functions

Death penalty
The most simple penalty function.
Infeasible solutions are assigned the worst possible fitness value
or are simply eliminated from the optimization process.
Keeps the search from using valuable information from infeasible
solutions.
Not suitable for very small feasible region with respect to thewhole search space.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

27 / 156

Penalty functions

Death penalty
The most simple penalty function.
Infeasible solutions are assigned the worst possible fitness value
or are simply eliminated from the optimization process.
Keeps the search from using valuable information from infeasible
solutions.
Not suitable for very small feasible region with respect to thewhole search space.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

27 / 156

Penalty functions

Death penalty
The most simple penalty function.
Infeasible solutions are assigned the worst possible fitness value
or are simply eliminated from the optimization process.
Keeps the search from using valuable information from infeasible
solutions.
Not suitable for very small feasible region with respect to thewhole search space.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

27 / 156

Penalty functions

Death penalty
The most simple penalty function.
Infeasible solutions are assigned the worst possible fitness value
or are simply eliminated from the optimization process.
Keeps the search from using valuable information from infeasible
solutions.
Not suitable for very small feasible region with respect to thewhole search space.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

27 / 156

Penalty functions

Static penalty functions
Those whose penalty factor values (ri and cj , i = 1, . . . , m andj = 1 . . . , m) remain fixed during all the process.
Kuri and Villegas-Quezada [59].
Homaifar et al. [43]. Hoffmeister and Sprave [42].
Le Riche et al. [112]).

The main drawback is the generalization of such type of approach,i.e., the values that may be suitable for one problem are normally
unsuitable for another one.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

28 / 156

Penalty functions

Static penalty functions
Those whose penalty factor values (ri and cj , i = 1, . . . , m andj = 1 . . . , m) remain fixed during all the process.
Kuri and Villegas-Quezada [59].
Homaifar et al. [43]. Hoffmeister and Sprave [42].
Le Riche et al. [112]).

The main drawback is the generalization of such type of approach,i.e., the values that may be suitable for one problem are normally
unsuitable for another one.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

28 / 156

Penalty functions
Dynamic penalty functions
Time (usually the generation counter in a NIA) is used to affect thepenalty factors.
Considering the usage of exterior penalty functions, soft penalties
are expected first, while severe penalties are adopted in the lastpart of the search.
Examples:Joines and Houck [48].
Kazarlis and Petridis[51].
Crossley and Williams [21].

The cooling factor of the simulated annealing algorithm has been
employed to vary the penalty factors by Michalewicz and Attia [94].
The main disadvantages of dynamic penalty functions are theparameters for their dynamic tuning and the difficulty to generalize
them.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

29 / 156

Penalty functions
Dynamic penalty functions
Time (usually the generation counter in a NIA) is used to affect thepenalty factors.
Considering the usage of exterior penalty functions, soft penalties
are expected first, while severe penalties are adopted in the lastpart of the search.
Examples:Joines and Houck [48].
Kazarlis and Petridis[51].
Crossley and Williams [21].

The cooling factor of the simulated annealing algorithm has been
employed to vary the penalty factors by Michalewicz and Attia [94].
The main disadvantages of dynamic penalty functions are theparameters for their dynamic tuning and the difficulty to generalize
them.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

29 / 156

Penalty functions
Dynamic penalty functions
Time (usually the generation counter in a NIA) is used to affect thepenalty factors.
Considering the usage of exterior penalty functions, soft penalties
are expected first, while severe penalties are adopted in the lastpart of the search.
Examples:Joines and Houck [48].
Kazarlis and Petridis[51].
Crossley and Williams [21].

The cooling factor of the simulated annealing algorithm has been
employed to vary the penalty factors by Michalewicz and Attia [94].
The main disadvantages of dynamic penalty functions are theparameters for their dynamic tuning and the difficulty to generalize
them.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

29 / 156

Penalty functions
Dynamic penalty functions
Time (usually the generation counter in a NIA) is used to affect thepenalty factors.
Considering the usage of exterior penalty functions, soft penalties
are expected first, while severe penalties are adopted in the lastpart of the search.
Examples:Joines and Houck [48].
Kazarlis and Petridis[51].
Crossley and Williams [21].

The cooling factor of the simulated annealing algorithm has been
employed to vary the penalty factors by Michalewicz and Attia [94].
The main disadvantages of dynamic penalty functions are theparameters for their dynamic tuning and the difficulty to generalize
them.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

29 / 156

Penalty functions
Dynamic penalty functions
Time (usually the generation counter in a NIA) is used to affect thepenalty factors.
Considering the usage of exterior penalty functions, soft penalties
are expected first, while severe penalties are adopted in the lastpart of the search.
Examples:Joines and Houck [48].
Kazarlis and Petridis[51].
Crossley and Williams [21].

The cooling factor of the simulated annealing algorithm has been
employed to vary the penalty factors by Michalewicz and Attia [94].
The main disadvantages of dynamic penalty functions are theparameters for their dynamic tuning and the difficulty to generalize
them.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

29 / 156

Penalty functions
Adaptive penalty functions
The behavior of the NIA is used to update the penalty factors.
Feasibility of the best solution in a number of generations by
Hadj-Alouane and Bean [34].
The fitness of the best feasible solution by Rasheed [105].
The balance between feasible and infeasible solutions by Hamda
and Schoenauer [35] and Hamida and Schoenauer [36].
The average of the objective function and the level of violation ofeach constraint by Barbosa and Lemonge [11].
Co-evolution by Coello [20].
Fuzzy logic by Wu and Yu [150].
Their main drawback lies in the following: there is no guaranteethat the values defined based on the current behavior will beindeed useful later.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

30 / 156

Penalty functions
Adaptive penalty functions
The behavior of the NIA is used to update the penalty factors.
Feasibility of the best solution in a number of generations by
Hadj-Alouane and Bean [34].
The fitness of the best feasible solution by Rasheed [105].
The balance between feasible and infeasible solutions by Hamda
and Schoenauer [35] and Hamida and Schoenauer [36].
The average of the objective function and the level of violation ofeach constraint by Barbosa and Lemonge [11].
Co-evolution by Coello [20].
Fuzzy logic by Wu and Yu [150].
Their main drawback lies in the following: there is no guaranteethat the values defined based on the current behavior will beindeed useful later.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

30 / 156

Penalty functions
Adaptive penalty functions
The behavior of the NIA is used to update the penalty factors.
Feasibility of the best solution in a number of generations by
Hadj-Alouane and Bean [34].
The fitness of the best feasible solution by Rasheed [105].
The balance between feasible and infeasible solutions by Hamda
and Schoenauer [35] and Hamida and Schoenauer [36].
The average of the objective function and the level of violation ofeach constraint by Barbosa and Lemonge [11].
Co-evolution by Coello [20].
Fuzzy logic by Wu and Yu [150].
Their main drawback lies in the following: there is no guaranteethat the values defined based on the current behavior will beindeed useful later.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

30 / 156

Penalty functions
Adaptive penalty functions
The behavior of the NIA is used to update the penalty factors.
Feasibility of the best solution in a number of generations by
Hadj-Alouane and Bean [34].
The fitness of the best feasible solution by Rasheed [105].
The balance between feasible and infeasible solutions by Hamda
and Schoenauer [35] and Hamida and Schoenauer [36].
The average of the objective function and the level of violation ofeach constraint by Barbosa and Lemonge [11].
Co-evolution by Coello [20].
Fuzzy logic by Wu and Yu [150].
Their main drawback lies in the following: there is no guaranteethat the values defined based on the current behavior will beindeed useful later.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

30 / 156

Penalty functions
Adaptive penalty functions
The behavior of the NIA is used to update the penalty factors.
Feasibility of the best solution in a number of generations by
Hadj-Alouane and Bean [34].
The fitness of the best feasible solution by Rasheed [105].
The balance between feasible and infeasible solutions by Hamda
and Schoenauer [35] and Hamida and Schoenauer [36].
The average of the objective function and the level of violation ofeach constraint by Barbosa and Lemonge [11].
Co-evolution by Coello [20].
Fuzzy logic by Wu and Yu [150].
Their main drawback lies in the following: there is no guaranteethat the values defined based on the current behavior will beindeed useful later.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

30 / 156

Penalty functions
Adaptive penalty functions
The behavior of the NIA is used to update the penalty factors.
Feasibility of the best solution in a number of generations by
Hadj-Alouane and Bean [34].
The fitness of the best feasible solution by Rasheed [105].
The balance between feasible and infeasible solutions by Hamda
and Schoenauer [35] and Hamida and Schoenauer [36].
The average of the objective function and the level of violation ofeach constraint by Barbosa and Lemonge [11].
Co-evolution by Coello [20].
Fuzzy logic by Wu and Yu [150].
Their main drawback lies in the following: there is no guaranteethat the values defined based on the current behavior will beindeed useful later.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

30 / 156

Penalty functions
Adaptive penalty functions
The behavior of the NIA is used to update the penalty factors.
Feasibility of the best solution in a number of generations by
Hadj-Alouane and Bean [34].
The fitness of the best feasible solution by Rasheed [105].
The balance between feasible and infeasible solutions by Hamda
and Schoenauer [35] and Hamida and Schoenauer [36].
The average of the objective function and the level of violation ofeach constraint by Barbosa and Lemonge [11].
Co-evolution by Coello [20].
Fuzzy logic by Wu and Yu [150].
Their main drawback lies in the following: there is no guaranteethat the values defined based on the current behavior will beindeed useful later.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

30 / 156

Penalty functions
Adaptive penalty functions
The behavior of the NIA is used to update the penalty factors.
Feasibility of the best solution in a number of generations by
Hadj-Alouane and Bean [34].
The fitness of the best feasible solution by Rasheed [105].
The balance between feasible and infeasible solutions by Hamda
and Schoenauer [35] and Hamida and Schoenauer [36].
The average of the objective function and the level of violation ofeach constraint by Barbosa and Lemonge [11].
Co-evolution by Coello [20].
Fuzzy logic by Wu and Yu [150].
Their main drawback lies in the following: there is no guaranteethat the values defined based on the current behavior will beindeed useful later.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

30 / 156

Penalty functions

Discussion
Diverse ways to define penalty factors (static, dynamic, adaptive,
co-evolved, fuzzy-adapted, etc.).
Not clear which approach was more competitive.
Most of the time, additional parameters were required.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

31 / 156

Penalty functions

Discussion
Diverse ways to define penalty factors (static, dynamic, adaptive,
co-evolved, fuzzy-adapted, etc.).
Not clear which approach was more competitive.
Most of the time, additional parameters were required.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

31 / 156

Penalty functions

Discussion
Diverse ways to define penalty factors (static, dynamic, adaptive,
co-evolved, fuzzy-adapted, etc.).
Not clear which approach was more competitive.
Most of the time, additional parameters were required.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

31 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

32 / 156

Decoders
One of the most competitive constraint-handling techniques in theearly years.
They are based on the idea of mapping the feasible region F of
the search space S onto an easier-to-sample space where a NIA
can provide a better performance [56].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

33 / 156

Decoders
One of the most competitive constraint-handling techniques in theearly years.
They are based on the idea of mapping the feasible region F of
the search space S onto an easier-to-sample space where a NIA
can provide a better performance [56].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

33 / 156

Decoders

The mapping process must guarantee that each feasible solution
in the search space is included in the decoded space and that a
decoded solution corresponds to a feasible solution in the search
space.
The transformation process must be fast and it is highly desirable
that small changes in the search space of the original problem
cause small changes in the decoded space as well.
Homomorphous maps: the feasible region is mapped into ann-dimensional cube, by Koziel and Michalewicz [56, 57].
Riemann mappings by Kim and Husbands [52, 53, 54].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

34 / 156

Decoders

The mapping process must guarantee that each feasible solution
in the search space is included in the decoded space and that a
decoded solution corresponds to a feasible solution in the search
space.
The transformation process must be fast and it is highly desirable
that small changes in the search space of the original problem
cause small changes in the decoded space as well.
Homomorphous maps: the feasible region is mapped into ann-dimensional cube, by Koziel and Michalewicz [56, 57].
Riemann mappings by Kim and Husbands [52, 53, 54].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

34 / 156

Decoders

Discussion
Their actual implementation is far from trivial.
They may involve a computational cost.
Decoders are rarely used nowadays.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

35 / 156

Decoders

Discussion
Their actual implementation is far from trivial.
They may involve a computational cost.
Decoders are rarely used nowadays.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

35 / 156

Decoders

Discussion
Their actual implementation is far from trivial.
They may involve a computational cost.
Decoders are rarely used nowadays.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

35 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

36 / 156

Special operators
A special operator is conceived as a way of either preserving thefeasibility of a solution or moving within a specific region ofinterest within the search space.
A variation operator which constructs linear combinations offeasible solutions to preserve their feasibility (GENOCOP) by
Michalewicz [93].
Special operators designed to convert solutions which only satisfy
linear constraints into fully feasible solutions (GENOCOP III) by
Michalewicz and Nazhiyath [95].
Special operators to assign values to the decision variables
aiming to keep the feasibility of the solution by Kowalczyk [55].
Special operators for two specific problems to sample theboundaries of their feasible regions by Schoenauer andMichalewicz [116, 117].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

37 / 156

Special operators
A special operator is conceived as a way of either preserving thefeasibility of a solution or moving within a specific region ofinterest within the search space.
A variation operator which constructs linear combinations offeasible solutions to preserve their feasibility (GENOCOP) by
Michalewicz [93].
Special operators designed to convert solutions which only satisfy
linear constraints into fully feasible solutions (GENOCOP III) by
Michalewicz and Nazhiyath [95].
Special operators to assign values to the decision variables
aiming to keep the feasibility of the solution by Kowalczyk [55].
Special operators for two specific problems to sample theboundaries of their feasible regions by Schoenauer andMichalewicz [116, 117].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

37 / 156

Special operators
A special operator is conceived as a way of either preserving thefeasibility of a solution or moving within a specific region ofinterest within the search space.
A variation operator which constructs linear combinations offeasible solutions to preserve their feasibility (GENOCOP) by
Michalewicz [93].
Special operators designed to convert solutions which only satisfy
linear constraints into fully feasible solutions (GENOCOP III) by
Michalewicz and Nazhiyath [95].
Special operators to assign values to the decision variables
aiming to keep the feasibility of the solution by Kowalczyk [55].
Special operators for two specific problems to sample theboundaries of their feasible regions by Schoenauer andMichalewicz [116, 117].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

37 / 156

Special operators
A special operator is conceived as a way of either preserving thefeasibility of a solution or moving within a specific region ofinterest within the search space.
A variation operator which constructs linear combinations offeasible solutions to preserve their feasibility (GENOCOP) by
Michalewicz [93].
Special operators designed to convert solutions which only satisfy
linear constraints into fully feasible solutions (GENOCOP III) by
Michalewicz and Nazhiyath [95].
Special operators to assign values to the decision variables
aiming to keep the feasibility of the solution by Kowalczyk [55].
Special operators for two specific problems to sample theboundaries of their feasible regions by Schoenauer andMichalewicz [116, 117].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

37 / 156

Special operators
A special operator is conceived as a way of either preserving thefeasibility of a solution or moving within a specific region ofinterest within the search space.
A variation operator which constructs linear combinations offeasible solutions to preserve their feasibility (GENOCOP) by
Michalewicz [93].
Special operators designed to convert solutions which only satisfy
linear constraints into fully feasible solutions (GENOCOP III) by
Michalewicz and Nazhiyath [95].
Special operators to assign values to the decision variables
aiming to keep the feasibility of the solution by Kowalczyk [55].
Special operators for two specific problems to sample theboundaries of their feasible regions by Schoenauer andMichalewicz [116, 117].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

37 / 156

Special operators

Discussion
Highly competitive results can be found when adopting special
operators.
Their main drawback is their limited applicability.
Most of them require an ad-hoc initialization process or at least
one feasible or partially-feasible solution in the initial population.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

38 / 156

Special operators

Discussion
Highly competitive results can be found when adopting special
operators.
Their main drawback is their limited applicability.
Most of them require an ad-hoc initialization process or at least
one feasible or partially-feasible solution in the initial population.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

38 / 156

Special operators

Discussion
Highly competitive results can be found when adopting special
operators.
Their main drawback is their limited applicability.
Most of them require an ad-hoc initialization process or at least
one feasible or partially-feasible solution in the initial population.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

38 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

39 / 156

Separation of objective function and constraints

Unlike combining the objective function and the values of theconstraints into a single value (i.e. penalty function), there areconstraint-handling techniques which work with the opposite idea.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

40 / 156

Separation of objective function and constraints

Powell and Skolnick in [103] proposed an approach based on thefollowing Equation.

fitness(~x ) =(f (~x ) ⇣1+r

Pm

i=1 gi (x ) +~⌘ if feasible~
otherwise
j=1 hj (x )Ppwhere a feasible solution has always a better fitness value withrespect to that of an infeasible solution, whose fitness is based
only on their accumulated constraint violation.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

41 / 156

Separation of objective function and constraints

Hinterding and Michalewicz in [41] proposed the idea of dividing
the search in two phases: (1) finding feasible solutions, regardlessof the objective function value, and (2) after a suitable number offeasible solutions has been found, optimizing the objectivefunction.
Such idea was revisited by Venkatraman and Yen [138].
Schoenauer and Xanthakis in [118] proposed a lexicographic
ordering (behavioral memory) to satisfy constraints, i.e., when acertain number of solutions in the population satisfy the first
constraint, an attempt to satisfy the second one is made (but thefirst constraint must continue to be satisfied), and so on.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

42 / 156

Separation of objective function and constraints

Hinterding and Michalewicz in [41] proposed the idea of dividing
the search in two phases: (1) finding feasible solutions, regardlessof the objective function value, and (2) after a suitable number offeasible solutions has been found, optimizing the objectivefunction.
Such idea was revisited by Venkatraman and Yen [138].
Schoenauer and Xanthakis in [118] proposed a lexicographic
ordering (behavioral memory) to satisfy constraints, i.e., when acertain number of solutions in the population satisfy the first
constraint, an attempt to satisfy the second one is made (but thefirst constraint must continue to be satisfied), and so on.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

42 / 156

Separation of objective function and constraints

Hinterding and Michalewicz in [41] proposed the idea of dividing
the search in two phases: (1) finding feasible solutions, regardlessof the objective function value, and (2) after a suitable number offeasible solutions has been found, optimizing the objectivefunction.
Such idea was revisited by Venkatraman and Yen [138].
Schoenauer and Xanthakis in [118] proposed a lexicographic
ordering (behavioral memory) to satisfy constraints, i.e., when acertain number of solutions in the population satisfy the first
constraint, an attempt to satisfy the second one is made (but thefirst constraint must continue to be satisfied), and so on.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

42 / 156

Separation of objective function and constraints
Deb [25] proposed a set of three feasibility criteria as follows:1

2

3

When comparing two feasible solutions, the one with the best
objective function is chosen.
When comparing a feasible and an infeasible solution, the feasible
one is chosen.
When comparing two infeasible solutions, the one with the lowest
sum of constraint violation is chosen.

The sum of constraint violation can be calculated as follows:(~x ) =mX

max(0, gi (~x ))2 +i=1

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

p
X
j=1

|hj (~x )|CEC 2017, SPAIN

43 / 156

Separation of objective function and constraints
Different multi-population schemes have been proposed.
Coello [19] divided a GA-population into sub-populations and each
sub-population tried to satisfy one constraint of a CNOP andanother one optimized the objective function.
Liang and Suganthan proposed a dynamic assignment of
sub-swarms to constraints in PSO [67].
The approach was further improved in [68], where only two
sub-swarms, one of them with a tolerance for inequality
constraints, were used. Each particle, and not a sub-swarm, wasdynamically assigned the objective function or the constraint, insuch a way that more difficult objectives to optimize (satisfy) wereassigned more frequently.
Li et al. [66] adopted a similar approach but using DE as a searchalgorithm.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

44 / 156

Separation of objective function and constraints
Different multi-population schemes have been proposed.
Coello [19] divided a GA-population into sub-populations and each
sub-population tried to satisfy one constraint of a CNOP andanother one optimized the objective function.
Liang and Suganthan proposed a dynamic assignment of
sub-swarms to constraints in PSO [67].
The approach was further improved in [68], where only two
sub-swarms, one of them with a tolerance for inequality
constraints, were used. Each particle, and not a sub-swarm, wasdynamically assigned the objective function or the constraint, insuch a way that more difficult objectives to optimize (satisfy) wereassigned more frequently.
Li et al. [66] adopted a similar approach but using DE as a searchalgorithm.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

44 / 156

Separation of objective function and constraints
Different multi-population schemes have been proposed.
Coello [19] divided a GA-population into sub-populations and each
sub-population tried to satisfy one constraint of a CNOP andanother one optimized the objective function.
Liang and Suganthan proposed a dynamic assignment of
sub-swarms to constraints in PSO [67].
The approach was further improved in [68], where only two
sub-swarms, one of them with a tolerance for inequality
constraints, were used. Each particle, and not a sub-swarm, wasdynamically assigned the objective function or the constraint, insuch a way that more difficult objectives to optimize (satisfy) wereassigned more frequently.
Li et al. [66] adopted a similar approach but using DE as a searchalgorithm.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

44 / 156

Separation of objective function and constraints
Different multi-population schemes have been proposed.
Coello [19] divided a GA-population into sub-populations and each
sub-population tried to satisfy one constraint of a CNOP andanother one optimized the objective function.
Liang and Suganthan proposed a dynamic assignment of
sub-swarms to constraints in PSO [67].
The approach was further improved in [68], where only two
sub-swarms, one of them with a tolerance for inequality
constraints, were used. Each particle, and not a sub-swarm, wasdynamically assigned the objective function or the constraint, insuch a way that more difficult objectives to optimize (satisfy) wereassigned more frequently.
Li et al. [66] adopted a similar approach but using DE as a searchalgorithm.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

44 / 156

Separation of objective function and constraints
Different multi-population schemes have been proposed.
Coello [19] divided a GA-population into sub-populations and each
sub-population tried to satisfy one constraint of a CNOP andanother one optimized the objective function.
Liang and Suganthan proposed a dynamic assignment of
sub-swarms to constraints in PSO [67].
The approach was further improved in [68], where only two
sub-swarms, one of them with a tolerance for inequality
constraints, were used. Each particle, and not a sub-swarm, wasdynamically assigned the objective function or the constraint, insuch a way that more difficult objectives to optimize (satisfy) wereassigned more frequently.
Li et al. [66] adopted a similar approach but using DE as a searchalgorithm.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

44 / 156

Separation of objective function and constraints

Liu et al. [69] proposed a separation scheme based on aco-evolutionary approach in which two populations are adopted.
The first one optimized the objective function without considering
the constraints, while the second population aimed to satisfy theconstraints of the problem. Each population could migrate
solutions to the other.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

45 / 156

Separation of objective function and constraints

Multi-objective optimization concepts (Pareto dominance andPareto ranking) have been quite popular to solve constrained
optimization problems [84]. Two groups can be identified:
1

2

CNOP as a bi-objective problem (the original objective function andthe sum of constraint violation).
CNOP as a multi-objective optimization problem (the original
objective function and each constraint are handled as objectives).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

46 / 156

Separation of objective function and constraints

The main shortcomings are related to the lack of bias provided by
Pareto ranking when used in a straightforward manner [115], andthe difficulties of these approaches to preserve diversity in the
population [84].
Additional mechanisms have been adopted such as Pareto
ranking in different search spaces [106, 107, 1, 4], the shrinking of
the search space [40] and the use of non-dominated sorting andclustering techniques to generate collaboration among
sub-populations [108].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

47 / 156

Separation of objective function and constraints

The main shortcomings are related to the lack of bias provided by
Pareto ranking when used in a straightforward manner [115], andthe difficulties of these approaches to preserve diversity in the
population [84].
Additional mechanisms have been adopted such as Pareto
ranking in different search spaces [106, 107, 1, 4], the shrinking of
the search space [40] and the use of non-dominated sorting andclustering techniques to generate collaboration among
sub-populations [108].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

47 / 156

Separation of objective function and constraints

Discussion
This type of constraint-handling technique has been found to
generate an important diversity loss.
It is important to design appropriate diversity maintenancemechanisms.
However, they are quite popular (usually no additional parameters
required and easy to generalize).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

48 / 156

Separation of objective function and constraints

Discussion
This type of constraint-handling technique has been found to
generate an important diversity loss.
It is important to design appropriate diversity maintenancemechanisms.
However, they are quite popular (usually no additional parameters
required and easy to generalize).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

48 / 156

Separation of objective function and constraints

Discussion
This type of constraint-handling technique has been found to
generate an important diversity loss.
It is important to design appropriate diversity maintenancemechanisms.
However, they are quite popular (usually no additional parameters
required and easy to generalize).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

48 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

49 / 156

General comments

The first attempts to generate constraint-handling techniques weresimilar to an exploration phase, in which a variety of approaches
were proposed.
Main shortcomings:
Unsuitable bias.
Need of a careful fine-tuning of parameters.
Difficult to generalize.
High computational cost and difficult implementations.

The exploitation phase was about to begin.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

50 / 156

General comments

The first attempts to generate constraint-handling techniques weresimilar to an exploration phase, in which a variety of approaches
were proposed.
Main shortcomings:
Unsuitable bias.
Need of a careful fine-tuning of parameters.
Difficult to generalize.
High computational cost and difficult implementations.

The exploitation phase was about to begin.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

50 / 156

General comments

The first attempts to generate constraint-handling techniques weresimilar to an exploration phase, in which a variety of approaches
were proposed.
Main shortcomings:
Unsuitable bias.
Need of a careful fine-tuning of parameters.
Difficult to generalize.
High computational cost and difficult implementations.

The exploitation phase was about to begin.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

50 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

51 / 156

Feasibility rules

The feasibility rules proposed by Deb [25, 100] constitute an
example of a constraint-handling technique that was proposedseveral years ago, but whose impact is still present in theliterature.
Its popularity lies on its ability to be coupled to a variety ofalgorithms, without introducing new parameters.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

52 / 156

Feasibility rules

The feasibility rules proposed by Deb [25, 100] constitute an
example of a constraint-handling technique that was proposedseveral years ago, but whose impact is still present in theliterature.
Its popularity lies on its ability to be coupled to a variety ofalgorithms, without introducing new parameters.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

52 / 156

Feasibility rules
Studies on other topics
Parameter control mechanisms in DE-based constrained
numerical optimization by Palomeque and Mezura-Montes (DEself-adaptive parameters, including diversity parameters) [89] andby Zielinski et al. (DE adaptive parameters) [162].
Zielinski and Laur [160] explored different termination conditions(e.g., improvement-based criteria, movement-based criteria,
distribution-based criteria) for DE in constrained optimization.
Zielinski and Laur [161] studied the effect of the tolerance utilized
in the equality constraints, where values between ✏ = 1 ⇥ 10 7and ✏ = 1 ⇥ 10 15 allowed the algorithm, coupled with thefeasibility rules, to reach competitive results.
Mezura-Montes and Coello Coello [83] explored diversity
mechanisms to improve the performance of evolution strategies
when solving CNOPs.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

53 / 156

Feasibility rules
Studies on other topics
Parameter control mechanisms in DE-based constrained
numerical optimization by Palomeque and Mezura-Montes (DEself-adaptive parameters, including diversity parameters) [89] andby Zielinski et al. (DE adaptive parameters) [162].
Zielinski and Laur [160] explored different termination conditions(e.g., improvement-based criteria, movement-based criteria,
distribution-based criteria) for DE in constrained optimization.
Zielinski and Laur [161] studied the effect of the tolerance utilized
in the equality constraints, where values between ✏ = 1 ⇥ 10 7and ✏ = 1 ⇥ 10 15 allowed the algorithm, coupled with thefeasibility rules, to reach competitive results.
Mezura-Montes and Coello Coello [83] explored diversity
mechanisms to improve the performance of evolution strategies
when solving CNOPs.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

53 / 156

Feasibility rules
Studies on other topics
Parameter control mechanisms in DE-based constrained
numerical optimization by Palomeque and Mezura-Montes (DEself-adaptive parameters, including diversity parameters) [89] andby Zielinski et al. (DE adaptive parameters) [162].
Zielinski and Laur [160] explored different termination conditions(e.g., improvement-based criteria, movement-based criteria,
distribution-based criteria) for DE in constrained optimization.
Zielinski and Laur [161] studied the effect of the tolerance utilized
in the equality constraints, where values between ✏ = 1 ⇥ 10 7and ✏ = 1 ⇥ 10 15 allowed the algorithm, coupled with thefeasibility rules, to reach competitive results.
Mezura-Montes and Coello Coello [83] explored diversity
mechanisms to improve the performance of evolution strategies
when solving CNOPs.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

53 / 156

Feasibility rules
Studies on other topics
Parameter control mechanisms in DE-based constrained
numerical optimization by Palomeque and Mezura-Montes (DEself-adaptive parameters, including diversity parameters) [89] andby Zielinski et al. (DE adaptive parameters) [162].
Zielinski and Laur [160] explored different termination conditions(e.g., improvement-based criteria, movement-based criteria,
distribution-based criteria) for DE in constrained optimization.
Zielinski and Laur [161] studied the effect of the tolerance utilized
in the equality constraints, where values between ✏ = 1 ⇥ 10 7and ✏ = 1 ⇥ 10 15 allowed the algorithm, coupled with thefeasibility rules, to reach competitive results.
Mezura-Montes and Coello Coello [83] explored diversity
mechanisms to improve the performance of evolution strategies
when solving CNOPs.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

53 / 156

Feasibility rules

Multi-operator mechanisms
The use of feasibility rules has favored the development ofapproaches with self-adaptive variation operator selection
mechanisms on DE:
jDE-2 by Brest [14], where different variants are combined with aninjection of solutions generated at random
SaDE by Huang et al. [46], where, besides the combination of DE
variants, SQP is adopted as a local search operator.
Four DE variants with four sub-populations with fixed-dynamic size
and migration by Elsayed et al. [80].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

54 / 156

Feasibility rules

Multi-operator mechanisms
The use of feasibility rules has favored the development ofapproaches with self-adaptive variation operator selection
mechanisms on DE:
jDE-2 by Brest [14], where different variants are combined with aninjection of solutions generated at random
SaDE by Huang et al. [46], where, besides the combination of DE
variants, SQP is adopted as a local search operator.
Four DE variants with four sub-populations with fixed-dynamic size
and migration by Elsayed et al. [80].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

54 / 156

Feasibility rules

Multi-operator mechanisms
The use of feasibility rules has favored the development ofapproaches with self-adaptive variation operator selection
mechanisms on DE:
jDE-2 by Brest [14], where different variants are combined with aninjection of solutions generated at random
SaDE by Huang et al. [46], where, besides the combination of DE
variants, SQP is adopted as a local search operator.
Four DE variants with four sub-populations with fixed-dynamic size
and migration by Elsayed et al. [80].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

54 / 156

Feasibility rules

Multi-operator mechanisms
The use of feasibility rules has favored the development ofapproaches with self-adaptive variation operator selection
mechanisms on DE:
jDE-2 by Brest [14], where different variants are combined with aninjection of solutions generated at random
SaDE by Huang et al. [46], where, besides the combination of DE
variants, SQP is adopted as a local search operator.
Four DE variants with four sub-populations with fixed-dynamic size
and migration by Elsayed et al. [80].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

54 / 156

Feasibility rules

Multi-operator mechanisms... and studies on PSO:
A combination of global-local best PSO with dynamic mutation
operator by Cagnina et al.[17]. Due to stagnation in some test
problems, a further version of this approach was proposed by thesame authors in [16], where a bi-population scheme and a “shake”
operator were added [16].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

55 / 156

Feasibility rules

Multi-operator mechanisms... and studies on PSO:
A combination of global-local best PSO with dynamic mutation
operator by Cagnina et al.[17]. Due to stagnation in some test
problems, a further version of this approach was proposed by thesame authors in [16], where a bi-population scheme and a “shake”
operator were added [16].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

55 / 156

Feasibility rules
Multi-operator mechanisms
and also on GAs.
Elsayed et al. implemented their four sub-population scheme with
GAs in [80].
Elsayed et al. [28] proposed a modified GA where a novel
crossover operator called multi-parent crossover and also a
randomized operator were added to a real-coded GA.
Elsayed et al. [27] compared ten different GA variants. The
crossover operators employed were triangular crossover,
Simulated binary crossover, parent-centric crossover, simplex
crossover, and blend crossover. The mutation operators adopted
were non-uniform mutation and polynomial crossover.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

56 / 156

Feasibility rules
Multi-operator mechanisms
and also on GAs.
Elsayed et al. implemented their four sub-population scheme with
GAs in [80].
Elsayed et al. [28] proposed a modified GA where a novel
crossover operator called multi-parent crossover and also a
randomized operator were added to a real-coded GA.
Elsayed et al. [27] compared ten different GA variants. The
crossover operators employed were triangular crossover,
Simulated binary crossover, parent-centric crossover, simplex
crossover, and blend crossover. The mutation operators adopted
were non-uniform mutation and polynomial crossover.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

56 / 156

Feasibility rules
Multi-operator mechanisms
and also on GAs.
Elsayed et al. implemented their four sub-population scheme with
GAs in [80].
Elsayed et al. [28] proposed a modified GA where a novel
crossover operator called multi-parent crossover and also a
randomized operator were added to a real-coded GA.
Elsayed et al. [27] compared ten different GA variants. The
crossover operators employed were triangular crossover,
Simulated binary crossover, parent-centric crossover, simplex
crossover, and blend crossover. The mutation operators adopted
were non-uniform mutation and polynomial crossover.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

56 / 156

Feasibility rules
Multi-operator mechanisms
and also on GAs.
Elsayed et al. implemented their four sub-population scheme with
GAs in [80].
Elsayed et al. [28] proposed a modified GA where a novel
crossover operator called multi-parent crossover and also a
randomized operator were added to a real-coded GA.
Elsayed et al. [27] compared ten different GA variants. The
crossover operators employed were triangular crossover,
Simulated binary crossover, parent-centric crossover, simplex
crossover, and blend crossover. The mutation operators adopted
were non-uniform mutation and polynomial crossover.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

56 / 156

Feasibility rules
Combination with special operators
Barkat Ullah [135] designed a mechanism to force infeasible
individuals to move to the feasible region through the applicationof search space reduction and diversity checking mechanisms
designed to avoid premature convergence.
Mezura-Montes and Cetina-Domı́ngez [82] proposed a special
operator designed to locate infeasible solutions close to the best
feasible solution.
A more recent version was proposed by the authors in [92], where
two operators were improved and a direct-search local operator
was added to the algorithm.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

57 / 156

Feasibility rules
Combination with special operators
Barkat Ullah [135] designed a mechanism to force infeasible
individuals to move to the feasible region through the applicationof search space reduction and diversity checking mechanisms
designed to avoid premature convergence.
Mezura-Montes and Cetina-Domı́ngez [82] proposed a special
operator designed to locate infeasible solutions close to the best
feasible solution.
A more recent version was proposed by the authors in [92], where
two operators were improved and a direct-search local operator
was added to the algorithm.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

57 / 156

Feasibility rules
Combination with special operators
Barkat Ullah [135] designed a mechanism to force infeasible
individuals to move to the feasible region through the applicationof search space reduction and diversity checking mechanisms
designed to avoid premature convergence.
Mezura-Montes and Cetina-Domı́ngez [82] proposed a special
operator designed to locate infeasible solutions close to the best
feasible solution.
A more recent version was proposed by the authors in [92], where
two operators were improved and a direct-search local operator
was added to the algorithm.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

57 / 156

Feasibility rules
Adapted to DE
Zielinski and Laur [159] coupled DE with the feasibility rules in a
greedy selection scheme between target and trial vectors.
Lampinen used a similar DE-based approach in [60]. However,
the third criterion (originally based on the sum of constraint
violation) was based on Pareto dominance in constraints space.
Kukkonen and Lampinen proposed their Generalized Differential
Evolution (GDE) [58] based on the aforementioned idea.
Mezura-Montes et al. [85, 90, 91] proposed a new DE variant
coupled with the ability to generate more than one offspring per
parent.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

58 / 156

Feasibility rules
Adapted to DE
Zielinski and Laur [159] coupled DE with the feasibility rules in a
greedy selection scheme between target and trial vectors.
Lampinen used a similar DE-based approach in [60]. However,
the third criterion (originally based on the sum of constraint
violation) was based on Pareto dominance in constraints space.
Kukkonen and Lampinen proposed their Generalized Differential
Evolution (GDE) [58] based on the aforementioned idea.
Mezura-Montes et al. [85, 90, 91] proposed a new DE variant
coupled with the ability to generate more than one offspring per
parent.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

58 / 156

Feasibility rules
Adapted to DE
Zielinski and Laur [159] coupled DE with the feasibility rules in a
greedy selection scheme between target and trial vectors.
Lampinen used a similar DE-based approach in [60]. However,
the third criterion (originally based on the sum of constraint
violation) was based on Pareto dominance in constraints space.
Kukkonen and Lampinen proposed their Generalized Differential
Evolution (GDE) [58] based on the aforementioned idea.
Mezura-Montes et al. [85, 90, 91] proposed a new DE variant
coupled with the ability to generate more than one offspring per
parent.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

58 / 156

Feasibility rules

Adapted to artificial immune systems
Cruz et al. [22] and Aragón et al. [6], based on the clonal selection
principle used the feasibility rules to rank antibodies based onaffinity.
Aragón et al. [7], based on a T-cell model in which three types ofcells (solutions) are adopted, used the feasibility rules as thecriteria in the replacement process.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

59 / 156

Feasibility rules

Adapted to artificial immune systems
Cruz et al. [22] and Aragón et al. [6], based on the clonal selection
principle used the feasibility rules to rank antibodies based onaffinity.
Aragón et al. [7], based on a T-cell model in which three types ofcells (solutions) are adopted, used the feasibility rules as thecriteria in the replacement process.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

59 / 156

Feasibility rules

Adapted to artificial bee colony
Karaboga and Basturk [50] and Karaboga and Akay [49] changed
a greedy selection based only on the objective function values by
the use of the feasibility rules with the aim of adapting an artificial
bee colony algorithm (ABC) to solve CNOPs.
Mezura-Montes and Cetina-Domı́nguez [82] and Mezura-Montes
and Velez-Koeppel [92] combined ABC with a smart-flight and alocal-search operator, respectively, to improve its performance inconstrained search spaces.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

60 / 156

Feasibility rules

Adapted to artificial bee colony
Karaboga and Basturk [50] and Karaboga and Akay [49] changed
a greedy selection based only on the objective function values by
the use of the feasibility rules with the aim of adapting an artificial
bee colony algorithm (ABC) to solve CNOPs.
Mezura-Montes and Cetina-Domı́nguez [82] and Mezura-Montes
and Velez-Koeppel [92] combined ABC with a smart-flight and alocal-search operator, respectively, to improve its performance inconstrained search spaces.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

60 / 156

Feasibility rules
Adapted to other NIAs
Ma and Simon [76] proposed an improved version of thebiogeography-based optimization (BBO) algorithm (inspired on the
study of distributions of species over time and space) with thefeasibility rules as criteria to choose solutions with the so-called“habitat suitability index”.
Liu et al. [72] proposed the organizational evolutionary algorithm(OEA). A static penalty function and the feasibility rules werecompared as constraint-handling techniques.
Mezura-Montes and Hernández-Ocaña [88] used the feasibility
rules with the Bacterial Foraging Optimization Algorithm (BFOA) inthe greedy selection mechanism within the chemotactic loop.
Landa and Coello [61] adopted the rules in an approach where acultural DE-based mechanism was developed.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

61 / 156

Feasibility rules
Adapted to other NIAs
Ma and Simon [76] proposed an improved version of thebiogeography-based optimization (BBO) algorithm (inspired on the
study of distributions of species over time and space) with thefeasibility rules as criteria to choose solutions with the so-called“habitat suitability index”.
Liu et al. [72] proposed the organizational evolutionary algorithm(OEA). A static penalty function and the feasibility rules werecompared as constraint-handling techniques.
Mezura-Montes and Hernández-Ocaña [88] used the feasibility
rules with the Bacterial Foraging Optimization Algorithm (BFOA) inthe greedy selection mechanism within the chemotactic loop.
Landa and Coello [61] adopted the rules in an approach where acultural DE-based mechanism was developed.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

61 / 156

Feasibility rules
Adapted to other NIAs
Ma and Simon [76] proposed an improved version of thebiogeography-based optimization (BBO) algorithm (inspired on the
study of distributions of species over time and space) with thefeasibility rules as criteria to choose solutions with the so-called“habitat suitability index”.
Liu et al. [72] proposed the organizational evolutionary algorithm(OEA). A static penalty function and the feasibility rules werecompared as constraint-handling techniques.
Mezura-Montes and Hernández-Ocaña [88] used the feasibility
rules with the Bacterial Foraging Optimization Algorithm (BFOA) inthe greedy selection mechanism within the chemotactic loop.
Landa and Coello [61] adopted the rules in an approach where acultural DE-based mechanism was developed.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

61 / 156

Feasibility rules
Adapted to other NIAs
Ma and Simon [76] proposed an improved version of thebiogeography-based optimization (BBO) algorithm (inspired on the
study of distributions of species over time and space) with thefeasibility rules as criteria to choose solutions with the so-called“habitat suitability index”.
Liu et al. [72] proposed the organizational evolutionary algorithm(OEA). A static penalty function and the feasibility rules werecompared as constraint-handling techniques.
Mezura-Montes and Hernández-Ocaña [88] used the feasibility
rules with the Bacterial Foraging Optimization Algorithm (BFOA) inthe greedy selection mechanism within the chemotactic loop.
Landa and Coello [61] adopted the rules in an approach where acultural DE-based mechanism was developed.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

61 / 156

Feasibility rules
Used in hybrid approaches
Muñoz-Zavala et al. [98] used a DE mutation operator to update
the local-best particle in PSO.
Wang et al. [142] implicitly used feasibility rules to rank theparticles in a hybrid multi-swarm PSO (HMPSO) where the DE
mutation operator was also adopted.
HMPSO was improved by Lui et al. in [70], where two additional
mutation operators were used. The number of evaluations
required by the improved approach, decreased in almost 50%.
He and Wang [38] used simulated annealing (SA) as a local
search operator and applied it to the gbest particle at eachgeneration in PSO.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

62 / 156

Feasibility rules
Used in hybrid approaches
Muñoz-Zavala et al. [98] used a DE mutation operator to update
the local-best particle in PSO.
Wang et al. [142] implicitly used feasibility rules to rank theparticles in a hybrid multi-swarm PSO (HMPSO) where the DE
mutation operator was also adopted.
HMPSO was improved by Lui et al. in [70], where two additional
mutation operators were used. The number of evaluations
required by the improved approach, decreased in almost 50%.
He and Wang [38] used simulated annealing (SA) as a local
search operator and applied it to the gbest particle at eachgeneration in PSO.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

62 / 156

Feasibility rules
Used in hybrid approaches
Muñoz-Zavala et al. [98] used a DE mutation operator to update
the local-best particle in PSO.
Wang et al. [142] implicitly used feasibility rules to rank theparticles in a hybrid multi-swarm PSO (HMPSO) where the DE
mutation operator was also adopted.
HMPSO was improved by Lui et al. in [70], where two additional
mutation operators were used. The number of evaluations
required by the improved approach, decreased in almost 50%.
He and Wang [38] used simulated annealing (SA) as a local
search operator and applied it to the gbest particle at eachgeneration in PSO.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

62 / 156

Feasibility rules
Used in hybrid approaches
Muñoz-Zavala et al. [98] used a DE mutation operator to update
the local-best particle in PSO.
Wang et al. [142] implicitly used feasibility rules to rank theparticles in a hybrid multi-swarm PSO (HMPSO) where the DE
mutation operator was also adopted.
HMPSO was improved by Lui et al. in [70], where two additional
mutation operators were used. The number of evaluations
required by the improved approach, decreased in almost 50%.
He and Wang [38] used simulated annealing (SA) as a local
search operator and applied it to the gbest particle at eachgeneration in PSO.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

62 / 156

Feasibility rules
Used in memetic algorithms
Menchaca-Mendez and Coello Coello [81] proposed a DE-basedalgorithm with a variation of the Nelder-Mead algorithm as a local
search operator.
Sun and Garibaldi [122] proposed an estimation of distribution
algorithm (EDA) with SQP as a local search operator.
Ullah et al. [136, 137] presented an agent-based memetic
algorithm where a learning process (a mutation operator chosen
by the solution) is used to improve solutions.
Ali and Kajee-Bagdadi [2] presented a DE-based approach with amodified version of the pattern search method as a local search
operator.
Hamza et al. [37] proposed a DE-based algorithm with aconstraint-consensus operator applied to infeasible vectors so as
to become them feasible.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

63 / 156

Feasibility rules
Used in memetic algorithms
Menchaca-Mendez and Coello Coello [81] proposed a DE-basedalgorithm with a variation of the Nelder-Mead algorithm as a local
search operator.
Sun and Garibaldi [122] proposed an estimation of distribution
algorithm (EDA) with SQP as a local search operator.
Ullah et al. [136, 137] presented an agent-based memetic
algorithm where a learning process (a mutation operator chosen
by the solution) is used to improve solutions.
Ali and Kajee-Bagdadi [2] presented a DE-based approach with amodified version of the pattern search method as a local search
operator.
Hamza et al. [37] proposed a DE-based algorithm with aconstraint-consensus operator applied to infeasible vectors so as
to become them feasible.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

63 / 156

Feasibility rules
Used in memetic algorithms
Menchaca-Mendez and Coello Coello [81] proposed a DE-basedalgorithm with a variation of the Nelder-Mead algorithm as a local
search operator.
Sun and Garibaldi [122] proposed an estimation of distribution
algorithm (EDA) with SQP as a local search operator.
Ullah et al. [136, 137] presented an agent-based memetic
algorithm where a learning process (a mutation operator chosen
by the solution) is used to improve solutions.
Ali and Kajee-Bagdadi [2] presented a DE-based approach with amodified version of the pattern search method as a local search
operator.
Hamza et al. [37] proposed a DE-based algorithm with aconstraint-consensus operator applied to infeasible vectors so as
to become them feasible.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

63 / 156

Feasibility rules
Used in memetic algorithms
Menchaca-Mendez and Coello Coello [81] proposed a DE-basedalgorithm with a variation of the Nelder-Mead algorithm as a local
search operator.
Sun and Garibaldi [122] proposed an estimation of distribution
algorithm (EDA) with SQP as a local search operator.
Ullah et al. [136, 137] presented an agent-based memetic
algorithm where a learning process (a mutation operator chosen
by the solution) is used to improve solutions.
Ali and Kajee-Bagdadi [2] presented a DE-based approach with amodified version of the pattern search method as a local search
operator.
Hamza et al. [37] proposed a DE-based algorithm with aconstraint-consensus operator applied to infeasible vectors so as
to become them feasible.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

63 / 156

Feasibility rules
Used in memetic algorithms
Menchaca-Mendez and Coello Coello [81] proposed a DE-basedalgorithm with a variation of the Nelder-Mead algorithm as a local
search operator.
Sun and Garibaldi [122] proposed an estimation of distribution
algorithm (EDA) with SQP as a local search operator.
Ullah et al. [136, 137] presented an agent-based memetic
algorithm where a learning process (a mutation operator chosen
by the solution) is used to improve solutions.
Ali and Kajee-Bagdadi [2] presented a DE-based approach with amodified version of the pattern search method as a local search
operator.
Hamza et al. [37] proposed a DE-based algorithm with aconstraint-consensus operator applied to infeasible vectors so as
to become them feasible.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

63 / 156

Feasibility rules

Empirical studies
Mezura-Montes and Flores-Mendoza compared PSO variants[87].
Mezura-Montes et al. compared DE variants [86].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

64 / 156

Feasibility rules

Empirical studies
Mezura-Montes and Flores-Mendoza compared PSO variants[87].
Mezura-Montes et al. compared DE variants [86].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

64 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

65 / 156

Stochastic ranking (SR)Proposed by Runarsson and Yao [114] to deal with theshortcomings of a penalty function (over and under penalization).
A user-defined parameter called Pf controls the criterion used forcomparison of infeasible solutions:
Based on their sum of constraint violation
Based only on their objective function value.

SR uses a bubble-sort-like process to rank the solutions in the
population.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

66 / 156

Stochastic ranking (SR)Proposed by Runarsson and Yao [114] to deal with theshortcomings of a penalty function (over and under penalization).
A user-defined parameter called Pf controls the criterion used forcomparison of infeasible solutions:
Based on their sum of constraint violation
Based only on their objective function value.

SR uses a bubble-sort-like process to rank the solutions in the
population.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

66 / 156

Stochastic ranking (SR)Proposed by Runarsson and Yao [114] to deal with theshortcomings of a penalty function (over and under penalization).
A user-defined parameter called Pf controls the criterion used forcomparison of infeasible solutions:
Based on their sum of constraint violation
Based only on their objective function value.

SR uses a bubble-sort-like process to rank the solutions in the
population.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

66 / 156

Stochastic ranking (SR)Begin
For i=1 to N
For j=1 to P-1
u=random(0,1)
If (Ij ) = (Ij+1 ) = 0 or (u < Pf )If f (Ij ) > f (Ij+1 )swap(Ij ,Ij+1 )Else
If (Ij ) > (Ij+1 )swap(Ij ,Ij+1 )End ForIf (not swap performed)
break
End ForEnd

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

67 / 156

Stochastic ranking (SR)Adapted to DE
Despite being a ranking process, SR has been adopted by NIAs
which do not rank solutions, such as DE.
Zhang et al. [156] used SR in a DE variant based on [90]. Pf was
defined by a dynamic parameter control mechanism (high value atthe beginning, low value at the end).
Liu et al. [73, 71] also used SR in DE and proposed the concept of
directional information related to the choice of the most convenient
search direction based on the DE mutation operator.
Fan et al. [30] ranked vectors with SR before the DE operators areapplied. The population is split into two sets: (1) the vectors withthe highest ranks, and (2) the remaining vectors. The base vector
and the vector which determines the search direction are chosen
at random from the first set. The other vector is chosen at random
from the second set.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

68 / 156

Stochastic ranking (SR)Adapted to DE
Despite being a ranking process, SR has been adopted by NIAs
which do not rank solutions, such as DE.
Zhang et al. [156] used SR in a DE variant based on [90]. Pf was
defined by a dynamic parameter control mechanism (high value atthe beginning, low value at the end).
Liu et al. [73, 71] also used SR in DE and proposed the concept of
directional information related to the choice of the most convenient
search direction based on the DE mutation operator.
Fan et al. [30] ranked vectors with SR before the DE operators areapplied. The population is split into two sets: (1) the vectors withthe highest ranks, and (2) the remaining vectors. The base vector
and the vector which determines the search direction are chosen
at random from the first set. The other vector is chosen at random
from the second set.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

68 / 156

Stochastic ranking (SR)Adapted to DE
Despite being a ranking process, SR has been adopted by NIAs
which do not rank solutions, such as DE.
Zhang et al. [156] used SR in a DE variant based on [90]. Pf was
defined by a dynamic parameter control mechanism (high value atthe beginning, low value at the end).
Liu et al. [73, 71] also used SR in DE and proposed the concept of
directional information related to the choice of the most convenient
search direction based on the DE mutation operator.
Fan et al. [30] ranked vectors with SR before the DE operators areapplied. The population is split into two sets: (1) the vectors withthe highest ranks, and (2) the remaining vectors. The base vector
and the vector which determines the search direction are chosen
at random from the first set. The other vector is chosen at random
from the second set.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

68 / 156

Stochastic ranking (SR)Adapted to DE
Despite being a ranking process, SR has been adopted by NIAs
which do not rank solutions, such as DE.
Zhang et al. [156] used SR in a DE variant based on [90]. Pf was
defined by a dynamic parameter control mechanism (high value atthe beginning, low value at the end).
Liu et al. [73, 71] also used SR in DE and proposed the concept of
directional information related to the choice of the most convenient
search direction based on the DE mutation operator.
Fan et al. [30] ranked vectors with SR before the DE operators areapplied. The population is split into two sets: (1) the vectors withthe highest ranks, and (2) the remaining vectors. The base vector
and the vector which determines the search direction are chosen
at random from the first set. The other vector is chosen at random
from the second set.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

68 / 156

Stochastic ranking (SR)Adapted to other NIAs
Leguizamón and Coello Coello [63] added SR to an ACO version
for dealing with CNOPs. A comparison against traditional penalty
functions showed that SR provided better and more robust results.
Fonseca et al. [32] used ACO with SR to solve discrete structural
optimization problems.
Mallipeddi et al. [77] proposed a two-population evolutionary
programming (EP) approach with an external memory to store
solutions based on an Euclidean distance measure that aimed topromote diversity. SR was compared against the feasibility rules.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

69 / 156

Stochastic ranking (SR)Adapted to other NIAs
Leguizamón and Coello Coello [63] added SR to an ACO version
for dealing with CNOPs. A comparison against traditional penalty
functions showed that SR provided better and more robust results.
Fonseca et al. [32] used ACO with SR to solve discrete structural
optimization problems.
Mallipeddi et al. [77] proposed a two-population evolutionary
programming (EP) approach with an external memory to store
solutions based on an Euclidean distance measure that aimed topromote diversity. SR was compared against the feasibility rules.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

69 / 156

Stochastic ranking (SR)Adapted to other NIAs
Leguizamón and Coello Coello [63] added SR to an ACO version
for dealing with CNOPs. A comparison against traditional penalty
functions showed that SR provided better and more robust results.
Fonseca et al. [32] used ACO with SR to solve discrete structural
optimization problems.
Mallipeddi et al. [77] proposed a two-population evolutionary
programming (EP) approach with an external memory to store
solutions based on an Euclidean distance measure that aimed topromote diversity. SR was compared against the feasibility rules.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

69 / 156

Stochastic ranking (SR)Applications and other studies
Huan-Tong et al. [44] used SR with its original search algorithm,
an evolution strategy, (ES) for solving reactive power optimization
problems.
Runarsson and Yao [115] improved their ES by adding a
differential mutation similar to that used in DE. The authors
concluded that a good constraint-handling mechanism needs tobe coupled to an appropriate search engine.
SR has been further developed by Runarsson and Yao [113] in
one of the earliest approaches focused on using fitness
approximation for constrained numerical optimization(k-nearest-neighbors was adopted for such purpose).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

70 / 156

Stochastic ranking (SR)Applications and other studies
Huan-Tong et al. [44] used SR with its original search algorithm,
an evolution strategy, (ES) for solving reactive power optimization
problems.
Runarsson and Yao [115] improved their ES by adding a
differential mutation similar to that used in DE. The authors
concluded that a good constraint-handling mechanism needs tobe coupled to an appropriate search engine.
SR has been further developed by Runarsson and Yao [113] in
one of the earliest approaches focused on using fitness
approximation for constrained numerical optimization(k-nearest-neighbors was adopted for such purpose).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

70 / 156

Stochastic ranking (SR)Applications and other studies
Huan-Tong et al. [44] used SR with its original search algorithm,
an evolution strategy, (ES) for solving reactive power optimization
problems.
Runarsson and Yao [115] improved their ES by adding a
differential mutation similar to that used in DE. The authors
concluded that a good constraint-handling mechanism needs tobe coupled to an appropriate search engine.
SR has been further developed by Runarsson and Yao [113] in
one of the earliest approaches focused on using fitness
approximation for constrained numerical optimization(k-nearest-neighbors was adopted for such purpose).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

70 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

71 / 156

"-constrained method

Proposed by Takahama and Sakai [130]. It transforms a CNOP
into an unconstrained numerical optimization problem.
Two main components:
A relaxation of the limit to consider a solution as feasible.
A lexicographical ordering mechanism in which the minimization of
the sum of constraint violation precedes the objective function.

The value " > 0, determines the so-called "-level comparisons
between a pair of solutions ~x1 and ~x2 with objective function valuesf (~x1 ) and f (~x2 ) and sums of constraint violation (~x1 ) and (~x2 ).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

72 / 156

"-constrained method

Proposed by Takahama and Sakai [130]. It transforms a CNOP
into an unconstrained numerical optimization problem.
Two main components:
A relaxation of the limit to consider a solution as feasible.
A lexicographical ordering mechanism in which the minimization of
the sum of constraint violation precedes the objective function.

The value " > 0, determines the so-called "-level comparisons
between a pair of solutions ~x1 and ~x2 with objective function valuesf (~x1 ) and f (~x2 ) and sums of constraint violation (~x1 ) and (~x2 ).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

72 / 156

"-constrained method

Proposed by Takahama and Sakai [130]. It transforms a CNOP
into an unconstrained numerical optimization problem.
Two main components:
A relaxation of the limit to consider a solution as feasible.
A lexicographical ordering mechanism in which the minimization of
the sum of constraint violation precedes the objective function.

The value " > 0, determines the so-called "-level comparisons
between a pair of solutions ~x1 and ~x2 with objective function valuesf (~x1 ) and f (~x2 ) and sums of constraint violation (~x1 ) and (~x2 ).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

72 / 156

"-constrained method8< f (~x1 ) < f (~x2 ) , if (~x1 ), (~x2 )  "f (~x1 ) < f (~x2 ) , if (~x1 ) = (~x2 )(f (~x1 ), (~x1 )) <" (f (~x2 ), (~x2 )) ,:(~x1 ) < (~x2 ) , otherwise8< f (~x1 )  f (~x2 ) , if (~x1 ), (~x2 )  "f (~x1 )  f (~x2 ) , if (~x1 ) = (~x2 )(f (~x1 ), (~x1 )) " (f (~x2 ), (~x2 )) ,:(~x1 ) < (~x2 ) , otherwise

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

73 / 156

"-constrained method

If both solutions in the pairwise comparison are feasible, slightly
infeasible (as determined by the " value) or even if they have thesame sum of constraint violation, they are compared using theirobjective function values.
If both solutions are infeasible, they are compared based on theirsum of constraint violation.
If " = 1, the "-level comparison works by using only the objectivefunction values as the comparison criteria.
If " = 0, then the "-level comparisons <0 and 0 are equivalent toa lexicographical ordering (i.e., (~x ) precedes f (~x )).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

74 / 156

"-constrained method

If both solutions in the pairwise comparison are feasible, slightly
infeasible (as determined by the " value) or even if they have thesame sum of constraint violation, they are compared using theirobjective function values.
If both solutions are infeasible, they are compared based on theirsum of constraint violation.
If " = 1, the "-level comparison works by using only the objectivefunction values as the comparison criteria.
If " = 0, then the "-level comparisons <0 and 0 are equivalent toa lexicographical ordering (i.e., (~x ) precedes f (~x )).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

74 / 156

"-constrained method

If both solutions in the pairwise comparison are feasible, slightly
infeasible (as determined by the " value) or even if they have thesame sum of constraint violation, they are compared using theirobjective function values.
If both solutions are infeasible, they are compared based on theirsum of constraint violation.
If " = 1, the "-level comparison works by using only the objectivefunction values as the comparison criteria.
If " = 0, then the "-level comparisons <0 and 0 are equivalent toa lexicographical ordering (i.e., (~x ) precedes f (~x )).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

74 / 156

"-constrained method

If both solutions in the pairwise comparison are feasible, slightly
infeasible (as determined by the " value) or even if they have thesame sum of constraint violation, they are compared using theirobjective function values.
If both solutions are infeasible, they are compared based on theirsum of constraint violation.
If " = 1, the "-level comparison works by using only the objectivefunction values as the comparison criteria.
If " = 0, then the "-level comparisons <0 and 0 are equivalent toa lexicographical ordering (i.e., (~x ) precedes f (~x )).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

74 / 156

"-constrained method
Adapted to other NIAs
Takahama and Sakai used a similar approach called↵-constrained method into a GA [123]. Even mathematicalprogramming methods have been used with this approach(Nealder-Mead) [124].
Wang and Li also adopted the ↵-constrained method in [140],
using DE as their search engine
Takahama and Sakai adopted the "-constrained method in PSO[125], and mainly in DE [126].
Takahama et al. used their constraint-handling technique in a
hybrid PSO-GA [130].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

75 / 156

"-constrained method
Adapted to other NIAs
Takahama and Sakai used a similar approach called↵-constrained method into a GA [123]. Even mathematicalprogramming methods have been used with this approach(Nealder-Mead) [124].
Wang and Li also adopted the ↵-constrained method in [140],
using DE as their search engine
Takahama and Sakai adopted the "-constrained method in PSO[125], and mainly in DE [126].
Takahama et al. used their constraint-handling technique in a
hybrid PSO-GA [130].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

75 / 156

"-constrained method
Adapted to other NIAs
Takahama and Sakai used a similar approach called↵-constrained method into a GA [123]. Even mathematicalprogramming methods have been used with this approach(Nealder-Mead) [124].
Wang and Li also adopted the ↵-constrained method in [140],
using DE as their search engine
Takahama and Sakai adopted the "-constrained method in PSO[125], and mainly in DE [126].
Takahama et al. used their constraint-handling technique in a
hybrid PSO-GA [130].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

75 / 156

"-constrained method
Adapted to other NIAs
Takahama and Sakai used a similar approach called↵-constrained method into a GA [123]. Even mathematicalprogramming methods have been used with this approach(Nealder-Mead) [124].
Wang and Li also adopted the ↵-constrained method in [140],
using DE as their search engine
Takahama and Sakai adopted the "-constrained method in PSO[125], and mainly in DE [126].
Takahama et al. used their constraint-handling technique in a
hybrid PSO-GA [130].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

75 / 156

"-constrained method
Improvements
The " value is fine-tuned by Takahama and Sakai with dynamic[124], and adaptive parameter control mechanisms [127].
Zeng et al. [155] also proposed a dynamic decreasing mechanism
inspired in [36].
A gradient-based mutation was added to the DE-based approachby the same authors in [126] and by Zhang et al. in an EA in [157].
In [128], Takahama and Sakai improved their approach by adding
a decreasing probability on the use of the gradient-based
mutation. They also introduced two new mechanisms to deal withboundary constraints (reflecting back and assigning the limit
value).
The authors in [129] added an archive to store solutions and theability of a vector to generate more than one trial vector.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

76 / 156

"-constrained method
Improvements
The " value is fine-tuned by Takahama and Sakai with dynamic[124], and adaptive parameter control mechanisms [127].
Zeng et al. [155] also proposed a dynamic decreasing mechanism
inspired in [36].
A gradient-based mutation was added to the DE-based approachby the same authors in [126] and by Zhang et al. in an EA in [157].
In [128], Takahama and Sakai improved their approach by adding
a decreasing probability on the use of the gradient-based
mutation. They also introduced two new mechanisms to deal withboundary constraints (reflecting back and assigning the limit
value).
The authors in [129] added an archive to store solutions and theability of a vector to generate more than one trial vector.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

76 / 156

"-constrained method
Improvements
The " value is fine-tuned by Takahama and Sakai with dynamic[124], and adaptive parameter control mechanisms [127].
Zeng et al. [155] also proposed a dynamic decreasing mechanism
inspired in [36].
A gradient-based mutation was added to the DE-based approachby the same authors in [126] and by Zhang et al. in an EA in [157].
In [128], Takahama and Sakai improved their approach by adding
a decreasing probability on the use of the gradient-based
mutation. They also introduced two new mechanisms to deal withboundary constraints (reflecting back and assigning the limit
value).
The authors in [129] added an archive to store solutions and theability of a vector to generate more than one trial vector.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

76 / 156

"-constrained method
Improvements
The " value is fine-tuned by Takahama and Sakai with dynamic[124], and adaptive parameter control mechanisms [127].
Zeng et al. [155] also proposed a dynamic decreasing mechanism
inspired in [36].
A gradient-based mutation was added to the DE-based approachby the same authors in [126] and by Zhang et al. in an EA in [157].
In [128], Takahama and Sakai improved their approach by adding
a decreasing probability on the use of the gradient-based
mutation. They also introduced two new mechanisms to deal withboundary constraints (reflecting back and assigning the limit
value).
The authors in [129] added an archive to store solutions and theability of a vector to generate more than one trial vector.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

76 / 156

"-constrained method
Improvements
The " value is fine-tuned by Takahama and Sakai with dynamic[124], and adaptive parameter control mechanisms [127].
Zeng et al. [155] also proposed a dynamic decreasing mechanism
inspired in [36].
A gradient-based mutation was added to the DE-based approachby the same authors in [126] and by Zhang et al. in an EA in [157].
In [128], Takahama and Sakai improved their approach by adding
a decreasing probability on the use of the gradient-based
mutation. They also introduced two new mechanisms to deal withboundary constraints (reflecting back and assigning the limit
value).
The authors in [129] added an archive to store solutions and theability of a vector to generate more than one trial vector.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

76 / 156

"-constrained method
NIAs turning to the "-constrained method"-jDE by Brest et al. [12], where different DE variants, parameter
self-adaptation (including "), and population reduction were
employed.
An improved version called jDEsoco was proposed by Brest et al.
in [13], where an ageing mechanism to replace those solutions
stagnated in a local optimum was added. Moreover, only the 60%of the population was compared by the "-constrained method andthe remaining 40% was compared by only using the objectivefunction value.
Mezura-Montes et al. used the "-constrained method in ABC [86].
A dynamic mechanism for the equality constraints tolerance wasconsidered. The results obtained outperformed those reported bya previous ABC version with the feasibility rules [82].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

77 / 156

"-constrained method
NIAs turning to the "-constrained method"-jDE by Brest et al. [12], where different DE variants, parameter
self-adaptation (including "), and population reduction were
employed.
An improved version called jDEsoco was proposed by Brest et al.
in [13], where an ageing mechanism to replace those solutions
stagnated in a local optimum was added. Moreover, only the 60%of the population was compared by the "-constrained method andthe remaining 40% was compared by only using the objectivefunction value.
Mezura-Montes et al. used the "-constrained method in ABC [86].
A dynamic mechanism for the equality constraints tolerance wasconsidered. The results obtained outperformed those reported bya previous ABC version with the feasibility rules [82].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

77 / 156

"-constrained method
NIAs turning to the "-constrained method"-jDE by Brest et al. [12], where different DE variants, parameter
self-adaptation (including "), and population reduction were
employed.
An improved version called jDEsoco was proposed by Brest et al.
in [13], where an ageing mechanism to replace those solutions
stagnated in a local optimum was added. Moreover, only the 60%of the population was compared by the "-constrained method andthe remaining 40% was compared by only using the objectivefunction value.
Mezura-Montes et al. used the "-constrained method in ABC [86].
A dynamic mechanism for the equality constraints tolerance wasconsidered. The results obtained outperformed those reported bya previous ABC version with the feasibility rules [82].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

77 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

78 / 156

Novel penalty functions

The most popular approach recently found regarding
penalization-based approaches is the adaptive penalty function.
Dynamic penalty functions, which adopt the current generation
number to control the decrement of the penalty factor, are still
popular.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

79 / 156

Novel penalty functions

The most popular approach recently found regarding
penalization-based approaches is the adaptive penalty function.
Dynamic penalty functions, which adopt the current generation
number to control the decrement of the penalty factor, are still
popular.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

79 / 156

Novel penalty functions

Adaptive penalty functions
Farmani and Wright [31] proposed a two-part adaptive penalty
function. The first part increases the fitness of the infeasible
solutions with a better value of the objective function with respect
to the best solution in the current population. The second partmodifies the fitness values of the worst infeasible solutions.
Tessema and Yen [133] used the number of feasible solutions in
the current population to determine penalization values so as tofavor slightly infeasible solutions having a good objective function
value.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

80 / 156

Novel penalty functions

Adaptive penalty functions
Farmani and Wright [31] proposed a two-part adaptive penalty
function. The first part increases the fitness of the infeasible
solutions with a better value of the objective function with respect
to the best solution in the current population. The second partmodifies the fitness values of the worst infeasible solutions.
Tessema and Yen [133] used the number of feasible solutions in
the current population to determine penalization values so as tofavor slightly infeasible solutions having a good objective function
value.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

80 / 156

Novel penalty functions
Adaptive penalty functions
Mani and Patvardhan [79] proposed a two-population
GA-like-based approach. One population evolves by using an
adaptive penalty function. The other population evolves based on
feasibility rules. Both populations exchange solutions.
He et al. [39] used two PSO algorithms, one to co-evolve penalty
factors and the other one to evolve solutions to the optimization
problem.
Wu [151] proposed an artificial immune system (AIS) where an
adaptive penalty function was defined to assign its affinity to eachantibody.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

81 / 156

Novel penalty functions
Adaptive penalty functions
Mani and Patvardhan [79] proposed a two-population
GA-like-based approach. One population evolves by using an
adaptive penalty function. The other population evolves based on
feasibility rules. Both populations exchange solutions.
He et al. [39] used two PSO algorithms, one to co-evolve penalty
factors and the other one to evolve solutions to the optimization
problem.
Wu [151] proposed an artificial immune system (AIS) where an
adaptive penalty function was defined to assign its affinity to eachantibody.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

81 / 156

Novel penalty functions
Adaptive penalty functions
Mani and Patvardhan [79] proposed a two-population
GA-like-based approach. One population evolves by using an
adaptive penalty function. The other population evolves based on
feasibility rules. Both populations exchange solutions.
He et al. [39] used two PSO algorithms, one to co-evolve penalty
factors and the other one to evolve solutions to the optimization
problem.
Wu [151] proposed an artificial immune system (AIS) where an
adaptive penalty function was defined to assign its affinity to eachantibody.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

81 / 156

Novel penalty functions

Dynamic penalty functions
Tasgetiren and Suganthan [132] used of a dynamic penalty
function coupled with a multi-population DE algorithm where each
populations evolved independently.
Puzzi and Carpinteri [104] explored a dynamic penalty function
based on multiplications instead of summations in a GA-based
approach.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

82 / 156

Novel penalty functions

Dynamic penalty functions
Tasgetiren and Suganthan [132] used of a dynamic penalty
function coupled with a multi-population DE algorithm where each
populations evolved independently.
Puzzi and Carpinteri [104] explored a dynamic penalty function
based on multiplications instead of summations in a GA-based
approach.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

82 / 156

Novel penalty functions
Static penalty functions
Deb and Datta [26] obtained suitable penalty factors as follows:
A bi-objective problem (original objective function and sum of
constraint violation , restricted by a tolerance value) was solved
by a MOEA
A cubic curve to approximate the current obtained Pareto front
was generated by using four points whose values were below asmall tolerance.
The penalty factor was then defined by calculating thecorresponding slope at = 0.
After that, a traditional static penalty function was used to solve
the original CNOP by using a local search algorithm (Matlab’s
fmincon() procedure was used by the authors) using the solution
with the lowest value from the population of the MOEA as thestarting point for the search.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

83 / 156

Novel penalty functions
Static penalty functions
Deb and Datta [26] obtained suitable penalty factors as follows:
A bi-objective problem (original objective function and sum of
constraint violation , restricted by a tolerance value) was solved
by a MOEA
A cubic curve to approximate the current obtained Pareto front
was generated by using four points whose values were below asmall tolerance.
The penalty factor was then defined by calculating thecorresponding slope at = 0.
After that, a traditional static penalty function was used to solve
the original CNOP by using a local search algorithm (Matlab’s
fmincon() procedure was used by the authors) using the solution
with the lowest value from the population of the MOEA as thestarting point for the search.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

83 / 156

Novel penalty functions
Static penalty functions
Deb and Datta [26] obtained suitable penalty factors as follows:
A bi-objective problem (original objective function and sum of
constraint violation , restricted by a tolerance value) was solved
by a MOEA
A cubic curve to approximate the current obtained Pareto front
was generated by using four points whose values were below asmall tolerance.
The penalty factor was then defined by calculating thecorresponding slope at = 0.
After that, a traditional static penalty function was used to solve
the original CNOP by using a local search algorithm (Matlab’s
fmincon() procedure was used by the authors) using the solution
with the lowest value from the population of the MOEA as thestarting point for the search.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

83 / 156

Novel penalty functions
Static penalty functions
Deb and Datta [26] obtained suitable penalty factors as follows:
A bi-objective problem (original objective function and sum of
constraint violation , restricted by a tolerance value) was solved
by a MOEA
A cubic curve to approximate the current obtained Pareto front
was generated by using four points whose values were below asmall tolerance.
The penalty factor was then defined by calculating thecorresponding slope at = 0.
After that, a traditional static penalty function was used to solve
the original CNOP by using a local search algorithm (Matlab’s
fmincon() procedure was used by the authors) using the solution
with the lowest value from the population of the MOEA as thestarting point for the search.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

83 / 156

Novel penalty functions
Static penalty functions
Deb and Datta [26] obtained suitable penalty factors as follows:
A bi-objective problem (original objective function and sum of
constraint violation , restricted by a tolerance value) was solved
by a MOEA
A cubic curve to approximate the current obtained Pareto front
was generated by using four points whose values were below asmall tolerance.
The penalty factor was then defined by calculating thecorresponding slope at = 0.
After that, a traditional static penalty function was used to solve
the original CNOP by using a local search algorithm (Matlab’s
fmincon() procedure was used by the authors) using the solution
with the lowest value from the population of the MOEA as thestarting point for the search.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

83 / 156

Novel penalty functions

Static penalty functions
In [23], Datta and Deb extended their approach to deal withequality constraints.
Two main changes:
The punishment provided by the penalty value obtained by thebi-objective problem was increased if the local search failed togenerate a feasible solution.
The small tolerance used for choosing the four points employed toapproximate the cubic curve was relaxed.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

84 / 156

Novel penalty functions

Static penalty functions
In [23], Datta and Deb extended their approach to deal withequality constraints.
Two main changes:
The punishment provided by the penalty value obtained by thebi-objective problem was increased if the local search failed togenerate a feasible solution.
The small tolerance used for choosing the four points employed toapproximate the cubic curve was relaxed.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

84 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

85 / 156

Novel special operators
The recent proposals based on the use of special operators thathave been revised here emphasize the current focus on
generating proposals which are easier to generalize.
Leguizamón and Coello Coello [62] proposed a boundary operator
based on conducting a binary search between a feasible and an
infeasible solution. Furthermore, the authors designed a strategy
to select which constraint (if more than one is present in a CNOP)
is analyzed.
The search algorithm was an ACO variant for continuous search
spaces.
The approach needed an additional constraint-handling technique(a penalty function was used in this case)

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

86 / 156

Novel special operators
The recent proposals based on the use of special operators thathave been revised here emphasize the current focus on
generating proposals which are easier to generalize.
Leguizamón and Coello Coello [62] proposed a boundary operator
based on conducting a binary search between a feasible and an
infeasible solution. Furthermore, the authors designed a strategy
to select which constraint (if more than one is present in a CNOP)
is analyzed.
The search algorithm was an ACO variant for continuous search
spaces.
The approach needed an additional constraint-handling technique(a penalty function was used in this case)

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

86 / 156

Novel special operators
The recent proposals based on the use of special operators thathave been revised here emphasize the current focus on
generating proposals which are easier to generalize.
Leguizamón and Coello Coello [62] proposed a boundary operator
based on conducting a binary search between a feasible and an
infeasible solution. Furthermore, the authors designed a strategy
to select which constraint (if more than one is present in a CNOP)
is analyzed.
The search algorithm was an ACO variant for continuous search
spaces.
The approach needed an additional constraint-handling technique(a penalty function was used in this case)

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

86 / 156

Novel special operators
The recent proposals based on the use of special operators thathave been revised here emphasize the current focus on
generating proposals which are easier to generalize.
Leguizamón and Coello Coello [62] proposed a boundary operator
based on conducting a binary search between a feasible and an
infeasible solution. Furthermore, the authors designed a strategy
to select which constraint (if more than one is present in a CNOP)
is analyzed.
The search algorithm was an ACO variant for continuous search
spaces.
The approach needed an additional constraint-handling technique(a penalty function was used in this case)

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

86 / 156

Novel special operators
Huang et al. [45] proposed a boundary operator in a
two-population approach.
The first population evolves by using DE as the search engine,
based only on the objective function value (regardless of
feasibility).
The second population stores only feasible solutions and theboundary operator uses solutions from both populations togenerate new solutions, through the application of the bisection
method in the boundaries of the feasible region.
The Nelder-Mead simplex method was used as a local search
operator
It does not require an additional constraint-handling technique, but
a feasible solutions is needed at the beginning of the process.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

87 / 156

Novel special operators
Huang et al. [45] proposed a boundary operator in a
two-population approach.
The first population evolves by using DE as the search engine,
based only on the objective function value (regardless of
feasibility).
The second population stores only feasible solutions and theboundary operator uses solutions from both populations togenerate new solutions, through the application of the bisection
method in the boundaries of the feasible region.
The Nelder-Mead simplex method was used as a local search
operator
It does not require an additional constraint-handling technique, but
a feasible solutions is needed at the beginning of the process.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

87 / 156

Novel special operators
Huang et al. [45] proposed a boundary operator in a
two-population approach.
The first population evolves by using DE as the search engine,
based only on the objective function value (regardless of
feasibility).
The second population stores only feasible solutions and theboundary operator uses solutions from both populations togenerate new solutions, through the application of the bisection
method in the boundaries of the feasible region.
The Nelder-Mead simplex method was used as a local search
operator
It does not require an additional constraint-handling technique, but
a feasible solutions is needed at the beginning of the process.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

87 / 156

Novel special operators
Huang et al. [45] proposed a boundary operator in a
two-population approach.
The first population evolves by using DE as the search engine,
based only on the objective function value (regardless of
feasibility).
The second population stores only feasible solutions and theboundary operator uses solutions from both populations togenerate new solutions, through the application of the bisection
method in the boundaries of the feasible region.
The Nelder-Mead simplex method was used as a local search
operator
It does not require an additional constraint-handling technique, but
a feasible solutions is needed at the beginning of the process.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

87 / 156

Novel special operators
Huang et al. [45] proposed a boundary operator in a
two-population approach.
The first population evolves by using DE as the search engine,
based only on the objective function value (regardless of
feasibility).
The second population stores only feasible solutions and theboundary operator uses solutions from both populations togenerate new solutions, through the application of the bisection
method in the boundaries of the feasible region.
The Nelder-Mead simplex method was used as a local search
operator
It does not require an additional constraint-handling technique, but
a feasible solutions is needed at the beginning of the process.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

87 / 156

Novel special operators
Constraint satisfaction
Wanner et al. [149] proposed the Constraint Quadratic
Approximation (CQA), which is a special operator designed torestrict an evolutionary algorithm (a GA in this case) to sample
solutions inside an object with the same dimensions of thefeasible region of the search space.
This is achieved by a second-order approximation of the objectivefunction and one equality constraint.
A static penalty function was used to guide the GA search and theequality constraint was transformed into two inequality constraints
by using a small ✏ tolerance.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

88 / 156

Novel special operators
Constraint satisfaction
Wanner et al. [149] proposed the Constraint Quadratic
Approximation (CQA), which is a special operator designed torestrict an evolutionary algorithm (a GA in this case) to sample
solutions inside an object with the same dimensions of thefeasible region of the search space.
This is achieved by a second-order approximation of the objectivefunction and one equality constraint.
A static penalty function was used to guide the GA search and theequality constraint was transformed into two inequality constraints
by using a small ✏ tolerance.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

88 / 156

Novel special operators
Constraint satisfaction
Wanner et al. [149] proposed the Constraint Quadratic
Approximation (CQA), which is a special operator designed torestrict an evolutionary algorithm (a GA in this case) to sample
solutions inside an object with the same dimensions of thefeasible region of the search space.
This is achieved by a second-order approximation of the objectivefunction and one equality constraint.
A static penalty function was used to guide the GA search and theequality constraint was transformed into two inequality constraints
by using a small ✏ tolerance.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

88 / 156

Novel special operators
Constraint satisfaction
Peconick et al. [102] proposed the Constraint Quadratic
Approximation for Multiple Equality Constraints (CQA-MEC).
An iterative projection algorithm was able to find points satisfying
the approximated quadratic constraints with a low computational
overhead.
It still requires the static penalty function to work.
Araujo et al. [8] extended the previous approaches to deal withmultiple inequality constraints by using a special operator in which
the locally convex inequality constraints are approximated byquadratic functions, while the locally non-convex inequality
constraints are approximated by linear functions.
The dependence of the static penalty function remains in this lastapproach.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

89 / 156

Novel special operators
Constraint satisfaction
Peconick et al. [102] proposed the Constraint Quadratic
Approximation for Multiple Equality Constraints (CQA-MEC).
An iterative projection algorithm was able to find points satisfying
the approximated quadratic constraints with a low computational
overhead.
It still requires the static penalty function to work.
Araujo et al. [8] extended the previous approaches to deal withmultiple inequality constraints by using a special operator in which
the locally convex inequality constraints are approximated byquadratic functions, while the locally non-convex inequality
constraints are approximated by linear functions.
The dependence of the static penalty function remains in this lastapproach.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

89 / 156

Novel special operators
Constraint satisfaction
Peconick et al. [102] proposed the Constraint Quadratic
Approximation for Multiple Equality Constraints (CQA-MEC).
An iterative projection algorithm was able to find points satisfying
the approximated quadratic constraints with a low computational
overhead.
It still requires the static penalty function to work.
Araujo et al. [8] extended the previous approaches to deal withmultiple inequality constraints by using a special operator in which
the locally convex inequality constraints are approximated byquadratic functions, while the locally non-convex inequality
constraints are approximated by linear functions.
The dependence of the static penalty function remains in this lastapproach.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

89 / 156

Novel special operators
Constraint satisfaction
Peconick et al. [102] proposed the Constraint Quadratic
Approximation for Multiple Equality Constraints (CQA-MEC).
An iterative projection algorithm was able to find points satisfying
the approximated quadratic constraints with a low computational
overhead.
It still requires the static penalty function to work.
Araujo et al. [8] extended the previous approaches to deal withmultiple inequality constraints by using a special operator in which
the locally convex inequality constraints are approximated byquadratic functions, while the locally non-convex inequality
constraints are approximated by linear functions.
The dependence of the static penalty function remains in this lastapproach.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

89 / 156

Novel special operators
Constraint satisfaction
Peconick et al. [102] proposed the Constraint Quadratic
Approximation for Multiple Equality Constraints (CQA-MEC).
An iterative projection algorithm was able to find points satisfying
the approximated quadratic constraints with a low computational
overhead.
It still requires the static penalty function to work.
Araujo et al. [8] extended the previous approaches to deal withmultiple inequality constraints by using a special operator in which
the locally convex inequality constraints are approximated byquadratic functions, while the locally non-convex inequality
constraints are approximated by linear functions.
The dependence of the static penalty function remains in this lastapproach.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

89 / 156

Novel special operators
Constraint satisfaction
Ullah et al.[134] proposed an agent-based memetic algorithm inwhich the authors adopt a special local operator for equality
constraints.
It is applied to some individuals in the population as follows: thesatisfaction of a randomly chosen equality constraint is verified fora given solution. If it is not satisfied, a decision variable, alsochosen at random, is updated with the aim to satisfy it. If theconstraint is indeed satisfied, two other variables are modified insuch a way that the constraint is still satisfied (i.e., the constraint issampled).
This special operator is only applied during the early stages of thesearch because it reduces the diversity in the population.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

90 / 156

Novel special operators
Constraint satisfaction
Ullah et al.[134] proposed an agent-based memetic algorithm inwhich the authors adopt a special local operator for equality
constraints.
It is applied to some individuals in the population as follows: thesatisfaction of a randomly chosen equality constraint is verified fora given solution. If it is not satisfied, a decision variable, alsochosen at random, is updated with the aim to satisfy it. If theconstraint is indeed satisfied, two other variables are modified insuch a way that the constraint is still satisfied (i.e., the constraint issampled).
This special operator is only applied during the early stages of thesearch because it reduces the diversity in the population.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

90 / 156

Novel special operators
Constraint satisfaction
Ullah et al.[134] proposed an agent-based memetic algorithm inwhich the authors adopt a special local operator for equality
constraints.
It is applied to some individuals in the population as follows: thesatisfaction of a randomly chosen equality constraint is verified fora given solution. If it is not satisfied, a decision variable, alsochosen at random, is updated with the aim to satisfy it. If theconstraint is indeed satisfied, two other variables are modified insuch a way that the constraint is still satisfied (i.e., the constraint issampled).
This special operator is only applied during the early stages of thesearch because it reduces the diversity in the population.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

90 / 156

Novel special operators
Feasible directions
Spadoni and Stefanini [121] transformed a CNOP into an
unconstrained search problem by sampling feasible directions
instead of solutions of a CNOP.
Three special operators, related to feasible directions for box
constraints, linear inequality constraints, and quadratic inequality
constraints, are utilized to generate new solutions by using DE as
the search algorithm.
The main contribution of the approach is that it transforms a
CNOP into an unconstrained search problem without using apenalty function. However, it cannot deal with nonlinear (either
equality or inequality) constraints.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

91 / 156

Novel special operators
Feasible directions
Spadoni and Stefanini [121] transformed a CNOP into an
unconstrained search problem by sampling feasible directions
instead of solutions of a CNOP.
Three special operators, related to feasible directions for box
constraints, linear inequality constraints, and quadratic inequality
constraints, are utilized to generate new solutions by using DE as
the search algorithm.
The main contribution of the approach is that it transforms a
CNOP into an unconstrained search problem without using apenalty function. However, it cannot deal with nonlinear (either
equality or inequality) constraints.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

91 / 156

Novel special operators
Feasible directions
Spadoni and Stefanini [121] transformed a CNOP into an
unconstrained search problem by sampling feasible directions
instead of solutions of a CNOP.
Three special operators, related to feasible directions for box
constraints, linear inequality constraints, and quadratic inequality
constraints, are utilized to generate new solutions by using DE as
the search algorithm.
The main contribution of the approach is that it transforms a
CNOP into an unconstrained search problem without using apenalty function. However, it cannot deal with nonlinear (either
equality or inequality) constraints.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

91 / 156

Novel special operators

General operators made special
Lu and Chen [75] proposed an approach called self-adaptive
velocity particle swarm optimization (SAVPSO).
Three elements:
The position of the feasible region with respect to the whole search
space.
The connectivity and the shape of the feasible region.
The ratio of the feasible region with respect to the search space.

The velocity formula was modified in such a way that each particle
has the ability to self-adjust its velocity according to theaforementioned features of the feasible region.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

92 / 156

Novel special operators

General operators made special
Lu and Chen [75] proposed an approach called self-adaptive
velocity particle swarm optimization (SAVPSO).
Three elements:
The position of the feasible region with respect to the whole search
space.
The connectivity and the shape of the feasible region.
The ratio of the feasible region with respect to the search space.

The velocity formula was modified in such a way that each particle
has the ability to self-adjust its velocity according to theaforementioned features of the feasible region.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

92 / 156

Novel special operators

General operators made special
Lu and Chen [75] proposed an approach called self-adaptive
velocity particle swarm optimization (SAVPSO).
Three elements:
The position of the feasible region with respect to the whole search
space.
The connectivity and the shape of the feasible region.
The ratio of the feasible region with respect to the search space.

The velocity formula was modified in such a way that each particle
has the ability to self-adjust its velocity according to theaforementioned features of the feasible region.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

92 / 156

Novel special operators

Constraint satisfaction
Wu et al. [152] and Li & Li [65] modified variation operators in NIAs
in such a way that the recombination of feasible and infeasible
solutions led to the generation of more feasible solutions.
An adaptive mechanism to maintain infeasible solutions wasadded to the approach.
This latter version was specifically based on DE’s variation
operators [65].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

93 / 156

Novel special operators

Constraint satisfaction
Wu et al. [152] and Li & Li [65] modified variation operators in NIAs
in such a way that the recombination of feasible and infeasible
solutions led to the generation of more feasible solutions.
An adaptive mechanism to maintain infeasible solutions wasadded to the approach.
This latter version was specifically based on DE’s variation
operators [65].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

93 / 156

Novel special operators

Constraint satisfaction
Wu et al. [152] and Li & Li [65] modified variation operators in NIAs
in such a way that the recombination of feasible and infeasible
solutions led to the generation of more feasible solutions.
An adaptive mechanism to maintain infeasible solutions wasadded to the approach.
This latter version was specifically based on DE’s variation
operators [65].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

93 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

94 / 156

Multi-objective concepts

Despite the fact that empirical evidence has suggested thatmulti-objective concepts are not well-suited to solve CNOPs, there
are highly competitive constraint-handling techniques based onsuch concepts.
The use of transformation of a CNOP into a bi-objective
optimization problem (objective function and sum of constraint
violation) has been preferred over considering each constraint as
a separate objective.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

95 / 156

Multi-objective concepts

Despite the fact that empirical evidence has suggested thatmulti-objective concepts are not well-suited to solve CNOPs, there
are highly competitive constraint-handling techniques based onsuch concepts.
The use of transformation of a CNOP into a bi-objective
optimization problem (objective function and sum of constraint
violation) has been preferred over considering each constraint as
a separate objective.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

95 / 156

Multi-objective concepts
Bi-objective problem
Ray et al. [109] proposed the Infeasibility Driven Evolutionary
Algorithm (IDEA).
The second objective is the constraint violation measure, (zerovalue for feasible solutions and a sum of ranking values based on
the violation per constraint).
The union of parents and offspring is split in two sets, one with thefeasible solutions and the other with the infeasible ones.
Non-dominated sorting ranks both sets separately and, based on
the proportion of desired feasible solutions, they are chosen firstfrom the infeasible set and later on, the best ranked feasible
solutions are chosen.
SQP was added to IDEA in the Infeasibility Empowered Memetic
Algorithm (IMEA) [120].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

96 / 156

Multi-objective concepts
Bi-objective problem
Ray et al. [109] proposed the Infeasibility Driven Evolutionary
Algorithm (IDEA).
The second objective is the constraint violation measure, (zerovalue for feasible solutions and a sum of ranking values based on
the violation per constraint).
The union of parents and offspring is split in two sets, one with thefeasible solutions and the other with the infeasible ones.
Non-dominated sorting ranks both sets separately and, based on
the proportion of desired feasible solutions, they are chosen firstfrom the infeasible set and later on, the best ranked feasible
solutions are chosen.
SQP was added to IDEA in the Infeasibility Empowered Memetic
Algorithm (IMEA) [120].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

96 / 156

Multi-objective concepts
Bi-objective problem
Ray et al. [109] proposed the Infeasibility Driven Evolutionary
Algorithm (IDEA).
The second objective is the constraint violation measure, (zerovalue for feasible solutions and a sum of ranking values based on
the violation per constraint).
The union of parents and offspring is split in two sets, one with thefeasible solutions and the other with the infeasible ones.
Non-dominated sorting ranks both sets separately and, based on
the proportion of desired feasible solutions, they are chosen firstfrom the infeasible set and later on, the best ranked feasible
solutions are chosen.
SQP was added to IDEA in the Infeasibility Empowered Memetic
Algorithm (IMEA) [120].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

96 / 156

Multi-objective concepts
Bi-objective problem
Ray et al. [109] proposed the Infeasibility Driven Evolutionary
Algorithm (IDEA).
The second objective is the constraint violation measure, (zerovalue for feasible solutions and a sum of ranking values based on
the violation per constraint).
The union of parents and offspring is split in two sets, one with thefeasible solutions and the other with the infeasible ones.
Non-dominated sorting ranks both sets separately and, based on
the proportion of desired feasible solutions, they are chosen firstfrom the infeasible set and later on, the best ranked feasible
solutions are chosen.
SQP was added to IDEA in the Infeasibility Empowered Memetic
Algorithm (IMEA) [120].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

96 / 156

Multi-objective concepts
Bi-objective problem
Ray et al. [109] proposed the Infeasibility Driven Evolutionary
Algorithm (IDEA).
The second objective is the constraint violation measure, (zerovalue for feasible solutions and a sum of ranking values based on
the violation per constraint).
The union of parents and offspring is split in two sets, one with thefeasible solutions and the other with the infeasible ones.
Non-dominated sorting ranks both sets separately and, based on
the proportion of desired feasible solutions, they are chosen firstfrom the infeasible set and later on, the best ranked feasible
solutions are chosen.
SQP was added to IDEA in the Infeasibility Empowered Memetic
Algorithm (IMEA) [120].
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

96 / 156

Multi-objective concepts

Bi-objective problem
Wang et al. [147], in their adaptive trade-off model (ATM) divided
the search in three phases based on the feasibility of solutions in
the population:
Only infeasible solutions (Pareto dominance)
Feasible and infeasible solutions (fitness value based on feasible
solutions ratio).
Only feasible solutions (objective function).

Wang et al. [146] used the ATM with a NIA in which the variation
operators were simplex crossover and one of two mutations.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

97 / 156

Multi-objective concepts

Bi-objective problem
Wang et al. [147], in their adaptive trade-off model (ATM) divided
the search in three phases based on the feasibility of solutions in
the population:
Only infeasible solutions (Pareto dominance)
Feasible and infeasible solutions (fitness value based on feasible
solutions ratio).
Only feasible solutions (objective function).

Wang et al. [146] used the ATM with a NIA in which the variation
operators were simplex crossover and one of two mutations.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

97 / 156

Multi-objective concepts

Bi-objective problem
Wang et al. [145] added a shrinking mechanism to ATM in the
Accelerated ATM (AATM).
The ATM was coupled with DE in a recent approach [143],
showing an improvement in the results.
Liu et al. [72] used the ATM in an EA but with two maindifferences:
Good point set crossover was used to generate offspring.
Feasibility rules were the criteria to select solutions in the second
stage of the ATM.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

98 / 156

Multi-objective concepts

Bi-objective problem
Wang et al. [145] added a shrinking mechanism to ATM in the
Accelerated ATM (AATM).
The ATM was coupled with DE in a recent approach [143],
showing an improvement in the results.
Liu et al. [72] used the ATM in an EA but with two maindifferences:
Good point set crossover was used to generate offspring.
Feasibility rules were the criteria to select solutions in the second
stage of the ATM.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

98 / 156

Multi-objective concepts

Bi-objective problem
Wang et al. [145] added a shrinking mechanism to ATM in the
Accelerated ATM (AATM).
The ATM was coupled with DE in a recent approach [143],
showing an improvement in the results.
Liu et al. [72] used the ATM in an EA but with two maindifferences:
Good point set crossover was used to generate offspring.
Feasibility rules were the criteria to select solutions in the second
stage of the ATM.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

98 / 156

Multi-objective concepts
Bi-objective problem
Li et al. [64] used a PSO algorithm in which Pareto dominance
was used as a criterion in the pbest update process and in theselection of the local-best leaders in a neighborhood. The sum of
constraint violation worked as a tie-breaker.
Venter and Haftka [139] also adopted PSO as their searchalgorithm. However, the leader selection was based most of thetime on the sum of constraint violation, while the rest of the time
the criterion was one of the three following choices:
The original objective function.
The crowding distance.
Pareto dominance.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

99 / 156

Multi-objective concepts
Bi-objective problem
Li et al. [64] used a PSO algorithm in which Pareto dominance
was used as a criterion in the pbest update process and in theselection of the local-best leaders in a neighborhood. The sum of
constraint violation worked as a tie-breaker.
Venter and Haftka [139] also adopted PSO as their searchalgorithm. However, the leader selection was based most of thetime on the sum of constraint violation, while the rest of the time
the criterion was one of the three following choices:
The original objective function.
The crowding distance.
Pareto dominance.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

99 / 156

Multi-objective concepts
Bi-objective problem
Wang et al. [141] used a hybrid selection mechanism based on
Pareto dominance and tournament selection into a Adaptive
Bacterial Foraging Algorithm (ABFA).
Wang et al. [144] proposed the use of Pareto dominance in a
Hybrid Constrained EA (HCOEA). A global search carried out by
an EA is coupled to a local search operator based on SPX.
Wang et al. [148] proposed a steady state EA by applying
orthogonal crossover to a randomly chosen set of solutions in thecurrent population. After that, the non-dominated solutions
obtained from the set of offspring are chosen. Alternative,
solutions can also be chosen if they have a lower sum of
constraint violation.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

100 / 156

Multi-objective concepts
Bi-objective problem
Wang et al. [141] used a hybrid selection mechanism based on
Pareto dominance and tournament selection into a Adaptive
Bacterial Foraging Algorithm (ABFA).
Wang et al. [144] proposed the use of Pareto dominance in a
Hybrid Constrained EA (HCOEA). A global search carried out by
an EA is coupled to a local search operator based on SPX.
Wang et al. [148] proposed a steady state EA by applying
orthogonal crossover to a randomly chosen set of solutions in thecurrent population. After that, the non-dominated solutions
obtained from the set of offspring are chosen. Alternative,
solutions can also be chosen if they have a lower sum of
constraint violation.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

100 / 156

Multi-objective concepts
Bi-objective problem
Wang et al. [141] used a hybrid selection mechanism based on
Pareto dominance and tournament selection into a Adaptive
Bacterial Foraging Algorithm (ABFA).
Wang et al. [144] proposed the use of Pareto dominance in a
Hybrid Constrained EA (HCOEA). A global search carried out by
an EA is coupled to a local search operator based on SPX.
Wang et al. [148] proposed a steady state EA by applying
orthogonal crossover to a randomly chosen set of solutions in thecurrent population. After that, the non-dominated solutions
obtained from the set of offspring are chosen. Alternative,
solutions can also be chosen if they have a lower sum of
constraint violation.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

100 / 156

Multi-objective concepts

Three-objective problem
Reynoso-Meza et al. [111] proposed the spherical-pruning
multi-objective optimization differential evolution (sp-MODE).
The second objective was the sum of constraint violation forinequality constraints and the third objective was the sum of
constraint violation for equality constraints.
An external archive was used to store non-dominated solutions.
The sphere-pruning operator aims to find the best trade-off
between feasibility and the optimization of the objective function.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

101 / 156

Multi-objective concepts

Three-objective problem
Reynoso-Meza et al. [111] proposed the spherical-pruning
multi-objective optimization differential evolution (sp-MODE).
The second objective was the sum of constraint violation forinequality constraints and the third objective was the sum of
constraint violation for equality constraints.
An external archive was used to store non-dominated solutions.
The sphere-pruning operator aims to find the best trade-off
between feasibility and the optimization of the objective function.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

101 / 156

Multi-objective concepts

Three-objective problem
Reynoso-Meza et al. [111] proposed the spherical-pruning
multi-objective optimization differential evolution (sp-MODE).
The second objective was the sum of constraint violation forinequality constraints and the third objective was the sum of
constraint violation for equality constraints.
An external archive was used to store non-dominated solutions.
The sphere-pruning operator aims to find the best trade-off
between feasibility and the optimization of the objective function.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

101 / 156

Multi-objective concepts

Three-objective problem
Reynoso-Meza et al. [111] proposed the spherical-pruning
multi-objective optimization differential evolution (sp-MODE).
The second objective was the sum of constraint violation forinequality constraints and the third objective was the sum of
constraint violation for equality constraints.
An external archive was used to store non-dominated solutions.
The sphere-pruning operator aims to find the best trade-off
between feasibility and the optimization of the objective function.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

101 / 156

Multi-objective concepts

Three-objective problem
Zeng et al. [154] proposed converting a constrained problem intoa dynamic constrained three-objective optimization problem.
The original objective.
The constraint-violation (decreasing).
A niche count (decreasing).

Three evolutionary multi-objective optimization algorithms were
tested in the approach.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

102 / 156

Multi-objective concepts

Three-objective problem
Zeng et al. [154] proposed converting a constrained problem intoa dynamic constrained three-objective optimization problem.
The original objective.
The constraint-violation (decreasing).
A niche count (decreasing).

Three evolutionary multi-objective optimization algorithms were
tested in the approach.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

102 / 156

Multi-objective concepts

Many-objective problem
Gong and Cai [33] used Pareto dominance in the space definedby the constraints of a problem as a constraint-handlingmechanism in a DE-based approach.
An orthogonal process was employed for both, generating theinitial population and for applying crossover.
An external archive stored non-dominated solutions.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

103 / 156

Multi-objective concepts

Many-objective problem
Gong and Cai [33] used Pareto dominance in the space definedby the constraints of a problem as a constraint-handlingmechanism in a DE-based approach.
An orthogonal process was employed for both, generating theinitial population and for applying crossover.
An external archive stored non-dominated solutions.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

103 / 156

Multi-objective concepts

Many-objective problem
Gong and Cai [33] used Pareto dominance in the space definedby the constraints of a problem as a constraint-handlingmechanism in a DE-based approach.
An orthogonal process was employed for both, generating theinitial population and for applying crossover.
An external archive stored non-dominated solutions.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

103 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

104 / 156

Ensemble of constraint-handling techniques

Mallipeddi and Suganthan [78] proposed an ensemble of fourconstraint techniques (ECHT):
Feasibility rules.
Stochastic ranking.
A self-adaptive penalty function.
The "-constrained method.

A four sub-population scheme was considered.
One EP-based and one DE-based versions were designed.
Each constraint-handling technique was used to evolve an specificsub-population.
All sub-populations share all of their offspring,Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

105 / 156

Ensemble of constraint-handling techniques

Mallipeddi and Suganthan [78] proposed an ensemble of fourconstraint techniques (ECHT):
Feasibility rules.
Stochastic ranking.
A self-adaptive penalty function.
The "-constrained method.

A four sub-population scheme was considered.
One EP-based and one DE-based versions were designed.
Each constraint-handling technique was used to evolve an specificsub-population.
All sub-populations share all of their offspring,Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

105 / 156

Ensemble of constraint-handling techniques

Mallipeddi and Suganthan [78] proposed an ensemble of fourconstraint techniques (ECHT):
Feasibility rules.
Stochastic ranking.
A self-adaptive penalty function.
The "-constrained method.

A four sub-population scheme was considered.
One EP-based and one DE-based versions were designed.
Each constraint-handling technique was used to evolve an specificsub-population.
All sub-populations share all of their offspring,Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

105 / 156

Ensemble of constraint-handling techniques

Mallipeddi and Suganthan [78] proposed an ensemble of fourconstraint techniques (ECHT):
Feasibility rules.
Stochastic ranking.
A self-adaptive penalty function.
The "-constrained method.

A four sub-population scheme was considered.
One EP-based and one DE-based versions were designed.
Each constraint-handling technique was used to evolve an specificsub-population.
All sub-populations share all of their offspring,Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

105 / 156

Ensemble of constraint-handling techniques

Mallipeddi and Suganthan [78] proposed an ensemble of fourconstraint techniques (ECHT):
Feasibility rules.
Stochastic ranking.
A self-adaptive penalty function.
The "-constrained method.

A four sub-population scheme was considered.
One EP-based and one DE-based versions were designed.
Each constraint-handling technique was used to evolve an specificsub-population.
All sub-populations share all of their offspring,Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

105 / 156

Ensemble of constraint-handling techniques

Elsayed et al. [29] proposed a DE-based algorithm where the
combination of four DE-mutations, two DE recombinations andtwo constraint-handling techniques (feasibility rules and"-constrained method) generated sixteen variants which wereassigned to each individual in a single-population algorithm.
The rate of usage for each variant was based on its improvement
measured by its ability to generate better solutions.
A local search algorithm was applied.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

106 / 156

Ensemble of constraint-handling techniques

Elsayed et al. [29] proposed a DE-based algorithm where the
combination of four DE-mutations, two DE recombinations andtwo constraint-handling techniques (feasibility rules and"-constrained method) generated sixteen variants which wereassigned to each individual in a single-population algorithm.
The rate of usage for each variant was based on its improvement
measured by its ability to generate better solutions.
A local search algorithm was applied.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

106 / 156

Ensemble of constraint-handling techniques

Elsayed et al. [29] proposed a DE-based algorithm where the
combination of four DE-mutations, two DE recombinations andtwo constraint-handling techniques (feasibility rules and"-constrained method) generated sixteen variants which wereassigned to each individual in a single-population algorithm.
The rate of usage for each variant was based on its improvement
measured by its ability to generate better solutions.
A local search algorithm was applied.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

106 / 156

Ensemble of constraint-handling techniques

A similar idea was presented in a combination of two DE variants
and a variable neighborhood search with three constraint-handlingtechniques (feasibility rules, "-constrained method, and an
adaptive penalty function) by Tasgetiren et al. [131].

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

107 / 156

Ensemble of constraint-handling techniques

The ECHT opens a new paradigm in constraint-handlingtechniques.
The design of mechanisms which allow the combination of
approaches that can be seen as complementary (in terms of theway in which they operate).
However, as the combination of several techniques considerablyenhances the capabilities of an approach, it is also required todefine parameter values for each of these techniques.
Parameter control [74] becomes an important issue when
designing ensemble approaches.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

108 / 156

Ensemble of constraint-handling techniques

The ECHT opens a new paradigm in constraint-handlingtechniques.
The design of mechanisms which allow the combination of
approaches that can be seen as complementary (in terms of theway in which they operate).
However, as the combination of several techniques considerablyenhances the capabilities of an approach, it is also required todefine parameter values for each of these techniques.
Parameter control [74] becomes an important issue when
designing ensemble approaches.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

108 / 156

Ensemble of constraint-handling techniques

The ECHT opens a new paradigm in constraint-handlingtechniques.
The design of mechanisms which allow the combination of
approaches that can be seen as complementary (in terms of theway in which they operate).
However, as the combination of several techniques considerablyenhances the capabilities of an approach, it is also required todefine parameter values for each of these techniques.
Parameter control [74] becomes an important issue when
designing ensemble approaches.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

108 / 156

Ensemble of constraint-handling techniques

The ECHT opens a new paradigm in constraint-handlingtechniques.
The design of mechanisms which allow the combination of
approaches that can be seen as complementary (in terms of theway in which they operate).
However, as the combination of several techniques considerablyenhances the capabilities of an approach, it is also required todefine parameter values for each of these techniques.
Parameter control [74] becomes an important issue when
designing ensemble approaches.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

108 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

109 / 156

A bird’s eye view

TechniqueFR

Core
conceptThree criteria for
pairwise selection

SR

Ranking process"-CM

Transforms a constrained
problem into an
unconstrained problem
Focus on adaptive and dynamic
approaches
Focus on boundary
operators andequality constraints
Focused on bi-objective
transformationof a CNOP
Pareto dominance
Combination of two
or more constraint-handlingtechniques

NPF
NSO
MOC

ECHT

Efrén Mezura-Montes

Pros

Cons

Simple to add
into a NIA
No extra parameters
Easy to implement

May causepremature convergence

Very competitive
performanceWell-known
transformation process
Tendency to design
easy to generalize
operators
Both, Pareto
ranking and dominancestill popular
Verycompetitive
performance

Constraint-Handling in Nat-Insp. Opt.

Not all NIAs haveordering in their processes
One extra parameter
Extra parameters
Local search forhigh performance
Some of them
add extra parameters
Stilllimited usage
May require
an additional
constraint-handlingtechniqueRequires thedefinition ofseveral parameter values

CEC 2017, SPAIN

110 / 156

How important is the search algorithm?
DE is the most preferred algorithm, usually coupled with thefeasibility rules.
GAs are popular when coupled with penalty functions.
PSO has been mainly coupled with the feasibility rules as well.
ES has been usually coupled with the stochastic ranking.
EP, ACO scarcely used.
Among novel algorithms, ABC with feasibility rules has been
particularly popular.
AIS recently coupled with the feasibility rules.
Gradient-based local search frequently found.
Special operators focused on equality constraints.
Multi-operator algorithms preferred over hybrid approaches.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

111 / 156

How important is the search algorithm?
DE is the most preferred algorithm, usually coupled with thefeasibility rules.
GAs are popular when coupled with penalty functions.
PSO has been mainly coupled with the feasibility rules as well.
ES has been usually coupled with the stochastic ranking.
EP, ACO scarcely used.
Among novel algorithms, ABC with feasibility rules has been
particularly popular.
AIS recently coupled with the feasibility rules.
Gradient-based local search frequently found.
Special operators focused on equality constraints.
Multi-operator algorithms preferred over hybrid approaches.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

111 / 156

How important is the search algorithm?
DE is the most preferred algorithm, usually coupled with thefeasibility rules.
GAs are popular when coupled with penalty functions.
PSO has been mainly coupled with the feasibility rules as well.
ES has been usually coupled with the stochastic ranking.
EP, ACO scarcely used.
Among novel algorithms, ABC with feasibility rules has been
particularly popular.
AIS recently coupled with the feasibility rules.
Gradient-based local search frequently found.
Special operators focused on equality constraints.
Multi-operator algorithms preferred over hybrid approaches.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

111 / 156

How important is the search algorithm?
DE is the most preferred algorithm, usually coupled with thefeasibility rules.
GAs are popular when coupled with penalty functions.
PSO has been mainly coupled with the feasibility rules as well.
ES has been usually coupled with the stochastic ranking.
EP, ACO scarcely used.
Among novel algorithms, ABC with feasibility rules has been
particularly popular.
AIS recently coupled with the feasibility rules.
Gradient-based local search frequently found.
Special operators focused on equality constraints.
Multi-operator algorithms preferred over hybrid approaches.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

111 / 156

How important is the search algorithm?
DE is the most preferred algorithm, usually coupled with thefeasibility rules.
GAs are popular when coupled with penalty functions.
PSO has been mainly coupled with the feasibility rules as well.
ES has been usually coupled with the stochastic ranking.
EP, ACO scarcely used.
Among novel algorithms, ABC with feasibility rules has been
particularly popular.
AIS recently coupled with the feasibility rules.
Gradient-based local search frequently found.
Special operators focused on equality constraints.
Multi-operator algorithms preferred over hybrid approaches.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

111 / 156

How important is the search algorithm?
DE is the most preferred algorithm, usually coupled with thefeasibility rules.
GAs are popular when coupled with penalty functions.
PSO has been mainly coupled with the feasibility rules as well.
ES has been usually coupled with the stochastic ranking.
EP, ACO scarcely used.
Among novel algorithms, ABC with feasibility rules has been
particularly popular.
AIS recently coupled with the feasibility rules.
Gradient-based local search frequently found.
Special operators focused on equality constraints.
Multi-operator algorithms preferred over hybrid approaches.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

111 / 156

How important is the search algorithm?
DE is the most preferred algorithm, usually coupled with thefeasibility rules.
GAs are popular when coupled with penalty functions.
PSO has been mainly coupled with the feasibility rules as well.
ES has been usually coupled with the stochastic ranking.
EP, ACO scarcely used.
Among novel algorithms, ABC with feasibility rules has been
particularly popular.
AIS recently coupled with the feasibility rules.
Gradient-based local search frequently found.
Special operators focused on equality constraints.
Multi-operator algorithms preferred over hybrid approaches.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

111 / 156

How important is the search algorithm?
DE is the most preferred algorithm, usually coupled with thefeasibility rules.
GAs are popular when coupled with penalty functions.
PSO has been mainly coupled with the feasibility rules as well.
ES has been usually coupled with the stochastic ranking.
EP, ACO scarcely used.
Among novel algorithms, ABC with feasibility rules has been
particularly popular.
AIS recently coupled with the feasibility rules.
Gradient-based local search frequently found.
Special operators focused on equality constraints.
Multi-operator algorithms preferred over hybrid approaches.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

111 / 156

How important is the search algorithm?
DE is the most preferred algorithm, usually coupled with thefeasibility rules.
GAs are popular when coupled with penalty functions.
PSO has been mainly coupled with the feasibility rules as well.
ES has been usually coupled with the stochastic ranking.
EP, ACO scarcely used.
Among novel algorithms, ABC with feasibility rules has been
particularly popular.
AIS recently coupled with the feasibility rules.
Gradient-based local search frequently found.
Special operators focused on equality constraints.
Multi-operator algorithms preferred over hybrid approaches.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

111 / 156

How important is the search algorithm?
DE is the most preferred algorithm, usually coupled with thefeasibility rules.
GAs are popular when coupled with penalty functions.
PSO has been mainly coupled with the feasibility rules as well.
ES has been usually coupled with the stochastic ranking.
EP, ACO scarcely used.
Among novel algorithms, ABC with feasibility rules has been
particularly popular.
AIS recently coupled with the feasibility rules.
Gradient-based local search frequently found.
Special operators focused on equality constraints.
Multi-operator algorithms preferred over hybrid approaches.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

111 / 156

Benchmarks
The first one
Function
g01
g02
g03
g04
g05
g06
g07
g08
g09
g10
g11
g12
g13
g14
g15
g16
g17
g18
g19
g20
g21
g22
g23
g24

Efrén Mezura-Montes

n
13
20
10
5
4
2
10
2
7
8
2
3
5
10
3
5
6
9
15
24
7
22
9
2

Type of function
quadratic
nonlinear
nonlinearquadratic
nonlinear
nonlinearquadratic
nonlinear
nonlinearlinearquadratic
quadratic
nonlinear
nonlinearquadratic
nonlinear
nonlinearquadratic
nonlinearlinearlinearlinearlinearlinear⇢0.0003%99.9973%
0.0026%27.0079%0.0000%0.0057%0.0000%0.8581%0.5199%0.0020%0.0973%4.7697%0.0000%0.0000%0.0000%0.0204%0.0000%0.0000%33.4761%0.0000%0.0000%0.0000%0.0000%79.6556%

LI
9
2
0
4
2
0
3
0
0
6
0
0
0
0
0
4
0
0
0
0
0
0
0
0

Constraint-Handling in Nat-Insp. Opt.

NI
0
0
0
2
0
2
5
2
4
0
0
1
0
0
0
34
0
13
5
6
1
1
2
2

LE
0
0
0
0
0
0
0
0
0
0
0
0
1
3
1
0
0
0
0
2
0
8
3
0

NE
0
0
1
0
3
0
0
0
0
0
1
0
2
0
1
0
4
0
0
12
5
11
1
0

a
6
1
1
2
3
2
6
0
2
6
1
0
3
3
2
4
4
6
0
16
6
19
6
2

CEC 2017, SPAIN

112 / 156

Benchmarks

The second one

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

113 / 156

Benchmarks
The second one

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

114 / 156

Benchmarks
The most recent

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

115 / 156

Benchmarks
The most recent

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

116 / 156

Performance measures

Evals (number of solution evaluations to find a feasible solution).
Progress ratio (difference between the objective function value ofthe first and best feasible solutions found).
AFES (average number of solution evaluations in a set of
successful runs).
FP (percentage of feasible runs).
P (percentage of successful runs).
SP (successful performance computed by AFES divided by P).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

117 / 156

Performance measures

Evals (number of solution evaluations to find a feasible solution).
Progress ratio (difference between the objective function value ofthe first and best feasible solutions found).
AFES (average number of solution evaluations in a set of
successful runs).
FP (percentage of feasible runs).
P (percentage of successful runs).
SP (successful performance computed by AFES divided by P).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

117 / 156

Performance measures

Evals (number of solution evaluations to find a feasible solution).
Progress ratio (difference between the objective function value ofthe first and best feasible solutions found).
AFES (average number of solution evaluations in a set of
successful runs).
FP (percentage of feasible runs).
P (percentage of successful runs).
SP (successful performance computed by AFES divided by P).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

117 / 156

Performance measures

Evals (number of solution evaluations to find a feasible solution).
Progress ratio (difference between the objective function value ofthe first and best feasible solutions found).
AFES (average number of solution evaluations in a set of
successful runs).
FP (percentage of feasible runs).
P (percentage of successful runs).
SP (successful performance computed by AFES divided by P).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

117 / 156

Performance measures

Evals (number of solution evaluations to find a feasible solution).
Progress ratio (difference between the objective function value ofthe first and best feasible solutions found).
AFES (average number of solution evaluations in a set of
successful runs).
FP (percentage of feasible runs).
P (percentage of successful runs).
SP (successful performance computed by AFES divided by P).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

117 / 156

Performance measures

Evals (number of solution evaluations to find a feasible solution).
Progress ratio (difference between the objective function value ofthe first and best feasible solutions found).
AFES (average number of solution evaluations in a set of
successful runs).
FP (percentage of feasible runs).
P (percentage of successful runs).
SP (successful performance computed by AFES divided by P).

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

117 / 156

Outline
1

2

3

4

Introduction
The problem of interest
Some important concepts
Mathematical-programming methods
Why alternative methods?
The early years
Penalty functions
Decoders
Special operators
Separation of objective function and constraints
General comments
Current constraint-handling techniques
Feasibility rules
Stochastic ranking"-constrained method
Novel penalty functions
Novel special operators
Multi-objective concepts
Ensemble of constraint-handling techniques
Summary and current trends
A bird’s eye view
Current trends

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

118 / 156

Current trends

Constraint-handling for EMO
EMO approaches usually adopt constraint-handling techniques for
single-objective optimization.
Topics of interest:
Performance measures.
Diversity mechanisms.
Boundary operators.
Many-objective multi-constrained optimization.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

119 / 156

Current trends

Constraint-handling for EMO
EMO approaches usually adopt constraint-handling techniques for
single-objective optimization.
Topics of interest:
Performance measures.
Diversity mechanisms.
Boundary operators.
Many-objective multi-constrained optimization.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

119 / 156

Current trends

Constraint approximation
Fitness approximation methods have been extensively applied tounconstrained optimization problems.
Jin [47] proposed to enlarge the feasible region by using
surrogates to ease the generation of fesible solutions.
Regis [110] used radial basis functions as surrogates toapproximate constraints and objective functions in constrained
multi-objective optimization problems.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

120 / 156

Current trends

Constraint approximation
Fitness approximation methods have been extensively applied tounconstrained optimization problems.
Jin [47] proposed to enlarge the feasible region by using
surrogates to ease the generation of fesible solutions.
Regis [110] used radial basis functions as surrogates toapproximate constraints and objective functions in constrained
multi-objective optimization problems.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

120 / 156

Current trends

Constraint approximation
Fitness approximation methods have been extensively applied tounconstrained optimization problems.
Jin [47] proposed to enlarge the feasible region by using
surrogates to ease the generation of fesible solutions.
Regis [110] used radial basis functions as surrogates toapproximate constraints and objective functions in constrained
multi-objective optimization problems.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

120 / 156

Current trends

Constraint approximation
Datta and Regis [24] proposed an evolution strategy coupled withcubic radial basis functions to solve constrained multi-objective
optimization problems.
Miranda-Varela and Mezura-Montes [97] added feasibility
information in the evolution control of a surrogate-assisteddifferential evolution to solve constrained optimization problems.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

121 / 156

Current trends

Constraint approximation
Datta and Regis [24] proposed an evolution strategy coupled withcubic radial basis functions to solve constrained multi-objective
optimization problems.
Miranda-Varela and Mezura-Montes [97] added feasibility
information in the evolution control of a surrogate-assisteddifferential evolution to solve constrained optimization problems.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

121 / 156

Current trends

Dynamic constraints
There is a considerable amount of research devoted to deal withunconstrained dynamic optimization problems.
Initial efforts have focused on constrained dynamic optimization
problems.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

122 / 156

Current trends

Dynamic constraints
There is a considerable amount of research devoted to deal withunconstrained dynamic optimization problems.
Initial efforts have focused on constrained dynamic optimization
problems.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

122 / 156

Current trends

Dynamic constraints
Nguyen and Yao [99] started the research on DCOPs, byproviding a benchmark and an initial comparison of algorithms
based mainly on hypermutation and repair methods.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

123 / 156

Current trends
BenchmarkEfrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

124 / 156

Current trends

Dynamic constraints
Pal et al. [101] proposed one of the first competitive algorithms for
DCOPs based on the gravitational search algorithm and a repair
method.
Ameca-Alducin et al. [3] proposed a DE-based approach with arepair mechanism based on sampling to solve DCOPs.
Immigrants and change of DE variants were used as well.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

125 / 156

Current trends

Dynamic constraints
Pal et al. [101] proposed one of the first competitive algorithms for
DCOPs based on the gravitational search algorithm and a repair
method.
Ameca-Alducin et al. [3] proposed a DE-based approach with arepair mechanism based on sampling to solve DCOPs.
Immigrants and change of DE variants were used as well.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

125 / 156

Current trends

Dynamic constraints
Sharma & Sharma [119] used special operators and Tabu searchconcepts to deal with DCOPs.
Aragón et al. [5] proposed a T-cell-inspired approach to solve
DCOPs where four sub-populations with different goals interacted
in the dynamic search space.
Bu et al. [15] proposed two new benchmarks and a dynamic
species-based PSO with an ensemble of tracking feasible regions
strategies.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

126 / 156

Current trends

Dynamic constraints
Sharma & Sharma [119] used special operators and Tabu searchconcepts to deal with DCOPs.
Aragón et al. [5] proposed a T-cell-inspired approach to solve
DCOPs where four sub-populations with different goals interacted
in the dynamic search space.
Bu et al. [15] proposed two new benchmarks and a dynamic
species-based PSO with an ensemble of tracking feasible regions
strategies.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

126 / 156

Current trends

Dynamic constraints
Sharma & Sharma [119] used special operators and Tabu searchconcepts to deal with DCOPs.
Aragón et al. [5] proposed a T-cell-inspired approach to solve
DCOPs where four sub-populations with different goals interacted
in the dynamic search space.
Bu et al. [15] proposed two new benchmarks and a dynamic
species-based PSO with an ensemble of tracking feasible regions
strategies.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

126 / 156

Current trends

Ensembles/multi-operator NIAs
This topic is still in its starting phase.
More combinations and adaptive mechanisms within theensembles of constraint-handling techniques and/or multi-operator
NIAs are expected.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

127 / 156

Current trends

Ensembles/multi-operator NIAs
This topic is still in its starting phase.
More combinations and adaptive mechanisms within theensembles of constraint-handling techniques and/or multi-operator
NIAs are expected.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

127 / 156

Current trends

TheoryThere is some work on runtime analysis in constrained search
spaces with EAs [158] and also in the usefulness of infeasible
solutions in the search process [153].
Other theoretical studies have focused on some ES variants, suchas the (1+1)-ES [10] and more recently the (1, )-ES [9].
More research in this area is required.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

128 / 156

Current trends

TheoryThere is some work on runtime analysis in constrained search
spaces with EAs [158] and also in the usefulness of infeasible
solutions in the search process [153].
Other theoretical studies have focused on some ES variants, suchas the (1+1)-ES [10] and more recently the (1, )-ES [9].
More research in this area is required.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

128 / 156

Current trends

TheoryThere is some work on runtime analysis in constrained search
spaces with EAs [158] and also in the usefulness of infeasible
solutions in the search process [153].
Other theoretical studies have focused on some ES variants, suchas the (1+1)-ES [10] and more recently the (1, )-ES [9].
More research in this area is required.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

128 / 156

References I
S. Akhtar, K. Tai, and T. Ray.
A Socio-Behavioural Simulation Model for Engineering Design Optimization.
Engineering Optimization, 34(4):341–354, 2002.
M. M. Ali and Z. Kajee-Bagdadi.
A local exploration-based differential evolution algorithm for constrained global optimization.
Applied Mathematics and Computation, 208(1):31–48, February 1 2009.
M.-Y. Ameca-Alducin, E. Mezura-Montes, and N. Cruz-Ramı́rez.
Differential evolution with combined variants and a repair method to solve dynamic constrained optimization problems.
Soft Computing, pages 1–30, 2016.
A. Angantyr, J. Andersson, and J.-O. Aidanpaa.
Constrained Optimization based on a Multiobjective Evolutionary Algorithms.
In Proceedings of the Congress on Evolutionary Computation 2003 (CEC’2003), volume 3, pages 1560–1567,
Piscataway, New Jersey, December 2003. Canberra, Australia, IEEE Service Center.
V. Aragón, S. Esquivel, and C. Coello-Coello.
Artificial immune system for solving dynamic constrained optimization problems.
In E. Alba, A. Nakib, and P. Siarry, editors, Metaheuristics for dynamic optimization, Studies in Computational Intelligence,
pages 225–263. Springer, Heidelberg, Germany, 2013.
V. S. Aragón, S. C. Esquivel, and C. A. Coello Coello.
Artificial immune system for solving constrained optimization problems.
Revista Iberoamericana de Inteligencia Artificial, 11(35):55–66, 2007.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

129 / 156

References II
V. S. Aragón, S. C. Esquivel, and C. A. Coello Coello.
A novel model of artificial immune system for solving constrained optimization problems with dynamic tolerance factor.
In A. Gelbukh and Ángel Fernando Kuri Morales, editors, Proceedings of the Mexican International Conference on
Artificial Intelligence (MICAI’2007), pages 19–29, Aguascalientes, México, November 2007. Springer. Lecture Notes in
Artificial Intelligence Vol. 4827.
M. C. Araujo, E. F. Wanner, F. G. G. aes, and R. H. C. Takahashi.
Constrained Optimization Based on Quadratic Approximations in Genetic Algorithms.
In E. Mezura-Montes, editor, Constraint-Handling in Evolutionary Computation, chapter 9, pages 193–217. Springer.
Studies in Computational Intelligence, Volume 198, Berlin, 2009.
ISBN 978-3-642-00618-0.
D. Arnold.
On the behaviour of the (1, )-ES for a simple constrained problem.
In Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms (FOGA’2011), pages 15–24. ACM Press,
June 2011.
D. V. Arnold and D. Brauer.
On the Behaviour of the (1+1)-ES for a Simple Constrained Problem.
In G. Rudolph, T. Jansen, S. Lucas, C. Poloni, and N. Beume, editors, Parallel Problem Solving from Nature–PPSN X,
pages 1–10. Springer. Lecture Notes in Computer Science Vol. 5199, Dortmund, Germany, September 2008.
H. J. Barbosa and A. C. Lemonge.
An adaptive penalty scheme in genetic algorithms for constrained optimization problems.
In W. Langdon and et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’2002),
pages 287–294, San Francisco, California, July 2002. Morgan Kaufmann Publishers.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

130 / 156

References III
J. Brest.
Constrained real-parameter optimization with ✏-self-adaptive differential evolution.
In E. Mezura-Montes, editor, Constraint-Handling in Evolutionary Optimization, volume 198, pages 73–93.
Springer-Verlag, Studies in Computational Intelligence Series, ISBN:978-3-642-00618-0, 2009.
J. Brest, B. Boškovič, and V. Žumer.
An improved self-adaptive differential evolution algorithm in single objective constrained real-parameter optimization.
In 2010 Congress on Evolutionary Computation (CEC’2010), pages 1073–1078, Barcelona, Spain, July 2010. IEEE
Service Center.
J. Brest, V. Zumer, and M. S. Maucec.
Self-Adaptative Differential Evolution Algorithm in Constrained Real-Parameter Optimization.
In 2006 IEEE Congress on Evolutionary Computation (CEC’2006), pages 919–926, Vancouver, BC, Canada, July 2006.
IEEE.
C. Bu, W. Luo, and L. Yue.
Continuous dynamic constrained optimization with ensemble of locating and tracking feasible regions strategies.
IEEE Transactions on Evolutionary Computation, 21(1):14–33, 2017.
L. Cagnina, S. Esquivel, and C. Coello-Coello.
A Bi-population PSO with a Shake-Mechanism for Solving Constrained Numerical Optimization.
In 2007 IEEE Congress on Evolutionary Computation (CEC’2007), pages 670–676, Singapore, September 2007. IEEE
Press.
L. C. Cagnina, S. C. Esquivel, and C. A. C. Coello.
A Particle Swarm Optimizer for Constrained Numerical Optimization.
In T. P. Runarsson, H.-G. Beyer, E. Burke, J. J. Merelo-Guervós, L. D. Whitley, and X. Yao, editors, Parallel Problem
Solving from Nature (PPSN IX). 9th International Conference, pages 910–919, Reykjavik, Iceland, September 2006.
Reykjavik, Iceland, Springer.
Lecture Notes in Computer Science Vol. 4193.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

131 / 156

References IV
C. A. C. Coello.
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, January 2002.
C. A. Coello Coello.
Treating Constraints as Objectives for Single-Objective Evolutionary Optimization.
Engineering Optimization, 32(3):275–308, 2000.
C. A. Coello Coello.
Use of a Self-Adaptive Penalty Approach for Engineering Optimization Problems.
Computers in Industry, 41(2):113–127, January 2000.
W. A. Crossley and E. A. Williams.
A Study of Adaptive Penalty Functions for Constrained Genetic Algorithm Based Optimization.
In AIAA 35th Aerospace Sciences Meeting and Exhibit, Reno, Nevada, January 1997. AIAA Paper 97-0083.
N. Cruz-Cortés, D. Trejo-Pérez, and C. A. C. Coello.
Handling Constraints in Global Optimization using an Artificial Immune System.
In C. Jacob, M. L. Pilat, P. J. Bentley, and J. Timmis, editors, Artificial Immune Systems. 4th International Conference,
ICARIS 2005, pages 234–247, Banff, Canada, August 2005. Springer.
Lecture Notes in Computer Science Vol. 3627.
R. Datta and K. Deb.
A bi-objective based hybrid evolutionary-classical algorithm for handling equality constraints.
In R. Takahashi and et al., editors, 2011 Evolutionary Multicriterion Optimization Conference (EMO’2011), pages
313–327, Heidelberg, Germany, April 2011. Springer-Verlag.
LNCS Vol. 6576.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

132 / 156

References V
R. Datta and R. G. Regis.
A surrogate-assisted evolution strategy for constrained multi-objective optimization.
Journal of Computational Science, 57:270–284, 2016.
K. Deb.
An Efficient Constraint Handling Method for Genetic Algorithms.
Computer Methods in Applied Mechanics and Engineering, 186(2/4):311–338, 2000.
K. Deb and R. Datta.
A Fast and Accurate Solution of Constrained Optimization Problems Using a Hybrid Bi-Objective and Penalty Function
Approach.
In 2010 IEEE Congress on Evolutionary Computation (CEC’2010), pages 165–172, Barcelona, Spain, July 18–23 2010.
IEEE Press.
S. Elsayed, R. Sarker, and D. Essam.
A comparative study of different variants of genetic algorithms for constrained optimization.
In 2010 International Conference on Simulated Evolution and Learning (SEAL’2010), pages 177–186, Kanpur, India,
December 2010. Springer LNCS Vol. 6457.
S. Elsayed, R. Sarker, and D. Essam.
Ga with a new multi-parent crossover for constrained optimization.
In 2011 IEEE Congress on Evolutionary Computation (CEC’2011), pages 857–864, New Orleans, USA, July 2011. IEEE
Press.
S. Elsayed, R. Sarker, and D. Essam.
Integrated strategies differential evolution algorithm with a local search for constrained optimization.
In 2011 IEEE Congress on Evolutionary Computation (CEC’2011), pages 2618–2625, New Orleans, USA, July 2011.
IEEE Press.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

133 / 156

References VI
Z. Fan, J. Liu, T. Sorensen, and P. Wang.
Improved differential evolution based on stochastic ranking for robust layout synthesis of mems components.
IEEE Transactions on Industrial Electronics, 56(4):937–948, April 2009.
R. Farmani and J. A. Wright.
Self-Adaptive Fitness Formulation for Constrained Optimization.
IEEE Transactions on Evolutionary Computation, 7(5):445–455, October 2003.
L. Fonseca, P. Capriles, H. Barbosa, and A. Lemonge.
A stochastic rank-based ant system for discrete structural optimization.
In Proceedings of the 2007 IEEE Swarm Intelligence Symposium (SIS 2007), pages 68–75, Honolulu, Hawaii, USA, April
2007. IEEE Press.
W. Gong and Z. Cai.
A Multiobjective Differential Evolution Algorithm for Constrained Optimization.
In 2008 Congress on Evolutionary Computation (CEC’2008), pages 181–188, Hong Kong, June 2008. IEEE Service
Center.
A. B. Hadj-Alouane and J. C. Bean.
A Genetic Algorithm for the Multiple-Choice Integer Program.
Operations Research, 45:92–101, 1997.
H. Hamda and M. Schoenauer.
Adaptive techniques for Evolutionary Topological Optimum Design.
In I. Parmee, editor, Proceedings of the Fourth International Conference on Adaptive Computing in Design and
Manufacture (ACDM’2000), pages 123–136, University of Plymouth, Devon, UK, April 2000. Springer-Verlag.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

134 / 156

References VII
S. B. Hamida and M. Schoenauer.
ASCHEA: New Results Using Adaptive Segregational Constraint Handling.
In Proceedings of the Congress on Evolutionary Computation 2002 (CEC’2002), volume 1, pages 884–889, Piscataway,
New Jersey, May 2002. IEEE Service Center.
N. Hamza, S. Elsayed, D. Essam, and R. Sarker.
Differential evolution combined with constraint consensus for constrained optimization.
In 2011 IEEE Congress on Evolutionary Computation (CEC’2011), pages 865–871, New Orleans, USA, July 2011. IEEE
Press.
Q. He and L. Wang.
A hybrid particle swarm optimization with a feasibility-based rule for constrained optimization.
Applied Mathematics and Computation, 186(2):1407–1422, March 15th 2007.
Q. He, L. Wang, and F.-Z. Huang.
Nonlinear Constrained Optimization by Enhanced Co-evolutionary PSO.
In 2008 Congress on Evolutionary Computation (CEC’2008), pages 83–89, Hong Kong, June 2008. IEEE Service Center.
A. Hernández-Aguirre, S. Botello-Rionda, C. A. Coello Coello, G. Lizárraga-Lizárraga, and E. Mezura-Montes.
Handling Constraints using Multiobjective Optimization Concepts.
International Journal for Numerical Methods in Engineering, 59(15):1989–2017, April 2004.
R. Hinterding and Z. Michalewicz.
Your Brains and My Beauty: Parent Matching for Constrained Optimisation.
In Proceedings of the 5th International Conference on Evolutionary Computation, pages 810–815, Anchorage, Alaska,
May 1998.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

135 / 156

References VIII
F. Hoffmeister and J. Sprave.
Problem-independent handling of constraints by use of metric penalty functions.
In L. J. Fogel, P. J. Angeline, and T. Bäck, editors, Proceedings of the Fifth Annual Conference on Evolutionary
Programming (EP’96), pages 289–294, San Diego, California, February 1996. The MIT Press.
A. Homaifar, S. H. Y. Lai, and X. Qi.
Constrained Optimization via Genetic Algorithms.
Simulation, 62(4):242–254, 1994.
G. Huan-Tong, S. Qing-Xi, J. Feng, and S. Yi-Jie.
An evolution strategy with stochastic ranking for solving reactive power optimization.
In 2009 2nd International Conference on Power Electronics and Intelligent Transportation System (PEITS’2009), pages
14–17, Shenzhen, Dec 19-20 2009. IEEE Press.
ISBN 978-1-4244-4544-8.
F.-Z. Huang, L. Wang, and Q. He.
A Hybrid Differential Evolution with Double Populations for Constrained Optimization.
In 2008 Congress on Evolutionary Computation (CEC’2008), pages 18–25, Hong Kong, June 2008. IEEE Service Center.
V. L. Huang, A. K. Qin, and P. N. Suganthan.
Self-adaptative Differential Evolution Algorithm for Constrained Real-Parameter Optimization.
In 2006 IEEE Congress on Evolutionary Computation (CEC’2006), pages 324–331, Vancouver, BC, Canada, July 2006.
IEEE.
Y. Jin.
Surrogate-assisted evolutionary computation: Recent advances and future challenges.
Swarm and Evolutionary Computation, 1(2):61–70, 2011.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

136 / 156

References IX
J. Joines and C. Houck.
On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GAs.
In D. Fogel, editor, Proceedings of the first IEEE Conference on Evolutionary Computation, pages 579–584, Orlando,
Florida, 1994. IEEE Press.
D. Karaboga and B. Akay.
A modified artificial bee colony (abc) algorithm for constrained optimization problems.
Applied Soft Computing, 11(3):3021–3031, 2011.
D. Karaboga and B. Basturk.
Artificial bee colony(abc) optimization algorithm for solving constrained optimization problems.
In P. Melin, O. Castillo, L. T. Aguilar, J. Kacptrzyk, and W. Pedrycz, editors, Foundations of Fuzzy Logic and Soft
Computing, 12th International Fuzzy Systems Association, World Congress, IFSA 2007, pages 789–798, Cancun,
Mexico, June 2007. Springer, Lecture Notes in Artificial Intelligence Vol. 4529.
S. Kazarlis and V. Petridis.
Varying Fitness Functions in Genetic Algorithms: Studying the Rate of Increase of the Dynamic Penalty Terms.
In A. E. Eiben, T. Bäck, M. Schoenauer, and H.-P. Schwefel, editors, Proceedings of the 5th Parallel Problem Solving fromNature (PPSN V), pages 211–220, Heidelberg, Germany, September 1998. Amsterdan, The Netherlands,
Springer-Verlag.
Lecture Notes in Computer Science Vol. 1498.
D. G. Kim and P. Husbands.
Riemann Mapping Constraint Handling Method for Genetic Algorithms.
Technical Report CSRP 469, COGS, University of Sussex, UK, 1997.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

137 / 156

References X
D. G. Kim and P. Husbands.
Landscape Changes and the Performance of Mapping Based Constraint Handling Methods.
In A. E. Eiben, T. Bäck, M. Schoenauer, and H.-P. Schwefel, editors, Proceedings of the 5th Parallel Problem Solving fromNature (PPSN V), pages 221–230, Heidelberg, Germany, September 1998. Amsterdan, The Netherlands,
Springer-Verlag.
Lecture Notes in Computer Science Vol. 1498.
D. G. Kim and P. Husbands.
Mapping Based Constraint Handling for Evolutionary Search; Thurston’s Circle Packing and Grid Generation.
In I. Parmee, editor, The Integration of Evolutionary and Adaptive Computing Technologies with Product/System Design
and Realisation, pages 161–173. Springer-Verlag, Plymouth, United Kingdom, April 1998.
R. Kowalczyk.
Constraint Consistent Genetic Algorithms.
In Proceedings of the 1997 IEEE Conference on Evolutionary Computation, pages 343–348, Indianapolis, USA, April
1997. IEEE.
S. Koziel and Z. Michalewicz.
A Decoder-based Evolutionary Algorithm for Constrained Parameter Optimization Problems.
In T. Bäck, A. E. Eiben, M. Schoenauer, and H.-P. Schwefel, editors, Proceedings of the 5th Parallel Problem Solving fromNature (PPSN V), pages 231–240, Heidelberg, Germany, September 1998. Amsterdan, The Netherlands,
Springer-Verlag.
Lecture Notes in Computer Science Vol. 1498.
S. Koziel and Z. Michalewicz.
Evolutionary Algorithms, Homomorphous Mappings, and Constrained Parameter Optimization.
Evolutionary Computation, 7(1):19–44, 1999.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

138 / 156

References XI
S. Kukkonen and J. Lampinen.
Constrained Real-Parameter Optimization with Generalized Differential Evolution.
In 2006 IEEE Congress on Evolutionary Computation (CEC’2006), pages 911–918, Vancouver, BC, Canada, July 2006.
IEEE.
A. Kuri-Morales and C. V. Quezada.
A Universal Eclectic Genetic Algorithm for Constrained Optimization.
In Proceedings 6th European Congress on Intelligent Techniques & Soft Computing, EUFIT’98, pages 518–522, Aachen,
Germany, September 1998. Verlag Mainz.
J. Lampinen.
A Constraint Handling Approach for the Differential Evolution Algorithm.
In Proceedings of the Congress on Evolutionary Computation 2002 (CEC’2002), volume 2, pages 1468–1473,
Piscataway, New Jersey, May 2002. IEEE Service Center.
R. Landa Becerra and C. A. Coello Coello.
Cultured differential evolution for constrained optimization.
Computer Methods in Applied Mechanics and Engineering, 195(33–36):4303–4322, July 1 2006.
G. Leguizamón and C. A. C. Coello.
Boundary Search for Constrained Numerical Optimization Problems with an Algorithm Inspired on the Ant Colony
Metaphor.
IEEE Transactions on Evolutionary Computation, 13(2):350–368, 2009.
G. Leguizamón and C. Coello-Coello.
A Boundary Search based ACO Algorithm Coupled with Stochastic Ranking.
In 2007 IEEE Congress on Evolutionary Computation (CEC’2007), pages 165–172, Singapore, September 2007. IEEE
Press.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

139 / 156

References XII
L. D. Li, X. Li, and X. Yu.
A Multi-Objective Constraint-Handling Method with PSO Algorithm for Constrained Engineering Optimization Problems.
In 2008 Congress on Evolutionary Computation (CEC’2008), pages 1528–1535, Hong Kong, June 2008. IEEE Service
Center.
S. Li and Y. Li.
A new self-adaption differential evolution algorithm based component model.
In Advances in Computation and Intelligence, pages 54–63. Springer. Lecture Notes in Computer Science, Vol. 6362,
2010.
Z. Li, J. Liang, X. He, and Z. Shang.
Differential evolution with dynamic constraint-handling mechanism.
In 2010 Congress on Evolutionary Computation (CEC’2010), pages 1899–1906, Barcelona, Spain, July 2010. IEEE
Service Center.
J. J. Liang and P. N. Suganthan.
Dynamic Multi-Swarm Particle Swarm Optimizer with a Novel Constrain-Handling Mechanism.
In 2006 IEEE Congress on Evolutionary Computation (CEC’2006), pages 316–323, Vancouver, BC, Canada, July 2006.
IEEE.
J. J. Liang, S. Zhigang, and L. Zhihui.
Coevolutionary comprehensive learning particle swarm optimizer.
In 2010 Congress on Evolutionary Computation (CEC’2010), pages 1505–1512, Barcelona, Spain, July 2010. IEEE
Service Center.
B. Liu, H. Ma, X. Zhang, B. Liu, and Y. Zhou.
A memetic co-evolutionary differential evolution algorithm for constrained optimization.
In 2007 IEEE Congress on Evolutionary Computation (CEC’2007), pages 2996–3002, Singapore, September 2007. IEEE
Press.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

140 / 156

References XIII
H. Liu, Z. Cai, and Y. Wang.
Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization.
Applied Soft Computing, 10(2):629–640, 2010.
J. Liu, Z. Fan, and E. D. Goodman.
SRaDE: An Adaptive Differential Evolution Based on Stochastic Ranking.
In 2009 Genetic and Evolutionary Computation Conference (GECCO’2009), pages 1871–1872, Montreal, Canada, July
8–12 2009. ACM Press.
ISBN 978-1-60558-325-9.
J. Liu, W. Zhong, and L. Hao.
An organizational evolutionary algorithm for numerical optimization.
IEEE Transactions on Systems, Man, and Cybernetics Part B—Cybernetics, 37(4):1052–1064, August 2007.
R. Liu, Y. Li, W. Zhang, and L. Jiao.
Stochastic ranking based differential evolution algorithm for constrained optimization problem.
In 2009 ACM SIGEVO Summit on Genetic and Evolutionary Computation (GEC’2009), pages 887–890, Shanghai, China,
June 12-14 2009. ACM Press.
ISBN 978-1-60558-326-6.
F. G. Lobo, C. F. Lima, and Z. Michalewicz, editors.
Parameter Setting in Evolutionary Algorithms.
Springer, Berlin, Germany, 2007.
H. Lu and W. Chen.
Self-adaptive velocity particle swarm optimization for solving constrained optimization problems.
Journal of Global Optimization, 41(3):427–445, July 2008.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

141 / 156

References XIV
H. Ma and D. Simon.
Blended biogeography-based optimization for constrained optimization.
Engineering Applications of Artificial Intelligence, 24(3):517–525, April 2011.
R. Mallipeddi, P. Suganthan, and B. Qu.
Diversity enhanced adaptive evolutionary programming for solving single objective constrained problems.
In IEEE 2009 Congress on Evolutionary Computation (CEC’2009), pages 2106–2113, Trondheim, Norway, May 2009.
IEEE Service Center.
R. Mallipeddi and P. N. Suganthan.
Ensemble of Constraint Handling Techniques.
IEEE Transactions On Evolutionary Computation, 14(4):561–579, August 2010.
A. Mani and C. Patvardhan.
A novel hybrid constraint-handling technique for evolutionary optimization.
In IEEE 2009 Congress on Evolutionary Computation (CEC’2009), pages 2577–2583, Trondheim, Norway, May 2009.
IEEE Service Center.
S. M.Elsayed, R. A. Sarker, and D. L. Essam.
Multi-operator based evolutionary algorithms for solving constrained optimization problems.
Computers & Operations Research, 38(12):1877–1896, 2011.
A. Menchaca-Méndez and C. A. Coello Coello.
A new proposal to hybridize the nelder-mead method to a differential evolution algorithm for constrained optimization.
In IEEE 2009 Congress on Evolutionary Computation (CEC’2009), pages 2598–2605, Trondheim, Norway, May 2009.
IEEE Service Center.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

142 / 156

References XV
E. Mezura-Montes and O. Cetina-Domı́nguez.
Exploring promising regions of the search space with the scout bee in the artificial bee colony for constrained optimization.
In C. H. Dagli and et al., editors, Proceedings of the Artificial Neural Networks in Enginnering Conference (ANNIE’2009),
volume 19 of Intelligent Engineering Systems Through Artificial Neural Networks, pages 253–260, St. Louis, MO, USA,
November 2009. ASME Press.
E. Mezura-Montes and C. A. Coello Coello.
A Simple Multimembered Evolution Strategy to Solve Constrained Optimization Problems.
IEEE Transactions on Evolutionary Computation, 9(1):1–17, February 2005.
E. Mezura-Montes and C. A. Coello-Coello.
Constrained optimization via multiobjective evolutionary algorithms.
In D. C. in Joshua Knowles and K. Deb, editors, Multiobjective Problems Solving from Nature: From Concepts to
Applications, pages 53–76. Springer-Verlag, Natural Computing Series, 2008, ISBN: 978-3-540-72963-1., 2008.
E. Mezura-Montes, C. A. Coello Coello, and E. I. Tun-Morales.
Simple Feasibility Rules and Differential Evolution for Constrained Optimization.
In R. Monroy, G. Arroyo-Figueroa, L. E. Sucar, and H. Sossa, editors, Proceedings of the 3rd Mexican International
Conference on Artificial Intelligence (MICAI’2004), pages 707–716, Heidelberg, Germany, April 2004. Springer Verlag.
Lecture Notes in Artificial Intelligence No. 2972.
E. Mezura-Montes, M. Damian-Araoz, and O. Cetina-Domı́nguez.
Smart flight and dynamic tolerances in the artificial bee colony for constrained optimization.
In 2010 Congress on Evolutionary Computation (CEC’2010), pages 4118–4125, Barcelona, Spain, July 2010. IEEE
Service Center.
E. Mezura-Montes and J. I. Flores-Mendoza.
Improved particle swarm optimization in constrained numerical search spaces.
In R. Chiong, editor, Nature-Inspired Algorithms for Optimization, volume 193, pages 299–332. Springer-Verlag, Studies in
Computational Intelligence Series, 2009, ISBN: 978-3-540-72963-1., 2009.
Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

143 / 156

References XVI
E. Mezura-Montes and B. Hernández-Ocaña.
Modified bacterial foraging optimization for engineering design.
In C. H. Dagli and et al., editors, Proceedings of the Artificial Neural Networks in Enginnering Conference (ANNIE’2009),
volume 19 of Intelligent Engineering Systems Through Artificial Neural Networks, pages 357–364, St. Louis, MO, USA,
November 2009. ASME Press.
E. Mezura-Montes and A. G. Palomeque-Ortiz.
Parameter Control in Differential Evolution for Constrained Optimization.
In 2009 Congress on Evolutionary Computation (CEC’2009), pages 1375–1382, Tronheim, Norway, May 2009. IEEE
Service Center.
E. Mezura-Montes, J. Velázquez-Reyes, and C. A. C. Coello.
Promising Infeasibility and Multiple Offspring Incorporated to Differential Evolution for Constrained Optimization.
In H.-G. Beyer, U.-M. O’Reilly, D. Arnold, W. Banzhaf, C. Blum, E. Bonabeau, E. Cant Paz, D. Dasgupta, K. Deb, J. Foste r,
E. de Jong, H. Lipson, X. Llora, S. Mancoridis, M. Pelikan, G. Raidl, T. Soule, A. Tyrrell, J.-P. Watson, and E. Zitzler,
editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’2005), volume 1, pages
225–232, New York, June 2005. Washington DC, USA, ACM Press.
ISBN 1-59593-010-8.
E. Mezura-Montes, J. Velázquez-Reyes, and C. A. C. Coello.
Modified Differential Evolution for Constrained Optimization.
In 2006 IEEE Congress on Evolutionary Computation (CEC’2006), pages 332–339, Vancouver, BC, Canada, July 2006.
IEEE.
E. Mezura-Montes and R. E. Velez-Koeppel.
Elitist artificial bee colony for constrained real-parameter optimization.
In 2010 Congress on Evolutionary Computation (CEC’2010), pages 2068–2075, Barcelona, Spain, July 2010. IEEE
Service Center.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

144 / 156

References XVIIZ. Michalewicz.
Genetic Algorithms + Data Structures = Evolution Programs.
Springer-Verlag, third edition, 1996.
Z. Michalewicz and N. F. Attia.
Evolutionary Optimization of Constrained Problems.
In Proceedings of the 3rd Annual Conference on Evolutionary Programming, pages 98–108. World Scientific, 1994.
Z. Michalewicz and G. Nazhiyath.
Genocop III: A co-evolutionary algorithm for numerical optimization with nonlinear constraints.
In D. B. Fogel, editor, Proceedings of the Second IEEE International Conference on Evolutionary Computation, pages
647–651, Piscataway, New Jersey, 1995. IEEE Press.
Z. Michalewicz and M. Schoenauer.
Evolutionary Algorithms for Constrained Parameter Optimization Problems.
Evolutionary Computation, 4(1):1–32, 1996.
M.-E. Miranda-Varela and E. Mezura-Montes.
Surrogate-assisted differential evolution with an adaptive evolution control based on feasibility to solve constrained
optimization problems.
In Proceedings of the 5th International Conference on Soft Computing for Problem Solving, (SocProsS 2015), pages
809–822, Saharanpur, INDIA, 2015. Springer.
A. E. Muñoz-Zavala, A. Hernández-Aguirre, E. R. Villa-Diharce, and S. Botello-Rionda.
PESO+ for Constrained Optimization.
In 2006 IEEE Congress on Evolutionary Computation (CEC’2006), pages 935–942, Vancouver, BC, Canada, July 2006.
IEEE.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

145 / 156

References XVIII
L.-T. Nguyen and X. Yao.
Continuous dynamic constrained optimization the challenges.
IEEE Transactions on Evolutionary Computation, 16(6):769–786, 2012.
A. I. Oyman, K. Deb, and H.-G. Beyer.
An Alternative Constraint Handling Method for Evolution Strategies.
In Proceedings of the Congress on Evolutionary Computation 1999 (CEC’99), volume 1, pages 612–619, Piscataway,
New Jersey, July 1999. IEEE Service Center.
K. Pal, C. Saha, S. Das, and C. Coello-Coello.
Dynamic constrained optimization with offspring repair based gravitational search algorithm.
In Proceedings of the 2013 IEEE Congress on Evolutionary Computation (CEC’2013), pages 2414–2421, Cancun,
MEXICO, 2013. IEEE Press.
G. Peconick, E. F. Wanner, and R. H. C. Takahashi.
Projection-based local search operator for multiple equality constraints within genetic algorithms.
In 2007 IEEE Congress on Evolutionary Computation (CEC’2007), pages 3043–3049, Singapore, September 2007. IEEE
Press.
D. Powell and M. M. Skolnick.
Using genetic algorithms in engineering design optimization with non-linear constraints.
In S. Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms (ICGA-93), pages 424–431,
San Mateo, California, July 1993. University of Illinois at Urbana-Champaign, Morgan Kaufmann Publishers.
S. Puzzi and A. Carpinteri.
A double-multiplicative dynamic penalty approach for constrained evolutionary optimization.
Structural and Multidisciplinary Optimization, 35(5):431–445, May 2008.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

146 / 156

References XIX
K. Rasheed.
An Adaptive Penalty Approach for Constrained Genetic-Algorithm Optimization.
In J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. L.
Riolo, editors, Proceedings of the Third Annual Genetic Programming Conference, pages 584–590, San Francisco,California, 1998. Morgan Kaufmann Publishers.
T. Ray, T. Kang, and S. K. Chye.
An Evolutionary Algorithm for Constrained Optimization.
In D. Whitley, D. Goldberg, E. Cantú-Paz, L. Spector, I. Parmee, and H.-G. Beyer, editors, Proceedings of the Genetic andEvolutionary Computation Conference (GECCO’2000), pages 771–777, San Francisco, California, July 2000. Morgan
Kaufmann.
T. Ray and K. Liew.
A Swarm with an Effective Information Sharing Mechanism for Unconstrained and Constrained Single Objective
Optimization Problems.
In Proceedings of the Congress on Evolutionary Computation 2001 (CEC’2001), volume 1, pages 75–80, Piscataway,
New Jersey, May 2001. IEEE Service Center.
T. Ray and K. Liew.
Society and Civilization: An Optimization Algorithm Based on the Simulation of Social Behavior.
IEEE Transactions on Evolutionary Computation, 7(4):386–396, August 2003.
T. Ray, H. K. Singh, A. Isaacs, and W. Smith.
Infeasibility driven evolutionary algorithm for constrained optimization.
In E. Mezura-Montes, editor, Constraint-Handling in Evolutionary Optimization, volume 198, pages 145–165.
Springer-Verlag, Studies in Computational Intelligence Series, ISBN:978-3-642-00618-0, 2009.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

147 / 156

References XX
R. G. Regis.
Multi-objective constrained black-box optimization using radial basis function surrogates.
Journal of Computational Science, 16:140–155, 2016.
G. Reynoso-Meza, X. Blasco, J. Sanchis, and M. Martı́nez.
Multiobjective optimization algorithm for solving constrained single objective problems.
In 2010 Congress on Evolutionary Computation (CEC’2010), pages 3418–3424, Barcelona, Spain, July 2010. IEEE
Service Center.
R. G. L. Riche, C. Knopf-Lenoir, and R. T. Haftka.
A Segregated Genetic Algorithm for Constrained Structural Optimization.
In L. J. Eshelman, editor, Proceedings of the Sixth International Conference on Genetic Algorithms (ICGA-95), pages
558–565, San Mateo, California, July 1995. University of Pittsburgh, Morgan Kaufmann Publishers.
T. P. Runarsson.
Constrained Evolutionary Optimization by Approximate Ranking and Surrogate Models.
In X. Yao, E. Burke, J. A. Lozano, J. Smith, , J. J. Merelo-Guervós, J. A. Bullinaria, J. Rowe, P. Tiňo, A. Kabán, and H.-P.
Schwefel, editors, Proceedings of 8th Parallel Problem Solving From Nature (PPSN VIII), pages 401–410, Heidelberg,
Germany, September 2004. Birmingham, UK, Springer-Verlag.
Lecture Notes in Computer Science Vol. 3242.
T. P. Runarsson and X. Yao.
Stochastic Ranking for Constrained Evolutionary Optimization.
IEEE Transactions on Evolutionary Computation, 4(3):284–294, September 2000.
T. P. Runarsson and X. Yao.
Search biases in constrained evolutionary optimization.
IEEE Transactions on Systems, Man, and Cybernetics Part C—Applications and Reviews, 35(2):233–243, May 2005.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

148 / 156

References XXI
M. Schoenauer and Z. Michalewicz.
Evolutionary Computation at the Edge of Feasibility.
In H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, editors, Proceedings of the Fourth Conference on Parallel
Problem Solving from Nature (PPSN IV), pages 245–254, Heidelberg, Germany, September 1996. Berlin, Germany,
Springer-Verlag.
M. Schoenauer and Z. Michalewicz.
Boundary Operators for Constrained Parameter Optimization Problems.
In T. Bäck, editor, Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA-97), pages
322–329, San Francisco, California, July 1997. Morgan Kaufmann.
M. Schoenauer and S. Xanthakis.
Constrained GA Optimization.
In S. Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms (ICGA-93), pages 573–580,
San Mateo, California, July 1993. University of Illinois at Urbana-Champaign, Morgan Kauffman Publishers.
A. Sharma and D. Sharma.
A constraint guided search for improving evolutionary algorithms.
In Proceedings of the 19th international conference in Neural information processing (ICONIP), pages 269–279, Doha,QATAR, 2012. Springer.
H. K. Singh, T. Ray, and W. Smith.
Performance of infeasibility empowered memetic algorithm for cec 2010 constrained optimization problems.
In 2010 Congress on Evolutionary Computation (CEC’2010), pages 3770–3777, Barcelona, Spain, July 2010. IEEE
Service Center.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

149 / 156

References XXII
M. Spadoni and L. Stefanini.
Handling box, linear and quadratic-convex constraints for boundary optimization with differential evolution algorithms.
In Proceedings of the Ninth International Conference on Intelligence Systems Design adn Applications (ISDA’2009),
pages 7–12. IEEE Computer Society, 2009.
J. Sun and J. M. Garibaldi.
A Novel Memetic Algorithm for Constrained Optimization.
In 2010 IEEE Congress on Evolutionary Computation (CEC’2010), pages 549–556, Barcelona, Spain, July 18–23 2010.
IEEE Press.
T. Takahama and S. Sakai.
Constrained Optimization by ↵ Constrained Genetic Algorithm (↵GA).
Systems and Computers in Japan, 35(5):11–22, May 2004.
T. Takahama and S. Sakai.
Constrained Optimization by Applying the ↵ Constrained Method to the Nonlinear Simplex Method with Mutations.
IEEE Transactions on Evolutionary Computation, 9(5):437–451, October 2005.
T. Takahama and S. Sakai.
Constrained optimization by " constrained particle swarm optimizer with "-level control.
In Proceedings of the 4th IEEE InternationalWorkshop on Soft Computing as Transdisciplinary Science and Technology(WSTST’05), pages 1019–1029. Muroran, Japan, 2005.
T. Takahama and S. Sakai.
Constrained Optimization by the ✏ Constrained Differential Evolution with Gradient-Based Mutation and Feasible Elites.
In 2006 IEEE Congress on Evolutionary Computation (CEC’2006), pages 308–315, Vancouver, BC, Canada, July 2006.
IEEE.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

150 / 156

References XXIII
T. Takahama and S. Sakai.
Constrained optimization by ✏ constrained differential evolution with dynamic ✏-level control.
In U. K. Chakraborty, editor, Advances in Differential Evolution, pages 139–154. Springer, Berlin, 2008.
ISBN 978-3-540-68827-3.
T. Takahama and S. Sakai.
Solving difficult constrained optimization problems by the ✏ constrained differential evolution with gradient-based mutation.
In E. Mezura-Montes, editor, Constraint-Handling in Evolutionary Optimization, volume 198, pages 51–72.
Springer-Verlag, Studies in Computational Intelligence Series, ISBN:978-3-642-00618-0, 2009.
T. Takahama and S. Sakai.
Constrained optimization by the "-constrained differential evolution with an archive and gradient-based mutation.
In 2010 Congress on Evolutionary Computation (CEC’2010), pages 1680–1688, Barcelona, Spain, July 2010. IEEE
Service Center.
T. Takahama, S. Sakai, and N. Iwane.
Constrained optimization by the epsilon constrained hybrid algorithm of particle swarm optimization and genetic algorithm.
In AI 2005: Advances in Artificial Intelligence, pages 389–400. Springer-Verlag, 2005.
Lecture Notes in Artificial Intelligence Vol. 3809.
M. Tasgetiren, P. Suganthan, Q. Pan, R. Mallipeddi, and S. Sarman.
An ensemble of differential evolution algorithms for constrained function optimization.
In 2010 Congress on Evolutionary Computation (CEC’2010), pages 967–975, Barcelona, Spain, July 2010. IEEE Service
Center.
M. F. Tasgetiren and P. N. Suganthan.
A Multi-Populated Differential Evolution Algorithm for Solving Constrained Optimization Problem.
In 2006 IEEE Congress on Evolutionary Computation (CEC’2006), pages 340–354, Vancouver, BC, Canada, July 2006.
IEEE.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

151 / 156

References XXIV
B. Tessema and G. G. Yen.
An adaptive penalty formulation for constrained evolutionary optimization.
IEEE Transactions on Systems, Man and Cybernetics Part A—Systems and Humans, 39(3), 2009.
A. S. B. Ullah, R. Sarker, and C. Lokan.
An agent-based memetic algorithm (ama) for nonlinear optimization with equality constraints.
In IEEE 2009 Congress on Evolutionary Computation (CEC’2009), pages 70–77, Trondheim, Norway, May 2009. IEEE
Service Center.
A. S. S. M. B. Ullah, R. Sarker, and D. Cornforth.
Search Space Reduction Technique for Constrained Optimization with Tiny Feasible Space.
In 2008 Genetic and Evolutionary Computation Conference (GECCO’2008), pages 881–888, Atlanta, USA, July 2008.
ACM Press.
ISBN 978-1-60558-131-6.
A. S. S. M. B. Ullah, R. Sarker, D. Cornforth, and C. Lokan.
An Agent-based Memetic Algorithm (AMA) for Solving constrainted Optimization Problems.
In 2007 IEEE Congress on Evolutionary Computation (CEC’2007), pages 999–1006, Singapore, September 2007. IEEE
Press.
A. S. S. M. B. Ullah, R. Sarker, D. Cornforth, and C. Lokan.
Ama: a new approach for solving constrained real-valued optimization problems.
Soft Computing, 13(8–9):741–762, 2008.
S. Venkatraman and G. G. Yen.
A Generic Framework for Constrained Optimization Using Genetic Algorithms.
IEEE Transactions on Evolutionary Computation, 9(4), August 2005.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

152 / 156

References XXV
G. Venter and R. T. Haftka.
Constrained particle searm optimization using a bi-objective formulation.
Structural and Multidisciplinary Optimization, 40(1-6):65–76, January 2010.
L. Wang and L. po Li.
An effective differential evolution with level comparison for constrained engineering design.
Structural and Multidisciplinary Optimization, 41(6):947–963, June 2010.
Q. Wang, X.-Z. Gao, and C. Wang.
An Adaptive Bacterial Foraging Algorithm For Constrained Optimization.
International Journal of Innovative Computing Information and Control, 6(8):3585–3593, August 2010.
Y. Wang and Z. Cai.
A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems.
Frontiers of Computer Science in China, 3(1):38–52, 2009.
Y. Wang and Z. Cai.
Hybrid differential evolution and adaptive trade-off model to solve constrained optimization problems.
In 2010 Congress on Evolutionary Computation (CEC’2010), pages 2846–2850, Barcelona, Spain, July 2010. IEEE
Service Center.
Y. Wang, Z. Cai, G. Guo, and Y. Zhou.
Multiobjective optimization and hybrid evolutionary algorithm to solve constrained optimization problems.
IEEE Transactions on Systems, Man and Cybernetics Part B–Cybernetics, 37(3):560–575, June 2007.
Y. Wang, Z. Cai, and Y. Zhou.
Accelerating adaptive trade-off model using shrinking space technique for constrained evolutionary optimization.
International Journal for Numerical Methods in Engineering, 77(11):1501–1534, 2009.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

153 / 156

References XXVI
Y. Wang, Z. Cai, Y. Zhou, and Z. Fan.
Constrained optimization based on hybrid evolutionary algorithm and adaptive constraint-handling technique.
Structural and Multidisciplinary Optimization, 37(4):395–413, January 2009.
Y. Wang, Z. Cai, Y. Zhou, and W. Zeng.
An Adaptive Tradeoff Model for Constrained Evolutionary Optimization.
IEEE Transactions on Evolutionary Computation, 12(1):80–92, February 2008.
Y. Wang, H. Liu, Z. Cai, and Y. Zhou.
An orthogonal design based constrained evolutionary optimization algorithm.
Engineering Optimization, 39(6):715–736, September 2007.
E. F. Wanner, F. G. Guimarı̈¿ 12 s, R. H. Takahashi, R. R. Saldanha, and P. J. Fleming.
Constraint quadratic approximation operator for treating equality constraints with genetic algorithms.
In 2005 IEEE Congress on Evolutionary Computation (CEC’2005), volume 3, pages 2255–2262, Edinburgh, Scotland,
September 2005. IEEE Press.
B. Wu and X. Yu.
Fuzzy Penalty Function Approach for Constrained Function Optimization with Evolutionary Algorithms.
In Proceedings of the 8th International Conference on Neural Information Processing, pages 299–304, Shanghai, China,
November 2001. Fudan University Press.
J.-Y. Wu.
Solving Constrained Global Optimization Via Artificial Immune System.
International Journal on Artificial Intelligence Tools, 20(1):1–27, February 2011.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

154 / 156

References XXVII
Y. Wu, Y. Li, and X. Xu.
A Novel Component-Based Model and Ranking Strategy in Constrained Evolutionary Optimization.
In R. Huang, Q. Yang, J. Pei, J. ao Gama, X. Meng, and X. Li, editors, Advanced Data Mining and Applications, 5thInternational Conference (ADMA’2009), pages 362–373. Springer. Lecture Notes in Computer Science, Vol. 5678, Beijing,
China, 2009.
Y. Yu and Z.-H. Zhou.
On the Usefulness of Infeasible Solutions in Evolutionary Search: A Theoretical Study.
In 2008 Congress on Evolutionary Computation (CEC’2008), pages 835–840, Hong Kong, June 2008. IEEE Service
Center.
S. Zeng, R. Jiao, C. Li, X. Li, and J. S. Alkasassbeh.
A general framework of dynamic constrained multiobjective evolutionary algorithms for constrained optimization.
IEEE Transactions on Cybernetics, 2017.
S. Zeng, H. Shi, H. Li, G. Chen, L. Ding, and L. Kang.
A Lower-dimensional-Search Evolutionary Algorithm and Its Application in Constrained Optimization Problem.
In 2007 IEEE Congress on Evolutionary Computation (CEC’2007), pages 1255–1260, Singapore, September 2007. IEEE
Press.
M. Zhang, W. Luo, and X. Wang.
Differential evolution with dynamic stochastic selection for constrained optimization.
Information Sciences, 178(15):3043–3074, August 1 2008.
Q. Zhang, S. Zeng, R. Wang, H. Shi, G. Chen, L. Ding, and L. Kang.
Constrained Optimization by the Evolutionary Algorithm with Lower Dimensional Crossover and Gradient-Based Mutation.
In 2008 Congress on Evolutionary Computation (CEC’2008), pages 273–279, Hong Kong, June 2008. IEEE Service
Center.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

155 / 156

References XXVIII
Y. Zhou and J. He.
A runtime analysis of evolutionary algorithms for constrained optimization problems.
IEEE Transactions on Evolutionary Computation, 11(5):608–619, October 2007.
K. Zielinski and R. Laur.
Constrained Single-Objective Optimization Using Differential Evolution.
In 2006 IEEE Congress on Evolutionary Computation (CEC’2006), pages 927–934, Vancouver, BC, Canada, July 2006.
IEEE.
K. Zielinski and R. Laur.
Stopping criteria for differential evolution in constrained single-objective optimization.
In U. K. Chakraborty, editor, Advances in Differential Evolution, pages 111–138. Springer, Berlin, 2008.
ISBN 978-3-540-68827-3.
K. Zielinski, S. P. Vudathu, and R. Laur.
Influence of Different Deviations Allowed for Equality Constraints on Particle Swarm Optimization and Differential
Evolution.
In N. Krasnogor, G. Nicosia, M. Pavone, and D. Pelta, editors, Nature Inspired Cooperative Strategies for Optimization,
pages 249–259. Springer, Berlin, 2008.
ISBN 978-3-540-78986-4.
K. Zielinski, X. Wang, and R. Laur.
Comparison of Adaptive Approaches for Differential Evolution.
In G. Rudolph, T. Jansen, S. Lucas, C. Poloni, and N. Beume, editors, Parallel Problem Solving from Nature–PPSN X,
pages 641–650. Springer. Lecture Notes in Computer Science Vol. 5199, Dortmund, Germany, September 2008.

Efrén Mezura-Montes

Constraint-Handling in Nat-Insp. Opt.

CEC 2017, SPAIN

156 / 156