Sistema Integral de Asignación de Carga Académica con la Utilización de Algoritmos Evolutivos para Resolución del Problema de Horarios en la UPVM

ÍNDICE DE CONTENIDOS

Capítulo 1. Introducción a los Horarios Académicos
1.1. La globalización y las Tecnologías de la Información y Comunicaciones
1.2. Las TIC y los Horarios Académicos
1.3. Panorama general del caso de estudio:“La Universidad Politécnica del Valle de México”
1.4. Problemáticas detectadas en los casos de estudio.
1.5. La importancia y relación de las TIC en el desarrollo de SIACA
1.6. Contenido del Libro

Capítulo 2. Antecedentes del Sistema Integral de Asignación de Carga Académica ysu aplicación en la UPVM
2.1. Introducción
2.2. Asignación de la carga académica
2.3. Análisis del problema de Generación de ACA en la UPVM
2.4. Variables involucradas

Capítulo 3. Los Algoritmos Evolutivos
3.1. Introducción
3.2. Los Algoritmos Evolutivos
3.3. Principales características de los algoritmos evolutivos
3.4. Componentes de los algoritmos evolutivos
3.5. Algoritmos evolutivos multiobjetivos
3.6 Algunos ejemplo del uso de los Algoritmos evolutivos

Capítulo 4. Diseño del Algoritmo evolutivo multiobjetivo para la asignación de lacarga académica en la UPVM
4.1. Introducción
4.2. Definición de las variables involucradas
4.3. Asignación de los espacios n variables a la carga académica
4.4. Aplicación del algoritmo evolutivo

Capítulo 5. Desarrollo del Sistema Integral de Asignación de Carga Académica
5.1. Introducción
5.2. Planeamiento del Sistema Integral de Asignación de Carga Académica
5.3. Diseño del Sistema Integral de Asignación de Carga Académica
5.4. Desarrollo del módulo Portada
5.5. Desarrollo del módulo Contraseña
5.6. Desarrollo del módulo Menú Principal
5.7. Desarrollo del módulo Permisos y Restricciones
5.8. Desarrollo del módulo Docentes
5.9. Desarrollo del módulo Catálogos
5.10. Desarrollo del módulo Horarios

Capítulo 6. Resultados Obtenidos
6.1. Prospectiva, escalamiento e impacto social

7. Referencias

Resumen

La asignación de la carga académica cualquier institución educativa en México es un proceso complejo debido a la cantidad de variables que se presentan y el criterio con el que se aplican. Este trabajo presenta un algoritmo evolutivo que se va a aplicar a un sistema el cual va a ser capaz de encontrar la asignación óptima de clases, maestros, espacio y horarios. Se realizaran pruebas al algoritmo, tomando como base los requerimientos en un período cuatrimestral determinado de la división de informática (DIIN) de la Universidad Politécnica del Valle de México (UPVM) y una lista de los maestros disponibles y su horario, en busca de encontrar los mejores resultados que los obtenidos en forma manual.

Abstract

The assignment of the academic load any educational institution in Mexico is a complex process due to the number of variables that occur and the criterion applied. This paper presents an evolutionary algorithm to be applied to a system which will be able to find the optimal allocation of classes, teachers, space and time. Test the algorithm were made, based on the requirements in a four-month period determined by the division of information technology (Deen) at the Polytechnic University of the Valley of Mexico (UPVM) and a list of teachers available and schedule, looking to find better results than those obtained manually.

Palabras Clave

Tecnología de la Información y Comunicaciones (TIC)

C Sharp

MySql

Algoritmo evolutivo

Asignación de carga académica

Grupo-materia

Plan reticular

Perfil académico.

ABREVIATURAS

Abbildung in dieser Leseprobe nicht enthalten

SIGLAS

Abbildung in dieser Leseprobe nicht enthalten

Capítulo 1. Introducción a los Horarios Académicos

1.1. La globalización y las Tecnologías de la Información y Comunicaciones

Actualmente la globalización, conocida como un proceso que se inicia en el siglo XV con el descubrimiento de América, consiste básicamente en ampliar los horizontes humanos al comunicar personas de diferentes culturas y grados de desarrollo social y económico; ésta ha hecho entrar a la humanidad en la era de la comunicación universal (Marín, 1998).

