EXPERIMENTO IA

Prévia do material em texto

1. 
O cromossomo é um componente fundamental para o algoritmo genético. No caso do problema da 
mochila, o cromossomo foi representado como uma string de bits. Levando isso em consideração, escolha 
a alternativa correta. 
Resposta incorreta. 
A. 
A string de bits representa o valor da função de avaliação em binário; 
A string de bits representa quais itens do problema seriam inseridos na mochila, sendo que os índices de cada 
bit indicam os índices de cada item, os bits de valor 0 indicam que o item não foi inserido na mochila, e os bits 
de valor 1 indicam que o item foi inserido na mochila. 
 
Resposta incorreta. 
B. 
Um cromossomo representa uma geração da população; 
Um cromossomo representa um elemento, um indivíduo, da população. Ele representa um candidato a solução, 
e um conjunto de cromossomos representa uma população. 
 
VOCÊ ACERTOU! 
C. 
No caso do problema da mochila, dois cromossomos diferentes podem ter o mesmo valor de função de 
avaliação. 
É possível que diferentes combinações de inserções de itens levem a um mesmo valor de avaliação. Por 
exemplo, suponha o caso em que só temos três itens: o item 0 com valor 30, o item 1 com valor 10 e o item 2 
com valor 20. Caso tenhamos um cromossomo 100 e outro cromossomo 011, o valor de aptidão é o mesmo 
para os dois. 
 
2. 
Durante o laboratório, como forma de colocar em prática os conceitos de algoritmos genéticos, foram 
implementadas as funções “public double Avaliacao()”, “public Cromossomo[] crossover(...)”, "private 
int selecionaPai(double somaAvaliacoes)", “public int somaAvaliacoes()” e “public CromossomoMochila 
getMelhorCorrente()”. Sobre essas funções, indique a alternativa correta: 
Resposta incorreta. 
A. 
a função "Avaliacao()" vai retornar 1 somente se o cromossomo não corresponder a uma solução válida; 
A função em questão retorna a aptidão do cromossomo e é calculada como o valor total dos itens ou 1, caso o 
peso total exceda o limite do problema. 
 
RESPOSTA CORRETA. 
B. 
a função "Avaliacao()" vai retornar 1 no caso de o peso ultrapassar o limite, mesmo que a soma dos itens da 
sacola não ultrapasse esse valor; 
Da forma como o problema da mochila está implementado, caso tivéssemos itens com valores entre 0 e 1, o 
valor total da mochila seria aumentado para 1 caso o peso fosse excedido. Uma solução, nesse caso, seria 
reduzir o valor da aptidão retornada para um valor muito menor do que os dos itens da sacola. 
 
Você não acertou! 
C. 
o ponto de corte do crossover é um dos parâmetros da função "crossover(...)". 
O ponto de corte é gerado aleatoriamente dentro da função em questão, não sendo ele um parâmetro da função. 
 
3. 
O método da roleta viciada é uma forma aleatória de selecionar os cromossomos ao mesmo tempo que 
favorece a seleção de indivíduos mais aptos (com maior avaliação). Suponha o caso de termos quatro 
cromossomos, tal que o valor dos quatro está em ordem na tabela a seguir: 
 
 
Seguindo essa tabela e considerando a implementação do método da roleta viciada feito em laboratório, 
selecione a alternativa correta: 
Resposta incorreta. 
A. 
caso fosse sorteado o número 36, o indivíduo 1 seria escolhido; 
Como 36 é maior que a avaliação acumulada do indivíduo 1 (30) e menor que a do indivíduo 2 (45), o 
indivíduo 2 será escolhido. 
 
Resposta incorreta. 
B. 
o indivíduo 3 tem a maior chance de ser escolhido; 
Apesar de o valor da avaliação acumulada ser maior, o que faz a diferença é o valor da avaliação do indivíduo. 
O indivíduo 3 só pode ser sorteado se o número que for sorteado for 45, visto que é menor que a sua avaliação 
acumulada e é igual à avaliação acumulada do indivíduo 2. 
 
