INF1771 - INTELIGÊNCIA ARTIFICIAL
LISTA DE EXERCÍCIOS 2
Aluno:
1.
O grafo abaixo mostra a ligação entre 5 cidades e as respectivas distâncias em
quilômetros:
8
9
Tem-se um problema onde é necessário passar por todas as cidades, apenas uma vez.
O objetivo é encontrar uma rota de menor custo usando um algoritmo genético.
a) Proponha uma maneira de codificar os cromossomos.
b) Defina uma função de aptidão para avaliar a qualidade dos cromossomos.
c) Gere dois cromossomos e avalie a aptidão deles.
d) Realize o cruzamento entre os cromossomos.
e) Aplique uma mutação em um gene dos cromossomos.
f) Aplique a função de aptidão nos descendentes gerados verificando se a solução
encontrada é melhor ou não.
2) Considere a seguinte equação:
2x + y² + w = 52
a) Proponha uma maneira de codificar os cromossomos.
b) Defina uma função de aptidão para avaliar a qualidade dos cromossomos.
c) Defina como o método de seleção dos pais será utilizado.
d) Defina os operadores genéticos de recombinação e mutação.
e) Gere uma população inicial de 4 cromossomos e avalie a aptidão deles.
f) Aplique os operadores de recombinação e mutação sobre essa população para gerar
uma nova geração, em seguida avalie a aptidão da nova geração. Repita esse processo
por 8 gerações ou até que a solução do problema seja encontrada.
3) Problema SAT
Seja x = (x
valores em {0,1}). Seja f(x) = [c
m cláusulas, onde cada cláusula c
variáveis booleanas ou sua negação.
1
, x
2
,..., x
n
i
) um vetor de n variáveis booleanas (i.e. cada variável x assume um dos
(x) ∧ c (x) ∧,..., ∧ c (x)] uma fórmula normal conjuntiva com
(x) é uma disjunção de literais, e um literal é uma das
1
2
m
j
1 2 3
Por exemplo, considere um vetor com três variáveis x = (x , x , x ). Um exemplo de fórmula
normal conjuntiva seria:
1 2 2 3 1 3
f(x) = [(x )∧ (¬x ) ∧ (x ∨ ¬x ) ∧ (x ∨ ¬x )]
Composta pelas seguintes cláusulas:
c
1
c
2
c
3
c
4
(x) = (x
1
)
(x) = (¬x
2
)
(x) = (x
(x) = (x
2
1
∨ ¬x
∨ ¬x
3
3
)
)
1 2 n
Uma fórmula é dita satisfatível quando existe uma atribuição de valores para (x , x ,..., x )
tal que todas as cláusulas da fórmula sejam satisfeitas, isto é, c (x) = 1 para j=1,...,m. No
exemplo acima, f(x) é satisfatível e x = (1, 0, 0) é uma possível atribuição de valores para as
variáveis x , x e x que tornam verdadeiras todas as quatro cláusulas da fórmula.
j
1
2
3
O problema SAT consiste em: dada uma fórmula, responder se a fórmula é satisfatível ou
não. Encontrar uma atribuição de valores que satisfaçam uma dada fórmula é uma tarefa
que pode ser formulada como um problema de busca. Assim, para um conjunto qualquer
de variáveis x = (x , x ,..., x ) e uma dada fórmula f(x) = [c (x) ∧ c (x) ∧,..., ∧ c (x)], proponha
1 2 n 1 2 m
uma solução para o problema SAT como Algoritmos Genéticos.
Para isso, use o seguinte caso base:
(¬x ∨ ¬z ∨ y) ∧ (¬y ∨ z) ∧ (x ∨ ¬z) ∧ (y) ∧ (¬y ∨ ¬x ∨ ¬w ∨ z)
a) Proponha uma maneira de codificar os cromossomos.
b) Defina uma função de aptidão para avaliar a qualidade dos cromossomos.
c) Defina como o método de seleção dos pais será utilizado.
d) Defina os operadores genéticos de recombinação e mutação.
e) Gere uma população inicial de 4 cromossomos e avalie a aptidão deles.
f) Aplique os operadores de recombinação e mutação sobre essa população para gerar
uma nova geração, em seguida avalie a aptidão da nova geração. Repita esse processo
por 8 gerações ou até que a solução do problema seja encontrada.