La globalización ha generado una sociedad de la información que cambia y multiplica las posibilidades de adquisición, gestión, actualización y acceso a cualquier tipo de dato a través del uso de las Tecnologías de la Información y Comunicaciones mejor conocidas como TIC (Repáraz, 2001), que son técnicas o tratamientos para el uso y transmisión de los datos a través del empleo de la computación, Internet y las telecomunicaciones.

Las TIC, con el uso de Internet, han roto las limitaciones del espacio y del tiempo en la comunicación humana, lo cual ha generado nuevas consecuencias en la educación, ya que la globalización exige a la escuela compaginar una de sus funciones esenciales, como es la transmisión de una cultura y valores universales, a través de diversos medios de aprendizaje que no están limitados al aula de clase.

Las TIC han generado nuevas herramientas, estrategias y metodologías, con diferentes funciones para los docentes como son: el interés por lograr una integración de campos de conocimiento y el uso de sus experiencias para crear elementos más innovadores para el desarrollo de diversos tipos de software o sistemas informáticos que faciliten sus actividades educativas.

Con el uso de las TIC, los diferentes tipos de usuarios logran que su empleo sea planificado y estratégico a fin de lograr un ambiente ameno y significativo en el proceso educativo orientado al uso de la red que a través del uso de Internet Explorer, Firefox, entre otros permite navegar por en un medio accesible mejor conocido como Internet, en donde los presidentes de academia y administrativos tendrán la oportunidad de seleccionar la información que les sea útil además de poder generar sus horarios académicos.

1.2. Las TIC y los Horarios Académicos

Las TIC han mejorado el proceso de la generación de horarios ya que existe la necesidad de administrar y coordinar los recursos económicos, materiales y humanos en beneficio a los requerimientos y necesidades de estas, por consiguiente en cada inicio de periodo escolar se presenta la necesidad de organizar y distribuir los horarios de clases de maestros en función a diversas variables, sin embargo la asignación de cada horario presenta condiciones particulares originadas por los docentes como son la disponibilidad, los espacios disponibles, los horarios de los alumnos y algunos otros factores que afectan su realización.

Los horarios académicos ó Scheduling como comúnmente se conoce; es un proceso que consiste en crear una plantilla en la cual se tengan perfectamente estructuradas las asignaciones, (materias, lugar, día y la hora) que serán impartidas por los docentes sin que existan traslapos entre los profesores ó la ubicación de las materias, debido a esto es considerado un problema de asociación de n variables ya que se tiene que organizar una secuencia de eventos con recursos limitados y restricciones impuestas en un periodo de tiempo especificado. Por consiguiente la presente investigación pretende analizar el problema de asignación de la carga académica (ACA) en la generación de Horarios Académicos en una institución de educación superior con el fin de establecer un modelo general del problema y proponer un sistema computacional para resolverlo utilizando algoritmos evolutivos.

En la actualidad existen diversas técnicas para la resolución de problemas de ACA en los horarios, las cuales se clasifican según Jesús Mejía en 2008 como dos grandes grupos:

1. Técnicas tradicionales: Programación entera, Programación Lineal, Tableau, etc.
2. Técnicas no tradicionales: Algoritmos heurísticos o meta-heurísticos que proveen de una buena solución en un tiempo moderado y que suelen proveer de mejores resultados en instancias grandes del problema.

Otra clasificación de la problemática en ACA realizada por Wren en 1998 es la siguiente:

a) Rostering (Lista, Catalogo): ubicación de recursos en determinados periodos siguiendo un patrón.
b) Sequencing (Secuenciación): encontrar un orden para la ejecución de las actividades.
c) Timetabling: muestra cuándo una tarea o evento en particular debe ser llevado a cabo.

1.3. Panorama general del caso de estudio:“La Universidad Politécnica del Valle de México”

La Universidad Politécnica del Valle de México (UPVM), es un Organismo Público Descentralizado de Carácter Estatal, con personalidad jurídica y patrimonio propio y forma parte del Sistema de Universidades Politécnicas de la Secretaría de Educación Pública (SEP). La UPVM está basada en el modelo de competencias que surge debido a la globalización, al orden económico y social. Una característica que está presente en varios sistemas educativos es el modelo de competencias en función de una globalización humanista (Ferrer, 1999). Este surge dentro de la UNESCO, con base en la Declaración Mundial sobre la Educación Superior en el Siglo XXI: Visión y Acción, dentro de la cual se propone un nuevo modelo educativo centrado en el estudiante.