VOCÊ ACERTOU! 
C. 
o indivíduo 0 tem a maior probabilidade de ser escolhido. 
Para sortear o indivíduo 0, qualquer número sorteado entre 0 e 19 (incluso nesse intervalo) vai valer (20 
possibilidades), enquanto, para sortear o indivíduo 1, precisaríamos de números entre 20 e 29 (10 
possibilidades), para o indivíduo 2, precisaríamos de números entre 30 e 44 (15 possibilidades), e para o 
indivíduo 3, somente o número 45 seria válido (1 possibilidade). Dessa forma, o indivíduo 0 é o mais provável 
de ser escolhido. 
 
4. 
O cromossomo representado por uma string de bits representa, em cada bit, se um elemento foi incluído 
ou não na mochila. Considere os itens dispostos na tabela a seguir: 
 
 
Suponha que o limite de peso para este problema é 6 e que a função de avaliação segue a implementação 
do laboratório. Selecione a alternativa correta: 
Resposta incorreta. 
A. 
o cromossomo 1101 representa uma solução válida; seu valor de avaliação é 7, e o seu peso é 12; 
O cromossomo 1101 indica que os itens 0, 1 e 3 foram selecionados. Dessa forma, o valor total é 4 + 5 + 3 = 
12, e o peso total é 2 + 3 + 2 = 7. Como o peso total ultrapassa o peso limite (solução inválida), o valor de 
avaliação é alterado para 1. 
 
Você não acertou! 
B. 
o cromossomo 1101 representa uma solução inválida; seu valor de avaliação é 1, e o seu peso é 12; 
O cromossomo 1101 indica que os itens 0, 1 e 3 foram selecionados. Dessa forma, o valor total é 4 + 5 + 3 = 
12, e o peso total é 2 + 3 + 2 = 7. Como o peso total ultrapassa o peso limite (solução inválida), o valor de 
avaliação é alterado para 1. 
 
RESPOSTA CORRETA. 
C. 
o cromossomo 1011 representa uma solução válida; seu valor de avaliação é 10, e o seu peso é 5. 
O cromossomo 1011 indica que os itens 0, 2 e 3 foram selecionados. Dessa forma, o valor total é 4 + 3 + 3 = 
10, e o peso total é 2 + 1 + 2 = 5. Como o peso total é menor que o limite, então o cromossomo 1011 representa 
uma solução válida. 
 
5. 
A mutação é um processo que ocorre aleatoriamente para cada cromossomo gerado após o crossover. 
Considerando a implementação feita no laboratório e o processo de mutação, indique a alternativa 
correta: 
RESPOSTA CORRETA. 
A. 
para uma taxa de mutação igual a 1, os cromossomos filhos serão garantidamente alterados; 
O gerador de números aleatórios “Math.random()” retorna números entre 0 (inclusivo) e 1 (exclusivo). Dessa 
forma, quando a taxa de mutação é 1, todo número gerado será menor que 1, o que vai garantir que a mutação 
ocorra em cada cromossomo resultado de crossover. 
 
Resposta incorreta. 
B. 
sempre que ocorre mutação em um dos filhos, o outro deverá passar pelo processo de mutação também; 
O processo de mutação ocorre de maneira individual para cada cromossomo gerado por crossover. Assim, não 
há garantias de que o outro filho também vai passar por um processo de mutação. Só há garantia quando a taxa 
de mutação é 1, assim, todos os cromossomos filhos vão passar pelo processo de mutação. 
 
