UNIVERSIDAD NACIONAL ABIERTA
VICERRECTORADO ACADEMICO
SUBPROGRAMA DISEÑO ACADÉMICO
AREA INGENIERÍA
PLAN DE CURSO
Identificación
Nombre: COMPUTACIÓN EVOLUTIVA
Código: 350
U.C: 4
Carrera: Ingeniería de Sistemas
Código: 236
Semestre : Formación Profesional
Prelaciones: Investigación de Operaciones II (348)
Autor: MSc. María Eugenia Mazzei
Asesores: MSc. Carmen Z. Maldonado
Lic. Carmen Velásquez
Dr. Antonio Alfonzo
Prof. María Martín
Nivel Central
Caracas, Abril 2015
2
II. FUNDAMENTACIÓN
La Computación Evolutiva es una vertiente de la Computación que se basa
en la imitación de los procesos evolutivos y en el comportamiento de
organizaciones sociales existentes en la naturaleza, para la resolución de
problemas de ingeniería, de Investigación de Operaciones o de optimización en
general. Los problemas de optimización surgen en situaciones en las cuales se
requiere hallar la mejor solución bajo ciertas condiciones y contemplan la
administración de recursos en forma eficiente. En el campo de la Ingeniería,
existen problemas de diseño de dispositivos o de estructuras, entre otros, en los
cuales se requiere optimizar el espesor, la capacidad, la presión o el peso.
Son ejemplos típicos del campo de la Investigación de Operaciones: los
problemas de producción, de ubicación, de asignación, de programación de
cursos, de planificación, de distribución y los problemas de redes estáticas y
dinámicas, entre otros. El diseño de algoritmos estándares para hallar la solución
de problemas, en el contexto evolutivo, se inspira en conceptos y maneras de
organización que pertenecen al campo de la biología, entre ellos están: las
poblaciones, la recombinación, las mutaciones, la supervivencia del más apto, la
organización de enjambres de abejas, hormigas y aves.
El curso de Computación Evolutiva que se presenta es una introducción al
empleo de conceptos bio-inspirados, llevados al diseño de algoritmos, con el fin
de resolver problemas. Estos algoritmos están basados en la utilización de
técnicas heurísticas y proveen un enfoque sencillo y novedoso para su tratamiento
y solución a través del computador.
La asignatura Computación Evolutiva pertenece al grupo de asignaturas de
Formación Profesional y puede cursarse a partir del séptimo semestre. Debido a
su naturaleza esencialmente algorítmica, se le concibe dentro del bloque de
Computación; no obstante, es preciso que el estudiante haya cursado las
asignaturas obligatorias pertenecientes al bloque de Investigación de
Operaciones, ya que existe una estrecha vinculación entre el tipo de problema
abordado y el área de investigación de operaciones. Cabe destacar que esta
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
3
relación entre la Computación y la Optimización es una tendencia actual, la cual
se ha de poner en práctica a través de este curso.
Se espera que esta asignatura contribuya con la formación del estudiante de
Ingeniería de Sistemas, en el sentido de ofrecer una nueva manera de resolver
problemas, pues se emplean conceptos tomados de la naturaleza para fortalecer
las destrezas computacionales adquiridas en cursos anteriores.
El curso es de carácter teórico-práctico; por una parte comprende un
conjunto de conceptos y técnicas, cuya asimilación es fundamental para su
aplicación; y por otra, el empleo de estos para la implementación y pruebas de
algoritmos en el computador. Como condición para alcanzar un buen desempeño,
se espera que el estudiante posea las destrezas básicas de programación
adquiridas en los semestres iniciales de la carrera, así como las técnicas de
optimización aprendidas en los semestres medios.
Para la administración del curso se cuenta con el siguiente paquete
instruccional:
o Plan de curso.
o Texto UNA. en formato, digital “Computación Evolutiva”, 2013, en formato
PDF.
o Presentaciones digitalizadas en formato PDF, 2011.
o Libro de consulta, disponible en formato PDF: Introducción a la
Computación Evolutiva (Notas de Curso), 2008, Carlos A. Coello.
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
4
III. PLAN DE EVALUACION
Orientaciones generales: MODALIDAD OBJETIVO CONTENIDO
• Las pruebas son de modalidad presencial y de desarrollo.
• Los objetivos correspondientes a cada unidad están ponderados, lo cual consiste Primera prueba
1, 2, 3
Módulo I: U 1,2
en la asignación de peso a los objetivos evaluables de la asignatura, de acuerdo parcial Módulo II: U 3
con la importancia y/o complejidad que tienen. La escala de ponderación de esta
asignatura es de 1 a 5 puntos. Esta ponderación está determinada por la
incidencia de los objetivos evaluables en: el perfil de la carrera, el objetivo terminal Segunda prueba Módulo II: U 4 y 5
parcial
4,5,6,7 Módulo III: U 6 y 7
de la asignatura y los objetivos terminales de las asignaturas sobre las que existe
prelación.
Módulo I: U 1,2
• Las especificaciones del trabajo práctico se suministran con la primera prueba 1,2,3,4,
Prueba integral Módulo II: U 3,4,5
parcial. Si el estudiante no va a presentar esta prueba, debe retirar un ejemplar de 5,6,7 Módulo III: U 6 y 7
estas en el lugar de presentación. El estudiante consignará el trabajo resuelto con
la prueba integral.
Nivel Corrector: Está totalmente asignado al Nivel Central.
Responsable: MSc. María Eugenia Mazzei (Especialista en Contenido) Trabajo práctico 8 Módulo IV: unidad 8
Dirección de correo electrónico: mmazzei@[Link]
Teléfono: (0212) – 5552376
M U O OBJETIVOS
1 1 Aplicar métodos tradicionales y/o métodos basados en heurísticas en la resolución de problemas de optimización.
I
2 2 Aplicar conceptos bio-inspirados en la realización de abstracciones a problemas.
3 3 Aplicar algoritmos genéticos en la resolución de problemas.
II 4 4 Aplicar estrategias evolutivas en la resolución de problemas.
5 5 Aplicar técnicas de Programación Genética en la resolución de problemas.
6 6 Aplicar los conceptos y técnicas relacionados con los enjambres de hormiga para la resolución de problemas.
III Aplicar los conceptos y técnicas relacionados con los enjambres de partículas para la resolución de problemas.
7 7
Resolver un problema del mundo real, empleando los conceptos y técnicas relacionados con los algoritmos
IV 8 8
evolutivos, la inteligencia social o enfoques afines.
Objetivo: 1 2 3 4 5 6 7 8 Peso acumulado: 1 -9 10 11 12 13 14 15 16 17 18
Peso: 1 1 3 2 2 2 2 5 Calificación 1 2 3 4 5 6 7 8 9 10
Peso máximo: 18 puntos Criterio de dominio académico: 14 puntos
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
5
ORIENTACIONES GENERALES
• El material instruccional recomendado para este curso está disponible en formato PDF, en la Biblioteca
Digital UNA. El software de programación a emplear para la realización de ejercicios y del trabajo práctico es de
libre elección.
• Lea las instrucciones que aparecen en el MIA.
• Realice los ejercicios propuestos en cada unidad, en el Material de Apoyo.
• Contacte con otros estudiantes del curso a fin de compartir materiales instruccionales hallados en Internet y de
discutir los temas abordados.
• Consulte otros libros sugeridos en la bibliografía complementaria.
• Consulte las direcciones electrónicas especificadas en el MIA. Si no se hacen referencias específicas, se
recomienda buscar el tema en Internet, empleando algún buscador.
• Ante cualquier duda, consulte con su asesor en su Centro Local.
• Si desea hacer algún comentario o sugerencia acerca del curso, comuníquese con el profesor que lo administra a
través de la dirección de correo electrónico suministrada por la carrera.
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
6
IV. DISEÑO DE LA INSTRUCCIÓN DEL CURSO
Objetivo del curso: Resolver problemas de optimización, con sentido analítico y creativo, a través de la aplicación
los conceptos y técnicas de la Computación Evolutiva.
Objetivo Contenido
1 El problema de optimización. Métodos de búsqueda. Métodos basados en
heurísticas: Recocido Simulado y Búsqueda Tabú. Algoritmos.
Conceptos biológicos y su analogía con la computación. Poblaciones. Función de
evaluación (o de fitness). Vecindad. Generaciones. Computación Evolutiva.
2
Fundamentos. Pasos de un Algoritmo Evolutivo. Operadores de Variación.
Operadores de Selección. Ventajas
Generalidades. Esquemas de representación. Operadores de Cruce y de Mutación.
3 Formulación Matemática del GA. Algoritmo estándar. Aplicación del GA para la
resolución de problemas.
Generalidades. Tipos de Estrategias Evolutivas. Cruce. Mutación. Algoritmo Estándar.
4
Aplicación de EE en la resolución de problemas.
Fundamentos. Representación de los individuos en árboles. Algoritmo Estándar.
5 Aplicación de GP en la resolución de problemas.
Generalidades de los sistemas sociales artificiales. Fundamentos de los Algoritmos
6 Hormiga. Algoritmo ACO. Aplicación del Algoritmo ACO en la resolución de
problemas.
Fundamentos de los Algoritmos de Enjambres de Partículas. Algoritmo PSO.
7 Aplicación del Algoritmo PSO en la resolución de problemas. Variantes del algoritmo.
Temas incluidos: Vida Artificial. Autómata Celular: El Juego de la Vida. Redes de
8 Neuronas Artificiales. Caso de Estudio: Algoritmo Genético.
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
7
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIÓN
Materiales Instruccionales: Producto: Solución a un
• Material instruccional de apoyo. problema dado,
• Software: lenguaje de programación de propósito general empleando un método
• Presentación: “Optimización” tradicional o uno basado
• Direcciones electrónicas suministradas en el MIA en heurísticas: Recocido
Simulado o Búsqueda
Actividades a realizar: Tabú.
• Lea el capítulo 1, sección 1.1, en el MIA. Procedimiento: Se
• Resuelva los ejercicios y autoevaluación propuestos en el material valorará la abstracción
instruccional. realizada para resolver el
1 • Vea la presentación, hasta el Método de Ascenso de Colinas problema y la correcta
Aplicar métodos Estocástico (inclusive). aplicación del método.
tradicionales y/o • Consulte la dirección electrónica (sección 1):
métodos basados [Link] Instrumento: Una
en heurísticas en la
prueba presencial de
resolución de
• Implemente los algoritmos de Recocido Simulado y Búsqueda Tabú, desarrollo donde se
problemas de
optimización. empleando algún lenguaje de programación de propósito general. aplicará un método
Pruebe el algoritmo con ejemplos de funciones a optimizar en un tradicional o uno basado
intervalo. en heurísticas.
• Intercambie ejemplos de problemas de búsqueda con otros
estudiantes del curso. Compare los resultados obtenidos al ejecutar Momento: Primera
los programas. prueba parcial y la
prueba Integral.
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
8
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE
EVALUACIÓN
Producto: Aplicación de
Materiales Instruccionales: conceptos bio-inspirados
en una abstracción del
• Material instruccional de apoyo.
problema.
• Software: lenguaje de programación de propósito general
• Presentación: “Optimización” Procedimiento: Se
• Direcciones electrónicas suministradas en el MIA valorará la correcta
aplicación del concepto
Actividades a realizar: de inspiración biológica.
• Lea el capítulo 1, sección 1.2, y en el capítulo 2, secciones 1.2 y 3 en
el MIA. Instrumento: Una
• Resuelva los ejercicios y autoevaluación propuestos en el material prueba presencial de
instruccional. desarrollo donde se
• Vea en la presentación, los métodos de búsqueda bio-inspirados. aplicará un concepto
2 • Investigue sobre problemas a los cuales se les pueda dar un proveniente de la
Aplicar conceptos biología a una situación
bio-inspirados en la
tratamiento para su solución, empleando conceptos bio-inspirados.
• Implemente algoritmos que generen poblaciones de individuos. dada.
realización de
abstracciones a Consulte la dirección electrónica (sección 2):
[Link] Momento: Primera
problemas.
prueba parcial y la
prueba Integral.
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
9
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE
EVALUACIÓN
Materiales Instruccionales: Producto: Aplicación del
algoritmo genético en la
• Material instruccional de apoyo.
resolución de un
• Libro de consulta: Introducción a la Computación Evolutiva, de
problema.
C. Coello (está en formato PDF).
• Software de propósito general
• Presentación: “Algoritmos Evolutivos” Procedimiento: Se
• Direcciones electrónicas suministradas en el MIA valorará la correcta
abstracción del problema
Actividades a realizar: y la aplicación del
• Lea el capítulo 2, secciones 1 a 9 en el MIA. algoritmo genético.
3 • Lea en el capítulo 3 del libro de consulta, titulado “Principales
Aplicar algoritmos Paradigmas”, lo relacionado con el algoritmo genético. Instrumento: Una
genéticos en la prueba presencial de
• Resuelva los ejercicios y autoevaluación propuestos en el material
resolución de desarrollo donde se
problemas. instruccional.
• Vea en la presentación, lo correspondiente a los algoritmos aplicará alguna variante
evolutivos, hasta algoritmos genéticos (inclusive). del algoritmo genético.
• Diseñe estructuras de datos que permitan representar soluciones en
Momento: Primera
forma de cromosoma.
prueba parcial y la
• Implemente funciones que simulen los operadores de selección y
prueba Integral.
variación.
• Implemente el algoritmo genético. Pruebe el algoritmo con diferentes
ejemplos.
• Consulte la dirección electrónica (secciones: 3, 4 y 5):
[Link] en esta
dirección se hace referencias a algoritmos genéticos interactivos, los
cuales pueden accederse, a través de los enlaces presentados.
• Discuta con otros estudiantes del curso acerca de la implementación
del algoritmo genético.
•
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
10
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE
EVALUACIÓN
Materiales Instruccionales: Producto: Aplicación de
estrategias evolutivas en
• Material instruccional de apoyo.
la resolución de un
• Libro de consulta: Introducción a la Computación Evolutiva, de
problema.
C. Coello (está en formato PDF).
• Software de propósito general. Procedimiento: Se
• Presentación: “Algoritmos Evolutivos”. valorará la correcta
• Direcciones electrónicas suministradas en el MIA . aplicación de las
estrategias evolutivas.
Actividades a realizar: Instrumento: Una
4
Aplicar estrategias • Lea el capítulo 2, sección 11, en el MIA, el cual corresponde a prueba presencial de
evolutivas en la Estrategias Evolutivas. desarrollo donde se
resolución de • Realice un cuadro que contenga las diferentes estrategias evolutivas aplicará algún tipo de
problemas. estrategia evolutiva.
aprendidas y su descripción.
• Lea en el capítulo 3 del libro de consulta, titulado “Principales
Paradigmas”, lo referente a estrategias evolutivas. Momento: Segunda
• Resuelva los ejercicios y autoevaluación propuestos en el material prueba parcial y la
instruccional. prueba Integral.
• Vea en la presentación lo correspondiente a las estrategias
evolutivas.
• Implemente funciones en los algoritmos realizados que simulen las
estrategias evolutivas aprendidas.
• Consulte la dirección electrónica :
[Link]
[Link]
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
11
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE
EVALUACIÓN
Materiales Instruccionales: Producto: Aplicación de la
programación genética en la
• Material instruccional de apoyo.
resolución de un problema.
• Libro de consulta: Introducción a la Computación
Evolutiva, de C. Coello (está en formato PDF).
Procedimiento: Se valorará la
• Software de propósito general. correcta modelación y/o
• Presentación: “Algoritmos Evolutivos”. aplicación del algoritmo de
• Direcciones electrónicas suministradas en el MIA. Programación Genética.
Instrumento: Una prueba
Actividades a realizar: presencial de desarrollo donde
• Lea el capítulo 2, secciones 12 a 15, en el MIA, el cual se aplicará el algoritmo de
corresponde a Programación Genética. programación genética.
5 • Lea en el capítulo 3 del libro de consulta, titulado “Principales
Aplicar técnicas de Paradigmas”, lo referente a programación genética. Momento: Segunda prueba
Programación • Resuelva los ejercicios y autoevaluación propuestos en el parcial y la prueba Integral.
Genética en la material instruccional.
resolución de
problemas. • Vea en la presentación lo correspondiente a Programación
Genética.
• Implemente funciones en los algoritmos realizados que
simulen la aplicación del algoritmo de programación genética.
Pruebe el algoritmo con ejemplos.
• Consulte la dirección electrónica :
[Link]
• Comparta con otros estudiantes del curso ejemplos del uso de
estrategias evolutivas, que permitan probar los algoritmos
implementados.
•
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
12
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE
EVALUACIÓN
Producto: Aplicación de la
Materiales Instruccionales: meta-heurística basada en
colonias de hormigas para la
• Material instruccional de apoyo.
resolución de un problema.
• Software de propósito general
• Presentación: “Inteligencia Social” Procedimiento: Se valorará la
• Direcciones electrónicas suministradas en el MIA correcta modelación y/o
aplicación del algoritmo.
Actividades a realizar:
• Lea en el MIA, capítulo 3, la sección sobre algoritmos basados Instrumento: Una prueba
en colonias de hormigas. presencial de desarrollo donde
se aplicará el algoritmo basado
6 • Resuelva los ejercicios y autoevaluación propuestos en el en colonias de hormigas.
Aplicar los
material instruccional.
conceptos y técnicas Momento: Segunda prueba
relacionados con los
enjambres de • Diseñe las estructuras de datos apropiadas para implementar parcial y la prueba Integral.
hormiga para la el algoritmo.
resolución de
problemas. • Vea en la presentación lo correspondiente a los algoritmos
hormiga.
• Implemente funciones en los algoritmos realizados que
simulen la aplicación del algoritmo hormiga.
• Consulte en la siguiente dirección electrónica :
[Link]/juanra/jornadas0809/O_Cordon.pdf
la sección que trata sobre los algoritmos hormiga.
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
13
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE
EVALUACIÓN
Materiales Instruccionales: Producto: Aplicación de la
meta-heurística basada en
• Material instruccional de apoyo.
enjambres de partículas para
• Software de propósito general
la resolución de un problema.
• Presentación: “Inteligencia Social”
• Direcciones electrónicas suministradas en el MIA Procedimiento: Se valorará la
correcta modelación y/o
Actividades a realizar: aplicación del algoritmo de
• Lea en el capítulo 3 del MIA, la sección que corresponde a enjambres.
Optimización por enjambres de partículas.
• Resuelva los ejercicios y autoevaluación propuestos en el Instrumento: Una prueba
material instruccional. presencial de desarrollo donde
• Vea en la presentación lo correspondiente a los algoritmos de se aplicará el algoritmo basado
optimización de partículas. en optimización de partículas.
7
Aplicar los • Diseñe las estructuras de datos apropiadas para implementar
conceptos y técnicas el algoritmo. Momento: Segunda prueba
relacionados con los • Implemente funciones que realicen la evaluación de las parcial y la prueba Integral.
enjambres de partículas, su generación aleatoria y su topología. Luego
partículas para la implemente el algoritmo de optimización de partículas.
resolución de
• Discuta con otros estudiantes del curso aspectos relacionados
problemas.
con la implementación del algoritmo de enjambres de
partículas.
• Consulte la dirección electrónica :
[Link]
• Consulte en la siguiente dirección electrónica :
[Link]/juanra/jornadas0809/O_Cordon.pdf
la sección dedicada a los algoritmos de enjambres de
partículas.
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
14
OBJETIVO ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE
EVALUACIÓN
Producto: Aplicación de algún
Materiales Instruccionales: método bio-inspirado en la
resolución de un problema.
• Material instruccional de apoyo.
• Libro de consulta: Redes Neuronales Artificiales y sus
Procedimiento: Se valorará la
Aplicaciones, Xabier Basogain.
correcta modelación del
Documento en formato PDF: Hojas de Cálculo para la
problema, la implementación del
Simulación de Redes de Neuronas Artificiales(RNA),
algoritmo y la obtención de la
García, J., López, A. M., Romero, J. E., García, A. R.,
solución.
Camacho, C., Cantero, J. L., Atienza, M.,Salas, R.
8 • Software de propósito general Instrumento: Trabajo práctico.
Resolver un • Direcciones electrónicas suministradas en el MIA y otras
problema del mundo que traten los temas a abordar.
real, empleando los Momento: Entrega de las
conceptos y técnicas especificaciones con la primera
relacionados con los parcial, por parte de la carrera y
algoritmos Actividades a realizar: consignación del problema
evolutivos, la resuelto con la prueba Integral,
inteligencia social o por parte del estudiante.
enfoques afines. • Lea en el capítulo 4 del MIA, los temas expuestos.
• Investigue en la web sobre estos temas y otros afines a la
Computación Evolutiva.
• Lea los casos de estudio.
• Diseñe algoritmos apropiados para la resolución de
problemas de optimización, empleando nuevos enfoques
bio-inspirados.
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
15
V. BIBLIOGRAFÍA
Obligatoria
Coello, C. A., Introducción a la Computación Evolutiva (Notas de Curso), 2008,
En formato PDF.
Mazzei, M., E., (2013) Texto UNA: Computación Evolutiva (UNA). En formato PDF.
Complementaria
Arrioja, N., Inteligencia Artificial. Users, Gradi S.A. Argentina, 2007.
Basogain, X., Redes Neuronales Artificiales y sus Aplicaciones,1998. En formato
PDF.
Bonabeau, E., Dorigo, M., Theraulaz ,G., Swarm Intelligence, From Natural to
Artificial Systems, Santa Fe Institute Studies in the Sciences of Complexity,
Oxford University Press,1999.
Dorigo, M., Stüzle, T., Ant Colony Optimization, MIT Press, 2004.
Goldgerg, D., E., Genetic Algorithms in Search, Optimization, and Machine
Learning, Addison-Wesley, 1989.
Kennedy J., Eberhart R., Swarm Intelligence. Morgan Kaufmann Publishers,
2001.
Koza J.,R., Genetic Programming II, MIT Press, 1994.
Michalewicz, .Z ., How to solve it. Modern Heuristics. Springer , 1998.
Michalewicz, Z., Genetic Algorithm + Data Structures = Evolutionary . Springer,
1996.
Nilsson, N., Artificial Intelligence: A New Sinthesis. Morgan Kaufmann Publishers
Inc., 1998.
Russell, S. J., Norvig, P., Inteligencia Artificial, Un Enfoque Moderno. Pearson
Educación, S. A., Madrid, 2003.
Computación Evolutiva (Cód. 350) Elaborado por: Msc. María Eugenia Mazzei – UNA - 2015