El modelo de competencias según el Instituto Politécnico Nacional (2004) se caracteriza principalmente por:

- La construcción que hacen los estudiantes de su propio conocimiento diseñan y definen sus propias trayectorias e intensidades de trabajo con el apoyo y la guía de sus profesores.
- La flexibilidad de planes y programas que reconocen las diferencias y requerimientos de los estudiantes.
- La distribución del tiempo que los docentes dedican a la planeación y el diseño de experiencias de aprendizaje.
- El desarrollo armónico de todas las dimensiones del estudiante la formación en los contenidos en donde se fomentan conocimientos propios de la profesión, y los conocimientos básicos que proporcionan las herramientas intelectuales esenciales para el aprendizaje permanente y la resolución de problemas complejos.
- El compromiso con la difusión y el fomento a la cultura científica y tecnológica, por lo que intensifica sus esfuerzos a efecto de que la sociedad reconozca la importancia del conocimiento tecnológico en el impulso al desarrollo y bienestar social.

1.4. Problemáticas detectadas en los casos de estudio.

En la UPVM el problema de asignación de horarios escolares es considerado un proceso en donde los presidentes de academia tienen que tomar de decisiones y decidir cómo asignar a los docentes en ciertos periodos de tiempo. Una definición más exacta del problema de ACA de horarios es la siguiente: “es una asignación, sujeta a restricciones, de los recursos otorgados con el propósito de ser establecidos en un espacio de tiempo, de tal manera que satisfaga lo más cercanamente posible el conjunto de objetivos deseados” (Wren,1998).

Al considerar que la asignación de horarios en la UPVM consiste en organizar un horario para las sesiones de un conjunto de asignaturas, tomando en consideración un número determinado de aulas o laboratorio en función a bloques de tiempo que presentan el problema de empates de profesores ya que las asignaturas no poseen un horario predeterminado y generalmente no todas las aulas o laboratorios no son aptas para todas las asignaturas. Las restricciones que influyen en la ACA en la UPVM son:

- El número de grupos y materia de cada cuatrimestre
- La información del perfil académico de cada docente
- Carga académica por materia o la asignación de grupos-materia por cada cuatrimestre.
- Horario del personal docente o las horas disponibles en que el profesor puede estar frente a grupo.
- Perfil académico del profesor o la asignación académica según la especialidad del docente.
- Número de alumnos por grupo o la cantidad total de alumnos que se asigne a un grupo.
- Número y características de aulas o espacios físicos disponibles en función a las necesidades específicas de cada asignatura y su capacidad máxima de alumnos que pueden ocuparlo.
- El turno matutino inicia de 7:00 a 14:00 hrs
- El turno vespertino inicia de 15:00 a 21:00 hrs.
- Se cuenta con una infraestructura de16 aulas, 4 salas de cómputo y 1 laboratorios de redes
- Se requieren como mínimo 5 horas de clase al día por grupo.

A continuación se clarifica los formatos y la importancia de los documentos oficiales que se contemplan en el ejercicio de impartición de asignaturas y el seguimiento académico dentro de la UPVM. Estos son los horarios de los grupo y el Horario del docente.

El horario de grupo (Anexo 1) es un instrumento que sirve como guía de control para que la UPVM de manera autónoma y a través de ciertas políticas, defina las asignaturas, horas, días, docentes y espacios de cada grupos para así cuantificar la distribución de cada asignatura que se imparta. Por otra parte, el horario del docente (Anexo 2) es un instrumento que sirve como guía para que los docentes determinen el lugar, el grupo y la materia que tienen que impartir considerando el día, la hora y el espacio.

Una vez detectadas las problemáticas con los horarios es necesario delimitar al considerar los instrumentos más relevantes para el análisis, diseño, codificación y aplicación del Sistema de Asignación de carga académica por consiguiente: si se contempla un diseño sencillo y práctico con la implementación de un algoritmo evolutivo en la generación de horarios académicos acorde a los requerimientos de los presidentes de academia y administrativos, entonces estos podrán generar una solución viable al problema de asignación de la carga académica en la UPVM en la división de informática.