Você não acertou! 
C. 
caso os dois filhos passem por um processo de mutação, o índice do bit que vai passar por mutação será o 
mesmo. 
O processo de mutação ocorre de maneira individual para cada cromossomo gerado por crossover. Assim, o 
índice do bit a ser mutado para cada cromossomo independe do outro que foi gerado. 
 
 
Considere a seguinte formulação de problema da mochila: temos quatro itens para serem inseridos em uma 
mochila de peso máximo 10. 
• O item 0 tem valor 3 e peso 5. 
• O item 1 tem valor 5 e peso 4. 
• O item 2 tem valor 10 e peso 8. 
• O item 3 tem valor 2 e peso 1. 
Com base na representação dos cromossomos do nosso algoritmo feita para o laboratório, assinale a alternativa 
correta: 
Resposta incorreta. 
A. 
O cromossomo 1001 tem um valor de fitness maior do que o cromossomo 1100. 
O valor de aptidão de 1001 é 3 + 2 = 5, e o peso é 5 + 1 = 6, enquanto o valor de aptidão do cromossomo 1100 
é 3 + 5 = 8, e o peso é 9. Como nenhum dos pesos ultrapassou o limite máximo, os valores de aptidão são 
mantidos. 
 
VOCÊ ACERTOU! 
B. 
O cromossomo 1101 apresenta um peso maior do que o cromossomo 0011. 
O cromossomo 1101 tem total de peso de 5 + 4 + 1 = 10, enquanto o cromossomo 0011 tem um totalde 8 + 1 = 
9. Portanto, o cromossomo 1101 apresenta maior peso na mochila do que o cromossomo 0011. 
 
Resposta incorreta. 
C. 
O cromossomo 1111 seria descartado antes de passar por qualquer operação pelo algoritmo genético. 
Apesar de o peso exceder o limite imposto pelo problema, a solução adotada pelo algoritmo é a de reduzir o 
valor de fitness, em vez de descartar diretamente. 
 
2. 
Sabemos que uma das fases do algoritmo genético é a de escolha de indivíduos para que ocorra crossover entre 
eles e eles produzam filhos. Sabendo desse fato, assinale a alternativa correta: 
Resposta incorreta. 
A. 
Todos os indivíduos da população que têm o valor de avaliação alto produzem filhos. 
Como a escolha dos indivíduos é feita por meio de um fator aleatório, não podemos garantir a escolha de 
indivíduos no processo de seleção, apenas podemos estimar que os mais aptos têm maior probabilidade de 
serem escolhidos. 
 
Resposta incorreta. 
B. 
O indivíduo com maior valor de avaliação é sempre escolhido para que haja crossover. 
O indivíduo mais apto pode impactar na probabilidade de escolha caso sua aptidão seja muito maior do que a 
dos demais indivíduos. Apesar disso, ainda existe a possibilidade de outros indivíduos serem escolhidos, visto 
que o processo é aleatório. 
 
VOCÊ ACERTOU! 
C. 
O algoritmo da roleta viciada privilegia a escolha dos indivíduos mais aptos, mas não descarta a escolha de 
indivíduos menos aptos. 
Por popular uma porção maior da distribuição no momento da escolha, os indivíduos mais aptos são 
privilegiados, enquanto os menos aptos têm uma porção menor da distribuição. 
 
 
3. 
O algoritmo genético implementado no laboratório é composto, basicamente, de três processos: crossover, 
seleção e mutação. Sobre essas etapas, selecione a alternativa correta: 
VOCÊ ACERTOU! 
A. 
Durante o ciclo, primeiro fazemos a seleção, seguida do crossover, e depois a mutação. 
De fato, para que haja crossover, precisamos selecionar os pares de cromossomos. Em seguida, os 
cromossomos filhos podem passar por mutação. 
 
Resposta incorreta. 
B. 
Durante o ciclo, primeiro aplicamos a mutação, seguida do crossover, e depois a seleção. 
A ordem correta é a seleção dos cromossomos, seguida da operação de crossover e, por último, a mutação — o 
que tende a aumentar a variedade entre os cromossomos da próxima geração. 
 
Resposta incorreta. 
C. 
O crossover entre cromossomos não ocorre sempre — somente quando há mutação em um cromossomo. 
O crossover sempre vai ocorrer nos pares de indivíduos selecionados. A mutação só ocorre nos cromossomos 
gerados por crossover, mas depende de um fator aleatório — ou seja, não há garantia de ocorrer para todo 
cromossomo. 
 
