Ferramenta

Anexo uma ligação para um sítio, que me parece interessante, sobre uma ferramenta em Python para Algoritmos Evolucionários, chamada pyevolve. Não a testei e por isso ... não me comprometo.

http://pyevolve.sourceforge.net/

Ernesto Costa

TP: atribuições

Aqui deixo a lista com a atribuição dos diferentes trabalhos. Podem trocar entre vocês o que vos coube em sorte, mas tal facto terá que me ser comunicado.

Bons trabalhos.

Nome	TP
Alex de Deus Marques Santos	2 - op. var. var.
Ana Catarina Jerónio Pedroso Coutinho Nogueira	1 - op. var.
André Gonçalo Pereira dos Santos Lourenço	15 - PSO: pop.
Bruno Andre Pinhal Catarino	8 - Novos op.
Francisco Luis Amado Reis Ventura	12 - Evo. Dif. I
Ivo Carlos Pereira Gonçalves	10 - Bloat
João Miguel Salgado Lopes	13 - Evo. Dif. II
João Pedro Amorim França	14 - PSO: viz.
Jorge André Pinto de Sousa	4 - Diversidade II
Luis Miguel Baptista Branco	3 - Diversidade I
Marco António Machado Simões	16 - PSO: vel.
Nuno Alexandre Almeida de Amicis Rebelo	11 - Ambientes Din.
Nuno António Marques Lourenço	21 - Mod. HP
Pedro Mateus Figueiredo	7 - Auto-Adaptação
Sérgio David dos Santos	20 - Fourier
Tiago Lopes Leitão	6 - Diversidade IV

Ernesto Costa

Subtree Mutation

Mais uma variante para o algoritmo de programação genética. Agora, o grupo formado pelo João Lopes, Nuno Lourenço e Ivo Gonçalves, oferece o algoritmo com recurso ao operador de mutação por substituição de uma sub-árvore.
A rotina que implementaram é a que se segue.

def sub_tree_mutation(parent,func_set,term_set,max_depth):
   """ Return a mutated version of the parent."""
   global count
   # Choose crossover point (indepently)  
   size_1 = indiv_size(parent)
   cross_point_1 = choice(range(size_1))
   # identify subtrees to echange
   sub_tree_1 = sub_tree(parent, cross_point_1)
   method = choice(['grow','full'])
   sub_tree_2 = gen_rnd_expr(func_set,term_set,max_depth,method)
   # Exchange
   new_par_1 = deepcopy(parent)
   offspring = replace_sub_tree(new_par_1, sub_tree_1,sub_tree_2)
   return offspring

Em relação ao código que me foi enviado, fiz uma pequena mudança: o operador não é estocástico. Assim, quando este operador é activado no programa principal (onde também fiz desaparecer o lado probabilístico) é porque já vai haver mutação.

O código completo pode ser obtido em: http://eden.dei.uc.pt/~ernesto/cevol/st_mut.py

Divirtam-se!

Ernesto Costa

Projectos

Está na hora de realizar os projectos. Vamos ter que usar vários tipos de algoritmos evolucionários: algoritmos genéticos, programação genética, evolução artificial e optimizador baseado em partículas. Já usámos os dois primeiros. Deixo aqgora aqui a ligação para os dois últimos. Descarreguem o código e tentem usar. Caso haja dúvidas é só perguntar!

Evolução diferencial

Optimizador baseado em partículas

Quem sobrevive??

Existem vários métodos para determinar quem sobrevive em cada etapa do processo evolutivo. Segue o código que implementa uma ideia simples. Repete-se um número de vezes igual ao tamanho da população: fazer um torneio com indivíduos da população de pais e escolher o pior. Fazer um torneio com os indivíduos da população dos filhos e escolher o melhor. Substituir, na população dos pais, o pior elemento pelo melhor da população dos filhos. Dos torneios o que retiramos são os índices dos indivíduos, não os indivíduos!

def survivors_steady_state(population, offspring, t_size):
    """The winner of a offspring tournamente replaces the loser of a population tournament."""
    for i in range(len(population)):
         # get indexes
        winner = positive_tournament(offspring,t_size)
       loser = negative_selection(population, t_size)
       # replace
        population[loser] = offspring[winner]
   return population

def positive_tournament(population, t_size):
    """Deterministic. Return the index of the winner of the tournament."""
    pool_index = [choice(range(len(population))) for i in range(t_size)]
    best_index = pool_index[0]
    for j in range(1, t_size):
         if population[pool_index[j]][1] > population[best_index][1]:
             best_index = pool_index[j]    
    return best_index

def negative_tournament(population, t_size):
    """Deterministic. Return the index of the worst individual in the tournament."""
    pool_index = [choice(range(len(population))) for i in range(t_size)]
    worst_index = pool_index[0]    
    for j in range(1, t_size):
        if population[pool_index[j]][1] < population[worst_index][1]:
         worst_index = pool_index[j]   
    return worst_index

Ernesto Costa

Programação genética: método de selecção por estado estável (steady-state model)

Neste tipo de abordagem, o pai com pior fitness é seleccionado e substituído por um filho (pela ordem que ocupa na lista ou escolhendo o melhor filho; neste exercício foi implementado o primeiro caso). Apenas nos interessa saber os índices dos indivíduos que participam na troca e não os próprios indivíduos (pois só acrescentam peso computacional). Por fim, sabemos ainda que a população não evolui toda de uma só vez, mas sim uma parte desta.

Então, o que fizemos foi o seguinte:
- escolhemos por torneio n indivíduos de toda a população (n é a dimensão do torneio)
- encontramos o pai com pior fitness- torneio negativo
- este é trocado por um filho, segundo a ordem sequencial de índice
- repetimos tantas vezes quantas a dimensão da população, e devolvemos o resultado.

