Arquivo de Python - Página 21 de 31

O que é cruzamento?

O cruzamento é uma operação fundamental em algoritmos genéticos. Ela imita a reprodução sexual da natureza. Dois indivíduos trocam partes de seu código genético. Assim, geram novos indivíduos para a próxima geração. Essa troca produz descendentes com características de ambos os pais. Portanto, a diversidade da população aumenta gradualmente. O cruzamento não cria informação do nada. Em vez disso, ele recombina o material existente de maneira criativa. Consequentemente, a busca por soluções melhores se torna mais eficiente. Ele é aplicado após a seleção dos pais. A taxa de cruzamento define sua probabilidade de ocorrência. Valores típicos ficam entre 60% e 90%. Caso contrário, os pais são copiados diretamente. O cruzamento é essencial para a exploração do espaço de soluções. Sem ele, o algoritmo seria apenas uma busca local.

Tipos comuns de cruzamento

Existem várias formas de realizar o cruzamento. O cruzamento de um ponto é o mais simples. Um ponto de corte é escolhido aleatoriamente. Os genes após esse ponto são trocados entre os pais. O cruzamento de dois pontos usa dois pontos de corte. A seção entre eles é que é trocada. O cruzamento uniforme é ainda mais flexível. Cada gene é trocado com uma probabilidade independente. Para representações binárias, esses métodos são diretos. Em problemas contínuos, usa-se o cruzamento aritmético. Ele calcula médias ponderadas dos valores dos pais. A escolha do tipo afeta a convergência do algoritmo. Por essa razão, deve-se testar diferentes abordagens. Cada problema pode exigir um tipo específico. A experimentação é sempre recomendada na prática.

Importância para a otimização

O cruzamento equilibra exploração e explotação no algoritmo. Ele permite combinar boas soluções parciais de diferentes indivíduos. Essa combinação pode gerar soluções superiores aos pais. A exploração é favorecida quando a população é diversa. A explotação ocorre quando os melhores indivíduos se cruzam. O cruzamento mantém a herança genética das melhores soluções. Ao mesmo tempo, ele introduz variabilidade controlada. Essa variabilidade evita a estagnação prematura do processo. É importante lembrar que o cruzamento não substitui a mutação. Ambos operam de forma complementar e simultânea. A mutação introduz novidade, enquanto o cruzamento reorganiza. Juntos, eles guiam a busca para o ótimo global. A eficácia do cruzamento foi comprovada em milhares de estudos. Ele é usado em engenharia, finanças e robótica. Sua simplicidade esconde um poder computacional imenso.

Exemplo clássico: o problema do caixeiro viajante

Considere um vendedor que deve visitar cinco cidades. Ele precisa percorrer a menor rota possível. Cada cidade é visitada exatamente uma vez. A distância entre cada par de cidades é conhecida. O objetivo é minimizar a distância total percorrida. Esse é o clássico problema do caixeiro viajante (TSP). Para resolvê-lo com algoritmo genético, usamos uma representação permutacional. Cada indivíduo é uma ordem de visita das cidades. O cruzamento deve respeitar que cada cidade aparece uma vez. O cruzamento de ordem (OX) é frequentemente aplicado aqui. Ele preserva a ordem relativa dos genes. Dois pontos de corte são escolhidos aleatoriamente. A seção entre eles é copiada do primeiro pai. Os genes restantes são preenchidos na ordem do segundo pai. Essa abordagem gera descendentes válidos e promissores.

Resolução em python para o google colab

O código abaixo implementa o TSP com 5 cidades. A distância é calculada pela métrica euclidiana. A população inicial é gerada aleatoriamente. O cruzamento de ordem é aplicado com taxa de 80%. A seleção é feita por torneio de tamanho 2. O algoritmo roda por 100 gerações. Ao final, a melhor rota é exibida em um gráfico. Dois gráficos são gerados: a evolução da distância e a rota final. Execute o código no Google Colab para ver os resultados. As bibliotecas numpy e matplotlib são utilizadas. Certifique-se de instalar todas as dependências. O código é autoexplicativo e comentado. Divirta-se explorando o poder do cruzamento!

