INF1771 - INTELIGÊNCIA ARTIFICIAL
LISTA DE EXERCÍCIOS 2
Aluno:
1
. Realize uma busca utilizando o algoritmo A* para encontrar o melhor caminho para
chegar a Bucharest partindo de Lugoj. Construa a árvore de busca criada pela execução do
algoritmo apresentando os valores de f(n), g(n) e h(n) para cada nó. Utilize a heurística de
distância em linha reta.
Arad
366 Mehadia
0 Neamt
241
234
380
100
Bucharest
Craiova
Drobeta
Eforie
160 Oradea
242 Pitesti
161 Rimnicu Vilcea 193
Fagaras
Giurgiu
Iasi
176 Sibiu
253
329
199
374
80
77
Timisoara
226 Vaslui
244 Zerind
151 Urziceni
Lugoj
Hirsova
2
. Utilize o algoritmo de busca local Hill Climbing na rede mostrada abaixo para chegar ao nó
em formato de estrela (n0) partindo do nó n18. Mostre a sequencia de nós visitados
durante a execução do algoritmo. Utilize a distancia em linha reta aproximada para
calcular a função heurística. Caso o algoritmo fique preso em um mínimo local, utilize o a
variação do Hill Climbing com reinicialização aleatória.
2
3
23
1
2
12
8
5
5
5
1
0
10
10
10
3
. O grafo abaixo mostra a ligação entre 5 cidades e as respectivas distâncias em
quilômetros:
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.
4
. Considere a seguinte equação:
2 3
x + y + w + z = 185
5
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.
5
. Problema SAT
Seja x = (x1, x2,..., xn) um vetor de n variáveis booleanas (i.e. cada variável xi assume um dos
valores em {0,1}). Seja f(x) = [c1(x) ∧ c2(x) ∧,..., ∧ cm(x)] uma fórmula normal conjuntiva com
m cláusulas, onde cada cláusula cj(x) é uma disjunção de literais, e um literal é uma das
variáveis booleanas ou sua negação.
Por exemplo, considere um vetor com três variáveis x = (x1, x2, x3). Um exemplo de fórmula
normal conjuntiva seria:
f(x) = [(x1)∧ (¬x2) ∧ (x2 ∨ ¬x3) ∧ (x1 ∨ ¬x3)]
Composta pelas seguintes cláusulas:
c1(x) = (x1)
c2(x) = (¬x2)
c3(x) = (x2 ∨ ¬x3)
c4(x) = (x1 ∨ ¬x3)
Uma fórmula é dita satisfatível quando existe uma atribuição de valores para (x1, x2,..., xn)
tal que todas as cláusulas da fórmula sejam satisfeitas, isto é, cj(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 x1, x2 e x3 que tornam verdadeiras todas as quatro cláusulas da fórmula.
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 = (x1, x2,..., xn) e uma dada fórmula f(x) = [c1(x) ∧ c2(x) ∧,..., ∧ cm(x)], proponha
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.