Ministerio de Cultura y Educación Universidad Nacional de San Luis Facultad de Ciencias Físico-Matemáticas y Naturales Departamento: Informatica Área: Area V: Automatas y Lenguajes |
I - Oferta Académica | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
|
II - Equipo Docente | ||||||||
---|---|---|---|---|---|---|---|---|
|
III - Características del Curso | |||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
IV - Fundamentación |
---|
Existen muchos problemas que requieren explorar grandes espacios de búsqueda para encontrar una solución óptima o quasi óptima.
Los métodos de búsqueda pueden clasificarse de distintas maneras, algunos dado un espacio de búsqueda y una función de evaluación devuelven siempre la misma solución (ej. la programación dinámica), otros pueden generar diferentes soluciones basados en el punto de partida (algoritmos greedy o hill_climbing), entre otras. Al respecto es interesante hacer notar que todas esas técnicas siempre tienen una única “mejor solución” almacenada que tratan de mejorar en el próximo paso, o sea, trabajan sobre o construyen una única solución cada vez que se ejecutan. Otras heurísticas trabajan sobre poblaciones de soluciones donde la función de evaluación se utiliza para medir el mérito de cada solución, aquí en cada iteración, a través de operadores especializados, toda la población de soluciones se modifica ya sea con una concepción basada en el paradigma Darwiniano de la evolución, o en leyes sociales o en el comportamiento cooperativo de las especies. |
V - Objetivos |
---|
Se espera que el alumno adquiera conocimientos de los distintas metheurísticas de búsqueda poblacionales aplicándolas en distintos tipos de problemas, por ejemplo, de scheduling, de optimización multiobjetivo, y otros propios de la investigación operativa, actualmente utilizados en la práctica profesional y en la investigación científica.
|
VI - Contenidos |
---|
1. Introducción. Inteligencia computacional, sus ramas. Motivación de la evolución como modelo de simulación. Campos de aplicación. Ventajas y desventajas de las metaheurísticas sobre otros enfoques.
2. Algoritmos Genéticos y otros algoritmos evolutivos. Representación del espacio de soluciones. Evaluación de las soluciones (fitness). Mecanismos de selección y operadores genéticos. Convergencia de Algoritmos Evolutivos. Hibridización. Algoritmos Evolutivos Avanzados. Aplicaciones de la Computación Evolutiva. Problemas clásicos de administración y optimización del uso de recursos. 3. Evolución Diferencial. Fundamentos básicos y conceptos previos. Algoritmos relacionados. Exploración del espacio de búsqueda a través de la mutación diferencial y crossover uniforme. Diferentes algoritmos derivados del concepto de Evolución Diferencial. 4. Colonias de Hormigas. Rastros de feronoma, su densidad. Optimización por simulación de Colonias de hormigas. Diferentes algotimos derivados: Ant System, AS-rank, Min-Max-AS, AS-elitista y Ant Colony System. Aplicación a problemas de optimización. 5. Cúmulos de partículas. Inteligencia colectiva. Evaluación, comparación e imitación. Optimización por cúmulos de Partículas. Optimización en espacios continuos y discretos. Hibridización. 6. Algoritmos Culturales. Descripción de los espacios de población y de pensamientos. Protocolos de comunicación. Generaciones de algoritmos culturales. |
VII - Plan de Trabajos Prácticos |
---|
A) desarrollo prácticos de aula y de computación.
B) desarrollo de proyectos de software grupales. |
VIII - Regimen de Aprobación |
---|
El régimen es sólo promocional. Promoción a través de desarrollo de prácticos y proyectos de software grupales.
|
IX - Bibliografía Básica |
---|
[1] Goldberg D. E., - Genetic Algorithms in Search, Optimization & Machine Learning,Addison Wesley, 1989.
[2] Michalewicz Z. - Genetic Algorithms + Data Structures = Evolutions Programs, Springer-Verlag, Third, Extended Edition, 1996 [3] Bäck T: Evolutionary algorithms in theory and practice. Oxford University Press, 1996. [4] Dorigo M. y Stützle T.: Ant Colony Optimization, MIT Press, 2004. [5] Kennedy J. y Eberhart R.: Swarm Intelligence, Morgan Kaufmann, 2003. [6] Dorigo M. y Di Caro G., The Ant Colony Optimization Metaheuristic, in [7] New Ideas in Optimization, McGraw Hill, 1999. [8] Reynolds Robert G., Cultural Algorithms: Teory and Applications. [9] Reynolds Robert G., An Introduction to Cultural Algorithms. [10] Kenneth V. Price, Rainer M. Storn, and Jouni A. Lampinen - Differential Evolution: A Practical Approach to Global Optimization (Natural Computing Series), Springer, 1ra Edición, 2005. |
X - Bibliografia Complementaria |
---|
[1] Proceedings of the Congress on Evolutionary Computation (CEC).
[2] Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). [3] Transactions on Evolutionary Computation, IEEE. [4] Evolutionary Conputation, MIT Press. |
XI - Resumen de Objetivos |
---|
El objetivo del curso es introducir al alumno en las más modernas metheurísticas de búsqueda poblacionales aplicándolas en distintos tipos de problemas, por ejemplo, de scheduling, de optimización multiobjetivo, y otros propios de la investigación operativa, actualmente utilizados en la práctica profesional y en la investigación científica. La temática pertenece al área de la Inteligencia Computacional.
|
XII - Resumen del Programa |
---|
1. Introducción. Inteligencia computacional, sus ramas. motivación de la evolución como modelo de simulación.
2. Algoritmos Genéticos y otros algoritmos evolutivos. 3. Evolución Diferencial, algoritmos derivados. 4. Colonias de Hormigas, algoritmos derivados. 5. Cúmulos de partículas. Inteligencia colectiva. 6. Algoritmos Culturales. Espacios de población y de pensamientos. |
XIII - Imprevistos |
---|
No se prevén.
|