1.5. La importancia y relación de las TIC en el desarrollo de SIACA

La presente investigación a través del análisis, diseño, codificación y fases de pruebas va a diseñar un sistema para administrar, gestionar y generar los horarios. Se trata de un proceso nuevo en la UPVM debido a que este tipo de instrumento no existe ni se usa actualmente.

Por lo tanto lo que se pretende es la elaboración de un Algoritmo Evolutivo que se aplique a un sistema de computo para reducir los errores que se pueden presentar actualmente en la asignación de horarios. A continuación se podría plantear la siguiente pregunta que se contestara en el desarrollo de la presente investigación: ¿se puede superar el problema de la elaboración de horarios académicos mediante el diseño y aplicación de un algoritmo evolutivo en el sistema de asignación de carga académica como apoyo a los presidentes de académica y administrativos el docente y en beneficio del docentes?.

Una vez definida la pregunta de investigación a continuación se presenta el objetivo general:

Desarrollar una solución computacional, basada en algoritmos evolutivos que sea capaz de resolver de manera automatizada la asignación de horarios de la División de Informática de la Universidad Politécnica del Valle de México.

A continuación se presentan los objetivos específicos son los siguientes:

- Diseñar un algoritmo evolutivo, que sea capaz de brindar una solución eficiente y eficaz al problema de asignación de horarios.
- Generar un prototipo que permita valorar adecuadamente el desempeño de los algoritmos que se generen con base en la metodología antes descrita
- Crear un sistema que sea capaz de optimizar la recolección, modificación y extracción de la información de experiencias educativas, asignaturas, docentes y horarios escolares.

Para concluir se puede afirmar que si se contemplan todos y cada uno de los parámetros en el análisis, diseño, codificación y fase de pruebas en el desarrollo del Sistema de Asignación de Horarios; éste va a representar un apoyo para las labores los presidentes de academia y una mejora en aspectos como la administración escolar.

1.6. Contenido del Libro

El documento está organizado de la siguiente manera:

En el capítulo 2 se propone el modelo general del problema de Asignación de Carga Académica (ACA) en una la UPVM. Se hace un análisis completo del problema y se identifican las variables involucradas. Finalmente se establece el modelo particular de la UPVM para resolver este problema.

En el capítulo 3 se presenta una breve introducción a los Algoritmos Evolutivos (AE) como una rama de la IA y se describen sus características generales. Se hace especial énfasis en los esquemas de representación y los operadores utilizados.

El capítulo 4 describe el prototipo computacional de optimización del problema antes descrito haciendo uso de AE, indicando su análisis, diseño, desarrollo y codificación.

En el capítulo 5 se muestran los resultados obtenidos por el AE desarrollado en la ACA para la UPVM. Se presentan dos escenarios distintos del problema, solucionados de la manera tradicional y por el AE para analizar las características de cada solución.

Capítulo 2. Antecedentes del Sistema Integral de Asignación de Carga Académica y su aplicación en la UPVM

2.1. Introducción

En la actualidad en la UPVM el problema de optimización de los horarios es un problema indefinido y que no puede formularse de forma clara y concisa debido a la cantidad de posibles variables que conlleva realizar este proceso. Sin embargo el abordaje matemático directo no es posible, y los modelos clásicos que son analíticamente tratables son también demasiado generales para proveer la precisión que requiere un horario. Además es importante mencionar que el tratamiento analítico resulta demasiado difícil y por tanto, costoso computacionalmente sobre todo cuando trabajamos con funciones de varias variables.

Para realizar una adecuada asignación de carga académica en la UPVM se realiza un modelo general (ACA) donde se establecen los factores que influyen así como la relación entre ellos, por ejemplo, es importante determinar el número de grupos-materia de acuerdo al archivo general de los alumnos y el plan reticular correspondiente, también es muy útil la información del perfil académico de la planta docente ya que servirá para hacer una buena asignación de profesores para cada grupos-materia.

Durante la realización de este proceso los presidentes de academia supervisan la información de cada docente, las preferencias académicas de los profesores y su horario disponible para impartir las materias, además de considerar algunos otros factores que afectan la realización de la ACA como la carga académica factible para los profesores, los espacios disponibles para la impartición de clases y algunas otras políticas particulares de asignación de clases.

