Ser Selectivo

Escolher os melhores para reprodução com variação é um elemento chave dos algoritmos evolucionários. Tem as suas nuances, pois demasiada pressão selectiva pode causara convergência prematura da população para um máximo local. Vários mecanismos de selecção foram propostos ao longo do tempo. Vejamos alguns.

Torneio

Simples de implementar, procurando contrariar a pressão selectiva ao escolher de modo aleatório os elementos que vão participar no torneio.

def tournament_sel(population, numb,size):
    mate_pool=[]
    for i in range(numb):
        indiv = tournament(population,size)
        mate_pool.append(indiv)
    return indiv

def tournament(population, numb_offspring, t_size):
    return [one_tournament(population,t_size) for count in range(numb_offspring)]

def one_tournament(population,size):
    """Maximization. Problem.Deterministic"""
    pool = random.sample(population, size)
    pool.sort(key=itemgetter(1),reverse = True)
    return pool[0]

Trata-se de um torneio determinístico, significando isso que o melhor é sempre o escolhido. Existe uma versão estocástica que usa um processo semelhante ao da recristalização simulada, podendo ser escolhido, com uma dada probabilidade, um indivíduo de menor qualidade.


Ordem
Outro algoritmo que procura contrariar a pressão selectiva é o algoritmo de selecção por ordem. Ordenam-se os indivíduos em função da sua qualidade mas escolha depende da posição e não do valor do mérito.

def rank(population, numb,s):
    """linear version."""
    pop_size = len(population)
    pop = population[:]
    pop.sort(key=itemgetter(1))
    probabilities = [((2 - s)/pop_size) + ((2*i*(s -1))/float((pop_size * (pop_size - 1))))
                     for i in range(pop_size)]
    mate_pool = []
    for i in range(numb):
        value = random.uniform(0,1)
        index = 0
        total = probabilities[index]
        while total < value:
            index += 1
            total += probabilities[index]
        mate_pool.append(population[index])
    return mate_pool

Roleta

O algoritmo clássico. A escolha de um indíviduo é directamente proporcional ao seu mérito. Tem problemas de diminuição da diversidade da população ao longo das gerações e, por isso, de convergência prematura. Para seleccionar n indivíduos simula-se a rotação de uma roleta igual número de vezes.

def roulette_wheel(population, numb):
    """ Select numb individuals from the population
    according with their relative fitness. MAX. """
    pop = population[:]
    pop.sort(key=itemgetter(1))
    total_fitness = sum([indiv[1] for indiv in pop])
    mate_pool = []
    for i in range(numb):
        value = random.uniform(0,1)
        index = 0
        total = pop[index][1]/ float(total_fitness)
        while total < value:
            index += 1
            total += pop[index][1]/ float(total_fitness)
        mate_pool.append(pop[index])
    return mate_pool

Amostragem Universal Estocástica

Este método permite com uma rotação apenas da roleta escolher todos os elementos. É preferível ao método da roleta clássico sempre que queremos obter mais do que um elemento. Se tivermos que produzir n descendentes escolhe-se um ponto aleatório entre [0, 1/n]. Depois marcam-se posições igualmente espaçadas de 1/n. A roleta está dividida de acordo com o mérito dos indivíduos. Roda-se uma vez e escolhem-se os indivíduos em frente de vada uma das n marcas.

def sus(population,numb):
    """ Stochastic Universal Sampling."""
    pop = population[:]
    pop.sort(key=itemgetter(1))
    total_fitness = sum([indiv[1] for indiv in pop])
    value = random.uniform(0,1.0/numb)
    pointers = [ value + i * (1.0/numb) for i in range(numb)]
    mate_pool = []
    for j in range(numb):
        val = pointers[j]
        index = 0
        total =pop[index][1]/float(total_fitness)
        while total < val:
            index += 1
            total += pop[index][1]/float(total_fitness)
        mate_pool.append(pop[index])
    return mate_pool