Aprenda Seleção, Cruzamento e Mutação

Estratégias de Seleção

A seleção é um processo crucial em algoritmos genéticos, determinando quais indivíduos contribuem para a próxima geração, equilibrando aptidão e diversidade. Existem várias estratégias de seleção amplamente utilizadas:

Seleção por Roleta: Atribui uma probabilidade de seleção a cada indivíduo proporcional à sua aptidão. Imagine uma roleta onde o tamanho de cada fatia corresponde à aptidão; indivíduos com maior aptidão têm maior chance de serem selecionados;
Seleção por Torneio: Seleciona aleatoriamente um grupo (torneio) de indivíduos e escolhe o melhor entre eles como pai. Este método é simples e eficaz, e o tamanho do torneio pode controlar a pressão de seleção;
Seleção por Ordenação: Ordena os indivíduos pela aptidão e atribui probabilidades de seleção com base em sua posição, em vez da aptidão absoluta. Isso ajuda a evitar a dominação por poucos indivíduos de alta aptidão, especialmente em problemas com grandes diferenças de aptidão.


              1234567891011121314151617
            
import random

def tournament_selection(population, fitnesses, tournament_size=3):
    """
    Selects one individual from the population using tournament selection.
    """
    # Randomly pick tournament_size individuals
    selected_indices = random.sample(range(len(population)), tournament_size)
    # Find the one with the highest fitness
    best_index = max(selected_indices, key=lambda idx: fitnesses[idx])
    return population[best_index]

# Example usage
population = [[0,1,1,0], [1,0,0,1], [1,1,0,0], [0,0,1,1]]
fitnesses = [3, 2, 5, 4]
parent = tournament_selection(population, fitnesses, tournament_size=2)
print("Selected parent:", parent)

Operadores de Crossover

Após a seleção, algoritmos genéticos utilizam o crossover para criar novos indivíduos combinando informações de dois pais. O crossover introduz variação e permite que o algoritmo explore novas combinações de características dentro da população.

Tipos comuns de crossover:

Crossover de Ponto Único: Um ponto de crossover é escolhido aleatoriamente. A primeira parte de um dos pais é combinada com a parte restante do outro.
Crossover de Dois Pontos: Dois pontos são selecionados aleatoriamente. O segmento entre eles é trocado entre os pais para produzir descendentes.
Crossover Uniforme: Cada gene do descendente é escolhido aleatoriamente de um dos dois pais com probabilidade igual.


              12345678910111213141516171819
            
import random

def single_point_crossover(parent1, parent2):
    """
    Performs single-point crossover between two parents.
    """
    if len(parent1) != len(parent2):
        raise ValueError("Parents must be of the same length")
    point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

# Example usage
p1 = [1, 0, 1, 0, 1]
p2 = [0, 1, 0, 1, 0]
offspring1, offspring2 = single_point_crossover(p1, p2)
print("Offspring 1:", offspring1)
print("Offspring 2:", offspring2)

Papel da Mutação

Mutação é um dos principais mecanismos em algoritmos genéticos. Ela introduz novo material genético na população, ajudando o algoritmo a evitar estagnação e continuar explorando novas soluções. Sem a mutação, a população pode se tornar muito semelhante, fazendo com que a busca fique presa em ótimos locais.

Por que a Mutação é Importante

Previne convergência prematura: a mutação garante que a população não se torne muito uniforme, evitando convergência subótima;
Mantém a diversidade: ao introduzir alterações aleatórias, a mutação mantém uma ampla variedade de variações genéticas disponíveis para as próximas gerações;
Permite escapar de ótimos locais: pequenas mudanças aleatórias permitem que o algoritmo explore novas áreas do espaço de busca que podem levar a soluções melhores;
Equilibra o cruzamento: enquanto o cruzamento combina características existentes, a mutação injeta novas, garantindo que o algoritmo continue gerando possibilidades inéditas.

Juntas, essas propriedades tornam a mutação essencial para um processo de busca robusto e adaptativo.

Operadores de Mutação Comuns

Diferentes representações de problemas requerem técnicas de mutação distintas. Os dois operadores mais utilizados são:

Mutação bit-flip: para representações binárias — inverte um bit de 0 para 1 ou de 1 para 0, introduzindo mudanças pequenas e controladas;
Mutação por troca: para representações baseadas em permutação (por exemplo, problemas de ordenação) — troca dois elementos dentro de um indivíduo para gerar uma nova configuração.


              1234567891011121314151617181920
            
import random

def bit_flip_mutation(individual, mutation_rate=0.1):
    """
    Performs bit-flip mutation on a binary list.
    """
    mutated = []
    for gene in individual:
        if random.random() < mutation_rate:
            mutated.append(1 - gene)  # Flip bit
        else:
            mutated.append(gene)
    return mutated

# Example usage
original = [1, 0, 1, 1, 0]
mutated = bit_flip_mutation(original, mutation_rate=0.5)
print("Original:", original)
print("Mutated:", mutated)

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 2. Capítulo 2

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Suggested prompts:

Can you explain how tournament size affects selection pressure?

What are the advantages and disadvantages of each selection strategy?

How do I choose the right selection strategy for my problem?

Awesome!

Completion rate improved to 6.25

Deslize para mostrar o menu