Este projeto implementa um Algoritmo Genético para otimização da função matemática f6 de Schaffer, uma função de benchmark amplamente utilizada em otimização global. O código foi modernizado e refatorado com nomes mais descritivos em português, mantendo a funcionalidade original descrita no livro "Algoritmos Genéticos" de Ricardo Linden.
- O que é este projeto
- A Função f6
- Como funciona o Algoritmo Genético
- Estrutura do Projeto
- Como executar
- Parâmetros configuráveis
- Exemplo de execução
Este projeto implementa um algoritmo genético para encontrar o máximo global da função de Schaffer f6. É um exemplo clássico de como técnicas de computação evolutiva podem ser aplicadas para resolver problemas de otimização complexos.
- ✅ Otimização global: Encontra o máximo da função f6 no domínio [-100, 100] x [-100, 100]
- ✅ Representação binária: Cromossomos codificados como strings binárias de 44 bits
- ✅ Operadores genéticos: Seleção por roleta, crossover de um ponto, mutação bit-a-bit
- ✅ Código modernizado: Utiliza boas práticas atuais do Java
- ✅ Nomes descritivos: Classes renomeadas para português (Individuo, AlgoritmoGenetico, etc.)
A função f6 de Schaffer é uma função de benchmark clássica em otimização global, definida como:
f6(x,y) = 0.5 - (sin²(√(x² + y²)) - 0.5) / (1 + 0.001(x² + y²))²
- Domínio: x, y ∈ [-100, 100]
- Máximo global: f6(0,0) = 1.0
- Tipo: Função multimodal com muitos máximos locais
- Dificuldade: Alta (muitas armadilhas para algoritmos de busca local)
- Nome: Também conhecida como "Schaffer's f6 function"
A função f6 possui múltiplos máximos locais que podem "enganar" algoritmos de otimização simples. O algoritmo genético, por trabalhar com uma população de soluções, consegue explorar diferentes regiões do espaço de busca simultaneamente.
- Cada solução (x,y) é codificada como uma string binária de 44 bits
- Primeiros 22 bits = coordenada x
- Últimos 22 bits = coordenada y
- Conversão: binário → decimal → intervalo [-100, 100]
- Gera uma população de soluções aleatórias
- Cada cromossomo é uma string binária aleatória
- Cada cromossomo é decodificado para (x,y)
- Calcula-se f6(x,y) como fitness
- Quanto maior o valor, melhor a solução
- Seleção por Roleta: Probabilidade proporcional ao fitness
- Soluções melhores têm maior chance de reprodução
- Crossover de um ponto: Combina dois pais em um filho
- Mutação: Inverte bits com pequena probabilidade
- Processo se repete por várias gerações
- População evolui em direção a soluções melhores
dhc-GA/
├── src/
│ ├── App.java # Aplicação principal
│ ├── Individuo.java # Classe base para cromossomos
│ ├── IndividuoF6.java # Cromossomo específico para f6
│ ├── AlgoritmoGenetico.java # Algoritmo genético base
│ └── AlgoritmoGeneticoF6.java # AG específico para f6
├── bin/ # Arquivos compilados
├── lib/ # Dependências (vazio)
├── README.md # Esta documentação
└── MODERNIZACAO.md # Detalhes das modernizações
App.java: Ponto de entrada, configura e executa o algoritmoIndividuo.java: Classe base que define um cromossomo genéricoIndividuoF6.java: Especialização para a função f6 de SchafferAlgoritmoGenetico.java: Implementação geral do algoritmo genéticoAlgoritmoGeneticoF6.java: AG especializado que usa IndividuoF6
- Java 8 ou superior
- JDK instalado e configurado
cd dhc-GA
javac -d bin src/*.javajava -cp bin AppNo arquivo App.java, você pode ajustar:
int numeroGeracoes = 100; // Número de gerações
int tamanhoPopulacao = 50; // Tamanho da população
double probabilidadeMutacao = 0.01; // Taxa de mutação (1%)- Gerações: 50-200 (mais gerações = busca mais refinada)
- População: 30-100 (maior população = mais diversidade)
- Mutação: 0.001-0.01 (muito alta pode destruir boas soluções)
=== Algoritmo Genético - Otimização da Função f6(x,y) ===
📋 Parâmetros configurados:
• Número de gerações: 100
• Tamanho da população: 50
• Probabilidade de mutação: 0.01
🚀 Iniciando evolução...
🧬 Inicializando população...
✓ População inicial criada com 50 indivíduos
📊 Geração 1/100
─────────────────────
Avaliando população ✓ | Soma fitness: 52,61
Processando crossover e mutação..... ✓
📊 Geração 2/100
─────────────────────
Avaliando população ✓ | Soma fitness: 55,43
Processando crossover e mutação..... ✓
...
📊 Geração 100/100
─────────────────────
Avaliando população ✓ | Soma fitness: 89,45
Processando crossover e mutação..... ✓
🏆 MELHOR SOLUÇÃO ENCONTRADA:
Índice: 23 | Fitness: 1.935874
┌─────────────────────────────────────────────────┐
│ SOLUÇÃO FINAL │
├─────────────────────────────────────────────────┤
│ Coordenadas: x = -2,4573, y = 1,8946 │
│ Fitness f6(x,y) = 1,935874 │
│ Cromossomo: 01111010010001000100000111111001111111100110 │
│ │
│ 💡 Máximo teórico: f6(0,0) = 1.000000 │
│ 📊 Distância do ótimo: -0,935874 │
└─────────────────────────────────────────────────┘
🎯 Execução concluída com sucesso!
- Coordenadas: Valores reais de x e y decodificados do cromossomo
- Fitness f6(x,y): Valor da função f6 para essa solução (quanto mais próximo de 1.0, melhor)
- Cromossomo: Representação binária da solução (44 bits: 22 para x + 22 para y)
- Distância do ótimo: Diferença entre o resultado e o máximo teórico
Este projeto é excelente para aprender sobre:
- Algoritmos Genéticos: Conceitos fundamentais de computação evolutiva
- Otimização Global: Como encontrar soluções em espaços complexos
- Codificação Binária: Representação de números reais em binário
- Operadores Genéticos: Seleção, crossover e mutação
- Funções de Benchmark: Uso de funções padrão para teste de algoritmos
- Implementar outros tipos de seleção (torneio, ranking)
- Adicionar crossover de dois pontos ou uniforme
- Implementar estratégias de diversidade
- Adicionar critérios de parada adaptativos
- Visualização gráfica da evolução
Referência: Baseado no livro "Algoritmos Genéticos" de Ricardo Linden