2.2. Asignación de la carga académica

La carga académica se puede definir como el proceso de asignación de los recursos (grupos, horas, días, docentes y asignatura) que determina un proceso de organización en una institución académica. A continuación se presenta el modelo general del problema en la UPVM se presenta la Fig. 1, en donde se aprecian las factores involucrados y la relación entre ellos.

Abbildung in dieser Leseprobe nicht enthalten

Figura 1. Modelo General de la Asignación de la Carga Académica en la UPVM.

Este modelo se divide en cuatro partes: profesores, grupos, Reglamento y los espacios disponibles, el cual se puede explicar de la siguiente manera:

- Profesores: se contempla todas las variables en donde interviene el profesor como su perfil académico, su disponibilidad de horario y las materias a impartir.
- Grupos: se contempla las materias disponibles por grupo, el período escolar y la carrera a la que pertenece.
- Reglamento: está vinculados con las reglas y políticas particulares de la UPVM en la asignación de carga académica (profesores y
- Los espacios: considera los espacios disponibles para la impartición de clases, la cantidad y características de las aulas de clases y laboratorios

2.3. Análisis del problema de Generación de ACA en la UPVM

Al no contar con periodos de configuración de asignaturas iguales, no se puede asignar una asignatura a un aula fija permanentemente, más aun, pueden crearse nuevas asignaturas en base a los alumnos y la disponibilidad de los profesores. Esto conlleva a la necesidad de configurar un horario cada fin de ciclo (cada 3 meses) para todas las asignaturas que serán impartidas en cada grupo. Algunos problemas detectados por la generación de una mala planeación del ACA son:

a) Cruce de horarios: generan espacios, grupos y docentes asignados mas de una vez en diversas horas y días.
b) Falta de planeación: genera la necesidad de crear un nuevo horario cada 3 meses, mala asignación de los recursos, inconsistencia de la carga de experiencias asignada a docentes (docentes con una mayor carga académica) y inconsistencia de la carga en las aulas (aulas con mayor número de asignaturas asignadas que otras)
c) Perdida de tiempo: genera que desfase del calendario académico y que los presidentes de academia deban abandonar sus otras actividades por un periodo de tiempo considerable.

Una vez definidos los principales problemas, a continuación se presentan las principales restricciones que se detectaron:

a) Las asignaturas no tienen un día, espacio y horario fijo, ya que puede ser movido de acuerdo a las necesidades del profesor que la imparte.
b) No existe un número de horas fijo por asignatura; de hecho existen asignaturas con una necesidad de 3 horas a la semana y otras con 6 horas, de las cuales se reparten en horas practicas (laboratorio) y teóricas (aula).
c) La división de informática de la UPVM tiene 16 posibles aulas y 5 laboratorios todas ellos con características especificas

Tomando en cuenta los datos anteriores, se puede generar una espacio de búsqueda en función a las posibles combinaciones en donde cada asignatura se determina de la siguiente manera:

ET=EPP+EPT

EPP= HAP * DP * HD * DD * AD

EPT= HAT * DP * HD * DD * AD

En donde:

ET: espacios totales disponibles para la asignatura

EPP: total de espacios disponibles para horas practicas de la asignatura

EPT: total de espacios disponibles para horas teóricas de la asignatura

HAP: horas practicas requeridas por la asignatura

HAT: horas teóricas requeridas por la asignatura

DP: numero de docentes disponibles para impartir la asignatura

HD: numero de horas disponibles al día

DD: numero de días disponibles

AD: numero de espacios disponibles

Un ejemplo de esto se puede visualizar con la asignatura de Programación Orientada a Objetos que tiene 6 horas a la semana (2 son teóricas y 4 son practicas) el resultado de este calculo es:

ET=1920+3840=5760

EPP=4*8*3*5*4=1920

EPT=2*8*3*5*16=3840

En donde podemos obtener 5760 posibles combinaciones para esta asignatura en particular. Si tomamos en consideración que en un periodo escolar se imparte esta asignatura a 6 grupos tenemos entonces: 5760 * 6 = 34,560 posibles horarios. Por supuesto, la amplia mayoría de ellos no son horarios válidos debido a las restricciones impuestas por la UPVM, algunas de ellas de carácter forzado (restricción dura) y otras que pueden tolerarse(restricción blanda), la Tabla 1 muestra las restricciones existentes:

