added constraints docs

wildart · Mar 19, 2021 · edd446b · edd446b
1 parent 5b1421c
commit edd446b
Show file tree

Hide file tree

Showing 3 changed files with 178 additions and 17 deletions.
diff --git a/docs/make.jl b/docs/make.jl
@@ -8,6 +8,7 @@ makedocs(
     pages = [
         "Home" => "index.md",
         "Tutorial" => "tutorial.md",
+        "Constraints" => "constraints.md",
         "Algorithms" => [
             "Genetic Algorithm" => "ga.md",
             "Differential Evolution" => "de.md",
@@ -24,4 +25,4 @@ makedocs(
     ]
 )
 
-deploydocs(repo = "github.com/wildart/Evolutionary.jl.git")
+# deploydocs(repo = "github.com/wildart/Evolutionary.jl.git")
diff --git a/docs/src/constraints.md b/docs/src/constraints.md
@@ -0,0 +1,111 @@
+```@setup cntr
+using Evolutionary
+```
+
+The nonlinear constrained optimization interface in `Evolutinary` assumes that the user can write the optimization problem as follows:
+
+```math
+\min_{x\in\mathbb{R}^n} f(x) \quad \text{such that}\\
+l_x \leq \phantom{c(}x\phantom{)} \leq u_x \\
+l_c \leq c(x) \leq u_c.
+```
+
+For equality constraints on ``x_j`` or ``c(x)_j`` you set those particular entries of bounds to be equal, ``l_j=u_j``.
+Likewise, setting ``l_j=-\infty`` or ``u_j=\infty`` means that the  constraint is unbounded from below or above respectively.
+
+Following examples show how to use constraints to optimize the [Booth function](https://www.sfu.ca/~ssurjano/booth.html).
+The function is defined as follows:
+
+```@repl cntr
+f(x)=(x[1]+2x[2]-7)^2+(2x[1]+x[2]-5)^2 # Booth
+```
+
+The function is usually evaluated on the square ``x_i ∈ [-10, 10]``, for all ``i = 1, 2``.
+The global minimum on this function is located at ``(1,3)``.
+
+```@example cntr
+ga = GA(populationSize=100,selection=uniformranking(3),
+        mutation=gaussian(),crossover=uniformbin())
+x0 = [0., 0.]
+results = Evolutionary.optimize(f, x0, ga)
+```
+
+## Box Constrained Optimization
+
+We want to optimize the [Booth function](https://www.sfu.ca/~ssurjano/booth.html) in
+the box ``0.5 \leq x_i \leq 2.0``, starting from the point ``x_0=(1,1)``.
+
+Reusing our Booth example from above, boxed minimization is performed by providing
+vectors of lower and upper bounds as follows:
+
+```@example cntr
+lower = [0.5, 0.5]
+upper = [2.0, 2.0]
+x0 = [1., 1.]
+results = Evolutionary.optimize(f, lower, upper, x0, ga)
+```
+
+The box constraints can be also defined using [`BoxConstraints`](@ref) object.
+
+```@docs
+BoxConstraints
+```
+
+```@example cntr
+cnst = BoxConstraints([0.5, 0.5], [2.0, 2.0])
+```
+
+This object can be passed as a parameter to the optimization call, [`Evolutionary.optimize`](@ref):
+
+```@example cntr
+results = Evolutionary.optimize(f, cnst, x0, ga) # or Evolutionary.optimize(f, cnst, ga)
+```
+
+## Penalty Constrained Optimization
+
+For the penalty constrained optimization, any value and linear/nonlinear constraints
+are transformed into the penalty to the minimized fitness function.
+In order to provide linear/nonlinear constraints to an optimization problem,
+you can use the following penalty constraint algorithm:
+
+```@docs
+PenaltyConstraints
+```
+
+We want to minimize the following function ``f(x,y) = 3x+9y`` that is subject to constraints
+``\sqrt(xy) \geq 100`` and ``x,y \geq 0``. The minimum of this function is near ``(173.41, 57.8)``.
+We begin  by defining constraints as follows:
+
+```@example cntr
+# x, y ≥ 0
+lx = [0.0, 0.0] # lower bound for values
+ux = [Inf, Inf] # upper bound for values
+# √xy ≥ 100
+c(x) = [ prod(map(e->sqrt(e>0 ? e : 0.0), x)) ] # negative values are zeroed
+lc   = [100.0] # lower bound for constraint function
+uc   = [ Inf ]   # upper bound for constraint function
+con = PenaltyConstraints(100.0, lx, ux, lc, uc, c) # first parameter is a penalty value
+```
+
+Now, we define the fitness function, an initial individual structure, and algorithm parameters;
+then we perform minimization as follows:
+
+```@example cntr
+f(x) = 3x[1]+9x[2] # fitness function
+x0 = [1., 1.] # individual
+ga = GA(populationSize=100,selection=tournament(7),
+        mutation=gaussian(),crossover=intermediate(2))
+results = Evolutionary.optimize(f, con, x0, ga)
+```
+
+We can use worst fitness constraint algorithm which doesn't require to specify the constraint penalty value
+
+```@docs
+WorstFitnessConstraints
+```
+```@example cntr
+con = WorstFitnessConstraints(lx, ux, lc, uc, c)
+```
+```@example cntr
+results = Evolutionary.optimize(f, con, x0, ga)
+```
diff --git a/src/api/constraints.jl b/src/api/constraints.jl
@@ -1,9 +1,9 @@
 # Public interface for AbstractConstraints
 
 """
-    constraints(c::AbstractConstraints, f::AbstractObjective, x)
+    value(c::AbstractConstraints, x)
 
-Return a values of constraints for a variable `x` given the set of constraints object `c`.
+Return a values of constraints for a variable `x` given the set of constraints in the object `c`.
 """
 value(c::AbstractConstraints, x) = nothing
 
@@ -22,27 +22,25 @@ Set a penalty to the `fitness` given the set of `constraints` and `population`.
 penalty!(fitness, c::AbstractConstraints, population) = fitness
 
 """
-    clip!(c::AbstractConstraints, x)
+    apply!(c::AbstractConstraints, x)
 
-Clip a variable `x` values to satisfy the bound constraints `c`.
+Appliy constrains `c` to a variable `x`, and return the variable.
 """
 apply!(c::AbstractConstraints, x) = x
 
-# Auxillary functions
+# Auxiliary functions
 
 """
-    isfeasible(constraints, x) -> Bool
-    isfeasible(bounds, x) -> Bool
+    isfeasible(bounds::ConstraintBounds, x) -> Bool
 
-Return `true` if point `x` is feasible, given the `constraints` which
-specify bounds `lx`, `ux`, `lc`, and `uc`. `x` is feasible if
+Return `true` if point `x` is feasible, given the `bounds` object with bounds `lx`, `ux`, `lc`, and `uc`. `x` is feasible if
 
     lx[i] <= x[i] <= ux[i]
     lc[i] <= c(x)[i] <= uc[i]
 
 for all possible `i`.
 """
-function isfeasible(bounds::ConstraintBounds, x, c::Union{Vector,Nothing}=nothing)
+function isfeasible(bounds::ConstraintBounds, x::AbstractVector, c::Union{AbstractVector,Nothing}=nothing)
     isf = true
     for (i,j) in enumerate(bounds.eqx)
         isf &= x[j] == bounds.valx[i]
@@ -60,6 +58,12 @@ function isfeasible(bounds::ConstraintBounds, x, c::Union{Vector,Nothing}=nothin
     end
     isf
 end
+
+"""
+    isfeasible(c::AbstractConstraints, x) -> Bool
+
+Return `true` if point `x` is feasible, given the constraints object `c`.
+"""
 isfeasible(c::AbstractConstraints, x) = isfeasible(c.bounds, x, value(c, x))
 
 # Implementations
@@ -70,7 +74,16 @@ isfeasible(c::NoConstraints, x)  = true
 getproperty(c::NoConstraints, s::Symbol) =
     s == :bounds ? ConstraintBounds(Float64[], Float64[], Float64[], Float64[]) : nothing
 
-"""Box constraints"""
+"""
+This type encodes box constraints for the optimization function parameters.
+
+The constructor takes following arguments:
+
+- `lower` is the vector of value lower bounds
+- `upper` is the vector of value upper bounds
+
+*Note: Sizes of the lower and upper bound vectors must be equal.*
+"""
 struct BoxConstraints{T} <: AbstractConstraints
     bounds::ConstraintBounds{T}
 end
@@ -79,16 +92,32 @@ BoxConstraints(lower::AbstractVector{T}, upper::AbstractVector{T}) where {T} =
 BoxConstraints(lower::T, upper::T, size) where {T} =
     BoxConstraints(fill(lower, size), fill(upper, size))
 apply!(c::BoxConstraints, x) = clip!(c.bounds, x)
+function show(io::IO,c::BoxConstraints)
+    print(io, "Box Constraints:")
+    indent = "    "
+    cb = c.bounds
+    NLSolversBase.showeq(io, indent, cb.eqx, cb.valx, 'x', :bracket)
+    NLSolversBase.showineq(io, indent, cb.ineqx, cb.σx, cb.bx, 'x', :bracket)
+end
 
 """
-This type encodes constraints as a following additional penalty for an objective function:
+This type encodes constraints as the following additional penalty for an objective function:
 
 ``p(x) = \\sum^n_{i=1} r_i max(0, g_i(x))^2``
 
-where ``g_i(x)`` is an inequality constraint. The equality constraints ``h_i(x) = 0`` are transformed
-to inequality constraints as follows:
+where ``r_i`` is a penalty value for ``i``th constraint, and ``g_i(x)`` is an inequality constraint.
+The equality constraints ``h_i(x) = 0`` are transformed to inequality constraints as follows:
 
 ``h(x) - \\epsilon  \\leq 0``
+
+The constructor takes following arguments:
+
+- `penalties`: a vector of penalty values per constraint (optional)
+- `lx`: a vector of value lower bounds
+- `ux`: a vector of value upper bounds
+- `lc`: a vector of constrain function lower bounds
+- `uc`: a vector of constrain function upper bounds
+- `c`: a constraint function which returns a constrain values
 """
 struct PenaltyConstraints{T,F} <: AbstractConstraints
     coef::Vector{T}
@@ -118,18 +147,34 @@ function penalty!(fitness::AbstractVector{T}, c::PenaltyConstraints{T,F}, popula
     end
     return fitness
 end
+function show(io::IO,c::PenaltyConstraints)
+    println(io, "Penalty Constraints:")
+    println(io, "  Penalties: $(c.coef)")
+    print(io, c.bounds)
+end
 
 """
-This type encodes constraints as a following additional penalty for an objective function:
+This type encodes constraints as the following additional penalty for an objective function:
 
 ``p(x) = f_{worst} + \\sum^n_{i=1} |g_i(x)|``
 
 if ``x`` is not feasible, otherwise no penalty is applied.
+
+The constructor takes following arguments:
+
+- `lx`: a vector of value lower bounds
+- `ux`: a vector of value upper bounds
+- `lc`: a vector of constrain function lower bounds
+- `uc`: a vector of constrain function upper bounds
+- `c`: a constraint function which returns a constrain values
 """
 struct WorstFitnessConstraints{T,F} <: AbstractConstraints
     bounds::ConstraintBounds{T}
     constraints::F   # constraints(x) returns the value of the constraint-functions at x
 end
+WorstFitnessConstraints(lx::AbstractVector{T}, ux::AbstractVector{T}, lc::AbstractVector{T},
+                        uc::AbstractVector{T}, cf=(x)->nothing) where {T} =
+    WorstFitnessConstraints(ConstraintBounds(lx, ux, lc, uc), cf)
 value(c::WorstFitnessConstraints, x) = c.constraints(x)
 apply!(c::WorstFitnessConstraints, x) = clip!(c.bounds, x)
 function penalty!(fitness::AbstractVector{T}, c::WorstFitnessConstraints{T,F}, population) where {T,F}
@@ -149,6 +194,10 @@ function penalty!(fitness::AbstractVector{T}, c::WorstFitnessConstraints{T,F}, p
     end
     return fitness
 end
+function show(io::IO,c::WorstFitnessConstraints)
+    print(io, "Worst Fitness ")
+    print(io, c.bounds)
+end
 
 """
 This type provides an additional type constraints on the varaibles required for mixed integer optimization problmes.
@@ -184,7 +233,7 @@ function clip!(bounds::ConstraintBounds{T}, x) where {T}
 end
 
 function penalty(bounds::ConstraintBounds{T}, coeff::AbstractVector{T},
-                 x, c::Union{AbstractVector,Nothing}=nothing) where {T}
+                 x, c::Union{AbstractVector{T},Nothing}=nothing) where {T}
     penalty = 0
     xc = nconstraints_x(bounds)
     for (i,j) in enumerate(bounds.eqx)