Avaliacao On-Line 4 (AOL 4) - Questionario - Modelagem e Otimizacao de Sistemas de Producao

Prévia do material em texto

Avaliação On-Line 4 (AOL 4) - Questionário
 Pergunta 1
 
 Leia o trecho de código a seguir, referente a um algoritmo genético feito para a resolução do
problema clássico das n-rainhas, através do software MATLAB:
num_total_conflitos = n*(n-1)/2;
conflitos_pop = zeros(N,1); apt = zeros(N,1);
for k = 1:N
n_conflitos = 0;
for i = 1:n % linhas do tabuleiro
for j = 1:n % colunas do tabuleiro
if abs(i-j) == abs(pop(k,i)-pop(k,j)) && i ~= j
n_conflitos = n_conflitos + 1;
end
end
end
n_conflitos = n_conflitos/2;
conflitos_pop(k,1) = n_conflitos;
apt(k,1) = 1 - (n_conflitos/num_total_conflitos);
end
Considerando o código apresentado e o conteúdo estudado sobre o desenvolvimento da
estrutura básica de um algoritmo genético, pode-se afirmar que o código representa:
 o cálculo do número mínimo de conflitos para a configuração atual, para afirmar se é ou não
uma solução viável para o problema.
 o cálculo do número de conflitos com base no valor obtido para as duas soluções
imediatamente anteriores, para avaliar se a solução é viável.
 o cálculo do número máximo de conflitos para a configuração atual, para afirmar se é ou não
uma solução viável para o problema.
 o cálculo do número de conflitos com base no valor obtido para a solução imediatamente
anterior, para avaliar se a solução é viável.
 o cálculo do número de possíveis conflitos para uma dada configuração para as rainhas do
tabuleiro, e a partir deste tem-se a aptidão da solução.
 
 Pergunta 2
 
 Veja o pseudocódigo a seguir:
“Entradas: A função f(.) e o escalar ε
Saída: A resposta R à pergunta: existe x tal que f(x) < ε?
R ← FALSO
Enquanto R = FALSO faça
Gerar aleatoriamente uma instância do vetor x
Se f(x) < ε então
R ← VERDADEIRO
Fim se
Fim enquanto”
Fonte: GASPAR-CUNHA, A.; TAKAHASHI, R.; ANTUNES, C. H. Manual de computação
evolutiva e meta-heurística. Coimbra: Coimbra University Press, 2012. p. 10.
Considerando este pseudocódigo e o conteúdo estudado sobre heurísticas,
meta-heurísticas e problemas não determinísticos, pode-se afirmar que:
 o algoritmo apresentado é um exemplo do uso de heurística bioinspirada na prática, para a
resolução do problema de otimização.
 x, neste caso, representa um conjunto de soluções e a estrutura, enquanto pode ser
implementada com a estrutura while no MATLAB.
 FALSO pode ser representado como uma variável contínua, 1 e VERDADEIRO como uma
variável inteira -1.
 ε representa um vetor de erro, definido a partir da diferença entre a resposta desejada e a
atual para o problema.
 o problema não determinístico é estruturado com base na resposta de valor acerca de uma
dada pergunta.
 
 Pergunta 3
 
 O algoritmo genético foi proposto por Holland no ano de 1975, como uma das primeiras
propostas de uso de heurísticas, desenvolvendo um algoritmo computacional bioinspirado
neste caso, com base em mecanismos e processos como a seleção natural e a evolução
genética.
Considerando essas informações sobre algoritmos genéticos, relacione os exemplos e
parâmetros apresentados com relação a estes métodos, na coluna numerada, com seus
possíveis contextos listados na coluna posterior:
1) Geração.
2) População.
3) Aptidão.
4) Genes.
( ) Função objetivo.
( ) Variável da solução.
( ) Conjunto de soluções.
( ) Iteração.
Agora, assinale a alternativa que apresenta a sequência correta:
 4, 2, 3, 1.
 2, 1, 3, 4.
 2, 4, 1, 3.
 3, 4, 2, 1.
 3, 2, 1, 4.
 
 Pergunta 4
 
 Um outro ponto importante a ser considerado no desenvolvimento de um algoritmo baseado
no método de busca tabu é o uso da denominada lista de tabus, referência para o processo
de busca que será realizado pelo algoritmo, na busca da solução viável.
Considerando essas informações e as possíveis estratégias relacionadas à busca tabu,
analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
I. ( ) Estratégias de intensificação, para exploração de certa região podem ser usadas para
melhorar o algoritmo de busca tabu básico.
II. ( ) Repete-se a melhoria local caso o ponto atual seja uma solução viável para o problema
analisado.
III. ( ) O algoritmo de busca tabu é mais indicado para problemas reais estruturados para a
minimização.
IV. ( ) O uso de processos de diversificação também faz parte de estratégias para melhoria
do algoritmo de busca tabu.
Agora, assinale a alternativa que apresenta a sequência correta:
 V, V, V, F.
 V, V, F, V.
 F, V, V, F.
 F, F, V, V.
 V, F, F, V.
 
 Pergunta 5
 
 A busca tabu (ou busca de tabus) é um exemplo importante do uso de meta-heurísticas, por
