Algoritmos

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) b) c) d) e) f) Proponha uma maneira de codificar os cromossomos. Defina uma função de aptidão para avaliar a qualidade dos cromossomos. Gere dois cromossomos e avalie a aptidão deles. Realize o cruzamento entre os cromossomos. Aplique uma mutação em um gene dos cromossomos. 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) b) c) d) e) f) Proponha uma maneira de codificar os cromossomos. Defina uma função de aptidão para avaliar a qualidade dos cromossomos. Defina como o método de seleção dos pais será utilizado. Defina os operadores genéticos de recombinação e mutação. Gere uma população inicial de 4 cromossomos e avalie a aptidão deles. 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 = (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