Primeira Lista de Exercícios

Prévia do material em texto

PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS
Instituto de Informática — Sistemas de Informação — Unidade Barreiro
Prof.: Saulo Augusto de Paula Pinto
Disciplina: Inteligência Artificial
2o Semestre de 2014
Primeira Lista de Exercícios
Revisão e preparação para a prova do dia 16/09/2014
Você considera que algum dos agentes apresentados em sala de aula e no Capítulo 2 do livro-texto passaria, sozinho, no teste de Turing? E se houvessem vários agentes de um mesmo tipo, eles poderiam passar? 
Critique o teste de Turing como um padrão para avaliar a inteligência de um sistema de software. Turing errou ao propor o teste que, posteriormente, receberia seu nome?
Ações reflexas (como retirar sua mão de uma chapa de aço quente ou afastar um mosquito impertinente) são racionais? São inteligentes?
Mostre as árvores de busca geradas pelos algoritmos da busca gulosa e A* para o problema de, partindo da Origem, alcançar o Destino:
�
Pense e descreva, em linhas gerais, uma maneira de resolver o problema do caixeiro viajante utilizando algoritmos genéticos. Como você codificaria as soluções como strings de bits?
Considere o seguinte relevo que representa um espaço de estados em que um máximo global deve ser alcançado:
Responda:
Os algoritmos Hill Climbing (versão básica, simples) e o Simulated Annealing, caso o ponto inicial seja em algum lugar entre os pontos D e E, alcançariam o máximo global?
Suponha que um algoritmo genético seja aplicado para tentar maximizar a função representada na figura. A população provavelmente estaria distribuída no espaço de soluções após um determinado número de gerações suficiente para uma “boa” convergência do AG, em torno dos máximos B, D, F e H? Explique.
Com um decaimento de temperatura adequado, o Hill Climbing alcançaria o máximo global H? Porquê?
Compare as características principais dos algoritmos de busca vistos em sala no tocante a: em que situações (problemas) podem ser aplicados ou são mais adequados? Quais os pontos fortes? Quais os pontos fracos?
O Hill Climbing e o Simulated Annealing poderiam ser aplicados a problemas como o do Caixeiro Viajante? Como?
Um AG pode se aplicado a problemas do tipo daquele de encontrar o melhor caminho entre Arad e Bucareste? Como?
Qual a importância da função de fitness para os algoritmos genéticos?
Para que serve o operador de mutação?
Como a programação genética (PG) difere dos AG? Explique as diferenças fundamentais e as diferenças que decorrem delas.
Considerando o grafo abaixo como uma instância do problema do caixeiro viajante, faça o que é proposto abaixo sabendo que deve-se utilizar algoritmos genéticos para resolvê-lo:
Proponha uma maneira de codificar os cromossomos (indivíduos).
Defina uma função de adequação (fitness) para avaliar a qualidade dos cromossomos.
Gere dois cromossomos “aleatoriamente” e avalie a adequação deles.
Realize o cruzamento entre os cromossomos gerados no item acima. 
Aplique uma mutação em um “gene” dos cromossomos. 
Aplique a função de fitness nos descendentes gerados verificando se a solução encontrada é melhor ou não.
E
D
C
B
�
Destino
h = 0
g = 400
g = 300
g = 200
g = 500
g = 300
g = 100
g = 100
g = 400
h = 500
h = 800
h = 1100
h = 1200
h = 1400
h = 1500
Origem
_1226384229/ole-[42, 4D, 2E, 08, 01, 00, 00, 00]