Algoritmos Genéticos

9.1 Introdução aos algoritmos genéticos.

Algoritmos Genéticos (GA) são um método de otimização e busca inspirado pelo processo de seleção natural, que imita processos biológicos evolutivos.

Algoritmos genéticos são aplicados para resolver problemas complexos, onde métodos tradicionais podem não ser eficazes. Esses algoritmos utilizam mecanismos de seleção, cruzamento (crossover) e mutações para evoluir soluções.

Princípios de funcionamento:

1. Inicialização:

É criada uma população inicial de soluções possíveis (cromossomos). Cada solução é codificada como uma string (string binária, string de caracteres ou outras estruturas).

2 Função de aptidão (fitness function):

Avalia a qualidade de cada solução na população.

3. Avaliação:

Cada solução (indivíduo) é avaliada usando a função de aptidão (fitness function), que determina quão bem a solução resolve o problema.

4. Seleção:

Soluções com melhor aptidão têm mais chances de serem escolhidas para reprodução. São frequentemente utilizados métodos como seleção por roleta (roulette wheel selection), seleção por torneio (tournament selection) e seleção por ranking (rank selection).

5. Cruzamento (crossover):

Soluções escolhidas (pais) são combinadas para criar novas soluções (descendentes). O crossover pode ser de ponto único, de dois pontos ou multiponto.

6. Mutação:

Alterações aleatórias nas novas soluções (mutações) são aplicadas para introduzir variedade. Isso ajuda o algoritmo a evitar mínimos locais.

7. Substituição:

A nova população substitui a antiga, e o processo se repete até que uma condição de parada seja atingida (por exemplo, atingir um número definido de gerações ou alcançar uma aptidão específica).

Vantagens e desvantagens

Vantagens:

• Ampla gama de aplicações: Podem ser aplicados para resolver várias problemas, incluindo aqueles onde métodos analíticos não funcionam.
• Otimização global: Capazes de encontrar ótimos globais em espaços multidimensionais e complexos.
• Flexibilidade: Podem ser usados com qualquer função de aptidão.

Desvantagens:

• Altos custos computacionais: Requerem recursos computacionais significativos, especialmente para populações grandes e problemas complexos.
• Dificuldades na configuração de parâmetros: Escolher os parâmetros (tamanho da população, probabilidade de mutação e crossover) pode ser complicado e ter um grande impacto no desempenho.
• Ausência de garantia de solução ótima: Não há garantia de que a solução encontrada será globalmente ótima.

Na verdade, o algoritmo genético é uma heurística altamente eficaz. Ele não garante que encontrará a melhor solução, mesmo que tenha acesso a todos os dados. Mas para situações complexas e volumes enormes de dados, ele fornece rapidamente uma solução próxima do ideal.

9.2 Exemplo de aplicação

Vamos considerar um exemplo de aplicação de algoritmo genético para otimizar uma função.

import random

# Parâmetros do algoritmo genético
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# Definição da função de aptidão
def fitness_function(x):
    return -x**2 + 10*x
            
# Inicialização da população
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# Seleção (torneio)
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# Cruzamento (um ponto)
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# Mutação
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# Ciclo principal do algoritmo genético
population = initialize_population(POPULATION_SIZE)
            
for generation in range(GENERATIONS):
    new_population = []
    for _ in range(POPULATION_SIZE):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        offspring = crossover(parent1, parent2)
        offspring = mutate(offspring)
        new_population.append(offspring)
    population = new_population
            
# Saída da melhor solução
best_individual = max(population, key=fitness_function)
print("Melhor solução:", best_individual)
print("Valor da função:", fitness_function(best_individual))
            
        

Vantagens e desvantagens

9.3 Otimização de função multidimensional

Problema:

Encontrar o valor mínimo de uma função multidimensional.

Solução:

Vamos usar o modelo anterior

import numpy as np

def fitness_function(x):
    return np.sum(x ** 2)
            
def create_individual(dim):
    return np.random.uniform(-10, 10, dim)
            
def create_population(pop_size, dim):
return np.array([create_individual(dim) for _ in range(pop_size)])
            
def select_individuals(population, fitness, num_parents):
    parents = np.empty((num_parents, population.shape[1]))
    for parent_num in range(num_parents):
        min_fitness_idx = np.where(fitness == np.min(fitness))
        min_fitness_idx = min_fitness_idx[0][0]
        parents[parent_num, :] = population[min_fitness_idx, :]
        fitness[min_fitness_idx] = float('inf')
    return parents
            
def crossover(parents, offspring_size):
    offspring = np.empty(offspring_size)
    crossover_point = np.uint8(offspring_size[1] / 2)
    for k in range(offspring_size[0]):
        parent1_idx = k % parents.shape[0]
        parent2_idx = (k + 1) % parents.shape[0]
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring
            
def mutate(offspring, mutation_rate):
    for idx in range(offspring.shape[0]):
        if np.random.rand() < mutation_rate:
            random_value = np.random.uniform(-1.0, 1.0, 1)
            offspring[idx, 4] = offspring[idx, 4] + random_value
    return offspring
            
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
    population = create_population(pop_size, dim)
    for generation in range(num_generations):
        fitness = np.array([fitness_function(ind) for ind in population])
        parents = select_individuals(population, fitness, num_parents)
        offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
        offspring_mutation = mutate(offspring_crossover, mutation_rate)
        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]:, :] = offspring_mutation
    best_solution = population[np.argmin(fitness)]
    return best_solution
# Exemplo de uso:
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"Melhor solução: {best_solution}")