ALGORITMO GENÉTICO APLICAÇÃO

UMA CAMINHONETE COM CAPACIDADE PARA 200KG DE CARGA PRECISA SER CARREGADA PARA ENTREGA. EXISTEM 3 TIPOS DE PRODUTOS PARA CARREGAR: ARMÁRIO (ITEM 1), GELADEIRA (ITEM 2) E FOGÃO (ITEM 3). AS MASSAS E VALORES DOS ITENS SÃO COMO MOSTRADOS NA TABELA ABAIXO. A QUANTIDADE DE CADA PRODUTO PARA ENTREGA É DE 3 ARMÁRIOS, 2 GELADEIRAS E 5 FOGÕES. QUANTO DE CADA PRODUTO DEVE SER CARREGADO DE MODO A ENTREGAR O MAIOR VALOR POSSÍVEL?

PRODUTO	MASSA (KG)	VALOR
ARMÁRIO	30	400
GELADEIRA	50	1.000
FOGÃO	20	500

DESENVOLVIMENTO:

MAX Z = 400X1 + 1000X2 + 500X3, onde X1, X2, X3 são as quantidades dos produtos 1, 2 e 3.

Restrições: 30X1 + 50X2 + 20X3 <= 200

X1 <= 3; X2 <=2; X3 <= 5

X1, X2, X3 INTEIROS

[pic 1]

[pic 2][pic 3][pic 4][pic 5][pic 6][pic 7][pic 8][pic 9][pic 10]

● TAMANHO DA POPULAÇÃO: 4 INDIVÍDUOS

● SELEÇÃO: ROLETA VICIADA

● CROSSOVER: 50% MELHORES E 50% PIORES. CROSSOVER DE ATÉ 2 GENES

● MUTAÇÃO: 10% DE CHANCE DO FILHO SOFRER MUTAÇÃO. MUTAÇÃO EM 1 GENE

● CRITÉRIO DE PARADA: REALIZAR 2 ITERAÇÕES SEM MELHORA

CRIAÇÃO DA POPULAÇÃO INICIAL

A POPULAÇÃO INICIAL SERÁ CRIADA DE FORMA ALEATÓRIA ATÉ CONSEGUIRMOS 4 INDIVÍDUOS VIÁVEIS.

               ARMÁRIO                                 GELADEIRA        

TOTAL	PROB.	P. ACUM.
0	0,250	0,250
1	0,250	0,500
2	0,250	0,750
3	0,250	1,000
TOTAL	PROB.	P. ACUM.
0	0,333	0,333
1	0,333	0,667
2	0,333	1,000

        

                 FOGÃO                

TOTAL	PROB.	P. ACUM.
0	0,167	0, 167
1	0, 167	0,333
2	0, 167	0,500
3	0,167	0,667
4	0,167	0,834
5	0,167	1,000

CROMOSSOMO:

       1            2            3                                        

 

● POSSUI 3 GENES

ENTÃO, SORTEAMOS NÚMEROS ALEATÓRIOS: 59 PARA ARMÁRIO, 53 PARA GELADEIRA E 7 PARA FOGÃO

0,500 < 0,59 < 0,750 = 2 UN; 0,333 < 0,53 < 0,667 = 1 UN; 0,07 < 0,167 = 0 UN

       1            2            3                                        

2

1

0

SEGUINDO O MESMO PROCEDIMENTO CRIAMOS A POPULAÇÃO INICIAL:

[pic 11]

POPULAÇÃO INICIAL:

	1	2	3	F.O
A	2	1	0	1800
B	1	0	5	2900
C	2	1	1	2300
D	0	1	0	1000

                                                       MELHOR: B (2900)

CRIAÇÃO DA SEGUNDA POPULAÇÃO

SELEÇÃO DOS PAIS:

MELHORES:

IND.	F.O	PROB.	P. ACUM.
B	2900	0,557	0,557
C	2300	0,450	1

NÚMERO ALEATÓRIO: 36         0,360 < 0,550          PAI B[pic 12][pic 13]

PIORES:

IND.	F.O	PROB.	P. ACUM.
A	1800	0,643	0,643
D	1000	0,547	1

NÚMERO ALEATÓRIO: 50         0,500 < 0,643          PAI A[pic 14][pic 15]

CROSSOVER:

B	1	0	5
A	2	1	0

                           0,333             0,666             1,000

NÚMEROS ALEATÓRIOS:            0,44                       GENE 2[pic 16][pic 17]

                                                       0,51                         GENE 2[pic 18][pic 19]

FILHOS:                                                                                  RESTRIÇÃO                      F.O