Prática de Algoritmos Genéticos
Disciplina:
Sistemas Inteligentes I
Prof. Frederico Brito Fernandes
[email protected]
CONTEÚDO
(1) Definição do Problema
(2) Modelando com AG
(3) Sua parte...
(4) Projeto coloração 2
(1) Definição do Problema
•
Problema da Alocação de Disciplinas:
a)
Objetivo:
–
b)
Montar os horários das disciplinas a cada semestre.
Formule uma solução para esse problema:
b1) usando AG, lembrando que você deve estabelecer:
(1)Tamanho do indivíduo; (2) Gene; (3)
Tamanho da população (4) Tipo de Seleção e (5) Taxa de Mutação
b2) a lógica de programação usada (independente de linguagem).
c)
Admita que a faculdade têm apenas:
–
–
–
dois períodos (P1 e P2);
três professores (Fechine, Nilton e Fred);
duas disciplinas por período (d1, d2, d3, d4 , d5, d6), onde
•
•
–
–
–
–
d1, d2, d3  P1;
d4 , d5, d6  P2;
Fechine leciona d1 e d4, Nilton leciona d2, d5 e Fred leciona d3, d6;
três noites de aula por semana, com duas aulas por noite;
Fechine não pode ensinar no primeiro horário da segunda;
não é permitido que uma mesma disciplina tenha duas aulas por noite.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
2/8
(2) Modelando com AG
a) Objetivo:
P1
– Todo coordenador tem a cansativa tarefa de montar os
horários das disciplinas a cada semestre.
– Possível solução:
P2
Seg
Ter
Qua
h1
(Fred, d3)
(Fechine, d1)
(Fred, d3)
h2
(Fechine, d1)
(Nilton, d2)
(Nilton, d2)
h1
h2
Seg
Ter
Qua
(Nilton, d5)
(Fred, d6)
(Nilton, d5)
(Fred, d6)
(Fechine, d4)
(Fechine, d4)
P1
P2
Seg1P1
Seg2P1
Ter1P1
Ter2P1
Qua1P1
Qua2P1
Seg1P2
Seg2P2
Ter1P2
Ter2P2
Qua1P2
Qua2P2
(p, d)
(p, d)
(p, d)
(p, d)
(p, d)
(p, d)
(p, d)
(p, d)
(p, d)
(p, d)
(p, d)
(p, d)
0
1
2
3
4
5
6
7
8
9
10
11
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
3/8
(2) Modelando com AG
b) Formulando uma solução para esse problema:
b1) usando AG, lembrando que você deve estabelecer:
(1)Tamanho do indivíduo; (2) Genes; (3) Tamanho da população (4) Tipo de
Seleção e (5) Taxa de Mutação
(1) Tamanho = 12 genes = indivíduo
Seg1P1
Qua2P1
Seg1P2
Seg2P2
Ter1P2
Ter2P2
Qua1P2
Qua1 Qua2
(p,Seg1
d) (p,Seg2
d) (p,Ter1
d) (p,Ter2
d) (p,
d) (p, d)
(p, d)
(p, d)
(p, d)
(p, d)
(p, d)
(p, d)
6
7
8
9
10
11
P1
0
Seg2P1
P1
1
Ter1P1
P1
2
Ter2P1
P1
3
Qua1P1
Obs: em geral, o gene={0,1}
Porém, resolvemos adotar um gene
composto por uma tupla (prof,disc)
P1
4
P1
5
Qua2P2
(2) Gene = { (prof, disc) }, onde:
prof = {Fechine, Fred, Nilton} = {00,01,10}
disc = {d1, d2, d3, d4 , d5, d6} = {000,001,010,011,100,101}
Ex: um indivíduo
01010
00000
00000
10001
60 bits
01010
10001
10100
01101
01101
00011
10100
00011
Fred=01 e d3=010
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
4/8
(2) Modelando com AG
b) Formulando uma solução para esse problema: (cont.)
(3) Tamanho da população: 100 indivíduos
0
01010
00000
00000
10001
01010
10001
10100
01101
01101
00011
10100
00011
1
01010
00000
00000
10001
01010
10001
10100
01101
01101
00011
10100
00011
10100
01101
01101
00011
10100
00011
...
99
...
01010
00000
00000
10001
01010
10001
(4) Tipo de seleção
Probabilística Simples: um ponteiro
(5) Taxa de Mutação: 0.5%
Se em cada nova população temos (60 * 100) 6000 bits, implica
dizer que serão trocados aleatoriamente 30 bits
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
5/8
(3) Sua parte agora...
•
•
Implemente o algoritmo simples de AG para esse problema
Dicas:
– Use o código inicial do site do professor para iniciar sua solução
– Para formação da nova população, despreze os pais e use apenas os
filhos
– A taxa de mutação igual a 0.5%, indica mudança de 30 bits, e para isso:
•
•
•
Faça uma função que escolha 30 indivíduos aleatoriamente
Em cada indivíduo, escolha um gene que será modificado
Implemente a regra:
– não é permitido que uma mesma disciplina tenha duas aulas por noite
•
Estenda o código do site para
– 5 dias por semana: seg, ter, qua, qui e sex
– 5 períodos: P1, P2, P3, P4 e P5
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
6/8
(4) Projeto Coloração 2
•
Implemente um algoritmo genético para seu problema abaixo:
E
C
E
B
F
F
B
A
D
E
A
D
B
Gefferson
F
F
B
C
A
A
B
Disciplina: Inteligência Artificial
C
E
D
Emanuela
F
Wisley
B
F
A
C
D
José Cláudio
C
D
C
D
E
Demetrius
Professor: Frederico Brito Fernandes
A
E
Thales
7/8
(4) Projeto Coloração 2
•
Implemente um algoritmo genético para seu problema abaixo:
A
B
B
A
C
E
D
E
F
C
F
D
E
B
C
D
E
F
Filipe
Disciplina: Inteligência Artificial
Henrique
F
D
F
E
A
C
A
A
B
Tiago
Johnny
B
D
F
C
E
Wágner
Professor: Frederico Brito Fernandes
D
B
C
A
Rivaldo
8/8