A selecção do Nuno Lourenço e do Sérgio Santos

Aqui vão as propostas do Nuno Lourenço e do Sérgio Santos para métodos de selecção. Primeiro o do Nuno Lourenço. Trata-se do método por roleta que implementou para o TSP:

def select_parents(populacao, fit_func, dic_cidades, n_parents):
soma = 0.0
fitness_individuos = []
parents = []

for individuo in populacao:
 temp = 1 / (1 + evaluate(fenotipo(individuo[0],dic_cidades)))
 soma += temp
 fitness_individuos.append(temp)

fitness_individuos[0]  /=  soma

for i in range(1,len(fitness_individuos)):
 fitness_individuos[i] = (fitness_individuos[i] / soma) + fitness_individuos[i-1]

for parent in range(n_parents):
 p = random()
 for ind in range(len(fitness_individuos)):
  if(p <= fitness_individuos[ind]):
   parents.append(populacao[ind])
   break
return parents

Este algoritmo está agarrado ao problema, não sendo por isso geral. Mas é fácil alterar, bastando para tal que os indivíduos sejam avaliados antes de serem seleccionados. Uma alternativa minha:

def roulette_wheel(population, numb):
    """ Select numb individuals from the population
    according with their relative fitness."""
    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

Uso o método uniform que é mais geral do que random, embora neste caso a diferença seja ... nenhuma! Também o uso de listas por compreensão. Em vez de fazer as somas só uma vez, elas são calculadas sempre que é necessário saber o valor. Não é muito eficiente!

Agora o método de amostragem estocástica universal: só com uma rotação da roleta seleccionar todos os elementos. Propõe o Sérgio Santos:

def amost_universal(population, num_parents):
 soma = sum([ind[1] for ind in population])
 probabilities = []
 temp_soma = 0
 for ind in population:
     prob = ind[1]/soma
     probabilities.append( prob + temp_soma )
     temp_soma += prob
 interval = 1.0 / num_parents
 pointer = uniform(0,interval)
 parents = []
 for n in range(num_parents):
     for i in range(len(population)):
         if probabilities[i] <= pointer:
             parents.append(population[i])
             break
     pointer += interval 
 return parents

Comentário: eu substituía o ciclo for mais o break por um ciclo while. A minha alternativa:

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