METODOS MATEMATICOS EN CIENCIAS DE LA COMPUTACION 07-08
UNIVERSIDAD DEL PAIS VASCO - EUSKAL HERRIKO UNIBERTSITATEA, UPV-EHU
Este trabajo práctico se deberá entregar para antes del 14 de marzo (viernes) del 2008. En caso de presentarlo en la convocatoria de septiembre, como fecha tope se considerará el día del examen de la convocatoria de septiembre. El trabajo consiste en dos partes:
lectura y resumen de al menos un artículo científico relacionado con las aplicaciones en el mundo real de los Heurísticos Estocásticos de Búsqueda;
comparativa de varios heurísticos de búsqueda: practicar (y "tocar tierra") con la intuitiva interfaz de la librería de heurísticos de optimización, LiO.
→
Forma
de entrega: documentación impresa dentro de un sobre transparente (en el que
meteré también vuestras entregas futuras), con vuestro nombre, e-mail de
contacto y grupo en la parte alta de la primera hoja. Grapad por un lado
las hojas correspondientes al resumen de la lectura, y por otro lado las
correspondientes a lo aprendido con LiO. Si la impresión ha podido ser a doble
cara, os lo agradecería.
Durante todo el curso realizaré entrevistas personalizadas
sobre el trabajo que habéis realizado con la mayor parte de la clase que
pueda. Os citaré por e-mail.
LECTURA Y RESUMEN DE ARTÍCULO CIENTÍFICO EN COMPUTACIÓN EVOLUTIVA
Puedes encontrar la versión Acrobat de los trabajos en el siguiente subdirectorio. También se pueden encontrar en Internet mediante distintos buscadores/servidores especializados en artículos científicos: buscador de Google para artículos científicos Google Scholar, servidor de artículos científicos "CiteSeer" de la Pittsburgh University. Todos ellos son trabajos publicados en revistas o conferencias internacionales del área.
Ten en cuenta que estos artículos que os propongo reflejan:
aplicaciones de los algoritmos genéticos a un problema concreto;
ampliciones y mejoras de los métodos heurísticos de búsqueda explicados en clase.
Si buscas en un buscador por aplicaciones de los Algoritmos Genéticos en casi cualquier área o problema, es muy posible que la encuentres. Si tienes curiosidad por alguna aplicación concreta y has encontrado un artículo de aplicación de los Genéticos en ella, enséñamelo e igual lo consideramos como artículo para que lo trabajes.
Para la elección del artículo os recomiendo la lectura del Abstract (o resumen general) de varios de ellos, ya que os dará una idea general de lo tratado por éste. Como podrás obervar, el esquema general de cualquier artículo científico sigue un patrón muy marcado: abstract - introducción - (revisión del estado del arte) - revisión de propuestas similares - decripción de la propuesta novedosa realizada - experimentación y sus resultados - conclusiones...
Como entregable de la práctica se redactará un documento técnico sobre lo leido-analizado, NO UNA TRADUCCION, en formato impreso de Word o Acrobat del artículo escogido. El entregable no debería exceder de las 2-3 páginas... La claridad, presentación y corrección ortográfica de esta redacción serán básicos para su evaluación, así como el análisis y respuesta a cada uno de los puntos que os planteo. El documento debe incluir y seguir los siguientes puntos:
Explicación del problema real que se trata de resolver
Explicación básica de la técnica y procedimiento utilizado en su resolución: ten en cuenta que no se utiliza un AG-canónico tal y como se explica en clase para resolver el problema OneMax... Trata de dar explicaciones básicas sobre la forma utilizada para representar los individuos de la búsqueda, la función objetivo concreta, operadores utilizados, reflexiones que hacen los autores sobre estas cuestiones... (y más cuestiones que consideres claves en el trabajo sobre la técnica utilizada). Relaciónalo con los conceptos aprendidos en las clases teóricas, y resalta dónde y cómo aparecen éstos en el artículo
Resultados obtenidos, niveles de satisfacción en la resolución del problema, conclusiones y análisis de los autores sobre el resultado
Cualquier otra cuestión o comentario que consideres oportuno
No hay que tenerlo "excesivo" respeto al inglés (de hecho no lo tenéis en todas las horas que pasáis en Internet), y menos todavía al inglés técnico utilizado en un área concreta de la ciencia: este "lenguaje dentro del lenguaje" (a veces casi una "jerga") es utilizado por investigadores en el área de todo el mundo y variadísimos orígenes, y no creo equivocarme al decir que está compuesto de no más allá de 200-300 palabras clave, alrededor de las que todo gira, y estando acompañada de un subconjunto reducido de verbos sencillos (to be, to have, to obtain, to study, to learn, to develop, to design...). No he encontrado en Internet una "pequeña guía" que abarcase un diccionario abreviado (o algo por el estilo) para este campo concreto de la "computación evolutiva": pero me he atrevido a crearos este breve diccionario-guía "ad-hoc", que aunque desordenado, creo que puede ayudar a familiarizarse con algunas palabras clave de este área de la ciencia y que os encontraréis en vuestros textos.
No se pide una comprensión total del trabajo y sus detalles. Ni mucho menos. ¿Es eso lo que creéis que buscamos? Sí buscamos una comprensión general de los objetivos del método presentado, su posible aplicación y resultados, descubrir cómo se mueve el mundo de la ciencia y las publicaciones científicas... No se busca que si no has entendido un párrafo concreto, te leas ese párrafo cuatro veces... Como ampliación voluntaria de la práctica se os propone el análisis y resumen de más de un artículo de entre los ofrecidos. Este esfuerzo será tenido en cuenta en la nota final de la asignatura y en la de esta práctica.
USO Y PRÁCTICA CON EL SOFTWARE LiO
Familiarización con la amigable y extraordinaria librería de heurísticos de optimización
LiO, realizado
por el grupo de Sistemas Inteligentes y Minería de Datos de la
Universidad de Castilla - La Mancha. Me parece
una herramienta excelente para adentrarse y "tocar tierra" en el campo
de los heurísticos de búsqueda, con una sencillez y elegancia de uso
dignas de mención. La librería puede utilizarse como plataforma-base de
programación de nuevas propuestas de algoritmos de búsqueda: nosotros
aún así utilizaremos su amigable y sencillo interfaz de usuario (en él
mismo veréis que bajo el término custom, se pueden programar
estas nuevas propuestas). He aquí la potencia de un lenguaje como Java,
que únicamente con un intérprete o runtime (JRE, JVM), es posible
ejecutar-interpretar este programa bajo cualquier sistema operativo:
PROMPT>>> java -jar LiO.jar
El fichero LiO.jar se encuentra en el subdirectorio
C:\LiO\deploy\ de los ordenadores de la facultad.
Una vez cargada la interfaz de trabajo de LiO, observáis que
tiene cuatro paneles-botones de parámetros principales (cada uno con sus
opciones de configurarlos):
el problema a optimizar - resolver (task)
el algoritmo de búsqueda a utilizar para ello (o motor de búsqueda) (search algorithm)
la condición de parada de dicho algoritmo (stop condition)
el tipo de output-información que queremos recibir acerca de la ejecución del algoritmo de búsqueda escogido sobre el problema a optimizar
El trabajo mínimo que os propongo consiste en que con una (o varias) función(es) de las que alberga LiO (en "task") y por medio de Algoritmos Genéticos, realicéis un estudio del efecto de los siguientes parámetros clave en un genético:
el tamaño de población
la probabilidad de cruce
la probabilidad de mutación
Probad
con 3 valores distintos para el tamaño de población (idea:
bajo-medio-alto¿?; decide tú mismo) ----- Realiza 5 ejecuciones para
cada posible valor, y quedaros con el tamaño
de población que mejor función objetivo media consiga (respecto a las 5
ejecuciones el que tenga mejor media de función objetivo, "Best Fitness", teniendo en cuenta la mejor
solución-individuo en cada ejecución). Esto es, en toda la práctica y
con cada algoritmo de búsqueda, toma las decisiones de con qué valor del
parámetro quedarte en base a la media del "fitness" de las 5
ejecuciones que hagas para cada valor del parámetro.
Una vez fijado el tamaño de población en el paso anterior,
probad con 3 valores distintos para la probabilidad de cruce
----- En base a 5 ejecuciones, quedaros con la probabilidad de cruce que
mejor función objetivo media (respecto a las 5 ejecuciones) consiga.
Una vez fijadas el tamaño de población y la probabilidad de
cruce en los pasos anteriores, probad con 3 valores distintos para la
probabilidad de mutación ----- En base a 5 ejecuciones, quedaros con
la probabilidad de mutación que mejor función objetivo media (respecto a
las 5 ejecuciones) consiga.
Compara ahora los resultados del "genético optimizado" con
los del EDA de LiO (es un UMDA explicado en clase y está dentro de la
carpeta "probabilistic"). Fíjate que el EDA de LiO tiene
únicamente un parámetro libre con el que "jugar". Para ser lo más justo posible en la
comparativa, ¿qué tamaño(s) de población le ponemos al EDA?
Rastrea en los demás algoritmos de búsqueda que ofrece LiO.
Te encontrarás al menos dos algoritmos que sí conoces, bien de esta
asignatura explicados por Abdel en el Tema 1 o de otra asignatura.
Inclúyelos en la comparativa que estamos haciendo:
-- MRHillClimbing ("Multiple Restart Hill Climbing", MRHC):
es un algoritmo de búsqueda de mejora iterativa clásico ("subida de la
colina, hill-climbing"), pero que realiza varias ejecuciones ("multiple
restart") empezando
desde distintos puntos aleatorios del espacio. Indaga en sus parámetros
("Configure"), y realiza según tu criterio-intuición-decisión una
"optimización de parámetros" similar a la que hemos hecho para el
Genético. Haz esta "optimización" únicamente para parámetros que
conozcas. Por lo menos, realiza esta optimización para el parámetro "startingPoints"
(cantidad de puntos aleatorios del espacio a partir de los cuales
comenzar una búsqueda hill-climbing voraz). Como con el Genético o el
EDA, toda decisión que tomes para el valor "idóneo" de cada parámetro
que sea en base a 5 ejecuciones... Dentro de los parámetros del MRHillClimbing, hay uno
denominado "HillClimbing": pincha en sus propiedades...
-- "Simmulated Annealing" (SA): los parámetros que tiene en su versión de
LiO los puedes observar siguiendo la transparencia del SA del
Tema 1: temperaturas inicial y final, factor de decrecimiento -
enfriamiento temperatura, número máximo de iteraciones del boucle-interno,
etc...
Inclúyelo en la comparativa optimizando sus parámetros en una línea
"similar" (dentro de lo posible) a cómo lo hemos hecho en los genéticos... ¿3 valores por
parámetros e ir optimizándolos uno a uno... tú mismo? En el SA los
parámetros y su comportamiento quizás no sea tan "intuitivo" como en los
genéticos... Como con el Genético o el EDA, toda decisión que tomes para
el valor "idóneo" de cada parámetro que sea en base a 5 ejecuciones...
Normas generales para realizar el trabajo:
la documentación a
entregar debe recoger los resultados de las experimentaciones y
sobre todo tus comentarios, tus conclusiones, sugerencias, etc.
Los resultados, bien resumidos en tablas-gráficas comprensibles.
Quiero tu opinión personal sobre esta primera práctica
(lectura artículo científico y LiO), así como sugerencias, mejoras
que me propones, cantidad de horas invertidas, etc.
escoge una función
binaria (task--"bitchain") de LiO de entre las que puedas ver
en esta web.
Lo haremos en binario ya que MRHillClimbing y SimmulatedAnnealing no
pueden trabajar en LiO con funciones continuas.
Estas funciones (Rosenbrock, Rastrigin, etc.) están originalmente definidas en un espacio de
números continuo: 3,14; 5,11; etc. Así, al decirle
que queremos optimizarlas en un espacio binario {0,1}, "bitchain", LiO
transforma los puntos del espacio numérico continuo a este espacio
binario: y le debemos decir con cuántos bits (bits per number)
queremos codificar una solución continua, a una binaria. (más
explicaciones sobre esta cuestión, en párrafos posteriores)
Estas funciones aparecen en LiO en maximización, cuando en la web indicada aparecen en minimización
(es lo de menos, max(z) ≈ min(-z)), pero teniendo el óptimo global en el
mismo punto-vector-solución (x*). !Ojo! Cuando se maximiza,
-21 es mejor que -27...
Ten en cuenta que por defecto LiO trabaja con 100 variables por
función ("size of the task-problem-function"). Esto se puede
modificar al configurar el "task". Esto afecta mucho en los tiempos
de ejecución... ¿no? Os recomiendo reducir el número de variables
entorno a 20-30...
escoge una función que
te dé juego y para la que no sea sencillo encontrar su óptimo
global. La solución óptima [X1*,
X2*, ..., Xsize*)] y el valor
óptimo de su función objetivo (z* = f (X1*,
X2*, ..., Xsize*)) aparecen en la
web anterior.
Identifica las funciones que aparecen en esta web y que a la vez las
tiene LiO disponibles como "bitchain".
para todo el trabajo,
escoge unos criterios de parada concretos y que sean los mismos para
todos los algoritmos de búsqueda. Fíjate en las 5 condiciones de
parada de LiO: con cumplirse una de ellas, la
búsqueda para. Si no se cambian, es habitual parar por llegar a 1000
iteraciones (generaciones).
Para que la comparativa sea más rica
y dé más juego y se marquen diferencias, quizás interese
ampliar-alargar las condiciones de parada...
¿Te parece "justa", tal y como os la propongo, la comparativa de
genéticos y UMDA, respecto a SA y MRHC...(los primeros basados en
"poblaciones de soluciones", los segundos basados en la idea de
mejorar-iterar una única solución?
Algunas características generales de LiO:
Dentro del "output" de
una ejecución, LiO por defecto no muestra la mejor solución a la que
se ha llegado. Al activar la opción "Show
Best individual" LiO nos muestra el mejor
individuo-solución encontrado en la búsqueda [X1,
X2...Xsize]: en él se puede observar variable a variable cuán
lejos-cerca se ha quedado del óptimo global (que tú sí conoces por
la web anterior, pero LiO durante la ejecución, obviamente no: él
optimiza "ciegas", sin saber a dónde va, sólo guiado por la función
objetivo).
Esto tiene más sentido hacerlo cuando la función está definida en
continuo, pudiendo ver cada variable Xi de la mejor
solución encontrada "a cuánto" se ha quedado del óptimo global de la
función continua: pero al trabajar en binario (porque HillClimbing y
SimmulatedAnnealing no pueden trabajar en continuo en LiO), vemos
números binarios que son una transformación de los números continuos
originales.
Puedes observar que LiO tiene una serie de problemas por
defecto: tanto codificados como una ristra-array de variables binarias
(como las explicaciones que os damos en las clases teóricas: bitchain,
por
ejemplo OneMax), con variables continuas (contchain), o codificados mediante
permutaciones (por ejemplo TSP).
Una
vez fijado el algoritmo de búsqueda, fíjate en que se pueden modificar
distintos parámetros de la función-"task" (size≈número-cantidad de
variables (del array) de dicha función,
etc.): ojo, por defecto muchas funciones tienen 100 variables, y
en algunas ocasiones puede esto requerir unos tiempos de cómputo muy
altos, y por otro lado son muchas para observar visualmente la mejor solución
encontrada en la búsqueda ("showbestindividual")... te recomiendo reducir el número de
variables, quizás a 20-30.
OneMax: es muy interesante ver cómo cambia el vector de
valores de la mejor solución encontrada
("showbest individual") en OneMax, cuando esta función está
definida bien en binario ("bitchain") o bien en continuo ("contchain").
Con el resto de
funciones que por definición son continuas (Rastrigin, Griewank...)
y al transformarlas a binario, fíjate en cómo
se "alarga" la mejor solución encontrada en el output, "Show Best
individual", que al final tendrá tantos bits como size x
bitspernumber. Obviamente, cuántos más bits para realizar dicha
transformación de numérica continua a ristra binaria ("bitspernumber"), mejor resolución y
precisión en la representación.
Prueba por ejemplo a optimizar una función continua con
size=2
(número de variables) y bitspernumber=10.
Si activas la opción "showbestindividual" verás algo así:
Best Individual = [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 1, 1, 1]
, donde los 10 primeros bits se refieren a la primera variable y los
10 últimos a la segunda .
Una pequeña información
sobre la marcha de la búsqueda, según progresa la ejecución
(no cuando ya ha parado-acabado), nos la ofrece la opción "Show Progress".
Para alguna de las
funciones observarás que encontrar el óptimo global no es nada
sencillo: ni con grandísimos tamaños de población, ni al
"empequeñecer" la función al limitarla a pocas variables, etc... Los
juegos y pruebas que se pueden realizar me parecen infinitos: cuánto
se aproxima la búsqueda al óptimo global aumentando el tamaño de la
población, o variando la probabilidad de cruce, el efecto de una
probabilidad de mutación cercana a 1, o el de la probabilidad de
cruce cercana a 0... ; cómo varía la dificultad del problema al
cambiar el tamaño de la función a optimizar (size, o número de variables
que la definen); efectos de los distintos criterios de parada y el juego
que nos dan para acercarnos más al óptimo al disponer de más/menos
cómputo; estudio de la distinta información de la salida (number of
evaluations-iterations to best); etc.
Mediante el botón "Show"
puedes obtener distintas gráficas acerca de la evolución de la última
búsqueda ejecutada.
En el subdirectorio que se genera al descomprimir LiO hay varios documentos que ayudan en su comprensión. Quizás el más sencillo, que como amena introducción puede servir, es su tutorial de uso: LiOUseTutorial.pdf