import numpy as np
import matplotlib.pyplot as plt
import random

# Coordenadas das cidades (x, y)
cidades = np.array([[0, 0], [1, 3], [2, 1], [3, 4], [4, 2]])
n_cidades = len(cidades)

# Matriz de distâncias euclidianas
def calc_distancias(cidades):
    n = len(cidades)
    dist = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            dist[i][j] = np.linalg.norm(cidades[i] - cidades[j])
    return dist

distancias = calc_distancias(cidades)

# Função de aptidão (distância total da rota)
def aptidao(rota):
    total = 0
    for i in range(n_cidades - 1):
        total += distancias[rota[i]][rota[i+1]]
    total += distancias[rota[-1]][rota[0]]  # retorna à origem
    return total

# Cruzamento de ordem (OX)
def cruzamento_ox(pai1, pai2):
    tamanho = len(pai1)
    a, b = sorted(random.sample(range(tamanho), 2))
    filho1 = [-1]*tamanho
    filho2 = [-1]*tamanho
    # Copia a seção do pai1 para filho1
    filho1[a:b+1] = pai1[a:b+1]
    # Preenche o restante com a ordem do pai2
    pos = b+1
    for gene in pai2:
        if gene not in filho1:
            if pos >= tamanho:
                pos = 0
            while filho1[pos] != -1:
                pos += 1
                if pos >= tamanho:
                    pos = 0
            filho1[pos] = gene
    # Copia a seção do pai2 para filho2
    filho2[a:b+1] = pai2[a:b+1]
    pos = b+1
    for gene in pai1:
        if gene not in filho2:
            if pos >= tamanho:
                pos = 0
            while filho2[pos] != -1:
                pos += 1
                if pos >= tamanho:
                    pos = 0
            filho2[pos] = gene
    return filho1, filho2

# Mutação por troca de dois genes
def mutacao(rota, taxa=0.1):
    if random.random() < taxa:
        i, j = random.sample(range(len(rota)), 2)
        rota[i], rota[j] = rota[j], rota[i]
    return rota

# Seleção por torneio
def torneio(populacao, aptidoes, k=2):
    indices = random.sample(range(len(populacao)), k)
    melhor = indices[0]
    for i in indices[1:]:
        if aptidoes[i] < aptidoes[melhor]:
            melhor = i
    return populacao[melhor]

# Parâmetros
tam_pop = 20
geracoes = 100
taxa_cruz = 0.8
taxa_mut = 0.1

# Inicialização da população (permutações aleatórias)
populacao = [random.sample(range(n_cidades), n_cidades) for _ in range(tam_pop)]
historico_melhor = []

for gen in range(geracoes):
    aptidoes = [aptidao(ind) for ind in populacao]
    melhor_atual = min(aptidoes)
    historico_melhor.append(melhor_atual)
    nova_populacao = []
    # Elitismo: mantém o melhor indivíduo
    melhor_ind = populacao[np.argmin(aptidoes)]
    nova_populacao.append(melhor_ind.copy())
    while len(nova_populacao) < tam_pop:
        pai1 = torneio(populacao, aptidoes)
        pai2 = torneio(populacao, aptidoes)
        if random.random() < taxa_cruz:
            filho1, filho2 = cruzamento_ox(pai1, pai2)
        else:
            filho1, filho2 = pai1.copy(), pai2.copy()
        filho1 = mutacao(filho1, taxa_mut)
        filho2 = mutacao(filho2, taxa_mut)
        nova_populacao.append(filho1)
        if len(nova_populacao) < tam_pop:
            nova_populacao.append(filho2)
    populacao = nova_populacao

# Resultado final
aptidoes_final = [aptidao(ind) for ind in populacao]
melhor_rota = populacao[np.argmin(aptidoes_final)]
distancia_melhor = min(aptidoes_final)
print("Melhor rota encontrada:", melhor_rota)
print("Distância total:", distancia_melhor)