Tabla 1. Restricciones del problema de asignación de carga académica en la UPVM

Abbildung in dieser Leseprobe nicht enthalten

2.4. Variables involucradas

Una vez definidas las restricciones y la problemática a continuación se presentan las variables que influyen en la asignación de grupos-materias en la UPVM:

a) Carga académica por cuatrimestre: se refiere a la asignación de grupos-materia por cada ciclo escolar.
b) Horario del personal docente: las horas disponibles en que el profesor puede estar frente a grupo (15 hrs por semana para profesores de asignatura y 20 hrs por semana para profesores de tiempo completo)
c) Perfil académico del profesor: hace referencia a la asignación de las materias que puede dar el profesor en función a su perfil académico
d) Número de alumnos por grupo: alumnos máximos que pueden ser asignados al grupo.
e) Número de espacios disponibles: espacios físicos disponibles para la impartición de clases (16 aulas, 4 laboratorios de computo y 1 laboratorio de redes).
f) Turnos disponibles y su horarios: se refiere a los horarios de cata turno (el turno matutino inicia de 7:00 a 14:00 hrs y el turno vespertino inicia de 15:00 a 21:00 hrs.
g) Horas disponibles por grupos: se refiere a las horas máximas y mínimas de los grupos (mínimo 5 horas y máximo 8 horas de clase al día por grupo).
h) Horas máximas por día: son 3 horas consecutivas.

Capítulo 3. Los Algoritmos Evolutivos

3.1. Introducción

El problema de la generación de ACA puede ser abarcado utilizando la computación evolutiva que es una rama de la inteligencia artificial que se emplea en problemas de búsqueda extensa y no lineal, en donde los métodos convencionales no son capaces de encontrar soluciones en un tiempo razonable. Por consiguiente la computación evolutiva se basa en los procesos naturales de la evolución, en donde muchos científicos han elegido a la evolución natural como medio de inspiración para la creación de algoritmos para resolver este tipo de problemas, ya que la evolución es una manera evidente de mostrar mejoras cuantitativas y cualitativas en cualquier especie del planeta.

Este tipo de computación que intenta simular a la evolución natural es generada a través de una función, normalmente llamada función de aptitud, en donde los individuos son soluciones completas generadas normalmente al azar y se evalúan a modo de que los mejores individuos sean capaz de reproducirse y dejar descendencia, las cuales pasarán por la mismo proceso una y otra vez hasta cumplir con una condición que se tiene que cumplir para detener el proceso; este tipo de computación se basa en uso de algoritmos que se basan en el principio de evolución o supervivencia del mejor conocidos como Algoritmos Evolutivos.

3.2. Los Algoritmos Evolutivos

Los algoritmos evolutivos pueden ser descritos como estrategias de optimización y búsqueda de soluciones, que se basan en la inspiración de la evolución en distintos sistemas biológicos, estos algoritmos tiene como objetivo mantener un conjunto de individuos que representan una posible solución del problema. Estos individuos tienen como función mezclarse y competir entre sí, siguiendo el principio de selección natural por el cual sólo los mejor adaptados sobreviven al paso del tiempo, en busca de una evolución hacia la mejor solución.

Los algoritmos evolutivos se pueden considerar como un método de optimización que trata de hallar una tupla de valores (xi,...,xn) que minimice una determinada función F(xi,...,xn). Los algoritmos evolutivos, se pueden utilizar para parametrizar el problema en una serie de variables, (xi,...,xn) que se codifican en una población de cromosomas. En esta población se debe aplicar uno o varios operadores genéticos y se fuerza una presión selectiva en donde los operadores utilizados se aplican en los cromosomas, o en la población.

Debidos a este funcionamiento los algoritmos evolutivos pueden ser implementados de forma independiente del problema. En los últimos años muchos investigadores de todo el mundo han utilizado y generado nuevos operadores y nuevas variantes algorítmicas evolutivas especializadas en los más diversos problemas. Sin embargo, no deben considerarse a las técnicas evolutivas como técnicas aisladas ni pensar que son adecuadas a todos los casos, si no entenderlas en el contexto de la que hoy se conoce como técnicas algorítmicas de Soft-Computing que según Bonissone, 1997, “es una rama de investigación muy activa en la actualidad que viene a recoger el testigo de los avances producidos en el campo de la Inteligencia Artificial después de que este resurgiera con fuerza a mediados de los años 80 del pasado siglo”.