O método foi implementado com duas funções: negative_tournament e survivors_steady_state. A primeira encontra o prior pai e a segunda faz a troca deste com um filho, devolvendo a população final.

def negative_tournament(population, size):
    """Deterministic"""
    pool_index = [choice(range(len(population))) for i in range(size)]
    worst_index = pool_index[0]   
    for j in range(1, size):
    if population[pool_index[j]][1] < population[worst_index][1]:
         worst_index = pool_index[j]   
    return worst_index

def survivors_steady_state(population, offspring, size):
   """Swap the worst parent by an offspring element"""
   for i in range(len(population)):
       worst_parent = negative_tournament(population, size)
       population[worst_parent] = offspring[i]
   return population

O código completo pode ser descarregado a partir de: aqui.

Nota: no programa principal, deve-se usar a função survivors_steady_state em vez da survivors_elitism.


Ana Nogueira

Livro sobre Programação Genética

Existem vários livros sobre programação genética, incluindo livros de texto. Este cujo URL indico é o melhor. Escrito pelos investigadores de maior relevo na área. E é de graça! E trás o código de um simulador em Java (:-(!). Código que pode ser descarregado a partir da mesma ligação. E... vão lá descarreguem e leiam para saber toda a história.



Livro sobre GP

Ernesto Costa

Para acabar com a Selecção

Para concluir as versões mais usadas de selecção vamos incluir o método por ordem:

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

Os interessados podem consultar o livro do Eiben e Smith, página 60.

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

Sejamos selectivos!

Existem vários métodos de selecção. A grande questão que se coloca a um designer é a seguinte: como seleccionar os progenitores de modo a garantir qualidade mas ao mesmo tempo não fazer convergir prematuramente a população para um máximo local?

A selecção por torneio procura responder a essa questão. No caso mais comum o torneio tem uma dimensão entre 2 e 5 e é determinista , isto é, o melhor é sempre escolhido para reprodução e variação. O Sérgio Santos manda a sua solução:

def torneio(num_progenitores, populacao):
  tam_torneio = 5
  progenitores = []

  for n in range(num_progenitores):
      elems_torneio = []
      for i in range(tam_torneio):
          elems_torneio.append(choice(populacao))
      elems_torneio.sort(key=itemgetter(1))
      progenitores.append(elems_torneio[0])
  return progenitores

O que podemos dizer. Bem, desde logo que funciona. Em segundo lugar, usa o método choice do módulo random. Usa um padrão de desenho simples: a partir de uma lista vazia vai acumulando os resultados parciais nessa lista. Conclusão: está bom!

Mas vou apresentar-vos uma alternativa:

def tournament_sel(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 = sample(population, size)
  pool.sort(key=itemgetter(1), reverse=True)
  return pool[0]

Quais são as diferenças principais? A separação do problema em duas partes, o uso de listas por comprensão (padrão de desenho alternativo) e o uso do método sample do módulo random para me dar de uma só vez todos os candidatos do torneio. No meu caso faço uma escolha sem reposição. Usando o choice a escolha é com reposição.

Ernesto Costa (com contributos de Sérgio Santos)

O seu a seu dono!

Aqui deixo a atribuição dos trabalhos teóricos. Boas leituras e melhores textos e apresentações.




Ernesto Costa

No princípio era a representação...

Disse nas aulas que quando estamos a desenvolver uma solução baseada em algoritmos evolucionários, a primeira coisa que fazemos é pensar na representação. seguem-se os operadores de variação adequados ao problema. No que diz respeito à representação, as mais comuns são:

- cadeias binárias
- permutações de inteiros
- vectores de reais

Definida a representação um outro aspecto a resolver é o da geração da população inicial, o que é feito em geral de modo aleatório. Vejamos como se pode fazer isso em Python. Comecemos pelas cadeias binárias:

def generate_pop_bin(tam_pop, tam_chromo):
  return [(generate_bit_string(tam_cromo),0) for j in range(tam_pop)]

def generate_bit_string(size):
 return [randint(0,1) for i in range(size)]

Como se vê precisamos do método randint do módulo random ,que terá que ser importado. Por outro lado note-se o uso, nas duas funções, de listas por compreensão. Finalmente, atente-se ao facto da nossa representação conter também um campo para o mérito de cada indivíduo.

E se for uma permutação de inteiros? Também não é complexo:

def generate_pop_perm_int(tam_pop, tam_chromo):
  return [(generate_permutation_int(tam_cromo),0) for j in range(tam_pop)]

def generate_permutation_int(tam_cromo):
 caminho = range(tam_cromo)
 shuffle(caminho)
 return caminho

Aqui é o método shuffle do módulo random que vem em nosso auxílio. Admitimos que a permutação é formada pelos inteiros de 0 até ao comprimento especificado menos um. Uma vez mais: listas por compreensão.

E finalmente o caos dos números reais.

def generate_pop_reals(pop_size, domain, sigma):
 return [generate_vector_reals(domain, sigma) for i in range(pop_size)]


def generate_vector_reals(domain, sigma):
 return [[uniform(domain[i][0], domain[i][1]), sigma[i]]for i in range(len(domain))]

E desta vez o que é que random nos deu? O método uniform. E mais listas por compreensão... E os parâmetros estratégicos na representação.

Atente-se no que têm em comum todas estas alternativas. E as diferenças?

Ernesto Costa

Todo o princípio é difícil...

E pronto. Vamos lá começar este blogue, a pensar nos alunos da Cadeira de Computação Evolucionária, do curso de Mestrado em Engenharia Informática da Univiersidade de Coimbra. O que daqui sairá não sei muito bem. Mas sei, isso sim, que o blogue será o resultado da acção (e omissão!!) de todos.

Vamos pois a isto!

Ernesto Costa