Python Passo Crossover de algoritmos genéticos

Ture · 28 de janeiro de 2020

Olá, estou implementando um GA do zero mas encontrei uma pedra: Na operação de crossover minha função acaba retornando diversos indivíduos iguais e não consigo identificar o porquê; Segue partes importantes para identificar o problema:

Notem que atribuo fitness randômicas a fim de teste e o código é relativamente maior mas o meu problema parece se encontrar aqui!

Peço que ignorem a "cara" dos meus indivíduos, é um GA para um problema bem específico incluindo um step de clusterização e seleção de features de cada cluster.

import random
import string
import pandas as pd
import numpy as np


class Agent:

    
    def __init__(self, Ncluster, Nfeatures, Nsamples):
                
        self.tamanho = Ncluster * Nfeatures
        
        self.Ncluster = Ncluster
        self.Nfeatures = Nfeatures
        self.Nsamples = Nsamples
        self.indiv = []
                
        for _ in range(self.tamanho):
            self.indiv.append(random.choice([0,1]))
        for _ in range(Nsamples):
            self.indiv.append(random.choice(range(Ncluster)))
            
        self.fitness = random.choice([0,1])

        
        
    def __str__(self):

        return 'Features: ' +  f'{self.indiv[:self.Ncluster*self.Nfeatures]}' +' Cluster/Sample: ' + f'{self.indiv[self.Ncluster*self.Nfeatures:]}'

    def __len__(self):
        return self.Ncluster * self.Nfeatures + self.Nsamples
    

         


def init_agents(population,Ncluster, Nfeatures, Nsamples):

    return [Agent(Ncluster, Nfeatures, Nsamples) for _ in range(population)]