se tratar de um algoritmo bastante comum na Pesquisa Operacional, inclusive. Além disso,
sabe-se que este tipo de estratégia considera o senso comum para a busca da solução
viável.
Considerando essas informações gerais e outras premissas da busca tabu, é correto afirmar
que:
 um dos principais artifícios usados na prática, neste caso, é inicializar as soluções zeradas.
 na busca tabu, prima-se a iteração com evolução (melhoria) na solução candidata.
 na busca tabu, geralmente utilizam-se heurísticas de fiscalização.
 este tipo de método contará com uma sub-rotina para a realização de busca local.
 a evolução da solução é avaliada de forma contrária em comparação com os algoritmos
genéticos.
 
 Pergunta 6
 
 Existem duas topologias básicas para o desenvolvimento de um algoritmo de enxame de
partículas: considerando-se a posição local de cada partícula somente ou levando em conta
a melhor posição encontrada até o momento, na iteração para cada partícula.
Com base nestas informações e no seu conhecimento acerca dos algoritmos de enxame de
partículas, analise as afirmativas a seguir:
I. Um primeiro passo geral a ser tomado na iteração neste tipo de algoritmo é gerar a
população inicial.
II. Caso a função associada seja multimodal, pode ser mais estratégico usar uma topologia
local.
III. Na estrutura local, o algoritmo atualiza a velocidade de cada partícula do enxame.
IV. A tomada de decisão final a cada iteração será feita por um especialista, para avaliar se
foi encontrado um mínimo global.
Está correto apenas o que se afirma em:
 I e IV.
 II e IV.
 III e IV.
 I e II.
 I, II e III.
 
 Pergunta 7
 
 Um dos primeiros e principais passos quando se desenvolve um algoritmo genético é
escolher a forma de representação das soluções candidatas e, consequentemente, das
variáveis. Tal representação pode ser binária, por exemplo, e em certos momentos do
processo será necessária então a decodificação para compreender o que de fato é a
solução apontada.
Considerando estas informações e o conteúdo estudado sobre algoritmos genéticos, analise
as asserções a seguir e a relação proposta entre elas:
I. A representação fenotípica, ou simplesmente fenótipo, semelhantemente ao que ocorre na
genética, na natureza, representará as características referentes aos genes.
Porque:
II. O fenótipo se trata, assim como é feito no algoritmo genético com o uso da representação
binária, por exemplo, da decodificação do genótipo.
 A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
 A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da
I.
 As asserções I e II são proposições falsas.
 As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
 
 Pergunta 8
 
 Leia o excerto a seguir:
“Otimização combinatória é uma disciplina de tomada de decisões no caso de problemas
discretos que pode ser encontrada em diversas áreas, tais como problemas de
planejamento e programação (scheduling) da produção, problemas de corte e
empacotamento, roteamento de veículos, redes de telecomunicação, sistemas de
distribuição de energia elétrica, problemas de localização, entre outros. Em muitos destes
problemas surgem frequentemente vários critérios de desempenho (funções objetivo), em
geral, conflitantesentre si.”
Fonte: ARROYO, J. E. C. et al. Heurísticas e meta-heurísticas para otimização combinatória
multiobjetivo. Doutorado (Teste de Engenharia Elétrica e de Computação) – Universidade
Estadual de Campinas, fev. 2002. p. 13. (Adaptado).
Considerando essas informações e o conteúdo estudado sobre otimização combinatória e o
uso de heurísticas, analise as afirmativas a seguir:
I. Uma das principais motivações para o desenvolvimento de métodos de otimização com
heurísticas foi, de fato, a otimização combinatória.
II. O problema de programação de tarefas é um tipo de problema de programação da
produção.
III. As heurísticas são mais usadas enquanto meta-heurísticas, geralmente são evitadas na
otimização combinatória.
IV. Tanto símiles quanto heurísticas são utilizadas no desenvolvimento de métodos não
tradicionais de otimização.
Está correto apenas o que se afirma em:
 I e II.
 III e IV.
 I, II e III.
 I e IV.
 II e IV.
 
 
 Pergunta 9
 
 O algoritmo de colônia de formigas é estruturado a partir de noções importantes do
comportamento social destes insetos, incluindo o processo de busca de alimentos, que
normalmente é estruturado na prática, na natureza do animal.
Considerando essas informações e o conteúdo estudado sobre o método, é possível afirmar
que:
 o problema no contexto é apresentado a partir de uma estrutura de grafo.
 o trajeto analisado será da fonte de alimento para a colônia de origem.
 os nós de transbordo, neste caso, representam a origem da formiga.
 cada camada da colônia é representada por pelo menos 10 formigas.
 os nós de suprimento representarão, neste contexto, os pais das formigas.
 
 Pergunta 10
 
 Além de artifícios como a medida de inércia, utilizam-se parâmetros de posição, local e
global em alguns casos, valores de aceleração local e global também na topologia global e
números aleatórios, que podem ser gerados para inserir diversidade à resolução.
Com base nessas informações e no seu conhecimento sobre o algoritmo de enxame de
partículas global, assinale a alternativa correta:
 os números aleatórios usados geralmente são dois e estarão entre 0 e 1.
 conceitos como feromônios são usados para entender como as formigas se movimentam na
água.
 a função de aptidão, neste caso, é definida aleatoriamente, dependendo do valor do
parâmetro r.
 as constantes de aceleração são usadas para o processo do cálculo da velocidade anterior.
 no caso deste tipo de algoritmo, a expertise do programador é menos usada.