🔍 Metaheuristic Search & Optimization

---

📋 Descrição

Este repositório implementa e compara algoritmos de busca meta-heurística aplicados a problemas de otimização contínua e discreta, desenvolvidos com NumPy, Matplotlib e Seaborn, sem uso de frameworks de otimização de alto nível.

Parte	Problema	Algoritmo(s)
1	Otimização Contínua — 6 funções objetivo 2D	Hill Climbing · LRS · GRS
2.1	8 Rainhas — combinatória discreta	Têmpera Simulada (SA)
2.2	Caixeiro Viajante 3D — roteamento de drone	Algoritmo Genético (GA)
2.3	Rastrigin 50D — comparação em alta dimensão	GA não canônico vs. LRS

---

📁 Estrutura do Repositório

metaheuristic-search-optimization/
│
├── 1_OTIMIZACAO_CONTINUA.py      # Hill Climbing, LRS e GRS nas 6 funções objetivo
├── 2_DOMINIO_DISCRETO.py         # Têmpera Simulada, GA caixeiro, GA não canônico
│
├── data/
│   └── CaixeiroGruposGA.csv      # Pontos 3D distribuídos em 4 regiões + origem
│
└── report/
    └── relatorio.pdf             # PDF

---

⚙️ Requisitos

pip install numpy matplotlib seaborn

Versões utilizadas: Python 3.8+ · NumPy · Matplotlib · Seaborn

---

📈 Parte 1 — Otimização Contínua (1_OTIMIZACAO_CONTINUA.py)

Objetivo

Encontrar mínimos ou máximos de seis funções objetivo bidimensionais com características distintas — unimodais, multimodais, com múltiplos ótimos locais e regiões de platô — comparando três estratégias de busca em R = 100 rodadas independentes com seed = 42.

Algoritmos

Algoritmo	Ponto inicial	Geração de candidato	Hiperparâmetro
Hill Climbing (HC)	Limite inferior do domínio	Perturbação uniforme em$[-\varepsilon, \varepsilon]$	ε
Local Random Search (LRS)	Uniforme no domínio	Ruído gaussiano$\mathcal{N}(0, \sigma)$ somado a $x_{best}$	σ
Global Random Search (GRS)	Uniforme no domínio	Nova amostra uniforme independente a cada iteração	—

Critério de parada (todos): máximo de 1000 iterações ou 100 iterações consecutivas sem melhoria em $x_{best}$.

Funções Objetivo

#	Expressão	Domínio	Tipo	Ótimo conhecido
f1	$x_1^2 + x_2^2$	$[-100,,100]^2$	mín	$0$ em $(0,0)$
f2	$e^{-(x_1^2+x_2^2)} + 2e^{-(x_1-1.7)^2-(x_2-1.7)^2}$	$[-2,4]\times[-2,5]$	máx	$\approx 2.0$ em $(1.7,,1.7)$
f3	Ackley	$[-8,,8]^2$	mín	$0$ em $(0,0)$
f4	Rastrigin 2D	$[-5.12,,5.12]^2$	mín	$0$ em $(0,0)$
f5	$\frac{x_1\cos(x_1)}{20} + 2e^{-x_1^2-(x_2-1)^2} + 0.01,x_1 x_2$	$[-10,,10]^2$	máx	$\approx 2.0$ em $(0,1)$
f6	$x_1\sin(4\pi x_1) - x_2\sin(4\pi x_2+\pi) + 1$	$[-1,,3]^2$	máx	múltiplos máx. locais

Hiperparâmetros Utilizados

Problema	ε (HC)	σ (LRS)
f1	0.80	0.50
f2	0.05	0.20
f3 (Ackley)	0.99	0.70
f4 (Rastrigin)	0.99	0.80
f5	0.10	0.50
f6	0.02	0.10

Resultados — Moda de $f(x^*)$ (100 rodadas)