4. 
Dentro da chamada da função “public static void main(String[] args)” implementada no laboratório, a classe 
implementada foi instanciada em "GA meuGA = new GA(pesos, valores, 100);", e executamos o algoritmo em 
“meuGA.run(0.01, 15, 10);”. Sobre esse trecho de código, podemos afirmar que: 
Resposta incorreta. 
A. 
O número de soluções exploradas pelo código do enunciado é menor do que se fosse executado 
“meuGA.run(0.01, 10, 5);”. 
Cada geração corresponde a um conjunto de possíveis soluções para o problema. No código proposto nessa 
alternativa, como serão feitas 10 gerações, e o número de indivíduos por população é 5, temos 50 soluções 
exploradas, sendo que, no código do enunciado, teríamos 15 gerações de 10 indivíduos, explorando 150 
soluções. Dessa forma, a implementação dessa alternativa explora menos soluções do que a do enunciado. 
 
RESPOSTA CORRETA. 
B. 
O número de soluções exploradas pelo código do enunciado é menor do que se fosse executado 
“meuGA.run(0.01, 10, 20);”. 
Cada geração corresponde a um conjunto de possíveis soluções para o problema. No código proposto nessa 
alternativa, como serão feitas 10 gerações, e o número de indivíduos por população é 20, temos 200 soluções 
exploradas, sendo que, no código do enunciado, teríamos 15 gerações de 10 indivíduos, explorando 150 
soluções. Dessa forma, a implementação dessa alternativa explora mais soluções do que a do enunciado. 
 
Você não acertou! 
C. 
Caso aumentássemos o primeiro argumento em “meuGA.run(0.01, 15, 10);” de 0.01 para 0.1, teríamos um 
número maior de ocorrências de crossover. 
O primeiro argumento é referente à taxa de mutação, a qual ocorre após o crossover. O crossover, por outro 
lado, vai ocorrer em todos os ciclos, sendo alterados somente os pares de cromossomos usados no processo. 
 
5. 
A operação de crossover funde características de dois cromossomos pais para gerar outros dois cromossomos 
(filhos). Sejam 10011 e 01000 dois cromossomos selecionados para crossover. Suponha que o ponto de corte 
gerado foi igual a 3. Sobre essa operação de crossover, assinale a alternativa correta: 
Resposta incorreta. 
A. 
Os filhos gerados serão 10010 e 01001. 
Para esse resultado, o ponto de corte deveria ser igual a 4. No caso do enunciado, o corte vai separar o primeiro 
cromossomo pai em dois: 100 e 11. O segundo cromossomo pai será separado em 010 e 00. Dessa forma, o 
primeiro filho terá a string “100” do primeiro pai concatenada à string “00” do segundo pai. O segundo filho 
terá a string “010” do segundo pai concatenada à string “11” do primeiro pai. 
 
Resposta incorreta. 
B. 
Os filhos gerados serão 11000 e 00011. 
Para esse resultado, o ponto de corte deveria ser igual a 1. No caso do enunciado, o corte vai separar o primeiro 
cromossomo pai em dois: 100 e 11. O segundo cromossomo pai será separado em 010 e 00. Dessa forma, o 
primeiro filho terá a string “100” do primeiro pai concatenada à string “00” do segundo pai. O segundo filho 
terá a string “010” do segundo pai concatenada à string “11” do primeiro pai. 
 
VOCÊ ACERTOU! 
C. 
Os filhos gerados serão 10000 e 01011. 
O corte vai separar o primeiro cromossomo pai em dois: 100 e 11. O segundo cromossomo pai será separado 
em 010 e 00. Dessa forma, o primeiro filho terá a string “100” do primeiro pai concatenada à string “00” do 
segundo pai. O segundo filho terá a string “010” do segundo pai concatenada à string “11” do primeiro pai, 
resultando nas strings da alternativa.