Perguntas sobre GRASP

Prévia do material em texto

# Pergunta Resposta Correta Justificativa
1 O que significa a sigla GRASP na área de meta-heurísticas? Greedy Randomized Adaptive Search Procedure (Procedimento de Busca Adaptativa Gulosa Randomizada) A sigla define os principais elementos do método: guloso, randomizado e adaptativo.
2 O GRASP é um algoritmo iterativo composto por duas fases principais que se repetem. Quais são essas duas fases? Fase de Construção (Construction) e Fase de Busca Local (Local Search) O algoritmo primeiro cria uma solução inicial semi-gulosa e depois a aprimora.
3 Na Fase de Construção do GRASP, qual o papel da Lista Restrita de Candidatos (RCL)? Permitir que a escolha do próximo elemento seja semi-gulosa, selecionando aleatoriamente um candidato dentro de um limite de qualidade. A RCL equilibra a gulodice e a randomização.
4 Como o parâmetro α (alfa) influencia a formação da Lista Restrita de Candidatos (RCL)? Define o limite de qualidade para um candidato ser incluído na RCL, controlando o grau de aleatoriedade da construção. α=0 resulta em uma escolha puramente gulosa; α=1 resulta em uma escolha puramente aleatória (dentro da lista de viáveis).
5 O que acontece na Fase de Busca Local (Local Search) do GRASP? A solução inicial (encontrada na Construção) é refinada, explorando soluções na sua vizinhança até que um ótimo local seja atingido. Esta fase é responsável por refinar a solução encontrada na construção, transformando-a em um ótimo local.
6 Por que o GRASP é considerado uma meta-heurística adaptativa? Porque a lista de candidatos (RCL) é reconstruída em cada etapa da fase de Construção com base nas escolhas anteriores já feitas para a solução parcial. A lista de opções e seus custos se adaptam dinamicamente à medida que a solução é construída.
7 Em um problema de otimização, se o GRASP for executado apenas uma vez (apenas uma iteração), o que o resultado provavelmente representará? Um ótimo local encontrado a partir de uma solução inicial semi-gulosa. Uma iteração completa (Construção + Busca Local) resulta sempre em uma solução que é um ótimo local.
8 Qual é a principal vantagem do GRASP em relação a uma heurística que utiliza apenas o componente guloso na fase de construção? A capacidade de escapar de ótimos locais na fase de construção e explorar múltiplas regiões do espaço de busca. A randomização do GRASP, ao ser repetida em várias iterações, permite que ele explore diferentes partes do espaço de busca.
9 Se o parâmetro α do GRASP for fixado em α=0 (RCL=1) em todas as iterações, o que a fase de Construção do GRASP representa? Uma construção puramente gulosa (heurística gulosa). Quando α=0, apenas o melhor candidato disponível pode entrar na RCL, eliminando o componente aleatório.
10 Qual das seguintes estratégias é um critério de parada comum para o algoritmo GRASP? Quando um número pré-definido de iterações (ou repetições) é executado. Como cada iteração do GRASP é independente, o critério mais simples e comum é limitar o número de vezes que o ciclo Construção-Busca Local é repetido.