# Otimização e evolução

Pesquisa local, subida da colina presa num ótimo local, arrefecimento simulado e algoritmos evolutivos.

Página: https://resumos.rgo.pt/cadeiras/ia/otimizacao-e-evolucao/

Nem todos os problemas pedem um caminho. Muitas vezes pedem um bom estado final, e o caminho até lá é irrelevante: é o caso de horários, escalas e das 4 rainhas desta página. A **pesquisa local** anda de vizinho em vizinho a melhorar uma função de avaliação, sem guardar a história. É barata e cega ao passado, o que lhe dá velocidade e lhe cria a armadilha central do tema: os ótimos locais.

## O exemplo das 4 rainhas

Tabuleiro 4 por 4 com uma rainha por coluna, representado pelo vetor das linhas, como \[1, 4, 2, 3\] (coluna 1 na linha 1, coluna 2 na linha 4, e por aí fora). A função de avaliação conta **pares de rainhas que se atacam** (mesma linha ou mesma diagonal): 0 é solução, e queremos minimizar. Vizinhos são os estados que mudam a linha de exatamente uma coluna, 12 vizinhos por estado.

Confirma a conta no estado inicial \[1, 4, 2, 1\]: os pares são (1,1)-(2,4), (1,1)-(3,2), (1,1)-(4,1), (2,4)-(3,2), (2,4)-(4,1) e (3,2)-(4,1). Atacam-se (1,1)-(4,1) pela linha e (3,2)-(4,1) pela diagonal. Total: 2 ataques.

## Subida da colina e o ótimo local

A **subida da colina** (hill climbing) repete: avalia os 12 vizinhos e move-se para o melhor; se nenhum for melhor, para. Passo 1 a partir de \[1, 4, 2, 1\]: um dos melhores vizinhos é \[1, 4, 2, 3\], com 1 ataque (só o par (3,2)-(4,3) se ataca na diagonal; confirma os outros cinco pares). Desce de 2 para 1 e move-se.

Passo 2 a partir de \[1, 4, 2, 3\]: os 12 vizinhos valem 1, 2, 3 ou 4. Os vizinhos que mudam a coluna 1 valem 2, 3 e 3; os da coluna 2 valem 4, 3 e 3; os da coluna 3 valem 3, 2 e 1; os da coluna 4 valem 2, 2 e 2. Nenhum é melhor que 1. A subida para aqui: estado com 1 ataque onde tudo à volta empata ou é pior. É um **ótimo local**, e a subida da colina, que só aceita melhorias estritas, nunca mais sai dele. Repara que \[3, 1, 4, 2\] tem 0 ataques (verifica os seis pares: nenhuma linha repetida, nenhuma diagonal com diferença igual), por isso o ótimo global existe e está longe.

![Paisagem de aptidão com o número de ataques por estado: um vale com 1 ataque que é ótimo local e um vale com 0 ataques que é o ótimo global, separados por uma subida.](https://resumos.rgo.pt/cadeiras/ia/otimizacao-e-evolucao/figura-1.svg)

A subida executável abaixo repete a regra estrita, avalia os 12 vizinhos e só se move para valor menor:

```python
import itertools

def ataques(e):
    n = 0
    for (c1, l1), (c2, l2) in itertools.combinations(enumerate(e), 2):
        if l1 == l2 or abs(l1 - l2) == abs(c1 - c2):
            n += 1
    return n

def vizinhos(e):
    for c in range(4):
        for l in (1, 2, 3, 4):
            if l != e[c]:
                v = list(e)
                v[c] = l
                yield tuple(v)

estado = (1, 4, 2, 1)
while True:
    print(estado, ataques(estado))
    melhor = min(vizinhos(estado), key=ataques)
    if ataques(melhor) >= ataques(estado):
        print("preso: nenhum vizinho melhora")
        break
    estado = melhor
```

Isto escreve `(1, 4, 2, 1) 2`, depois `(1, 4, 2, 3) 1`, e para com `preso`: de \[1, 4, 2, 1\] o único vizinho com 1 ataque é \[1, 4, 2, 3\], e de lá nenhum vizinho desce a 0.

## Sair da armadilha

Há três saídas clássicas. O **arrefecimento simulado** aceita por vezes um vizinho pior, com probabilidade que diminui ao longo do tempo (a “temperatura”). No início salta muito e explora; no fim comporta-se como a subida e refina. Aceitar piorar temporariamente é o que permite atravessar o vale entre o ótimo local e o global.

O **reinício aleatório** sorteia um estado novo quando prende e recomeça a subida. É simples e surpreendentemente eficaz quando os ótimos locais são muitos mas baratos de escalar.

Os **algoritmos evolutivos** mantêm uma população de estados e aplicam **seleção** (os melhores reproduzem-se), **cruzamento** (filhos combinam partes de dois pais) e **mutação** (troca aleatória de um gene). Uma mutação no estado preso, por exemplo trocar a coluna 1 de 1 para 3, produz \[3, 4, 2, 3\] com 3 ataques: pior no imediato, mas noutra região do espaço, onde a subida seguinte pode encontrar outro caminho. A mutação não promete melhorar; promete diversidade, que é o que falta a uma população presa.

O arrefecimento simulado aceita vizinhos piores com probabilidade que cai com a temperatura. Na paisagem acima, é o que permite descer do vale de 1 ataque, atravessar a subida e chegar ao vale de 0.

O reinício aleatório sorteia um estado novo quando prende e recomeça a subida. Resulta bem quando os vales são muitos mas cada subida é barata: cada tentativa custa pouco e uma delas cai perto do ótimo global.

A evolução mantém vários estados em paralelo e mistura-os por cruzamento e mutação. A diversidade da população faz o papel dos saltos aleatórios: há sempre alguém noutra região da paisagem.

[Vídeo: Genetic Algorithms Explained By Example](https://www.youtube.com/watch?v=uQj5UNhCPuo)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=uQj5UNhCPuo)

Como cai em teste

Pedem-te para executar dois ou três passos de subida da colina com a função dada, ou para explicar porque prendeu e que técnica o solta. Conta sempre todos os pares (para 4 rainhas são 6) e escreve os valores dos vizinhos antes de escolher. A justificação do ótimo local é uma frase com números: “vale 1 e nenhum dos 12 vizinhos é melhor”.

## O limite teórico

Estes métodos aproximados existem porque os problemas exatos são difíceis: muitas otimizações combinatórias são NP-difíceis, e a exaustão não escala, como recorda a página de [complexidade](https://resumos.rgo.pt/cadeiras/tc/complexidade/). A pesquisa local troca a garantia de otimalidade por velocidade e boas soluções na prática, e a escolha entre subida, arrefecimento e evolução depende do formato dos ótimos locais do teu problema.