Problema	Tipo	Hill Climbing	LRS	GRS
f1	mín	0.0006	0.0004	59.5697
f2	máx	1.0064	2.0026	1.9946
f3 (Ackley)	mín	15.9621	0.2880	2.0298
f4 (Rastrigin)	mín	27.5147	5.1522	3.1319
f5	máx	1.4369	0.5298	1.3568
f6	máx	1.0000	2.2516	5.0674

Conclusão: O LRS apresentou melhor equilíbrio em funções unimodais (f1, f3). O GRS destacou-se em funções fortemente multimodais (f4, f6). O HC mostrou-se sensível ao ponto de partida fixo, ficando preso em ótimos locais em 4 dos 6 problemas.

---

🎯 Parte 2 — Domínio Discreto (2_DOMINIO_DISCRETO.py)

2.1 — 8 Rainhas (Têmpera Simulada)

Posicionar 8 rainhas em um tabuleiro 8×8 sem que nenhuma ataque outra.

• Representação: vetor $x \in {1,\ldots,8}^8$ — índice = coluna, valor = linha
• Função objetivo: $f(x) = 28 - h(x)$, onde $h(x)$ é o número de pares atacantes · maximização
• Perturbação: troca a linha de uma única coluna aleatória (busca local controlada)
• Parâmetros: $T_0 = 50$ · $\alpha = 0.995$ (decaimento geométrico) · máx. 5000 iterações
• Parada antecipada: quando $f(x) = 28$ (zero ataques)

Resultado em execução única: $x = [4, 1, 5, 8, 2, 7, 3, 6]$

Métrica	Valor
Execuções para encontrar as 92 soluções distintas	650
Custo médio por solução nova	~7,1 execuções

2.2 — Caixeiro Viajante 3D (Algoritmo Genético)

Drone percorrendo 160 pontos tridimensionais (40 por região + origem), minimizando a distância euclidiana total da rota.

Parâmetro	Valor
Pontos por região	40 (total: 161 com origem)
Tamanho da população	N = 80
Máx. gerações	300
Seleção	Torneio (k = 3)
Recombinação	Order Crossover — OX (sem repetição de cidades)
Mutação	Swap entre dois genes (pm = 1%)
Elitismo	Ne = 5 melhores preservados por geração
Parada antecipada	15 gerações consecutivas sem variação > ε = 1.0

Métrica (10 rodadas)	Valor
Moda de gerações até convergência	78
Distância média	7169,77
Desvio padrão	462,33

2.3 — Rastrigin 50D: GA não canônico vs. LRS

$$ f(\mathbf{x}) = 10n + \sum_{i=1}^{n}\left(x_i^2 - 10\cos(\pi x_i)\right), \quad n = 50, \quad x_i \in [-5.12,;5.12] $$

GA não canônico: codificação real · torneio (k=3) · SBX (η=1) · mutação gaussiana (σ=0.1, pm=10%) · elitismo Ne=5 · 300 gerações

Efeito do tamanho de população (5 rodadas cada):

N	Média f(x)	Desvio padrão
30	264.01	29.55
60	230.70	22.11
100	187.45	10.84

Comparação GA (N=100) vs. LRS — 10 rodadas:

Método	Melhor	Média	Desvio padrão
GA não canônico	174.53	207.34	32.98
LRS	421.07	538.18	68.25

Conclusão: O GA não canônico superou o LRS em todas as métricas — o melhor valor encontrado é ~2,4× menor e a média ~2,6× menor. Em 50 dimensões, a manutenção de uma população com SBX e mutação gaussiana permite explorar simultaneamente múltiplas regiões do espaço, enquanto o LRS fica preso em mínimos locais da paisagem altamente multimodal da Rastrigin.

---

📊 Como Executar

Parte 1 — Otimização Contínua

python 1_OTIMIZACAO_CONTINUA.py

Saídas geradas:

• Histogramas de distribuição de $f(x^*)$ para cada função e algoritmo (100 rodadas)
• Linhas de moda e melhor valor em cada histograma
• Tabela de modas impressa no terminal

