IA Pauta 2Certamen 2004

Pauta Inteligencia Artificial
Certamen # 2
Profesor: Mar´ıa Cristina Riff
7 de Mayo de 2004
Nombre y Rol:
Instrucciones:
Escriba las respuestas con tinta para tener derecho a eventuales recorrecciones.
• Tiempo: Partes I y II : 70 minutos; Parte III: 30 minutos.
• No se permite ning´
un material adicional.
• Parte IV, a entregar en Secretar´ıa de Inform´
atica (sra. Lidia Ya˜
nez) el Lunes 10 deMayo 2004 antes de
las 9h05. No se acepta el env´ıo por e-mail.

1. Parte I: Materia (60 puntos)
1.

Considere un HC que permite soluciones infactibles. ¿ Cu´al es el vecindario de la candidata a soluci´on
[1, 0, 0, 1, 1] en el problema de la mochila?, explique (7 p.)
Depender´a del movimiento que use HC. Por ejemplo si el movimiento es tipo switch el vecindario
estar´a dado por [0, 0, 0, 1, 1],[1, 1, 0, 1, 1], [1, 0, 1, 1, 1], [1, 0, 0, 0, 1], [1, 0, 0, 1, 0].
Si el movimiento es agregar un objeto, el vecindario es [1, 1, 0, 1, 1], [1, 0, 1, 1, 1].

2.

¿Cu´al es la mejor combinaci´on entre exploraci´on y explotaci´on? (7 p.)
Comenzar con exploraci´on porque le permite al algoritmo diversidad e ir concentr´andose en explotaci´on
para lograr la convergencia

3.

Escriba un algoritmogreedy para resolver el problema de minimizar el n´
umero de colores al colorear un
mapa (9 p.)
Representaci´on: Color de la regi´on i.
Regla: Elegir la regi´on a´
un sin colorear con menor dominio y asignarle el color factible m´as usado
hasta ahora
Pseudoc´odigo.

Inteligencia Artificial, Departamento de Inform´atica, UTFSM
4.

Nombre y Rol

Explique si es verdadero o falso:
“Las Metaheur´ısticastratan de encontrar el Mejor o´ptimo local” (7 p.)
Verdadero, las metaheur´ısticas no pueden asegurar la obtenci´on del o´ptimo global, sin embargo
tratan de encontrar el Mejor o´ptimo local, que en el caso ideal corresponde al o´ptimo global
“El cruzamiento en un punto no es u
´til para la resoluci´on de problemas de optimizaci´on” (7 p.)
Falso, cuando el problema no tiene restricciones es unabuena Metaheur´ıstica.
“La mutaci´on de un algoritmo gen´etico standard es un algoritmo de b´
usqueda local” (7 p.)
Falso, la b´
usqueda local trata de optimizar la b´
usqueda en un vecindario, la mutaci´on no tiene
objetivo de optimizaci´on.

5.

¿ Qu´e alternativas tiene para manejar las restricciones en Simulated Annealing?. Ejemplifique (7 p.)
Funci´on objetivo + Penalizaci´on, Movimiento,Representaci´on, Descarte posterior al movimiento previa
condici´on de aceptaci´on.

6.

Compare Simulated Annealing con Tabu Search (9 p.):
Aspectos comunes: B´
usqueda Local dentro de un vecindario, requieren una soluci´on completa inicial
Diferencias: Criterio de aceptaci´on del movimento y forma de elegir soluciones candidatas
Mecanismo de exploraci´on: En SA la temperatura, en TS la forma de elegirel siguiente movimiento.

Inteligencia Artificial, Departamento de Inform´atica, UTFSM

Nombre y Rol

2. Parte II: Papers (15 p.)
1.

Explique la forma de comparar los resultados de las diferentes metaheur´ısticas usadas para 2D Packing
Problem (5 p.)
(aqui se refiere a las formas de medir ”en numeros”, las tablas que miden? y como las comparan en el
paper?..)
En el paper el objetivo principal scomparar la actuacin de algoritmos gen´eticos, los de evoluci´on Ingenua
y Simulated Annealing que sean pequeos para llevarlos a problemas de embalaje grandes. Para lo cual
se usan dos metaheur´ısticas distintas:
2 La t´ecnica BL
3 La t´ecnica BLF, la cual es m´as sofisticada, y computacionalmente m´as cara.
El resultado de algoritmos metaheur´ısticos se compara con estas dos t´ecnicas as como conotras t´ecnicas
como Hill Climbing y la de b´
usqueda aleatoria (TS)
Se compara los AG, con los algoritmos de evoluci´on ingenua. Los resultados indican que la actuaci´on de los algoritmos h´ıbridos es fuertemente dependiente de la naturaleza de la rutina, de colocaci´on
y el tamao del problema
1.- los m´etodos meta heur´ısticos que usan el decodificador BL, son comparados
2.- La misma...