# Gráfico 1: Evolução da melhor distância
plt.figure(figsize=(12, 5))
plt.subplot(1, 2, 1)
plt.plot(historico_melhor, color='blue')
plt.title("Evolução da Melhor Distância")
plt.xlabel("Geração")
plt.ylabel("Distância")
plt.grid(True)

# Gráfico 2: Rota final no mapa
plt.subplot(1, 2, 2)
rota_ordenada = cidades[melhor_rota]
plt.plot(rota_ordenada[:, 0], rota_ordenada[:, 1], 'o-', color='red', linewidth=2)
# Fechar o polígono
plt.plot([rota_ordenada[-1, 0], rota_ordenada[0, 0]],
         [rota_ordenada[-1, 1], rota_ordenada[0, 1]], 'r--', linewidth=1)
for i, (x, y) in enumerate(cidades):
    plt.text(x+0.05, y+0.05, str(i), fontsize=12, weight='bold')
plt.title("Melhor Rota Encontrada")
plt.xlabel("Coordenada X")
plt.ylabel("Coordenada Y")
plt.grid(True)
plt.tight_layout()
plt.show()

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

import numpy as np

import matplotlib.pyplot as plt

import random

# Coordenadas das cidades (x, y)

cidades = np.array([[0, 0], [1, 3], [2, 1], [3, 4], [4, 2]])

n_cidades = len(cidades)

# Matriz de distâncias euclidianas

def calc_distancias(cidades):

n = len(cidades)

dist = np.zeros((n, n))

for i in range(n):

for j in range(n):

dist[i][j] = np.linalg.norm(cidades[i] - cidades[j])

return dist

distancias = calc_distancias(cidades)

# Função de aptidão (distância total da rota)

def aptidao(rota):

total = 0

for i in range(n_cidades - 1):

total += distancias[rota[i]][rota[i+1]]

total += distancias[rota[-1]][rota[0]] # retorna à origem

return total

# Cruzamento de ordem (OX)

def cruzamento_ox(pai1, pai2):

tamanho = len(pai1)

a, b = sorted(random.sample(range(tamanho), 2))

filho1 = [-1]*tamanho

filho2 = [-1]*tamanho

# Copia a seção do pai1 para filho1

filho1[a:b+1] = pai1[a:b+1]

# Preenche o restante com a ordem do pai2

pos = b+1

for gene in pai2:

if gene not in filho1:

if pos >= tamanho:

pos = 0

while filho1[pos] != -1:

pos += 1

if pos >= tamanho:

pos = 0

filho1[pos] = gene

# Copia a seção do pai2 para filho2

filho2[a:b+1] = pai2[a:b+1]

pos = b+1

for gene in pai1:

if gene not in filho2:

if pos >= tamanho:

pos = 0

while filho2[pos] != -1:

pos += 1

if pos >= tamanho:

pos = 0

filho2[pos] = gene

return filho1, filho2

# Mutação por troca de dois genes

def mutacao(rota, taxa=0.1):

if random.random() < taxa:

i, j = random.sample(range(len(rota)), 2)

rota[i], rota[j] = rota[j], rota[i]

return rota

# Seleção por torneio

def torneio(populacao, aptidoes, k=2):

indices = random.sample(range(len(populacao)), k)

melhor = indices[0]

for i in indices[1:]:

if aptidoes[i] < aptidoes[melhor]:

melhor = i

return populacao[melhor]

# Parâmetros

tam_pop = 20

geracoes = 100

taxa_cruz = 0.8

taxa_mut = 0.1

# Inicialização da população (permutações aleatórias)

populacao = [random.sample(range(n_cidades), n_cidades) for _ in range(tam_pop)]

historico_melhor = []

for gen in range(geracoes):

aptidoes = [aptidao(ind) for ind in populacao]

melhor_atual = min(aptidoes)

historico_melhor.append(melhor_atual)

nova_populacao = []

# Elitismo: mantém o melhor indivíduo

melhor_ind = populacao[np.argmin(aptidoes)]

nova_populacao.append(melhor_ind.copy())

