Constraints in the Genetic Algorithm implemented in `Metaheuristics.jl`

AkchurinDA · December 9, 2024, 4:45pm

Opening a fresh thread based on the recommendation from @pierre-haessig.

My original question was:

How does the Genetic Algorithm implemented in Metaheuristics.jl “penalize” the objective function for not satisfying the constraints? From what I gather, it doesn’t use penalty method. I believe it uses some sort of a penalty-free method by simply comparing the individuals based on (1) their average constraint violations (i.e., \frac{1}{N_{g}} \sum_{i = 1}^{N_{g}} \max{(0, g_{i}(x))} + \frac{1}{N_{h}} \sum_{j = 1}^{N_{h}} |h_{j}(x)|, where g_{i}(x) are inequality constraints and h_{j}(x) are equality constraints) and (2) their objective function values. Is that true? If not, how does it handle the constraints then?

Really would love to know all the details of the Genetic Algorithm implemented in Metaheuristics.jl as I’m writing a journal article that uses the package.

Thanks!

P.S.: Maybe @jmejia8 and @jbytecode can chip in.

jbytecode · December 9, 2024, 5:11pm

Thank you for tagging me. However, I only collaborated on the implementation of our method MCCGA (Machine-coded compact genetic algorithm) and don’t know how the classical genetic algorithm is implemented in the package; @jmejia8 might be able to provide more useful information.

jmejia8 · December 10, 2024, 7:43pm

Hi @AkchurinDA

GA and the other unconstrained metaheuristics use the constraint violation average to firstly compare solutions. If solutions are either feasible or have the same constraint violation sum, the objective is used to compare them.

Implementation here:

github.com

jmejia8/Metaheuristics.jl/blob/master/src/common/compare.jl

"""
    is_better(A, B)
    return true if A is better than B in a minimization problem.
    Feasibility rules and dominated criteria are used in comparison.
"""
function is_better(A::T, B::T) where T <: xf_solution
    return A.f < B.f
end

# feasibility rules
function is_better(A::T, B::T) where T <: xfgh_solution

    A_vio = A.sum_violations
    B_vio = B.sum_violations

    if A_vio < B_vio
        return true
    elseif B_vio < A_vio
        return false
    end

This file has been truncated. show original

github.com

jmejia8/Metaheuristics.jl/blob/master/src/solutions/constrained.jl

# COP functions
function violationsSum(g::Vector, h::Vector; ε =0.0)
    if isempty(g) && isempty(h)
        return 0.0
    end
    
    if isempty(g)
        g = [0.0]
    end

    if isempty(h)
        h = [0.0]
    end
    
    sum_g = sum(max.(0.0, g))
    sum_h = 0.0


    for i = 1:length(h)
        if !isapprox(h[i], 0.0, atol=ε)

This file has been truncated. show original

AkchurinDA · December 10, 2024, 8:48pm

Thank you very much for your response, @jmejia8! Now it makes more sense.

Do you know how this type of constraint-handling method is called in the literature? If you used particular references during the implementation, could you please provide them so that I could cite in my article?

jmejia8 · December 10, 2024, 9:09pm

This constraint violation technique has different names (Deb’s rule, constraint violation rule, among others). The reference paper is at Redirecting

AkchurinDA · December 10, 2024, 9:42pm

Thank you very much!

To solve my integer program with nonlinear constraints I used SBX() method for crossover and PolynomialMutation() method for mutation. If you have any preferred references that you used during the implementation of these methods, could you please provide them as well? Thank you in advance.