Este tipo de algoritmo son altamente usados y aplicables que han tenido una adopción muy rápida tanto en la computación, la industria hasta en el ámbito militar, debido a esto, muchos centros de investigación aplican técnicas de inteligencia artificial en general y de computación evolutiva (Akbarzadeh-t, 2000) y cada vez existen más profesionales que aplican y utilizan estos algoritmos. Debido a su aplicabilidad este tipo de algoritmos hace posible hallar soluciones realistas y computacionalmente tratables en áreas como:

a) Optimización numérica con un número indeterminado de variables
b) Aprendizaje automático y reconocimiento de patrones.
c) Implementación de sistemas con situaciones anómalas o inesperadas.
d) Creación de sistemas en tiempo real, que sean capaces de dar una respuesta rápida en tiempos cortos.
e) Tratamiento de flujos de información de grandes volúmenes de datos.

3.3. Principales características de los algoritmos evolutivos

Las principales características de los algoritmos evolutivos es que permiten determinar lo siguiente:

a) Una población inicial de individuos.
b) Un medio ambiente para la población que cause una selección natural.
c) Una función de calidad para los individuos dentro del medio ambiente.
d) Las variables que se van a considerar para realizar una cruza en donde se seleccionan a dos o más individuos (padres) y se generan nuevos individuos a partir de la combinación de las características de los padres.

e) Las variables que se van a considerar para la mutación en donde se toma a un individuo mediante cierta probabilidad y se altera su código ligeramente, hasta generar a un nuevo individuo.

Otra característica de los algoritmos evolutivos es que su seudocódigo se realiza de la siguiente manera:

Inicio

Iniciar una población con soluciones candidato aleatorias

Evaluar cada candidato con una función de calidad

Seleccionar padres cruzar padres y generar una nueva población

Mutar nuevos individuos

Evaluar nuevos individuos

Seleccionar individuos que pasaran a la siguiente generación

Repetir todo el algoritmo hasta que se cumpla la condición de paro

Fin

La estructura general de los algoritmos evolutivos se ilustra en la figura 2.

Abbildung in dieser Leseprobe nicht enthalten

Figura 2. Estructura General de los Algoritmos Evolutivos.

Y la última característica de este tipo de algoritmo es que se utiliza lo siguiente para definir cada una de las características:

- Cadenas string de un cierto alfabeto de preferencia de algoritmos genéticos para representar al candidato.
- Vectores con valores reales en función de estrategias evolutivas.
- Máquinas de estado finito en función a Programación evolutiva.
- Árboles en función a Programación genética.

Sin embargo, existen representaciones alternativas dependiendo del problema que se quiere resolver, en donde se tienen que considerar los siguientes términos de los algoritmos genéticos como son:

a. La Estructura de codificación con la cual se construyen las soluciones para el problema se llaman cromosomas
b. Uno o más cromosomas pueden ser requeridos para conformar una población.
c. El conjunto completo de cromosomas se llama genotipo
d. Un individuo en particular, un organismo resultante, se llama fenotipo
e. Cada cromosoma contiene una serie de valores individuales llamados Genes.
f. Cada gen contiene información valiosa de una variable en particular y su
g. ubicación dentro del individuo se conoce como loco
h. Los diferentes valores de un gen son llamados alelos

3.4. Componentes de los algoritmos evolutivos

Los principales componentes de los algoritmos evolutivos son los siguientes:

a) Representación: consiste en construir candidatos, que deben pasar del contexto original del problema a su espacio de soluciones (representación de solución) donde la evolución toma su lugar, esto es construir el fenotipo (problemas), el genotipo (codificación de soluciones) y el proceso contrario genotipo a fenotipo (decodificación).

b) Función de calidad: tiene como objetivo representar los requerimientos para la adaptación de los individuos en el medio ambiente (determinar su calidad y asigna su probabilidad de supervivencia o cruza dentro de la población).

c) Población: son un conjunto de soluciones (genotipos o fenotipos) en un medio ambiente, y es la unidad que evoluciona en los algoritmos evolutivos, ya que los individuos son solo elementos estáticos que no cambian o se adaptan.

