Download Área de Posgrad Área de Posgrado

Área de Posgrado
Maestría en Ingeniería Biomédica
Carrera: Maestría en Ingeniería Biomédica
Curso de Posgrado: “Tópicos
Tópicos de Computación e Inteligencia Artificial aplicados a la
l Ingeniería Biomédica” INTRODUCCIÓN A LA COMPUTACIÓN
MPUTACIÓN EVOLUTIVA
1
Carga Horaria : 90 horas
Docente/s a cargo: Dr. Ignacio Ponzoni
Docentes colaboradores:
Semestre: 1°
2
Año: 2013
3
Modalidad : Curso teórico-práctico
práctico
Carácter : optativo
1:
Carga horaria:: la cantidad de horas reloj.
2:
Curso teórico:: curso donde se desarrolla en forma expositiva una temática propia de la disciplina
disc
Curso teórico-práctico:: curso que articula la modalidad del curso teórico con una actividad de la práctica con
relación a la temática de estudio. Lo teórico y lo práctico se dan simultáneamente en forma interrelacionada.
Seminario: actividad alrededor de una temática o problemática puntual, el objeto de estudio es acotado y permite
diferentes abordajes.
3:
Carácter: si son obligatorioss u optativos.
optativ
Programa Analítico: de foja:
Bibliografía de foja: a foja:
a foja:
Aprobado Res. C. D.:
Modificado/Anulado/ Res. C. D.:
Fecha:
Fecha:
Carece de validez sin la certificación dela Comisión de Posgrado:
1
Programa Analítico
Unidad 1: Introducción a la computación evolutiva.
¿Qué es computación evolutiva? Breve reseña histórica. Principios de los procesos evolutivos. Estructura
genérica de los algoritmos evolutivos. Principales enfoques evolutivos. La computación evolutiva en el contexto
de los problemas de búsqueda y optimización.
Unidad
idad 2: Conceptos básicos de algoritmos genéticos.
Algoritmos genéticos y Computación Evolutiva. Algoritmos genéticos como métodos de búsqueda. Algoritmos
Genético Canónico. Estructura de los algoritmos genéticos. Métodos y criterios necesarios para implementar
implem
algoritmos genéticos. Caso de estudio: SGA (Simple GeneticAlgorithm).
Unidad 3. Fundamentos teóricos de los algoritmos genéticos.
Análisis teórico de los algoritmos genéticos. Definiciones y conceptos básicos. La ecuación del crecimiento de los
esquemas. El teorema fundamental de los algoritmos genéticos. Hipótesis de los bloques constructivos.
Propiedad de paralelismo implícito de los algoritmos genéticos. Limitaciones prácticas del análisis teórico.
Unidad 4: Dificultades en el uso de los algoritmos genéticos.
Limitaciones de los algoritmos genéticos e inconvenientes asociados. El problema de la debilidad de los
algoritmos genéticos. El problema de la diversidad en los algoritmos genéticos. Convergencia prematura por
problemas de diversidad.
diversidad. Mecanismos de control de la diversidad. Presión selectiva. Pautas básicas para mejorar
la relación entre diversidad y presión selectiva. Técnicas de inicialización de poblaciones, convergencia de los
algoritmos genéticos y criterios de terminación.
Unidad
d 5: Representaciones.
Espacio de soluciones, representaciones y sus codificaciones. Discretización y codificación de dominios continuos.
El operador de inversión. Representaciones más empleadas: cadenas binarias, vectores de números reales y
permutaciones. Lineamientos generales para la codificación de representaciones.
permutaciones.
Unidad 6: Técnicas de selección y reemplazo.
Aspectos básicos de un método de selección. Teoría de la presión selectiva. Selección proporcional y algoritmos
de muestreo. Selección por torneos.
torneos. Selección basada en ranking. Otros métodos de selección. Comparación
entre los métodos de selección. Métodos de reemplazo.
Unidad 7: Operadores de búsqueda.
Exploración versus explotación. Aspectos centrales en el diseño de un operador de búsqueda. Operadores
Op
de
mutación y recombinación para representaciones basadas en: cadenas binarias, vectores de números reales,
permutaciones, y otras. Mejoras a los operadores de búsqueda. Parametrización de los operadores. Técnicas de
ajuste automático y adaptivo de
d los parámetros de búsqueda.
Unidad 8: Diseño y evaluación de la función de aptitud.
Dificultades en la elección y diseño de la función de evaluación de aptitud. Desplazamiento y escalado de la
función de aptitud. Funciones codificadoras y decodificadoras para distintas representaciones. Evaluación de la
aptitud competitiva.
Unidad 9: Algoritmos evolutivos multiobjetivo.
Motivación. Definición formal de un problema de optimización multiobjetivo.
multiobjetivo. Frontera de Pareto. Optimización
multiobjetivo y algoritmos evolutivos.
evolutivos. Métodos agregativos. Métodos basados en ranking de Pareto. Algoritmos
evolutivos multiobjetivos: NSGA, SPEA, PAES, NSGA-II,
NSGA SPEA-II.
Unidad 10: Técnicas para manejo de restricciones y tratamiento de individuos no factibles.
Introducción al manejo
manejo de restricciones y tratamiento de individuos no factibles. Funciones de penalización.
Decodificadores. Algoritmos de reparación. Operadores de preservación de restricciones. Otros métodos de
manejo de restricciones.
Unidad 11: Casos de estudio en aplicaciones
aplicaciones reales de Bioinformática y Quimioinformática.
Biclustering de datos de expresión de genes. Selección de descriptores moleculares en predicción de
propiedades farmacocinéticas de drogas.
2
Bibliografía
•
•
•
•
•
•
•
•
“Genetic Algorithms+DataStrutures=Evolution
Algorithms+DataStru
=Evolution Programs”, Michalewicz, 3rd
Ed.,Springer, 1996.
“Genetic Algorithms in Search, Optimization, and Machine Learning”, Goldberg,
20thEd., Addison--Wesley, 1999.
“Una introducción a la Computación Evolutiva”, Pérez Serrada. Apunte de
distribucióngratuita
uita en PDF.
“Evolutionary Algorithms for Solving Multi-objective
Multi objective Problems”,
CoelloCoello,Veldhuizen Lamont, 2nd. Ed., Kluwer, 2007.
CoelloCoello,Veldhuizen&
“Multiobjective
Multiobjective Evolutionary Algorithms and Applications”,
Applications”, Khor& Tan,Springer, 2009.
“Introduction
Introduction to Evolutionary Computing”,
Computi
Eiben& Smith,, Springer, 2010.
“Multi-Objective
Objective Optimization Using Evolutionary Algorithm”,
Algorithm”, Deb, Wiley, 2010.
“Evolutionary
Evolutionary Optimization Algorithms”,
Algorithms”, Dan Simon, Wiley, 2013.
3
Planificación del curso
Objetivos Generales:
El objetivo principal de este curso es introducir a los estudiantes los fundamentos y técnicas básicas para la
resolución de problemas empleando técnicas de computación evolutiva,
evolutiva, con especial énfasis en la resolución de
problemas en el ámbito de la ingeniería y la bioinformática.
bi
Objetivos Particulares:
Se espera que el estudiante adquiera, con la realización de este curso, habilidades para:
• decidir cuándo
ndo resulta apropiado el empleo de estas técnicas de computación evolutiva,
evolutiva
• seleccionar el método más apropiado, dentro de la computación evolutiva, para abordar el problema
bajo estudio,
• comprender como aplicar las distintas técnicas, en forma consistente y eficiente, en el tratamiento de
problemas de búsqueda y optimización,
optimización, lo cual implica desarrollar capacidades para definir nuevas
representaciones cromosómicas, operadores genéticos y funciones de aptitud mono y multiobjetivo.
multiobjetivo
Metodología de Trabajo:
Por cada unidad se desarrollarán clases del tipo expositivo-interrogativo, teórico-prácticas
prácticas con utilización de
diversoss recursos didácticos. Las primeras horas de cada clase se desarrollarán conceptosteóricos y la última hora
se destinará a guiar a los alumnos a través de ejemplos y problemas tipo para el desarrollo de susactividades
prácticas que podrán ser realizadas
realiz
en grupos de no más de dos integrantes. Al final del curso se
s abordará un
trabajo teórico-práctico
práctico integrador donde se tratará un caso particular en el que intervengansimultáneamente
varios de los tópicos desarrollados
desarrollado en el curso.
Equipo docente:
Dr. Ignacio Ponzoni
Cronograma del Curso:
Clase
1
Fecha
Martes 28/5
2
Miércoles 29/5
3
Jueves 30/5
4
Viernes 31/5
5
Sábado 1/6 ó
Lunes 3/6
Unidades
Unidad 1: Introducción a la computación evolutiva.
Unidad 2: Conceptos básicos de algoritmos genéticos.
Unidad 3. Fundamentos teóricos de los algoritmos genéticos.
Unidad 4: Dificultades en el uso de los algoritmos genéticos.
Unidad 5: Representaciones.
Unidad 6: Técnicas de selección y reemplazo.
Unidad 7: Operadores de búsqueda.
Unidad 8: Diseño y evaluación de la función de aptitud.
Unidad 9: Algoritmos evolutivos multiobjetivo.
Unidad 10: Técnicas para manejo de restricciones y tratamiento de
individuos no factibles.
Unidad 11: Casos de estudio en aplicaciones reales de Bioinformática y
Quimioinformática.
Examen
Condiciones de Regularidad y Promoción:
La regularidad será obtenida con la asistencia al 80% de las clases. Para la promoción del curso el alumno
deberáaprobar un examen de elección múltiple (multiple-choice)
(
) que se tomará el último día clases, y además
realizar un trabajo teórico-práctico
práctico integrador,
integrador, el cual podrá ser entregado con posterioridad a la finalización del
dictado de clases.
Infraestructura necesaria:
- Cañón proyector.
4