Algoritmos Genéticos Exercícios

Prévia do material em texto

Algoritmos Genéticos – Exercícios 
 
 
 
1) Considere o problema de maximização da função f(x) = x2 
 
Sabendo-se que o intervalo de domínio da função é [0,1023], indique uma representação possível para os 
cromossomas de um AG aplicável à solução do problema. 
 
a) Indique a aptidão de seleção os indivíduos: 
0000110110 
0010010101 
0001111001 
0010101101 
 
b) Indique o resultado da aplicação de um operador de crossover nos pares de indivíduos abaixo: 
 
Crossover de 1 ponto (ponto de corte = 3) 
0001100101 
0011010001 
 
Crossover de 2 pontos (pontos de corte 3 e 5) 
0010110101 
0001001100 
 
Crossover uniforme (máscara: 0010011010) 
0010110101 
0001001100 
 
 
2) Considere um problema envolvendo 40 variáveis com 10 valores possíveis cada uma. 
 
a) Qual o tamanho do espaço de soluções? 
 
b) Qual a representação de cromossoma você utilizaria na modelagem de um AG para resolver este 
problema? 
 
 
3) Considere a geração de indivíduos da questão 1b. 
 
a) Qual/quais indivíduos seriam relacionados pela técnica de elitismo? 
 
b) Qual/quais indivíduos seriam descartados pela técnica de Steady State com GAP = 2 ? 
 
 
4) Sejam 3 variáveis reais x1, x2 e x3 com 5 bits de representação cada, Dom(x1) = [-2,4], Dom(x2) = [0,2], 
Dom(x3) = [-1,1] e o cromossoma 001011110011010. Decodifique o cromossoma, informando os valores de 
x1, x2 e x3. 
 
 
5) Considere o problema de maximização da função f(x,y) = 1 + | x * y * sen (y /4) | onde x e y  [0,15] e seja a 
população inicial, sorteada aleatoriamente: 
 
 
 
Cromossomo X y f(x,y) 
01000011 4 3 9,5 
00101001 2 9 13,7 
10011011 9 11 71,0 
00001111 0 15 1,0 
10011001 5 5 18,7 
11100011 14 3 30,7 
 
 
a) Qual a probabilidade de seleção do último indivíduo? 
 
b) Qual seria o cromossoma selecionado, caso o método de seleção fosse a roleta e o valor sorteado 
fosse 83,2? Justifique. 
 
c) Considerando o padrão H=1******1*, indique: O(H), (H) e a aptidão média de H. 
 
 
6) Seja H um padrão arbitrário. Indique a probabilidade de sobrevivência de H mediante a aplicação do operador 
de: 
 
a) Crossover de um ponto 
 
b) Mutação simples 
 
 
7) A igualdade abaixo expressa o efeito da seleção de um padrão qualquer durante o ciclo evolucionário de um 
algoritmo genético. Explique esse efeito. 
 
f
f(H)
t)m(H,1)tm(H, 