def crossover(agents, population):

    offspring = []
    filho1 = agents[0]
    filho2 = agents[0]
    for _ in range((population - len(agents)) // 2):
        mask = []
        for _ in range(len(agents[0])):
            mask.append(random.choice([0,1]))
        pai, mae = random.sample(agents, 2)
        for bit in range(len(mask)):
            if mask[bit] == 1:
                filho1.indiv[bit] = pai.indiv[bit]
            else:
                filho1.indiv[bit] = mae.indiv[bit]
            if mask[bit] == 1:
                filho2.indiv[bit] = mae.indiv[bit]
            else:
                filho2.indiv[bit] = pai.indiv[bit]
        offspring.append(filho1)
        offspring.append(filho2)

    agents.extend(offspring)
    return agents

Antes de executar o crossover eu executo um processo de seleção de indivíduos, então o crossover é o responsável por criar novos indivíduos baseado nos selecionados(que é a própria lista agents) até o meu número "population" (que é o total de indivíduos de cada geração)

Ture · 7 de fevereiro de 2020

Pode fechar o post. Resolvido.

O problema é que classes em python são passadas por referência e não por cópia como tratei ela. Precisei usar o método deepcopy para driblar o problema. Para os interessados segue a solução:

def crossover(agents, population):

    offspring = []
    filho1 = agents[0]
    filho2 = agents[0]
    for i in range((population - len(agents)) // 2):
        mask = []
        for _ in range(len(agents[0])):
            mask.append(random.choice([0,1]))
        pai, mae = random.sample(agents, 2)
        for bit in range(len(mask)):
            if mask[bit] == 0:
                filho1.indiv[bit] = pai.indiv[bit]
                filho2.indiv[bit] = mae.indiv[bit]
            else:
                filho1.indiv[bit] = mae.indiv[bit]
                filho2.indiv[bit] = pai.indiv[bit]
        offspring.append(deepcopy(filho1))
        offspring.append(deepcopy(filho2))
    agents.extend(offspring)
    return agents

8 de fevereiro de 2020

Agora consegui compreender sua dúvida, sim realmente o Python faz referência a objetos criados, acho que você está em um área que eu não estudo, deve ser de Data Science, correto?

Bom, tudo que vou dizer aqui você já deve saber, mas como é um assunto de aprendizagem, tem gente que vai ler e talvez não saiba disso sobre o Python.

TUDO em absoluto no Python é tratado como um objeto e uma vez criado, ele pode ser referenciado e reaproveitado.

É uma forma inteligente da Python em poupar ciclos de processamento e alocação de memória, fazer reaproveitamento do objeto

Quando você associa uma lista por exemplo a uma variável, você está passando uma referência do objeto original.

numeros = 1 # Uma variável que recebe um valor inteiro

print(type(numeros)) # Imprime o tipo do objeto
print(id(numeros)) # Imprime o ID do objeto

lista = [1,2,3,4]

numeros  = lista # Aqui reaproveito o objeto "numeros", numeros é só uma etiqueta
		 # para humanos rotularem o ID do objeto, pois o ID é o que o PC entende.

# Imprime o tipo do objeto
print(type(lista)) 
print(type(numeros))

# Imprime o ID do objeto
print(id(numeros))
print(id(numeros))



"""
Produz na tela os seguintes resultados:

<class 'int'> O tipo
1678362528 O ID do objeto na memória

<class 'list'> A lista [1,2,3,4]

<class 'list'> O reaproveitamento do objeto por associação


3417928
3417928

Veja acima, o mesmo ID para ambos os objetos, mostra que são agora do mesmo tipo e endereço, 
herdando os valores do objeto por referência, você poderá mudar valores no objeto que recebeu a 
referência e pode novamente mudar sua característica como objeto(tipagem), pois o Python tem tipagem 
dinâmica e forte.
"""

No seu caso em específico não sei porque utilizar o deepcopy, a não ser sob essa justificativa de manter dados originais em um objeto e só alterar nas cópias(ou o contrário), acho eu que é uma das aplicações em Data Science, você tem uma coleção de dados e precisa iterar sobre eles e manter eles originais e inalteráveis ou trabalhando sobre as cópias.

Más com isso você pode aumentar o custo de processamento dependendo do que se destina o código.

Obrigado por esclarecer a sua dúvida aqui, até eu queria saber o que era....kkkk!

Ture · 18 de fevereiro de 2020

Em 08/02/2020 às 12:50, fspjonny disse:
Agora consegui compreender sua dúvida, sim realmente o Python faz referência a objetos criados, acho que você está em um área que eu não estudo, deve ser de Data Science, correto?

Bom, tudo que vou dizer aqui você já deve saber, mas como é um assunto de aprendizagem, tem gente que vai ler e talvez não saiba disso sobre o Python.

TUDO em absoluto no Python é tratado como um objeto e uma vez criado, ele pode ser referenciado e reaproveitado.

É uma forma inteligente da Python em poupar ciclos de processamento e alocação de memória, fazer reaproveitamento do objeto

Quando você associa uma lista por exemplo a uma variável, você está passando uma referência do objeto original.
numeros = 1 # Uma variável que recebe um valor inteiro

print(type(numeros)) # Imprime o tipo do objeto
print(id(numeros)) # Imprime o ID do objeto

lista = [1,2,3,4]

numeros  = lista # Aqui reaproveito o objeto "numeros", numeros é só uma etiqueta
		 # para humanos rotularem o ID do objeto, pois o ID é o que o PC entende.

# Imprime o tipo do objeto
print(type(lista)) 
print(type(numeros))

# Imprime o ID do objeto
print(id(numeros))
print(id(numeros))



"""
Produz na tela os seguintes resultados:

<class 'int'> O tipo
1678362528 O ID do objeto na memória

<class 'list'> A lista [1,2,3,4]

<class 'list'> O reaproveitamento do objeto por associação


3417928
3417928

Veja acima, o mesmo ID para ambos os objetos, mostra que são agora do mesmo tipo e endereço, 
herdando os valores do objeto por referência, você poderá mudar valores no objeto que recebeu a 
referência e pode novamente mudar sua característica como objeto(tipagem), pois o Python tem tipagem 
dinâmica e forte.
"""
No seu caso em específico não sei porque utilizar o deepcopy, a não ser sob essa justificativa de manter dados originais em um objeto e só alterar nas cópias(ou o contrário), acho eu que é uma das aplicações em Data Science, você tem uma coleção de dados e precisa iterar sobre eles e manter eles originais e inalteráveis ou trabalhando sobre as cópias.

Más com isso você pode aumentar o custo de processamento dependendo do que se destina o código.

Obrigado por esclarecer a sua dúvida aqui, até eu queria saber o que era....kkkk!

Sim, trabalho com data science entre um punhado de outras coisas.

O problema foi exatamente esse. Eu estava alterando toda vez o mesmo endereço da memória e adicionando na minha lista, como se estes fossem diferentes objetos na minha memória. O deepcopy foi a maneira mais simples que vi solucionar o problema, não realizei testes quanto a parte de custo mas no geral o crossover é uma das operações "leves" dentro de um algoritmo genético então não me preocupei muito com isso; Como funcionou eu fui por ai mesmo.

A área é realmente bem instigante, estou começando a mexer com isso e é realmente satisfatório quando tu consegues aplicar teus algoritmos em soluções mais complexas. No algoritmo em questão eu faço seleção de features individual para cada cluster(similar ao bi-clustering) juntamente com o processo de clusterização de um bocado de dados com um bocado de features hehehe.

Obrigado pela resposta!

Abraço.

18 de fevereiro de 2020

3 horas atrás, Ture disse:

Sim, trabalho com data science entre um punhado de outras coisas.

O problema foi exatamente esse. Eu estava alterando toda vez o mesmo endereço da memória e adicionando na minha lista, como se estes fossem diferentes objetos na minha memória. O deepcopy foi a maneira mais simples que vi solucionar o problema, não realizei testes quanto a parte de custo mas no geral o crossover é uma das operações "leves" dentro de um algoritmo genético então não me preocupei muito com isso; Como funcionou eu fui por ai mesmo.

A área é realmente bem instigante, estou começando a mexer com isso e é realmente satisfatório quando tu consegues aplicar teus algoritmos em soluções mais complexas. No algoritmo em questão eu faço seleção de features individual para cada cluster(similar ao bi-clustering) juntamente com o processo de clusterização de um bocado de dados com um bocado de features hehehe.

Obrigado pela resposta!

Abraço.

Rapaz, eu queria ter te mostrado esse vídeo antes, como não achei ele no dia da resposta e só hoje você me mandou essa mensagem, eu lembrei dele aqui agora, tinha até marcado ele:

Assiste ai se você não o assistiu ainda, fala sobre o Python vs R, no teu campo de trabalho é muito bom se cercar dessas ferramentas que se complementam.

Ture · 19 de fevereiro de 2020

@fspjonny Opa. darei uma olhada, o conteúdo parece bastante interessante.

Caso alguém ai esteja interessado em algoritmos genéticos achei esse link aqui do CdH mesmo que dá uma explicação sucinta mas boa do que se trata: https://www.clubedohardware.com.br/forums/topic/116581-algoritmos-genéticos/

Abraço a todos!