MT 11-12 Resolvido.md

Enunciado

Considere o exemplo dado nas aulas teóricas de arrumação de volumes em contentor mas com capacidade 80, e a respectiva população genética inicial. A penalização é 1 centésimo da proposta nas aulas. Supondo que usamos política elitista (mas só para o melhor) geraram-se depois 2 números aleatórios: 0,40 / 0,72 indicando quem são candidatos ao emparelhamento. Assuma a probabilidade de cruzamento de 75% e que a roleta deu agora os 3 números; 0.95 / 0.50 / 0.65. Assuma um ponto de cruzamento entre o 5o e 6o bits. A probabilidade de mutação é de 5% e só ao 25o número aleatório apareceu um inferior a 0,05.

a) Apresente a 2a geração. Explique pormenorizadamente todo o processo que seguiu.

b) Caso tivesse forçosamente que parar o algoritmo (na 2o geração) que solução escolhia e porquê?

Resolução

Fadaptação = Sum(V[i]*Xj[i]) - Penalização
Penalização = 0.01*R*(Sum(Xj[i]*P[i])-Cmax)²
R = max(V[i]/P[i]), Xj[i]=0
Probabilidade de Seleção (Ps)= Fa/Sum(Fa)

-Capacidade Maxima = 80
-Probabilidade de Cruzamento (Pc) = 0.75
-Politica elitista mas só para o melhor
-Probabilidade de mutação = 0,05 (ocorre apenas ao 25º numero aletorio)

V[i]={10,50,20,10,40,10,30,5,5,10}
P[i]={20,10,10, 5, 10, 15, 5, 5,5, 5}

Indivíduo	R	Função de Adaptação (Fa)	Penalização
X1	30/5 = 6	(10+50+20+10+5+5+10)-24 = 86	0.016((20+10+10+5+5+5+5)-80)² = 24
X2	5	(40+10+30+5+5+10)-61.25 = 38.75	0.015((10+15+5+5+5+5)-80)² = 61.25
X3	6	(10+50+40+10)-73.5 = 36.5	0.016((20+10+10+5)-80)² = 73.5

População Inicial	Fa	ProbabilidadeSeleção = Fa/FaTotal
X1 1111000111	86	0.533
X2 0000111111	38.75	0.24
X3 1100100001	36.5	0.22
FaTotal	161.25

Emparelhamento por seleção elitista para o melhor e probabilística os restantes (valores da roleta):
O nº de individuos selecionados tem que ser igual ao da população inicial (podendo-se repetir).

Indivíduo	Pmin	Pmax
X1	0	0.533
X2	0.533	0.773
X3	0.773	1

Como saiu na roleta os valores 0.40 e 0.72, seleciono X1 e o X2 pois 0.40 está no intervalo de X
e 0.72 está no intervalo de X2

Candidatos a emparelhamento

Indivíduo	Política
X1	Elitista
X1	Probabilística
X2	Probabilística

Cruzamento aplicado entre o 5º e 6º bits

Probabilidade = 0.75

Indivíduo	Valor	Cruzamento
X1	0.95
X1	0.50	x
X2	0.65	x

Indivíduo	Cruzamento	Mutação (25º bit)
X1 11110 | 00111	11110 | 00111	1111000111
X1 11110 | 00111	11110 | 11111	1111011111
X2 00001 | 11111	00001 | 00111	0000000111

1ª Geração	2ª Geração
X1 1111000111	X1 1111000111
X2 0000111111	X'1 1111011111
X3 1100100001	X'2 0000000111