cambio de evaluación en computación evolutiva


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.

8 comentarios en “cambio de evaluación en computación evolutiva

  1. Tras leer detenidamente el documento, ya tengo claras las dos actividades obligatorias que debo realizar. En cuanto a la primera actividad:

    Actividad 1

    Realizar la implementación de un algoritmo genético de acuerdo a las pautas establecidas en la actividad de aprendizaje relativa al tema 3. La implementación implica que el alumno realice personalmente un programa que funcione (no se considerará válido adaptar un programa ya existente). Se deberá entregar los ficheros fuentes y el ejecutable, junto con la documentación asociada a las soluciones obtenidas. El alumno puede encontrar en la sección de preguntas más frecuentes, algunas directrices útiles para la realización de esta 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.

  2. En cuanto a la segunda actividad:

    Actividad 2

    Programar una de las variantes existentes de algoritmo evolutivo distinta a la de algoritmos genéticos: estrategia evolutiva, programación evolutiva, programación genética o sistema clasificador. Preferiblemente dicha implementación se basará en las actividades de programación planificadas durante el curso.

    A diferencia de la actividad 1, aquí sí se permite la adaptación de alguna propuesta ya existente en el campo. El programa final deberá ser lo más completo posible, ofreciendo al usuario varias opciones para la inicialización de individuos, selección de padres, recombinación, mutación y selección de supervivientes.

    Se deberá entregar los ficheros fuentes y el ejecutable, junto con la documentación asociada a la solución de un problema elegido por el propio alumno o tomado de los propuestos en las actividades voluntarias correspondientes.

    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)

  3. 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:

    11 Theory

    11.1 Aims of this Chapter

    11.2 Competing Hyper-Planes in Binary Spaces: the Schema Theorem

    11.2.1 What is a Schema?
    11.2.2 Holland’s Formulation for the SGA
    11.2.3 Schema-Based Analysis of Variation Operators
    11.2.4 Walsh Analysis and Deception
    11.2.5 Criticisms and Recent Extensions of the Schema Theorem
    11.2.6 Gene Linkage: Identifying and Recombining Building Blocks

    11.3 Dynamical Systems

    11.4 Markov Chain Analysis

    11.5 Statistical Mechanics Approaches

    11.6 Reductionist Approaches

    11.7 Analysing EAs in Continuous Search Spaces

    11.8 No Free Lunch Theorems

    11.9 Exercises

    11.10 Further reading

    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:

    In this chapter we present a brief overview of some of the approaches taken to analysing and modelling the behaviour of Evoltutionary Algorithms. The “Holy Grail” of these efforts is the formulationof predictive models describing the behaviour of an EA on arbitrary problems, and permitting the specification of the most efficient form of optimizer for any given problem. However, (at least in the author’s opinions) this is unlikely ever to be realised, and most researchers will currently happily settle for techniques that provide any verifiable insights into EA behaviour, even on simple test problems. The reason for what might seem like limited ambition lies on one simple fact: evolutionary algorithms are hugely complex systems, involving many random factors. Moreover, while the field of EAs is fairly young, it is worth noting that the field of population genetics and evolutionary theory has a head start of more than a hundred years, and is still battling the barrier of complexity.

    Full descriptions and analysis of the various techniques currently used to develop EA theory would require both an amount of space and an assumption of prior knowledge of mathematics and statistics that are unsuitable here. We therefore restrict ourselves to a fairly brief description of the principal methods and results. For further details, we point the interested reader to the suggested textsa t the end of this chapter, ranging from “bird’s eye overviews” [124] to extensive monographs [50, 411]. We begin by describing some of the approaches taken to modelling EAs using a discrete representation (i.e for combinatorial optimization problems), before moving on to describe the techniques used for continuous representations. This chapter finishes with a description of an important theoretical result concerning all optimization algorithms, the No Free Lunch (NFL) theorem.

    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.

  4. 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.

  5. 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 libroIntroduction 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:

    8 Parameter Control in Evolutionary Algorithms

    8.1 Aims of this Chapter
    8.2 Introduction
    8.3 Examples of Changing Parameters

    8.3.1 Changing the Mutation Step Size
    8.3.2 Changing the Penalty Coefficients
    8.3.3 Summary

    8.4 Classification of Control Techniques

    8.4.1 What is Changed?
    8.4.2 How are Changes Made?
    8.4.3 What Evidence Informs the Change?
    8.4.4 What is the Scope of the Change?
    8.4.5 Summary

    8.5 Examples of Varying EA Parameters

    8.5.1 Representation
    8.5.2 Evaluation function
    8.5.3 Mutation
    8.5.4 Crossover
    8.5.5 Selection
    8.5.6 Population
    8.5.7 Varying Several Parameters Simultaneously

    8.6 Discussion
    8.7 Exercises
    8.8 Recommended Reading for this Chapter

    En el primer apartado Aims of this chapter los autores dicen lo siguiente:

    The issue of setting the values of various parameters of an evolutionary algorithm is crucial for good performance. In this chapter we discuss how to do this, beginning with the issue of whether these values are best set in advance or are best changed during evolution. We provide a classification of different approaches based on a number of complemetary features, and pay special attention to setting parameters on-the-fly. This has the potential of adjusting the algorithm to the problem while solving the problem.

    This chapter differs from nost of this book in that it represents rather more of a survey than a set of prescriptive details concerning how to implement a EA for a particular type of problem. For this reason, rather than end with one or two example applications, we have chosen to interleave a number of examples throughout the text. Thus we hope to both to clarify the points we wish to raise as we present them, and also to give the reader a feel for some of the many possibilities available for controlling different parameters.

    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:

    1. A.E. Eiben, R. Hinterding and Z. Michalewicz. Parameter Control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation. 3(2):124-141. 1999.

    2. J.E. Smith and T.C. Fogarty. Operator and parameter adaptation in genetic algorithms. Soft Computing, 1(2):81-87. 1997.

    3. J.E. Smith. On appropiate adaptation levels for the learning of gene linkage. Journal of Genetic Programming and Evolvable Machines. 3(2):129-155. 2002.

    4. T. Bäck. Self-adaptation. Chapter 21. pages 188-211 in T. Bäck, D.B. Fogel and Z. Michalewicz editors. Evolutionary Computation 2: Advanced Algorithms and Operators. Institute of Physics Publishing. 2000.

  6. 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:

    9 Multi-Modal Problems and Spatial Distribution

    9.1 Aims of this Chapter
    9.2 Introduction: Multi-Modal Problems and the Need for Diversity

    9.2.1 Multi-Modal Problems
    9.2.2 Genetic Drift
    9.2.3 Biological Motivations and Algorithmic Approaches
    9.2.4 Algorithmic vs. Genetic vs. Solution Space
    9.2.5 Summary

    9.3 Implicit Measures

    9.3.1 Multiple Populations in Tandem: Island Model EAs
    9.3.2 Spatial Distribution Within One Population: Diffusion Model EAs
    9.3.3 Automatic Speciation Using Mating Restrictions

    9.4 Explicit Diversity Maintenance

    9.4.1 Fitness Sharing
    9.4.2 Crowding

    9.5 Multi-Objective Evolutionary Algorithms

    9.5.1 Multi-Objective Optimisation Problems
    9.5.2 Dominance and Pareto optimality
    9.5.3 EA Approaches to Multi-Objective Optimisation

    9.6 Example Application: Distributed Co-Evolution of Job-shop Schedules
    9.7 Exercises
    9.8 Recommended Reading for this Chapter

    En su primer apartado, Aims of this Chapter, los autores presentan el tema de la siguiente manera:

    So far in our discussion of evolutionary algorityms we have considered the entire populationto act as a common genepool, with fitness as the primary feature affecting the likelihood of an individual taking part in the creation of new offspring, and surviving to the next generation. However we know that the evolution in vivo is also affectd by another major parameter, namely that of the physical space whithin which evolution occcurs, which imposes a sense of locality on genetic operators. However beautiful (i.e highly fit) the flowers in the municipal garden, it is extremely unlikely that they will be fertilised with pollen from a garden on the opposite side ofthe world.

    This separation brings with it several benefits, one of which is that it can aid the preservation of diversity within the population. As a result, different subgroups of the same global population may be adapted to the local conditions, as was famously described concerning finches on islands of the Galapagos archipielago by Charles Darwin. One theory holds that the phenomenon of speciation arises as an end result of increasingly specialised adaptation to particular environmental niches, so that eventually distinct subpopulations have evolved so differently that their offspring are no longer viable, even if mating is physically possible at all.

    Ideas such as that of a global population being subdivided into smaller, infrequently communicating populations, along with related concepts such as speciation and other mating restrictions, have benn widely investigated by EA practitioners as a means of preserving diversity and aiding the search for different high-quality solutions in multimodal problems. In this chapter we provide an overview of these approaches, ending with a dexcription of two areas of optimization ib which EAs are currently showing great promise, namely multiobjetive and dynamic problems.

    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:

    1. K. Deb. Multiobjective Optimization and Evolutionary Algorithms. John Wiley, Chichester, UK 2001.

    2. C.A. Coello, V.A. Van Veldhuizen, and G.B. Lamont. Evolutionary algorithms for solving multi-objective problems. Kluwer Academic Publishers., New York, May 2002.

    3. I. Parmee. Evolutionary and Adaptive COmputing in Engineering Design: The Integration of Adaptive Search Exploration and Optimization with Engineering Design Processes. Springer, Berlin, Heidelberg, New York, 2000

    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:

    10 Hybridisation with Other Techniques: Memetic Algorithms

    10.1 Aims of this Chapter
    10.2 Motivation for Hybridising EAs
    10.3 A Brief Introduction to Local Search

    10.3.1 Lamarckianism and the Baldwin Effect

    10.4 Structure of a Memetic Algorithm

    10.4.1 Heuristic or Intelligent Initialisation
    10.4.2 Hybridisation within Variation Operators: Intelligent Crossover and Mutation
    10.4.3 Local Search Acting on the Output from Variation Operators
    10.4.4 Hybridisation During the Genotype to Phenotype Mapping

    10.5 Design Issues for Memetic Algorithms

    10.5.1 Preservation of Diversity
    10.5.2 Choice of Operators
    10.5.3 Use of Knowledge

    10.6 Example Application: Multi-stage Memetic Timetabling
    10.7 Exercises
    10.8 Recommended Reading for this Chapter

    En la introducción del capítulo, apartado Aims of this Chapter los autores dicen lo siguiente:

    In the preceding chapters we describes the main varieties of evolutionay algorithms and described various examples of how they might be suitable implemented for different applications. In thos chapter we turn our attention to systems in which, rather than existing as a “stand-alone” algorithms, EA-based approaches are either incorporated wihin larger systems, or alternatively have other methods or data structures incorporated with them. This category of algorithms is very successful in practice and forms a rapidly growing research area with great potential. This area and the algorithms taht form its subject of study are named Memetic Algorithms (MA) In this chapter we explain the rationale behind MAs, outline a number of possibilities for combining EAs with other techniques, and give some guidelines for designing successful hybrid algorithms.

    Y finalmente en cuanto a las lecturas posteriores para ampliar conocimientos, en el apartado Recommended Reading for this Chapter, tenemos lo siguientes:

    1. P. Moscato. Memetic algorithms’ home page.
    http://www.densis.fee.unicamp.br/%7emoscato/memetic_home.html

    2. S. Blackmore. The meme machine. Oxford University Press. Oxford UK. 1999.

    3. Corne, Dorigo and Glover (Editors) New Ideas in Optimization, Chapters 14-18. pp. 217-294. McGrawHill. London. 1999

  7. 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:

    12 Constraint Handling

    12.1 Aims of this Chapter
    12.2 Constrained Problems

    12.2.1 Free Optimisation Problems
    12.2.2 Constraint Satisfaction Problems
    12.2.3 Constrained Optimisation Problems

    12.3 Two Main Types of Constraint Handling
    12.4 Ways to Handle Constraints in EAs

    12.4.1 Penalty Functions
    12.4.2 Repair Functions
    12.4.3 Restricting Search to the Feasible Region
    12.4.4 Decoder Functions

    12.5 Application Example: Graph 3-Colouring

    12.5.1 An Indirect Approach
    12.5.2 A Mixed Mapping-Direct Approach

    12.6 Exercises
    12.7 Recommended Reading for this Chapter

    En la introducción del capítulo los autores determinan que:

    In this chapter we consider the issue of constraint handling by evolutionary algorithms. This issue has great practical relevance because many practical problems are constrained. It is also a theoretically challenging subject since a grear deal of intractable problems (NP-Hard, NP-Complete, etc.) are constrained. The presence of constraints has the effect that not all possible combinations of variable values represent valid solutions to the problem at hand. Unfortunately, constraint handling is not strightforward in an EA, because the variation operators (mutation and recombination) are typically “blind” to constraints. That is, there is no guarantee that even if the parents satisfy some constraints, the offspring will saisfy them as well. In this chapter we elaborate on the notion of constrained problems and distinguish two different types: constrained optimization problems and constraint satisfaction problems. (this elaboration requires clarifying some basic notions, leading to definitions that implicitely have been used en earlier chapters) Based on this classification of constrained problems , we discuss what constraint handling means form an EA perspective, an review the most commonly applied EA techniques treat constraints. Analysing these techniques , we identify a number of commonn features and arrive ath the conclusion that the presence of constriants is not harmful , but rather helpful in that it provides extra information that EAs can utilise.

    Las lecturas que recomiendan los autores al final del capítulo para ampliar más información es la siguiente:

    1. T. Bäck, D.B. Fogel and Z. Michalewicz, editors. Evolutionary computation 2: Advanced algorithms and operators Part II: Chapters 6-12, pages 38-86. Institute of Physics Publishing, Bristol 2000. A series of chapters providing comprehensive reviews of different EA approaches to constraint handling, written by experts in the field.

    2. B.G.W. Craenen, A.E. Eiben, and J.I. van Hemert. Comparing evolutionary algorithms on binary constraint satisfaction problems. IEEE Transactions on Evolutionary Computation, 2003

    3. A.E. Eiben. Evolutionary algorithms and constraint satisfaction: Definitions, survey, methodology, and research directions. In Kallel, Naudts, Rogers, Eds. Theoretical Aspects of Evolutionary Computing. Springer, Berlin, Heidelberg, New York, 2001. Clear definitions and a good overview of evolutionary constraint handling methods from the CSP point of view.

    4. J. Smith. Handbook of Global Optimization. Volume 2, Chap. Genetic Algorithms, pages 275-362. Kluwer Academic Publishers, Boston 2002. A good overview of constraint handling methods in GAs from the COP point of view.

    5. Z. Michalewicz and M. Schoenauer. Evolutionary algorithms for constrained parameter optimisation problems. Evolutionary Computation, 4:1 pp. 1-32, 1996.

    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:

    13 Special Forms of Evolution

    13.1 Aims of this Chapter
    13.2 Co-evolution

    13.2.1 Cooperative co-evolution
    13.2.2 Competitive co-evolution
    13.2.3 Example Application: Co-evolutionary Constraint Satisfaction

    13.3 Interactive Evolution

    13.3.1 Optimisation, Design, Exploration
    13.3.2 Interactive Evolutionary Design and Art
    13.3.3 Example Application: The Mondriaan Evolver

    13.4 Non-Stationary Function Optimisation

    13.4.1 Algorithmic Approaches
    13.4.2 Selection and Replacement Policies
    13.4.3 Example Application: The Time Varying Knapsack Problem

    13.5 Exercises
    13.6 Recommended Reading for this Chapter

    En el primer apartado, Aims of this Chapter, los autores resumen el propósito de este capítulo:

    In this chapter we discuss special forms of evolution that in some sense deviate from the standard evolutionary algorithms. In particular, we present coevolution and interactive evolution that both work under “external influence”. In coevolution the influence comes from another population, ehose members affect the fitness of the main population. In turn, the main population also influences the fitness of the other one; hence the two populations evolve together. In interactive evolution this influence comes from a user who defines the fitness values by subjective preferences. In both of the cases, the fitness that is awarded to a solution may vary. In the first case because, the fitness is dependent on the evolutionary state of the second population, and in the second because users often display inconsistences. We finish the chapter by describing evolutionary approaches to problems where changing evaluation criteria form the very feature defining them.: nonstationary opiimisation problems.

    Como siempre en el apartado Recommended Reading for this Chapter tenemos bibliografía para ampliar conocimientos:

    1. P.J. Bentley, Ed. Evolutionary Design by Computers. Morgan Kaufmann, San Francisco, 1999

    2. P.J. Bentley, D.W. Corne, Eds. Creative Evolutionary Systems. Academic Press, 2002

    3. P.J. Bentley, D.W. Corne. An introduction to creative evolutionary systems. In Creative Evolutionary Systems (above), pp. 1-75.

    4. J. Branke, S. Kirby. Evolutionary Optimization in Dynamic Environments. Kluwer Academic Publishers, Boston 2001.

    5. J. Branke, H. schmeck. Designing evolutionary algorithms for dynamic optimization problems. In Ghosh, Tsutsui, Advances in evolutionary computation: theory and applications. Springer, Berlin, Heidelberg, New York 2003. pp. 239-262.

    6. W.D. Willis. Coevolving parasites imporve simulated evolution as an optimization procedure. In C.G. Langton et al., Eds. Proceedings of the Workshop on Artificial Life (ALIFE’90), pp. 313-324, Addison-Wesley, Redwood City, CA, USA, 1992

    7. J. Paredis. Coevolutionary algorithms. In T. Bäck, D. Fogel, Z. Michalewicz, Eds. Handbook of evolutionary computation. Institute of Physics Publishing, Birstol and Oxford University Press, New York 1997.

  8. 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:

    14 Working with Evolutionary Algorithms

    14.1 Aims of this Chapter
    14.2 What do you want an EA to do?
    14.3 Performance Measures

    14.3.1 Different Performance Measures
    14.3.2 Peak vs. Average Performance

    14.4 Test Problems for Experimental Comparisons

    14.4.1 Using Predefined Problem Instances
    14.4.2 Using Problem Instance Generators
    14.4.3 Using Real-World Problems

    14.5 Example Applications

    14.5.1 Bad Practice
    14.5.2 Better Practice

    14.6 Exercises
    14.7 Recommended Reading for this Chapter

    En la introducción del tema (Aims of this Chapter) los autores indican:

    The main objective of this chapter is to provide practical guidelines for working with EAs. Working with EAs often means comparing different versions experimentally. Guidelines to perform experimental comparisons are therefore given much attention, including the issues of algorithm performance measures, statistics, and benchmark test suites. The example application is also adjusted to the special topics here; it illustrates the application of different experimental practices, rather than EA design.

    La bibliografía extra que se menciona (Recommended Reading for this Chapter) puede ser muy interesante:

    1. T. Bäck, Z. Michalewicz. Test Landscapes in Handbook of Evolutionary Algorithms

    2. A.E. Eiben, M. Jelasity. A critical note on experimental research methodology in EC. In 2002 Congress on Evolutionary Computation CEC 2002. IEEE Press, Piscataway, NJ, 2002, pp. 582-587.

    3. D. Whitley, K. Mathias, S. Rana, J. Dzubera. Building better test functions. In L.J. Eshelman, Ed. Proceedings of the 6th International Conference on Genetic Algorithms. Morgan Kaufmann, San Francisco 1995. pp. 239-246.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s