Fitness sharing in DEAP

Question

Is there any way to implement fitness sharing/niching using DEAP? Specifically I'm looking for an implementation of the method defined here (Goldberg's fitness sharing) on page 98 of the pdf. If you know of any other methods that are in DEAP, that would be useful as well.

Thanks

Answer 1

Write your own selection routine. The default routines are at deap/tools/selection.py and might be useful as a guide to get started

For example:

def selYourSelectionRoutine(individuals, k):
    """Select the *k* best individuals among the input *individuals*.

    :param individuals: A list of individuals to select from.
    :param k: The number of individuals to select.
    :returns: A list containing the k best individuals.
    """
    return sorted(individuals, key=attrgetter("fitness"), reverse=True)[:k]

Then use it with the rest of deap as they prescribe:

toolbox.register("select", tools.selYourSelectionRoutine, yourargs)

I've got one that does something more like a probablistic selection based on relative fitness which I don't have the rights to, it's only about 10-15 lines of python—so it can be done, and isn't crazy difficult.

I'm not aware of any implementations of that specific selection routine that are publically available (yet).

Answer 2

To do fitness sharing, you would have to define your own shared fitness function that depends on the entire population.

Assuming you already defined a fitness function, you could do the following:

from scipy.spatial import distance_matrix

def sharing(distance, sigma, alpha):
    res = 0
    if distance<sigma:
        res += 1 - (distance/sigma)**alpha
    return res

def shared_fitness(individual, population, sigma, alpha):
    num = fitness(individual)[0]

    dists = distance_matrix([individual], population)[0]
    tmp = [sharing(d, sigma, alpha) for d in dists]
    den = sum(tmp)

    return num/den,

This shared fitness will favor individuals with fewer neighbors. sigma is the radius in which neighbors will penalize an individual's shared fitness. If sigma is bigger, then your niches will be further away, and you risk missing a local maximum. If sigma is smaller, you need a larger population, and your algorithm will take longer to run. alpha indicates how strong the penalization for nearby neighbors is.

This shared fitness can then be registered in your toolbox like a regular fitness.

population = toolbox.population()
toolbox.register('evaluate', shared_fitness, population=population, sigma=0.1, alpha=1.)

After that, you can use a standard algorithm like $\mu + \lambda$, that will select offspring based on their fitness, to get niching.