d) Evolución: se da al pasar de generación en generación con los individuos que se adaptan, aunque, por supuesto, un número mayor de individuos otorga una mayor diversidad en el espacio de solución de un problema.

e) Mecanismo de selección de padres: es el encargado de seleccionar los individuos que podrán generar descendencia, se determina con los individuos de mayor calidad (función de calidad).

f) Mecanismo de selección de supervivientes: este mecanismo de supervivencia actúa después de generada la descendencia y es la encargada de elegir a los individuos de mejor calidad para que pasen a la siguiente generación.

g) Operadores de variación: tiene como objetivo crear nueva descendencia a partir de una anterior. Los principales operadores de variación son:

a. Mutación: son variaciones impuestas a un individuo, este operador es siempre estocástico y su objetivo es dar mayor diversidad a la población
b. Recombinación o cruza: consiste en combinar dos o más individuos para generar nuevos con características similares a sus predecesores, a este proceso se le llama descendencia.

h) Inicialización: es la primera población, normalmente generada por individuos aleatorios, sin embargo, puede ser que se genere con base en una estrategia implementada para ayudar al algoritmo en el proceso de búsqueda.

i) Condición de término: existen varias condiciones de terminación para los algoritmos evolutivos, entre las más populares tenemos, el máximo tiempo de procesamiento permitido por el CPU, el periodo de tiempo determinado, el número de generaciones (ciclos del algoritmo) y la función de calidad ha llegado a su límite (se encontró al mejor individuo o a un óptimo deseable).

3.5. Algoritmos evolutivos multiobjetivos

El problema de la generación de ACA puede ser abarcado como un problema de optimización multiobjetivo (POM) que consiste en encontrar un vector de variables de decisión que satisfagan un cierto conjunto de restricciones y optimice un conjunto de funciones objetivo (J.J Durillo, 2010). Los Algoritmos Evolutivos y los Algoritmos Evolutivos Multiobjetos son estructuralmente similares, pero la diferencia radica en que un AEMO calcula i(i ≥ 2) funciones de aptitud mientras que el AE calcula solamente i; sin embargo, el operador de selección de un AE trabaja con un solo valor escalar. La forma más sencilla de conservar la estructura de un AE simple al abordar problemas multiobjetivo consiste en transformar el vector de aptitudes en un valor escalar.

Los algoritmos evolutivos multiobjetivos son aquellos que no incorporan el concepto de optimo de Pareto en el mecanismo de selección del algoritmo evolutivo, por consiguiente jerarquizan a la población de acuerdo a si un individuo es no dominado o no (usando el concepto de ́optimo de Pareto).

Históricamente podemos considerar que han habido dos generaciones de algoritmos evolutivos multiobjetivo:

a) Primera Generación: Caracterizada por el uso de jerarquización de Pareto y nichos. Algoritmos relativamente simples. También se produjeron enfoques m ́as rudimentarios (p.ej., funciones agregativas lineales).
b) Segunda Generación: Se introduce el concepto de elitismo en dos formas principales: usando selección (μ + λ) y usando una población secundaria.

Algunas ventajas de utilizar las técnicas evolutivas son:

1. Permite la generación de varios elementos del conjunto de óptimos de Pareto en una sola ejecución.
2. No requieren que el problema a resolver cumpla condiciones de continuidad y/o derivabilidad en sus funciones objetivo
3. Permiten mantener un conjunto de soluciones potenciales, el cual es sometido a un proceso de selección y es manipulado por operadores genéticos (generalmente la recombinación y la mutación (Eckart, 1999)).

En una reseña de AEMOs Fonseca y Fleming (Carlos M, 1994) presentan las principales estrategias para llevar a cabo la asignación de aptitud de los individuos. Estas estrategias se muestran a continuación:

1. Métodos de agregación: combinan los objetivos en una función escalar que es utilizada para calcular la aptitud un individuo, tienen la ventaja de producir una sola solución.
2. Métodos basados en población: son capaces de evolucionar múltiples soluciones no dominadas al mismo tiempo en una sola ejecución; cambian el criterio de selección durante la fase de reproducción y la búsqueda es guiada en varias direcciones al mismo tiempo.

[...]