Moo.GeneticAlgorithm.Constraints

Documentation

type ConstraintFunction a b = Genome a -> b

data Real b => Constraint a b

Define constraints using .<., .<=., .>., .>=., and .==. operators, with a ConstraintFunction on the left hand side.

For double inequality constraints use pairs of .<, <. and .<=, <=. respectively, with a ConstraintFunction in the middle.

Examples:

 function .>=. lowerBound
 lowerBound .<= function <=. upperBound

isFeasible

Arguments

:: (GenomeState gt a, Real b)

=> [Constraint a b]

constraints

-> gt

genome

-> Bool

Returns True if a genome represents a feasible solution, i.e. satisfies all constraints.

Simple equalities and inequalities

(.<.) :: Real b => ConstraintFunction a b -> b -> Constraint a b

(.<=.) :: Real b => ConstraintFunction a b -> b -> Constraint a b

(.>.) :: Real b => ConstraintFunction a b -> b -> Constraint a b

(.>=.) :: Real b => ConstraintFunction a b -> b -> Constraint a b

(.==.) :: Real b => ConstraintFunction a b -> b -> Constraint a b

Double inequalities

data Real b => LeftHandSideInequality a b

(.<) :: Real b => b -> ConstraintFunction a b -> LeftHandSideInequality a b

(.<=) :: Real b => b -> ConstraintFunction a b -> LeftHandSideInequality a b

(<.) :: Real b => LeftHandSideInequality a b -> b -> Constraint a b

(<=.) :: Real b => LeftHandSideInequality a b -> b -> Constraint a b

Constrained initalization

getConstrainedGenomes

Arguments

:: (Random a, Ord a, Real b)

=> [Constraint a b]

constraints

-> Int

n, how many genomes to generate

-> [(a, a)]

ranges for individual genome elements

-> Rand [Genome a]

random feasible genomes

Generate n feasible random genomes with individual genome elements bounded by ranges.

getConstrainedBinaryGenomes

Arguments

:: Real b

=> [Constraint Bool b]

constraints

-> Int

n, how many genomes to generate

-> Int

L, genome length

-> Rand [Genome Bool]

random feasible genomes

Generate n feasible random binary genomes.

Constrained selection

withDeathPenalty

Arguments

:: (Monad m, Real b)

=> [Constraint a b]

constraints

-> StepGA m a

unconstrained step

-> StepGA m a

constrained step

Kill all infeasible solutions after every step of the genetic algorithm.

“Death penalty is very popular within the evolution strategies community, but it is limited to problems in which the feasible search space is convex and constitutes a reasonably large portion of the whole search space,” -- (Coello 1999).

Coello, C. A. C., & Carlos, A. (1999). A survey of constraint handling techniques used with evolutionary algorithms. Lania-RI-99-04, Laboratorio Nacional de Informática Avanzada.

withFinalDeathPenalty

Arguments

:: (Monad m, Real b)

=> [Constraint a b]

constriants

-> StepGA m a

unconstrained step

-> StepGA m a

constrained step

Kill all infeasible solutions once after the last step of the genetic algorithm. See also withDeathPenalty.

withConstraints

Arguments

:: (Real b, Real c)

=> [Constraint a b]

constraints

-> ([Constraint a b] -> Genome a -> c)

non-negative degree of violation, see numberOfViolations and degreeOfViolation

-> ProblemType

-> SelectionOp a

-> SelectionOp a

Modify objective function in such a way that 1) any feasible solution is preferred to any infeasible solution, 2) among two feasible solutions the one having better objective function value is preferred, 3) among two infeasible solution the one having smaller constraint violation is preferred.

Reference: Deb, K. (2000). An efficient constraint handling method for genetic algorithms. Computer methods in applied mechanics and engineering, 186(2), 311-338.

numberOfViolations

Arguments

:: Real b

=> [Constraint a b]

constraints

-> Genome a

genome

-> Int

the number of violated constraints

A simple estimate of the degree of (in)feasibility.

Count the number of constraint violations. Return 0 if the solution is feasible.

degreeOfViolation

Arguments

:: Double

beta, single violation exponent

-> Double

eta, equality penalty in strict inequalities

-> [Constraint a Double]

constrains

-> Genome a

genome

-> Double

total degree of violation

An estimate of the degree of (in)feasibility.

Given f_j is the excess of j-th constraint function value, return sum |f_j|^beta. For strict inequality constraints, return sum (|f_j|^beta + eta). Return 0.0 if the solution is feasible.