x = 2,37
Infinitos valores dentro do intervalo.
FUNDAMENTOS DE OTIMIZAÇÃO · SUBTÓPICO 05
Algumas soluções deslizam; outras precisam ser reorganizadas.
Na otimização contínua, pequenas variações produzem candidatos próximos. Na combinatória, cada solução é uma configuração discreta, como uma rota, seleção ou sequência.
A→C→B→D
x = [A,C,B,D]Configurações separadas e enumeráveis.
01 · GEOMETRIA DO ESPAÇO
O tipo das variáveis muda o formato da busca.
Espaço contínuo
Entre dois pontos existem infinitas soluções intermediárias. Distância e direção possuem interpretação geométrica direta.
x ∈ ℝⁿEspaço combinatório
As soluções são objetos como subconjuntos, grafos ou permutações. A proximidade depende de uma operação definida.
x ∈ Ω02 · COMO CRIAR UM VIZINHO
Cada espaço exige movimentos compatíveis com sua representação.
Perturbar um valor
2,30+ δ2,37
Somar um pequeno deslocamento preserva o tipo real da variável.
x′ = x + δInverter um bit
10101flip10111
Uma posição muda entre zero e um.
0 ↔ 1Trocar posições
A B C DswapA D C B
A operação mantém todos os elementos sem repetições.
swap(i,j)Adicionar ou remover
{A,C}+ B{A,B,C}
O vizinho modifica a composição da seleção.
S′ = S ∪ {b}03 · CRESCIMENTO DO ESPAÇO
A combinatória cresce muito antes de parecer grande.
Tamanho nBinário · 2ⁿPermutação · n!Leitura
532120enumerável
101.0243.628.800já exige cuidado
201.048.5762,43 × 10¹⁸busca exaustiva impraticável
501,13 × 10¹⁵3,04 × 10⁶⁴espaço astronômico
04 · LABORATÓRIO INTERATIVO
Alterne entre um valor real e uma rota.
Observe como representação, movimento e avaliação mudam com o domínio.
05 · ESCOLHA DA TÉCNICA
A representação vem antes do algoritmo.
Defina a solução
O vetor precisa conter todas as decisões necessárias e nenhuma informação redundante.
Preserve a validade
Os operadores devem produzir candidatos do mesmo tipo, preferencialmente viáveis.
Defina vizinhanças
Pequenas alterações devem gerar soluções relacionadas de forma útil.
Escolha o método
Gradientes favorecem espaços suaves; operadores combinatórios trabalham com estruturas.
06 · NO CÓDIGO
O operador respeita o tipo da solução.
function vizinho(x, passo) {
const delta = (Math.random() * 2 - 1) * passo;
return x + delta;
}function vizinho(rota, i, j) {
const nova = [...rota];
[nova[i], nova[j]] = [nova[j], nova[i]];
return nova;
}PRÓXIMO SUBTÓPICO
Métodos exatos, heurísticas e metaheurísticas.
Agora podemos comparar diferentes estratégias para percorrer esses espaços.
Continuar estudo →