Parte 2 — Domínio Discreto

Antes de executar, ajuste o caminho do CSV na primeira linha de 2_DOMINIO_DISCRETO.py:

CAMINHO_CSV = "data/CaixeiroGruposGA.csv"

python 2_DOMINIO_DISCRETO.py

Saídas geradas:

• Solução das 8 rainhas e contagem de execuções para as 92 soluções distintas
• Melhor distância e geração de parada do caixeiro viajante
• Tabela comparativa GA não canônico vs. LRS na Rastrigin 50D

Atenção: todos os experimentos utilizam seed = 42 para garantir reprodutibilidade.

---

📐 Fundamentos Matemáticos

Hill Climbing — atualização

$$ x_{best} \leftarrow y \quad \text{se } f(y) \text{ melhor que } f(x_{best}), \quad y = x_{best} + \mathcal{U}(-\varepsilon,,\varepsilon) $$

Local Random Search — perturbação gaussiana

$$ y = x_{best} + \mathcal{N}(0,,\sigma), \quad x_{best} \leftarrow y \quad \text{se melhor} $$

Têmpera Simulada — critério de aceitação

$$ P(\text{aceitar}) = \begin{cases} 1 & \text{se } \Delta f \geq 0 \ e^{,\Delta f / T} & \text{se } \Delta f < 0 \end{cases}, \qquad \Delta f = f(x_{cand}) - f(x_{atual}) $$

Decaimento geométrico de temperatura

$$ T \leftarrow \alpha \cdot T, \quad \alpha = 0.995, \quad T_0 = 50 $$

Função objetivo — 8 rainhas

$$ f(x) = 28 - h(x), \quad h(x) = \text{número de pares de rainhas atacantes} $$

Fitness — Caixeiro Viajante

$$ \Psi(x) = d(origin, x_1) + \sum_{i=1}^{k-1} d(x_i, x_{i+1}) + d(x_k, origin) $$

SBX — Simulated Binary Crossover

$$ c_1 = \frac{1}{2}\left[(1+\beta),p_1 + (1-\beta),p_2\right], \quad \beta = \begin{cases}(2u)^{\frac{1}{\eta+1}} & u \leq 0.5 \ \left(\frac{1}{2(1-u)}\right)^{\frac{1}{\eta+1}} & u > 0.5\end{cases} $$

Rastrigin generalizada (50D)

$$ f(\mathbf{x}) = 10n + \sum_{i=1}^{n}\left(x_i^2 - 10\cos(\pi x_i)\right), \quad x_i \in [-5.12,;5.12] $$

---

🔬 Observações Técnicas

• Todos os algoritmos foram implementados manualmente com NumPy — sem uso de bibliotecas de otimização prontas.
• O critério de parada por estagnação (100 iterações sem melhoria na Parte 1, 15 gerações na Parte 2) evita desperdício computacional e garante convergência prática.
• O HC parte sempre do limite inferior do domínio, o que o torna sensível ao ponto de partida em funções multimodais.
• O operador OX garante que cada filho seja uma permutação válida das cidades, essencial no TSP.
• O elitismo com Ne = 5 é fundamental no GA do caixeiro: sem ele, o critério de estagnação perderia a referência de melhoria ao longo das gerações.
• A Rastrigin da Parte 2.3 usa $\cos(\pi x_i)$, conforme o enunciado — diferente da f4 2D que usa $\cos(2\pi x_i)$ (formulação clássica padrão).

---

📄 Relatório

O arquivo report/relatorio.pdf contém o relatório completo no formato de artigo científico (template IEEE), incluindo:

• Resumo — síntese dos métodos e principais resultados
• Metodologia — decisões de hiperparâmetros e critérios de parada
• Resultados — tabelas de modas, histogramas e análise comparativa
• Conclusões — análise crítica do desempenho de cada algoritmo por tipo de problema

---

📚 Referência

RUSSELL, Stuart J.; NORVIG, Peter. Artificial intelligence: a modern approach. London, 2010.