Hoy me he leído de muevo el sistema de evaluación de la asignatura y me he dado cuenta que, al no entregar a tiempo la primera de las actividades voluntarias especificadas he pasado automáticamente al segundo sistema de evaluación en el que tengo que realizar dos actividades obligatorias y un trabajo final a elegir de una oferta de nueve.
El sistema de evaluación, indicado por el equipo docente al principio del curso (allá por el mes de octubre de 2007) es el siguiente:
A continuación se describen un conjunto de directrices a tener en cuenta para el eficaz seguimiento y evaluación del curso. Así, el alumno dispone de dos modalidades de trabajo para poder superar el curso.
La primera corresponde a una evaluación continua (recomendada) en la que es necesario realizar una serie de actividades voluntarias programadas a lo largo del semestre. Es muy importante mencionar que el alumno que se acoja a esta modalidad deberá entregar todas las actividades programadas (no se evaluará en esta opción la entrega parcial de las mismas) y además hacerlo en el intervalo de tiempo asignado a cada una de ellas. Fecha de finalización de esta modalidad de trabajo: 31 de mayo (fecha tope de entrega de la última actividad voluntaria).
La segunda opción consiste en elaborar una serie de actividades obligatorias y un trabajo final. Consúltese la carpeta “Trabajos Fin de Asignatura” dentro de la pestaña de “Material del Estudio”. Si el alumno hubiera realizado algunas de las actividades voluntarias, las mismas se tendrían en cuenta en esta segunda opción para la evaluación del curso. Fecha de finalización de esta modalidad de trabajo: 30 de junio.
MUY IMPORTANTE: Aquellos alumnos que no respeten los plazos de entrega de la modalidad de trabajo elegida, no podrán aprobar el curso.
Contributed by Severino Fernández Galán
Así pues debo de realizar las actividades obligatorias y el trabajo. Para averiguar exactamente qué tengo que hacer tengo que leerme el documento donde se especifican dichas actividades y trabajo.
Tras leer detenidamente el documento, ya tengo claras las dos actividades obligatorias que debo realizar. En cuanto a la primera actividad:
La actividad de aprendizaje voluntaria del tema 3 (algoritmos genéticos) consiste en programar un algoritmo genético básico para el cálculo del valor óptimo de funciones reales definidas sobre varias variables. En cuanto a las directrices útiles que menciona hay un archivo que he obtenido del lugar indicado donde se dan las pautas de implementación con los ficheros asociados al mismo.
En cuanto a la segunda actividad:
He hecho una revisión de los problemas propuestos por las diferentes actividades voluntarias, que no he hecho: problema de las ocho reinas, problema de la mochila, la función de Ackley (una función multimodal) y cualquiera de las funciones multimodales disponible en el apéndice B del libro base (Introduction to Evolutionary Computing por A. E. Eiben y J. E. Smith, Springer, 2003), pp. 268-269. Ya hice un pequeño catálogo de esas funciones en la revisión de la bibliografía hace un mes.
Yo por mi parte me he acordado del capítulo 2 sobre computación evolutiva, pp. 47-78 del libro Genetic Fuzzy Systems – Evolutionary tuning and learning of fuzzy knowledge bases de Oscar Cordon et al. Para ilustrar el funcionamiento del algoritmo genético básico y todas sus modificaciones y las estrategias evolutivas utiliza un antiguo problema planteado por Jakob Bernoulli en 1696 llamado brachystochrone. Para el caso de la programación genética (genetic programming) se usa un problema de bloques (Block Stacking Problem)
Para hacer el trabajo que completa la evaluación de la asignatura hay nueve propuestas, de las que voy a tener que escoger una. Voy a ir repasando cada una de las propuestas para conocerlas más en profundidad y tomar una decisión. Empezamos con la primera:
1) ESTUDIO DE LOS MÉTODOS TEÓRICOS PARA EL ANÁLISIS DE ALGORITMOS EVOLUTIVOS
Clasificar y explicar los diferentes métodos teóricos para el análisis del comportamiento de un algoritmo evolutivo, indicando ventajas e inconvenientes de cada método.
Se recomienda partir del esquema seguido en el tema 11 del libro “Introduction to Evolutionary Computing” de Eiben y Smith, así como de las referencias bibliográficas que allí aparecen. Como lecturas iniciales se recomiendan los temas 1, 2 y 11 del libro mencionado. Se valorará el intento por parte del alumno de sugerir y explicar un método novedoso que persiga mejorar alguno de los inconvenientes de los métodos actuales.
Estos son los contenidos del capítulo principal para este trabajo que habría que mirar para este trabajo de investigación:
Puesto que habría que seguir la estructura del capítulo es útil conocer el sentido que le ha dado los autores al capítulo en el apartado 11.1 Aims of this Chapter:
De la lectura de ese párrafo se pueden extraer varias conclusiones. La primera que el estudio teórico de los algoritmos evolutivos requiere el empleo intensivo de matemáticas. La segunda es que estos algoritmos entran dentro de la categoría de sistemas complejos, que es un campo muy de actualidad en biología y física. La tercera es que el capítulo solamente hace un estudio superficial basándose en una división de la representación de los problemas en discretos (que son los que más de han estudiado, probablemente porque históricamente los algoritmos genéticos con representación binaria han sido los primeros en estudiarse) y continuos. Finalmente parece interesante el resultado teórico NFL. Las tres referencias bibliográficas que menciona explícitamente son las siguientes:
– [126] A.E. Eiben and G. Rudolph. Theory of evolutionary algorithms: a bird’s eyes overview. Theoretical Computer Science, 229:1 2 pp. 3-9. 1999.
– [50] H.G Beyer. The theory of Evolution Strategies. Springer, Berlin, Heidelberg. New York 2001.
– [411] M. D. Vose. The Simple Genetic Algorithm. MIT Press. Cambridge MA, 1999.
También se havcen mención a otras referencias que aparecen al final del capítulo, en el apartado 11.10 Further reading, que son las siguientes:
– A.E. Eiben and G. Rudolph. Theory of evolutionary algorithms: a bird’s eyes overview. Theoretical Computer Science, 229:1-2 pp. 3-9. 1999.
– L. Kallel, B. Naudts, and A. Rogers (editors) Theoretical Aspects of Evolutionary Computing. Springer, Berlin, Heidelberg. New York 2001. A collection of accessible introductory texts by experts in the field.
– C. Reeves and J. Rowe. Genetic Algorithms: Principles and Perspectives. Kluwer, Norwell MA, 2002.
– H.G Beyer. The theory of Evolution Strategies. Springer, Berlin, Heidelberg. New York 2001.
– W. M. Spears. Evolutionary Algorithms: the role of mutation and recombination. Springer, Berlin, Heidelberg. New York 2000.
– M. D. Vose. The Simple Genetic Algorithm. MIT Press. Cambridge MA, 1999.
– D.E. Goldberg. The Design of Innovation: Lessons from and for Competent Genetic Algorithms (Genetic Algorithms and Evolutionary Computation) Kluwer Academic Press, 2002.
Estudiamos un poco ahora a segunda propuesta de trabajo para evaluar la asignatura de computación evolutiva:
2) ESTUDIO DE LOS TIPOS DE REPRESENTACIÓN DE INDIVIDUOS EN ALGORITMOS EVOLUTIVOS
Enumerar, siguiendo un orden histórico, los diferentes tipos de representación de individuos que se han usado en algoritmos evolutivos. Relacionar cada representación con aquellos dominios para los que resulta adecuada. Sugerir nuevos tipos de representación e indicar problemas o dominios en los que su utilización sería ventajosa. Definir cómo se podrían implementar las fases de inicialización, selección de padres, recombinación, mutación y selección de supervivientes en los algoritmos evolutivos que se basaran en los nuevos métodos de representación sugeridos.
Como lecturas iniciales se recomiendan los temas 2, 3, 4, 5, 6 y 7 del libro “Introduction to Evolutionary Computing” de Eiben y Smith, así como las referencias bibliográficas allí presentes.
Los capítulos del libro que se mencionan corresponden a todas las ramas de algoritmos evolutivos que se tratan en el temario de la asignatura, excepto el capítulo 2 que es una introducción que da la visión general de todos los tipos de algoritmos:
2 What is an Evolutionary Algorithm?
3 Genetic Algorithms
4 Evolution Strategies
5 Evolutionary Programming
6 Genetic Programming
7 Learning Classifier Systems
Yo creo que como estrategia sería conveniente leerse en primer lugar el apartado Aims of this chapter de todos y cada uno de esos capítulos y luego para conocer las referencias bibliográficas que recomiendan los autores para ampliar información leerse directamente el apartado Recommended Reading for this Chapter.
Por lo que he podido ver en un primer vistazo, aunque algunas de las variantes de algoritmos evolutivos tienen un mecanismo principal de representación del conocimiento derivado de su origen histórico, alguno de ellos, en especial, los algoritmos genéticos han ido explorando nuevas formas de representación adaptadas al problema en cuestión al que se aplican derivadas de un conocimiento previo del problema y con el diseño añadido de nuevos operadores de mutación y combinación adaptados al mecanismo de representación diseñados para sacar el máximo partido a los mecanismos subyacentes de exploración y explotación del dominio de soluciones del problema.
Los algoritmos genéticos tienen como mecanismo de representación las codificaciones binarias. Estas codificaciones se han extendido al uso de vectores de números reales. En el caso de las estrategias evolutivas y la programación evolutiva los vectores de números reales han sido y son su mecanismo de representación. La programación genética representa un salto en los mecanismos de representación, utilizando estructuras de árbol. Estas estructuras son mecanismos de representación de lenguajes formales de programación y por eso se utilizan en este caso, ya que son precisamente programas de ordenador lo que se hace evolucionar. En el caso de los sistemas clasificadores, que son sistemas de aprendizaje automático, el mecanismo de representación son conjuntos de reglas. Si bien los conjuntos de reglas se pueden extraer de estructuras de árbol, estos conjuntos de reglas no tienen porque corresponder a dichas estructuras.
3) ESTUDIO DE UNA DE LAS FASES DE UN ALGORITMO EVOLUTIVO
Explicar las diferentes formas existentes de realizar una cualquiera de las fases de las que consta un algoritmo evolutivo: inicialización, selección de padres, recombinación, mutación o selección de supervivientes, partiendo de los contenidos y referencias bibliográficas que aparecen en el libro “Introduction to Evolutionary Computing” de Eiben y Smith.
Dependiendo de la fase elegida de un algoritmo evolutivo, se recomiendan las siguientes lecturas iniciales mínimas de dicho libro:
• Inicialización: temas 2, 3, 4, 5, 6, 7 y 10
• Selección de padres: temas 2, 3, 4, 5, 6 y 7
• Recombinación: temas 2, 3, 4, 5, 6 y 7
• Mutación: temas 2, 3, 4, 5, 6, 7 y 10
• Selección de supervivientes: temas 2, 3, 4, 5, 6 y 7
Se valorará el intento por parte del alumno de sugerir y explicar una forma novedosa de llevar a cabo la fase estudiada, de manera que se analicen las posibles ventajas que dicha técnica novedosa podría aportar.
4) ESTUDIO DE LAS TÉCNICAS DE CONTROL DE PARÁMETROS EN ALGORITMOS
EVOLUTIVOS
Clasificar y explicar las diferentes técnicas existentes para el control de los parámetros de un algoritmo evolutivo. Analizar las ventajas e inconvenientes de cada técnica particular. Se recomienda partir del esquema seguido en el tema 8 del libro “Introduction to Evolutionary Computing” de Eiben y Smith, así como de las referencias bibliográficas que allí aparecen.
Como lecturas iniciales se recomiendan los temas 2, 3, 4, 5, 6, 7 y 8 del citado libro. Se valorará el intento por parte del alumno de sugerir y explicar una técnica novedosa de control de parámetros, que persiga mejorar alguno de los inconvenientes de las técnicas actuales.
El capítulo 8 del libro tiene el siguiente contenido:
En el primer apartado Aims of this chapter los autores dicen lo siguiente:
En cuanto a las referencias bibliográficas, aparecen un montón a lo largo de los apartados del capítulo y sería una tarea ingente indicarlas aquí. No obstante en el último apartado, Recommended Reading for this Chapter tenemos las recomendadas una vez leído el capítulo por parte de los autores:
5) ESTUDIO DE LAS TÉCNICAS PARA EL MANTENIMIENTO DE LA DIVERSIDAD EN ALGORITMOS EVOLUTIVOS
Clasificar y describir las técnicas existentes para el mantenimiento de la diversidad, tanto en algoritmos evolutivos cuya función de adaptación está asociada a un solo objetivo como en aquellos algoritmos evolutivos que se utilizan en problemas multiobjetivo. Se recomienda partir del esquema seguido en el tema 9 del libro “Introduction to Evolutionary Computing” de Eiben y Smith, así como de las referencias bibliográficas que allí aparecen.
Como lecturas iniciales se recomiendan los temas 2, 3, 4, 5, 6, 7 y 9 del citado libro. Se valorará el intento por parte del alumno de sugerir y describir una técnica novedosa para el mantenimiento de la diversidad en algoritmo evolutivos, que persiga mejorar alguno de los inconvenientes de las técnicas actuales.
El tema 9 del libro que hay que utilizar como guía tiene la siguientes estructura de contenidos:
En su primer apartado, Aims of this Chapter, los autores presentan el tema de la siguiente manera:
En cuanto a la bibliografía que se menciona al final del capítulo, en el apartado Recommended Reading for this Chapter tenemos en este caso lo siguiente:
6) ESTUDIO DE LOS ALGORITMOS MEMÉTICOS
Definir en qué consiste un algoritmo memético básico y clasificar las distintas formas existentes de implementar dicho algoritmos, explicando las ventajas e inconvenientes de cada tipo de implementación.
Se recomienda partir del esquema seguido en el tema 10 del libro “Introduction to Evolutionary Computing” de Eiben y Smith, así como de las referencias bibliográficas que allí aparecen. Como lecturas iniciales se recomiendan los temas 2, 3, 4, 5, 6, 7 y 10 del citado libro.
Se valorará el intento por parte del alumno de sugerir y describir alguna variante de algoritmo memético, que persiga mejorar alguno de los inconvenientes de los algoritmos meméticos actuales.
El capítulo 10 del libro que se menciona como guía de este tema tiene los siguientes contenidos:
En la introducción del capítulo, apartado Aims of this Chapter los autores dicen lo siguiente:
Y finalmente en cuanto a las lecturas posteriores para ampliar conocimientos, en el apartado Recommended Reading for this Chapter, tenemos lo siguientes:
7) ESTUDIO DE LAS TÉCNICAS PARA EL MANEJO DE RESTRICCIONES EN ALGORITMOS EVOLUTIVOS
Clasificar y explicar las técnicas existentes para el tratamiento de problemas con restricciones mediante algoritmos evolutivos, identificando las ventajas e inconvenientes de dichas técnicas.
Se recomienda partir del esquema seguido en el tema 12 del libro “Introduction to Evolutionary Computing” de Eiben y Smith, así como de las referencias bibliográficas que allí aparecen. Como lecturas iniciales se recomiendan los temas 2, 3, 4, 5, 6, 7 y 12 del citado libro. Se valorará el intento por parte del alumno de sugerir y describir una técnica novedosa
para el manejo de restricciones en algoritmos evolutivos, que persiga mejorar alguno de los inconvenientes de las técnicas actuales.
El capítulo 12 del libro que se menciona como guía del trabajo tiene la siguiente estructura:
En la introducción del capítulo los autores determinan que:
Las lecturas que recomiendan los autores al final del capítulo para ampliar más información es la siguiente:
8 ) ESTUDIO DE FORMAS ESPECIALES DE EVOLUCIÓN
Clasificar y describir las diferentes formas especiales de evolución existentes. Hacer énfasis en la coevolución, la evolución interactiva y los algoritmos evolutivos aplicados a problemas de optimización de funciones no estacionarias.
[NOTA: He visto también un artículo relacionado con los algoritmos genéticos estructurados aplicados a las funciones no estacionarias]
Se recomienda partir del esquema seguido en el tema 13 del libro “Introduction to Evolutionary Computing” de Eiben y Smith, así como de las
referencias bibliográficas que allí aparecen.
Como lecturas iniciales se recomiendan los temas 2, 3, 4, 5, 6, 7 y 13 del citado libro. Se valorará el intento por parte del alumno de sugerir y
describir una forma novedosa de evolución, que o bien mejore algún inconveniente de las formas especiales de evolución actuales o bien sea adecuado para ser aplicado en un dominio específico que sea difícil de abordar mediante los algoritmos evolutivos tradicionales.
La estructura del capítulo 13 de guía en este trabajo es la siguiente:
En el primer apartado, Aims of this Chapter, los autores resumen el propósito de este capítulo:
Como siempre en el apartado Recommended Reading for this Chapter tenemos bibliografía para ampliar conocimientos:
9) DISEÑO, APLICACIÓN Y EVALUACIÓN DE UN ALGORITMO EVOLUTIVO
Evaluar desde un punto de vista computacional el comportamiento de uno de los dos algoritmos evolutivos implementados en las actividades 1 y 2. Se valorará la introducción de alguna variante propia del alumno en la implementación del algoritmo (nuevo método de inicialización
de la población, nuevo operador de variación y/o selección, etc).
En todo caso, se deberá:
1. Realizar un análisis exhaustivo del comportamiento del algoritmo cuando se varía el valor de sus parámetros con la finalidad de encontrar la mejor inicialización de parámetros. En este punto, recuerde que la evaluación siempre se hace desde un punto de vista estadístico (varias ejecuciones para una misma configuración de parámetros)
2. Obtener ideas sobre la conducta del AE dependiendo del método elegido para inicialización, selección de padres, recombinación, mutación o selección de supervivientes.
3. Estudiar cómo se comporta el AE en función del tamaño del problema.
4. Investigar cómo la prestación del AE se ve influida por el tipo de problema. Para ello, deberá probarlo sobre diferentes tipos de problemas.
Otra posibilidad es realizar un estudio de la conducta del AE dependiendo del tipo de representación elegida para la resolución del problema. Para realizar esta evaluación debe tenerse en cuenta las métricas y sugerencias indicadas en el tema 14 del libro “Introduction to Evolutionary Computing” de Eiben y Smith, así como su bibliografía asociada.
El capítulo 14 del libro tiene los siguientes contenidos:
En la introducción del tema (Aims of this Chapter) los autores indican:
La bibliografía extra que se menciona (Recommended Reading for this Chapter) puede ser muy interesante: