CODEWITHSUNDEEP
algorithmmathematical-optimizationgenetic-algorithmnonlinear-functions
LNRD.CLL
LNRD.CLL

Reputation: 385

Genetic Algorithm

I have a simple genetic algorithm that has to reach an optimal point of a trap function that is defined as follows:

def R(x):
    n = len(x)
    m = int(math.ceil(n/3))
    s = sum(x)

    if (s==n):
        return 2*n*n,
    elif (s<(n-m)):
        return n*s-B(x),
    else:
        return 0,

def B(x):
    i = 0
    n = len(x)
    mbs = 0

    # loops over all the variables
    while (i<n):

        k = i
        while (k<n and x[k]==0):
            k = k + 1

        #print("k="+str(k))

        j = k
        while (j<n and x[j]==1):
            j = j + 1

        if (j-k>mbs):
            mbs = j-k

        #print("j="+str(j))

        i = j

    return mbs

I've thought to augment a lot the pop size and "hope" to generate with the random.seed() the optimal individual in the first generation and then just propagate the number of copies of it. For doing this I would just consider a tournament selection with a "big" window for the tournament.

This solution works only with 5 and 10 attributes but doesn't work with 30. The point is that I don't know how to solve the 30 attributes case. Hoping that someone is able to help me.

Upvotes: 2

Views: 393

Answers (2)

manlio
manlio

Reputation: 18902

I can use only a simple GA with some elitism...

Given this constraint you can increase population size without using elitism, but it won't scale well.

zegkljan's idea of using novelty search, seems better and can be followed without altering the search engine.

Just change the fitness function:

score(i) = (1 − ρ) · fit(i) + ρ · nov(i)

fit(i) is your R function normalized:

fit(i) = (R(i) - Rmin) / (Rmax - Rmin)

and nov(i) is the normalized novelty function (you have to keep an archive of already seen individuals, but this doesn't entail modifications to the 'engine').

ρ ∈ [0,1] controls the relative importance of fitness and novelty.

For further details about this technique: When Novelty is not Enough (Giuseppe Cuccu, Faustino Gomez)

Upvotes: 2

zegkljan
zegkljan

Reputation: 8391

Trap functions and similar are just a problem for GAs.

One possible workaround might be to use a multi-objective evolutionary algorithm (MOEA), e.g. NSGA-II, and add a second objective which would be a "uniqueness" of the individual, e.g. an average hamming distance from the other individuals in the population, or a . This will force (kind-of) the evolution to explore other areas of the search space as well.

Have a look at novelty search. It's about abandoning the objective completely (for driving the evolution, but you still use it to find the best solution) and using just a "uniqueness" (called) novelty, to drive the search.

Upvotes: 1

Related Questions