1. Descripción del problema
El proyecto genera una malla curricular equilibrada a partir de un conjunto de cursos con créditos y pre-requisitos, distribuyendo cada curso en un semestre sin dejar de cumplir los límites de créditos y de cantidad de ramos por semestre. Corresponde a una variante del Balanced Academic Curriculum Problem (BACP). Para resolverlo se implementaron dos metaheurísticas: Hill Climbing y un Algoritmo Evolutivo, ambas construidas sobre una solución inicial generada con un algoritmo greedy. La calidad de una malla se mide con el error cuadrático medio (MSE) de los créditos entre semestres: mientras más bajo, más equilibrada queda la carga académica.
2. Análisis del problema
Definición del sistema
El sistema toma como entrada un archivo de texto con los parámetros del plan (número de semestres, rangos de créditos y de cantidad de ramos por semestre) y la lista de cursos con sus créditos y pre-requisitos. Con esa información arma la malla curricular y aplica los algoritmos de optimización hasta obtener una distribución válida y lo más equilibrada posible.
Entidades del dominio
Curso: representa una asignatura. Guarda nombre, créditos, la lista de cursos que
son pre-requisito suyo y la de cursos que dependen de él, además del rango de semestres en que puede
ubicarse (semestre_min, semestre_max), calculado una sola vez a partir de
la cadena de dependencias.
Semestre: representa un período académico. Mantiene los cursos que tiene asignados y el total de créditos actualizado en forma incremental, para no tener que recalcular la suma completa cada vez que se evalúa una solución.
MallaCurricular: clase central que agrupa todos los cursos y semestres del plan. Implementa la función objetivo, la validación de restricciones, la construcción de la solución inicial (greedy) y el movimiento de un curso entre semestres. Es la única clase que modifica el estado de la solución; los algoritmos operan sobre ella a través de su interfaz pública.
AlgoritmoOptimizacion, HillClimbingOpt, AlgoritmoEvolutivoOpt: la primera es una
clase abstracta con el método virtual puro optimizar(). Las otras dos la heredan e
implementan, respectivamente, la búsqueda local por Hill Climbing y la búsqueda poblacional del
Algoritmo Evolutivo. Ambas reciben una referencia a la malla sobre la que trabajan.
Interacción con el medio externo
| Componente externo | Tipo | Descripción |
|---|---|---|
Archivos *.txt | Entrada | Instancias del problema (BACP y UTFSM) |
| Consola | Salida | Progreso del Algoritmo Evolutivo durante la ejecución |
output.txt | Salida | Resultados de HC y AE: métricas, validez y malla generada |
3. Definición de requerimientos
CU-01: Carga y validación de una instancia curricular
Actor: usuario del sistema.
Precondición: existe un archivo *.txt con formato válido.
Flujo principal:
- El usuario indica el archivo de entrada a procesar en
main.cpp. - El sistema parsea los parámetros
p, a, b, c, dy crea laMallaCurricular. - Se cargan los cursos con sus créditos y pre-requisitos.
- Se calcula el rango de semestres válido para cada curso según sus dependencias.
Postcondición: la MallaCurricular queda lista para recibir un algoritmo de optimización.
CU-02: Optimización por búsqueda local (Hill Climbing)
Actor: sistema, invocado desde main().
Precondición: la malla ya fue cargada (CU-01).
Flujo principal:
- Se construye una solución inicial válida con el algoritmo greedy.
- En cada iteración se busca un movimiento de un curso a otro semestre que reduzca el MSE.
- Si se encuentra, se aplica de inmediato y se cuenta como movimiento.
- El proceso termina cuando ningún movimiento mejora el MSE o se llega al máximo de iteraciones.
Postcondición: la malla contiene la mejor solución encontrada por Hill Climbing, con MSE, tiempo y número de movimientos registrados.
CU-03: Optimización mediante Algoritmo Evolutivo
Actor: sistema, invocado desde main().
Precondición: la malla ya fue cargada (CU-01).
Flujo principal:
- Se construye la solución greedy y se generan 100 copias diversificadas aplicando movimientos aleatorios.
- En cada generación se evalúa el MSE de cada individuo de la población.
- Se seleccionan padres con ruleta ponderada, favoreciendo a los de menor MSE.
- Cada individuo de la nueva generación recibe una mutación, aleatoria al inicio y progresivamente más dirigida.
- El proceso se repite hasta convergencia o hasta 1000 generaciones.
Postcondición: la malla contiene la mejor solución encontrada por el Algoritmo Evolutivo.
4. Diseño
4.1 Diagrama de clases
Figura 1. Diagrama de clases del sistema, con la relación entre MallaCurricular, Curso, Semestre y los algoritmos de optimización.
4.2 Diagrama de secuencia - CU-02 (Hill Climbing)
Figura 2. Diagrama de secuencia para el caso de uso CU-02.
5. Implementación
El código fuente (src/main.cpp) está comentado por bloques: cada clase y cada método tiene
una línea o un bloque de comentario que explica su responsabilidad dentro del sistema, siguiendo la
misma organización que se describe en la sección de diseño. Esto permite que cualquier integrante
del equipo, o un tercero, entienda el rol de cada parte sin tener que leer la implementación completa.
No se incluyen en la entrega los archivos HTML que generaría una herramienta de documentación
automática, ya que son redundantes con lo comentado en el código y con este mismo informe.
El programa se ejecuta con ./programa (usa data/bacp8.txt por defecto) o
recibiendo una o más instancias como argumentos, por ejemplo
./programa data/bacp10.txt data/utfsm3.txt. Durante la ejecución se imprime en consola
el progreso de cada algoritmo (confirmación de carga, movimientos o generaciones, y validez de la
malla resultante), lo que permite observar cada caso de uso sin necesidad de abrir output.txt.
6. Pruebas
6.1 Caso de prueba 1 - CU-01: carga de bacp8.txt
Figura 3. Consola tras ejecutar ./programa: carga exitosa de data/bacp8.txt.
La instancia bacp8.txt define un plan de 8 semestres con 46 asignaturas, con
restricciones de entre 10 y 24 créditos por semestre y entre 2 y 10 ramos por semestre. El sistema
parsea correctamente los parámetros, construye los cursos con sus pre-requisitos y calcula el rango
de semestres válido para cada uno.
6.2 Caso de prueba 2 - CU-02: Hill Climbing sobre bacp8.txt
Figura 4. Resultado de Hill Climbing en consola: 1 movimiento aplicado, MSE final 11.375, malla válida.
Partiendo de la solución greedy inicial, Hill Climbing encontró un movimiento que reduce el MSE hasta 11.375 y luego no encontró más mejoras, por lo que convergió en una sola iteración. El tiempo de ejecución fue de 0 ms y la malla resultante es válida.
6.3 Caso de prueba 3 - CU-03: Algoritmo Evolutivo sobre bacp8.txt
Figura 5. Evolución del mejor MSE por generación y resultado final del Algoritmo Evolutivo en consola.
La población inicial (100 individuos diversificados a partir del greedy) mejora rápidamente durante la generación 0, bajando de un MSE de 113.375 a 27.375 en varios saltos sucesivos. En generaciones posteriores (17, 20, 21 y 23) sigue bajando hasta 7.375, y finalmente alcanza el mínimo de 5.375 en la generación 538, valor con el que termina la búsqueda (127 ms), en una malla válida. La mutación pasa de aleatoria a dirigida conforme avanzan las generaciones, lo que explica que las mejoras se concentren hacia la segunda mitad de la ejecución. Como el algoritmo conserva el mejor individuo visto durante toda la búsqueda (elitismo), el valor final coincide siempre con el mejor valor observado en consola.
| Algoritmo | Instancia | MSE final | Válido | Tiempo | Movimientos / generaciones |
|---|---|---|---|---|---|
| Hill Climbing | bacp8.txt | 11.375 | Sí | 0 ms | 1 movimiento |
| Algoritmo Evolutivo | bacp8.txt | 5.375 | Sí | 127 ms | 538 generaciones |
6.4 Dificultades encontradas
- Pasar el código de procedural a orientado a objetos sin alterar la lógica de los algoritmos: el original eran seis funciones libres, algunas con hasta 17 parámetros. Hubo que revisar con cuidado a qué clase le correspondía cada responsabilidad antes de mover el código.
-
Mantener 100 soluciones en paralelo en el Algoritmo Evolutivo sin duplicar toda la malla:
se resolvió con la estructura
EstadoMalla, que guarda solo la asignación de cursos y los créditos por semestre, mientras que los datos fijos de los cursos quedan en una sola instancia deMallaCurricular. -
Compilar en Windows con MSYS2 dio problemas con el PATH de las DLL de soporte. Se optó por trabajar
con WSL y Ubuntu, donde
build-essentialdeja todo configurado sin pasos adicionales. -
La función
movimiento()original recibía 17 parámetros. Al pasar a ser un método deMallaCurricularque opera sobre los atributos del objeto, quedó con solo dos parámetros. -
El Algoritmo Evolutivo no aplicaba elitismo: al terminar el bucle, el mejor individuo se buscaba en
la población final, pero la selección y mutación de las últimas generaciones podían haber
perdido al mejor individuo visto durante la búsqueda. Esto hacía que el valor reportado en
output.txtfuera a veces peor que el mejor valor mostrado en consola. Se corrigió guardando una copia del mejorEstadoMallaapenas se encuentra un nuevo mínimo, y restaurándola al final en vez de re-escanear la población.
6.5 Bugs conocidos
- El algoritmo greedy puede dejar un curso sin asignar si no cabe en ningún semestre y los límites ya están al máximo permitido. No ocurre con las instancias incluidas porque los cursos están en orden topológico en el archivo de entrada, pero no hay una verificación explícita para el caso contrario.
-
El cálculo de
semestre_maxa partir de los post-requisitos se hace en una sola pasada hacia adelante, lo que puede ser impreciso en planes con cadenas de dependencia largas que no estén ordenadas topológicamente en el archivo de entrada.
7. Código fuente
El proyecto comprimido está organizado en src/ (código fuente) y data/
(instancias *.txt), con Makefile y README.md en la raíz.
No incluye binarios ni archivos generados por el IDE.