while len(nova_populacao) < tam_pop:

pai1 = torneio(populacao, aptidoes)

pai2 = torneio(populacao, aptidoes)

if random.random() < taxa_cruz:

filho1, filho2 = cruzamento_ox(pai1, pai2)

else:

filho1, filho2 = pai1.copy(), pai2.copy()

filho1 = mutacao(filho1, taxa_mut)

filho2 = mutacao(filho2, taxa_mut)

nova_populacao.append(filho1)

if len(nova_populacao) < tam_pop:

nova_populacao.append(filho2)

populacao = nova_populacao

# Resultado final

aptidoes_final = [aptidao(ind) for ind in populacao]

melhor_rota = populacao[np.argmin(aptidoes_final)]

distancia_melhor = min(aptidoes_final)

print("Melhor rota encontrada:", melhor_rota)

print("Distância total:", distancia_melhor)

# Gráfico 1: Evolução da melhor distância

plt.figure(figsize=(12, 5))

plt.subplot(1, 2, 1)

plt.plot(historico_melhor, color='blue')

plt.title("Evolução da Melhor Distância")

plt.xlabel("Geração")

plt.ylabel("Distância")

plt.grid(True)

# Gráfico 2: Rota final no mapa

plt.subplot(1, 2, 2)

rota_ordenada = cidades[melhor_rota]

plt.plot(rota_ordenada[:, 0], rota_ordenada[:, 1], 'o-', color='red', linewidth=2)

# Fechar o polígono

plt.plot([rota_ordenada[-1, 0], rota_ordenada[0, 0]],

[rota_ordenada[-1, 1], rota_ordenada[0, 1]], 'r--', linewidth=1)

for i, (x, y) in enumerate(cidades):

plt.text(x+0.05, y+0.05, str(i), fontsize=12, weight='bold')

plt.title("Melhor Rota Encontrada")

plt.xlabel("Coordenada X")

plt.ylabel("Coordenada Y")

plt.grid(True)

plt.tight_layout()

plt.show()

O que é seleção em algoritmos evolutivos?

A seleção é um processo fundamental nos algoritmos evolutivos. Ela imita a escolha natural dos seres vivos. Indivíduos mais aptos têm maior chance de reprodução. Assim, a população melhora ao longo das gerações. Esse mecanismo guia a busca por soluções ótimas. Portanto, a seleção não é aleatória, mas direcionada. Ela equilibra exploração e exploração do espaço de busca. Sem ela, o algoritmo seria uma busca cega. Por isso, a seleção é o coração da evolução computacional.

Roleta: probabilidade proporcional à aptidão

A roleta é um método clássico de seleção proporcional. Cada indivíduo ocupa uma fatia da roleta. O tamanho da fatia é proporcional à sua aptidão. Então, indivíduos melhores têm áreas maiores. Um número aleatório decide qual fatia é escolhida. Esse processo é repetido até preencher a nova população. Contudo, a roleta pode sofrer com convergência prematura. Isso acontece quando um indivíduo muito bom domina. A diversidade da população pode ser reduzida rapidamente. Mesmo assim, ela é simples e intuitiva para iniciantes.

Torneio: competição direta entre indivíduos

O torneio é outro método de seleção muito usado. Ele escolhe aleatoriamente um grupo de indivíduos. O tamanho do grupo é definido pelo usuário. Depois, compara-se a aptidão de todos eles. O vencedor é aquele com maior aptidão. Esse vencedor é copiado para a nova geração. O processo se repete até completar a população. Uma vantagem é não precisar de normalização. Além disso, o torneio mantém pressão seletiva ajustável. Torneios maiores aumentam a pressão seletiva. Por outro lado, torneios menores preservam diversidade. Assim, o torneio é robusto e popular na prática.

Comparação entre roleta e torneio

