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!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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() |