Please enable JavaScript.
Coggle requires JavaScript to display documents.
Busca com otimização - Coggle Diagram
Busca com otimização
-
Algoritmo de busca
Algoritmos de otimização são métodos matemáticos e computacionais utilizados para encontrar a melhor solução para um problema específico, minimizando ou maximizando uma função objetivo
-
-
Algoritmo de busca
Hill-Climbing
-
Funcionamento
- Inicialização: Escolhe uma solução inicial aleatória ou heurística;
2 .Avaliação: Calcula o valor da função objetivo(fitness) para a solução atual;
3.Geração de vizinhos: Gera soluções vizinhas ( pequenas modificações na solução);
4.Seleção do Melhor Vizinho:
- Se algum vizinho for melhor que o atual, move-se para ele.
- Se nenhum vizinho for melhor, o algoritmo para (ótimo local)
5.Repete até encontrar um ótimo ou atingir um limite de iterações.
Busca iterativamente uma solução melhor na vizinhança da solução atual, sempre subindo em direção a um valor maior ( ou descendo, se for minimização)
Pseudocódigo
def hill_climbing(problema, max_iteracoes):
solucao_atual = gerar_solucaoinicial()
for in range(max_iteracoes):
vizinhos = gerar_vizinhos(solucao_atual)
melhor_vizinho = max((vizinhos, key=lambda x: problema.fitnrss(x))
if (problema.fitness(melhor_vizinho) <= problema.fitness(solucao_atual):
break
solucao_atual = melhor_vizinho
return solucao_atual
Problemas e soluções:
Ótimos locais: Pode ficar preso em uma solução que é boa apenas localmente
Solução: Usa Hill-Clibing com reinício aleatório (reinicia a busca de outro ponto)
Platôs (regiões planas): quando vários vizinhos têm um mesmo valor
Solução: Movimento aleatório ou aumentar o passo de busca.
Variações:
- Hill_Climbing Simples: Aceita apenas melhorias
- Hill-Climbing com Reinício Aleatório: reinicia a busca a partir de diferentes pontos para escapar de ótimos locais
-
Desvantagens: * Não lida bem com platôs (regiões planas) ou ótimos locais; Depende fortemente do ponto inicial.
Otimização: processo que usa métodos computacionais para para encontrar a melhor forma de projetar ou operar um dado sistema, representada pela melhor combinação de valores para para as variáveis do problema (solução ótima), considerando seus objetivos e suas restrições