A roleta é sensível à escala da aptidão. Já o torneio depende apenas de comparações relativas. A roleta pode ser implementada facilmente. O torneio é mais eficiente computacionalmente. A roleta é recomendada quando a aptidão é positiva. O torneio funciona bem com aptidões negativas também. Ambos os métodos são estocásticos por natureza. Eles introduzem aleatoriedade controlada no processo. Essa aleatoriedade evita ficar preso em ótimos locais. Portanto, a escolha entre eles é situacional. Iniciantes frequentemente começam com o torneio. Ele é mais tolerante a diferentes escalas de aptidão.

Exemplo clássico: maximização de uma função

Considere o problema de maximizar f(x) = x². O domínio é x no intervalo [0, 31]. Representamos x como um binário de 5 bits. A população inicial tem 6 indivíduos aleatórios. Usaremos seleção por torneio de tamanho 3. O crossover é de um ponto com probabilidade 0.7. A mutação troca um bit com chance 0.01. Executamos 20 gerações para evoluir a população. Ao final, esperamos encontrar x próximo de 31. Esse é um problema clássico de algoritmos genéticos. Ele ilustra bem o poder da seleção evolutiva. Agora, veja a resolução completa em Python abaixo.

import numpy as np
import matplotlib.pyplot as plt
import random

# Função objetivo (maximizar)
def fitness(x):
    return x**2

# Decodifica binário para inteiro
def decode(bits):
    return int(''.join(map(str, bits)), 2)

# Inicializa população aleatória (6 indivíduos, 5 bits)
pop_size = 6
bits = 5
pop = [[random.randint(0,1) for _ in range(bits)] for _ in range(pop_size)]

# Armazena melhores aptidões por geração
melhores = []
medias = []

for geracao in range(20):
    # Avalia aptidão
    fitnesses = [fitness(decode(ind)) for ind in pop]
    melhores.append(max(fitnesses))
    medias.append(np.mean(fitnesses))
    
    # Nova população por torneio (tamanho 3)
    nova_pop = []
    for _ in range(pop_size):
        # Seleciona 3 indivíduos aleatórios
        candidatos = random.sample(range(pop_size), 3)
        # Escolhe o de maior aptidão (vencedor)
        vencedor = max(candidatos, key=lambda i: fitnesses[i])
        nova_pop.append(pop[vencedor].copy())
    pop = nova_pop
    
    # Crossover de um ponto (prob 0.7)
    for i in range(0, pop_size-1, 2):
        if random.random() < 0.7:
            ponto = random.randint(1, bits-1)
            pop[i][ponto:], pop[i+1][ponto:] = pop[i+1][ponto:], pop[i][ponto:]
    
    # Mutação (prob 0.01 por bit)
    for i in range(pop_size):
        for j in range(bits):
            if random.random() < 0.01:
                pop[i][j] = 1 - pop[i][j]

# Resultado final
melhor_ind = max(pop, key=lambda ind: fitness(decode(ind)))
melhor_x = decode(melhor_ind)
print(f"Melhor x encontrado: {melhor_x} -> f(x) = {fitness(melhor_x)}")

# Gráficos
plt.figure(figsize=(12,4))
plt.subplot(1,2,1)
plt.plot(melhores, label='Melhor aptidão', color='green')
plt.plot(medias, label='Média da população', color='blue')
plt.xlabel('Geração')
plt.ylabel('Aptidão')
plt.title('Evolução da aptidão')
plt.legend()
plt.grid(True)

plt.subplot(1,2,2)
plt.bar(range(len(melhores)), melhores, alpha=0.6, color='orange')
plt.xlabel('Geração')
plt.ylabel('Melhor aptidão')
plt.title('Progresso do melhor indivíduo')
plt.grid(True)
plt.tight_layout()
plt.show()

import numpy as np

import matplotlib.pyplot as plt

import random

# Função objetivo (maximizar)

def fitness(x):

return x**2

# Decodifica binário para inteiro

def decode(bits):

return int(''.join(map(str, bits)), 2)

# Inicializa população aleatória (6 indivíduos, 5 bits)

pop_size = 6

bits = 5

pop = [[random.randint(0,1) for _ in range(bits)] for _ in range(pop_size)]

# Armazena melhores aptidões por geração

melhores = []

