Mutemo-nos

Nota prévia: nos algoritmos apresentados as alterações são permanentes. Deve garantir que esta questão não coloca problemas ao código que os usa.


Comecemos pelo mais simples: mutação de cadeias binárias.

def muta_bin(cromo,prob_muta, muta_func):
    for i in range(len(indiv)):
        cromo[i] = muta_func(cromo[i],prob_muta)
    return cromo

# binário
def muta_bin_gene(gene, prob_muta):
    g = gene
    value = random.random()
    if value < prob_muta:
        g ^= 1
    return g

Não há muito a dizer: cada gene tem uma certa probabilidade de ser mutado. O valor da probabilidade de mutação é um parâmetro. Há quem use um valor baseado na regra de que que essa probabilidade deve ser o inverso do comprimento do indivíduo, garantindo assim que, em média, um gene é mutado.

Passemos ao caso de permutações de inteiros. Falámos nas aulas no operador que escolhe duas posições e troca os respectivos valores:

def muta_perm_swap(cromo, prob_muta):
    value = random.random()
    if value < prob_muta:
        index = random.sample(xrange(len(cromo)),2)
        index.sort()
        i1,i2 = index
        cromo[i1],cromo[i2] = cromo[i2], cromo[i1]
    return cromo

Mas existem alternativas, isto é, operadores que quando aplicados transformam uma permutação noutra permutação.

Escolhe dois pontos e baralha o conteúdo do vector entre os dois pontos:

def muta_perm_scramble(cromo,prob_muta):
    value = random.random()
    if value < prob_muta:
        index = random.sample(xrange(len(cromo)),2)
        index.sort()
        i1,i2 = index
        scramble = cromo[i1:i2+1]
        random.shuffle(scramble) 
        cromo = cromo[:i1] + scramble + cromo[i2+1:]
    return cromo

Escolhe dois pontos e inverte o conteúdo entre os dois pontos:

def muta_perm_inversion(cromo,prob_muta):
    value = random.random()
    if value < prob_muta:
        index = random.sample(xrange(len(cromo)),2)
        index.sort()
        i1,i2 = index
        inverte = []
        for elem in cromo[i1:i2+1]:
              inverte = [elem] + inverte
        cromo = cromo[:i1] + inverte + cromo[i2+1:]
    return cromo

Selecionar dois pontos. Insere o valor do gene na segunda posição no primeiro e desloca desde a primeira até à segunda uma posição para a direita:

def muta_perm_insertion(cromo, prob_muta):
    value = random.random()
    if value < prob_muta:
        index = random.sample(xrange(len(cromo)),2)
        index.sort()
        i1,i2 = index
        gene = cromo[i2]
        for i in range(i2,i1,-1):
          cromo[i] = cromo[i-1]
        cromo[i1+1] = gene
    return cromo

Finalmente, vectores de reais. Cado da mutação gaussiana.

def muta_reals(icromo, prob_muta, domain, sigma):
    for i in range(len(cromo)):
         cromo[i] = muta_reals_gene(cromo[i],prob_muta, domain[i], sigma[i])
    return cromo

Aqui verificamos se o novo valor excede o intervalo possível e, em caso afirmativo, aproxima esse valor do extremo mais próximo:

def muta_reals_gene_b(gene,prob_muta, domain_gene, sigma_gene):
    value = random.random()
    if value < prob_muta:
        muta_value = random.gauss(0,sigma_gene)
        new_gene = gene + muta_value
        if new_gene < domain_gene[0]:
            new_gene = domain_gene[0]
        elif new_gene > domain_gene[1]:
           new_gene = domain_gene[1]
    return new_gene

Enquanto o novo valor não for válido continua a gerar valores:

 
def muta_reals_gene(gene,prob_muta, domain_gene, sigma_gene):
    value = random.random()
    if value < prob_muta:
       muta_value = random.gauss(0,sigma_gene)
       new_gene = gene + muta_value
       while not (domain_gene[0] <= new_gene <= domain_gene[1]):
           muta_value = random.gauss(0,sigma_gene)
       new_gene = gene + muta_value             
    return new_gene