medias = []

for geracao in range(20):

# Avalia aptidão

fitnesses = [fitness(decode(ind)) for ind in pop]

melhores.append(max(fitnesses))

medias.append(np.mean(fitnesses))

# Nova população por torneio (tamanho 3)

nova_pop = []

for _ in range(pop_size):

# Seleciona 3 indivíduos aleatórios

candidatos = random.sample(range(pop_size), 3)

# Escolhe o de maior aptidão (vencedor)

vencedor = max(candidatos, key=lambda i: fitnesses[i])

nova_pop.append(pop[vencedor].copy())

pop = nova_pop

# Crossover de um ponto (prob 0.7)

for i in range(0, pop_size-1, 2):

if random.random() < 0.7:

ponto = random.randint(1, bits-1)

pop[i][ponto:], pop[i+1][ponto:] = pop[i+1][ponto:], pop[i][ponto:]

# Mutação (prob 0.01 por bit)

for i in range(pop_size):

for j in range(bits):

if random.random() < 0.01:

pop[i][j] = 1 - pop[i][j]

# Resultado final

melhor_ind = max(pop, key=lambda ind: fitness(decode(ind)))

melhor_x = decode(melhor_ind)

print(f"Melhor x encontrado: {melhor_x} -> f(x) = {fitness(melhor_x)}")

# Gráficos

plt.figure(figsize=(12,4))

plt.subplot(1,2,1)

plt.plot(melhores, label='Melhor aptidão', color='green')

plt.plot(medias, label='Média da população', color='blue')

plt.xlabel('Geração')

plt.ylabel('Aptidão')

plt.title('Evolução da aptidão')

plt.legend()

plt.grid(True)

plt.subplot(1,2,2)

plt.bar(range(len(melhores)), melhores, alpha=0.6, color='orange')

plt.xlabel('Geração')

plt.ylabel('Melhor aptidão')

plt.title('Progresso do melhor indivíduo')

plt.grid(True)

plt.tight_layout()

plt.show()

Análise dos resultados esperados

O código executa no Google Colab sem modificações. A aptidão máxima teórica é 961 (para x=31). Com 20 gerações, frequentemente atingimos x=31. O gráfico da esquerda mostra a evolução das médias. Ele também exibe o melhor valor por geração. O gráfico da direita destaca o progresso do máximo. É comum ver saltos repentinos na curva. Esses saltos vêm do crossover e da mutação. A seleção por torneio mantém pressão constante. Portanto, a convergência é rápida e estável. Esse exemplo ensina na prática os conceitos. Ele é reproduzível e fácil de modificar. Tente alterar o tamanho do torneio, por exemplo. Observe como isso afeta a velocidade de convergência. A experimentação é a melhor forma de aprender.

Conclusão sobre seleção em algoritmos evolutivos

A seleção é o motor da evolução artificial. Roleta e torneio são duas estratégias complementares. A roleta é probabilística e baseada em proporções. O torneio é competitivo e baseado em comparações. Ambas têm vantagens e desvantagens conhecidas. A escolha depende do problema e da experiência. Para iniciantes, o torneio é geralmente recomendado. Ele é mais simples de ajustar e entender. Os gráficos mostram claramente o efeito da seleção. Eles revelam como a população melhora gradativamente. Por fim, lembre-se: sem seleção, não há evolução. Ela direciona a busca para regiões promissoras. Portanto, domine esse conceito para avançar. A prática com o código solidifica o aprendizado. Bons estudos e boas evoluções!

Cruzamento (Crossover)

O que é cruzamento?

Tipos comuns de cruzamento

Importância para a otimização

Exemplo clássico: o problema do caixeiro viajante

Resolução em python para o google colab

Seleção (Roleta, Torneio)

O que é seleção em algoritmos evolutivos?

Roleta: probabilidade proporcional à aptidão

Torneio: competição direta entre indivíduos

Comparação entre roleta e torneio

Exemplo clássico: maximização de uma função

Análise dos resultados esperados

Conclusão sobre seleção em algoritmos evolutivos