tesisv2 2 figzeus.inf.ucv.cl/~jrubio/docs/tesis/tesisvf.pdf · 6.2.1 formato de archivos de entrada...
TRANSCRIPT
1
INDICE GENERAL
INDICE GENERAL ...................................................................................................................................................... 1 INDICE DE FIGURAS.................................................................................................................................................. 3 1. Introducción y Discusión Bibliográfica ..................................................................................................................... 4
1.1 Discusión Bibliográfica....................................................................................................................................... 4 1.2 Motivación .......................................................................................................................................................... 5 1.3 Estructura de la tesis............................................................................................................................................ 6
2. Análisis de Objetivos y Metodología......................................................................................................................... 7
2.1 Objetivo General ................................................................................................................................................. 7 2.2 Objetivos Específicos.......................................................................................................................................... 7 2.3 Hipótesis.............................................................................................................................................................. 8 2.4 Metodología ........................................................................................................................................................ 8
3. Estado del Arte........................................................................................................................................................... 9
3.1 El Curriculum de Estudios en la Educación Superior. ........................................................................................ 9 3.1.1 Información sobre el currículo.....................................................................................................................9 3.1.2 Organización del currículo. ....................................................................................................................... 11 3.1.3 El sistema de créditos. ............................................................................................................................... 12
3.2 Problemas de Satisfacción de Restricciones...................................................................................................... 13 3.2.1 Conceptos Básicos de CSP. ....................................................................................................................... 13 3.2.2 Notación de CSP........................................................................................................................................ 14
3.3 Consistencia en un CSP..................................................................................................................................... 14 3.3.1 Niveles de Consistencia Local................................................................................................................... 14 3.3.2 Consistencia Global................................................................................................................................... 15
3.4 Colaboración de Técnicas ................................................................................................................................. 16 3.4.1 Ramificación Informada. ........................................................................................................................... 16 3.4.2 Búsqueda Local Restringida. ..................................................................................................................... 16
3.5 Heurísticas de selección de variables y selección de valores. ........................................................................... 18 4. Colaboración de Técnicas para resolver el Problema de Diseño de Mallas Curriculares ....................................... 20
4.1 Formulación del Problema. ............................................................................................................................... 20 4.2 Estrategias de Enumeración. ............................................................................................................................. 22
4.2.1 Búsqueda Local. ........................................................................................................................................ 22 4.3 Utilizando Métodos de Mejora (Improvement Methods) para guiar el proceso de resolución. ......................... 23
4.3.1 Representación. ......................................................................................................................................... 25 4.3.2 Función de Evaluación. .............................................................................................................................28 4.3.3 Modificación del Programa. ...................................................................................................................... 29
4.4 Optimizando Programas por Mejoras Iterativas. ............................................................................................... 31 4.4.1 Grafos Disyuntivos.................................................................................................................................... 32 4.4.2 Profundización Iterativa. ........................................................................................................................... 33 4.4.3 Tabu Search. .............................................................................................................................................. 34 4.4.4 Simulated Annealing. ................................................................................................................................ 35 4.4.5 Algoritmos Genéticos. ............................................................................................................................... 37
4.5 Propiedades deseables de la Metaheurística de resolución................................................................................ 39 5. Un Algoritmo de Mejora Iterativa Estocástica para resolver el Problema de Diseño de Mallas Curriculares ......... 42
5.1 Solución Inicial. ................................................................................................................................................ 42 5.2 Estructura del Vecindario. ................................................................................................................................. 42 5.3 El Algoritmo...................................................................................................................................................... 43
2
5.4 La Heurística Constructiva. ............................................................................................................................... 44 5.5 Esquema de Solución Propuesto para BACP. ................................................................................................... 45
5.5.1 Representación. ......................................................................................................................................... 46 6. Diseño de Prototipo.................................................................................................................................................. 48
6.1 Descripción del Prototipo.................................................................................................................................. 48 6.1.1 Modificaciones al modelo clásico. ............................................................................................................ 49
6.2 Análisis Funcional............................................................................................................................................. 49 6.2.1 Formato de Archivos de Entrada. .............................................................................................................. 49 6.2.2 Arquitectura del Prototipo. ........................................................................................................................51
6.3 Definición de propagadores y estrategia de enumeración en GecodeJ.............................................................. 52 6.4 Resultados Computacionales............................................................................................................................. 54
6.4.1 Restricciones Suaves versus Restricciones Duras. .................................................................................... 54 7. Conclusiones y Trabajo Futuro ................................................................................................................................ 57 REFERENCIAS........................................................................................................................................................... 58
3
INDICE DE FIGURAS Fig. 1 Función de distribución de soluciones en un espacio completo........................................................................... 6 Fig. 2 Un algoritmo de búsqueda local genérico.......................................................................................................... 23 Fig. 3. Un algoritmo general de mejora iterativa. ........................................................................................................25 Fig. 4. Grafo Disyuntivo representando un problema de asignación de trabajos con 3 trabajos y 3 maquinas............ 26 Fig. 5. Seudo-código dfor the randomised iterative improvement algorithm for course timetabling .......................... 44 Fig. 6. Esquema de Solución Propuesto....................................................................................................................... 45 Fig. 7. Cada evento (curso) es asignado según una lista de timeslots (períodos), y para cada timeslot t’ ∈ T’, se elige un conjunto de eventos e ∈ E que se colocará en este timeslot................................................................................... 46
Fig. 8. Matriz binaria, donde cada evento tiene que ser puesto exactamente una vez en un timeslot; ∑=
=n
jijx
1
1. ...... 46
Fig. 9. Visualización de malla curricular mediante la opción “Visualizar Malla”. ...................................................... 51 Fig. 10. Modelo Conceptual del Prototipo. .................................................................................................................. 52 Fig. 11. Espacio (Gecode Space). ................................................................................................................................ 53 Fig. 12. Resumen de Resultados Computaciones......................................................................................................... 54 Fig. 13. Resultados Computaciones Primera Solución ................................................................................................ 55 Fig. 14. Resultados Computaciones Mejor Solución ................................................................................................... 56 Fig. 15. Comparación Resultados Computacionales de la búsqueda de la primera v/s la mejor Solución .................. 56
4
Capítulo 1
Introducción y Discusión Bibliográfica
Un factor clave a considerar cuando se evalúa el éxito académico de los estudiantes es la carga académica
que tienen en cada semestre. La manera usual de medir esta carga es asignar, para cada curso, un número de créditos
que representan la cantidad de esfuerzo requerido para aprobar el curso. De este modo, la carga académica de cada
periodo esta dada por la suma de los créditos de cada curso inscrito en el periodo. Generalmente, se imponen
explícitamente varias restricciones cuando se desarrolla el currículo. Por ejemplo, se debe definir una carga máxima
por periodo para prevenir sobrecarga, y se deben establecer varias relaciones de precedencia sobre algunos cursos.
Asumiendo que una carga académica balanceada favorece las actividades académicas y facilita el éxito de los
estudiantes, se propone el desarrollo de un modelo para el diseño de currículos académicos balanceados.
El problema de diseñar un currículo académico balanceado consiste en la asignación de cursos a periodos de tal
forma que la carga académica de cada periodo sea balanceada, es decir, lo más similar posible entre un semestre y
otro. En esta tesis, se considera como carga académica balanceada la noción de crédito que representa el esfuerzo en
tiempo necesario para seguir exitosamente el curso. El proyecto se concentra en las carreras de informática ofrecidas
por la Pontificia Universidad Católica de Valparaíso, esto es, carreras de 4 y 6 años (8 y 12 periodos académicos
respectivamente). Sin embargo, en un primer acercamiento, se consideran además currículos para carreras de 5 años
(10 periodos académicos).
1.1 Discusión Bibliográfica
En la literatura se pueden encontrar diversos esfuerzos y propuestas para lograr una solución óptima al
problema de diseñar un currículo balanceado. El año 2001, en [Castro01] se presenta el primer acercamiento,
mediante un enfoque comparativo entre técnicas de programación lineal entera y estrategias (o heurísticas) de
selección de variables y de valor, basadas en la programación con restricciones. En [Hnich02] se presenta otro
acercamiento, este se centra en la comparación entre programación lineal entera y programación con restricciones,
aquí se coloca especial énfasis en el modelado del problema como CSP (Constraint Satisfaction Problem), en
[Flener02] también se presenta una propuesta desde el modelado, utilizando técnicas de modelado matricial. La
primera propuesta de hibridación entre técnicas completas e incompletas surge el año 2006 en [Lambert06] donde se
propone la utilización de algoritmos genéticos para guiar la búsqueda de soluciones al problema mediante
propagación de restricciones. En Chile, además de [Castro01], se puede referenciar el trabajo presentado en
[Solar06] donde se muestra una propuesta de balanceo de carga académica para un currículo basado en
5
competencias, se modela el problema como un problema de balanceo del tipo SALBP (Simple Assembly Line
Balancing Problem)-1 y se utiliza un programa computacional que implementa la heurística RPW (Ranked
Positional Weight).
Por otra parte, se han desarrollado numerosos estudios acerca de las estrategias de enumeración. Varios trabajos se
han centrado en la determinación de estrategias específicas de enumeración para cierta clase de problemas. Para un
problema dado, algunos estudios también tratan de determinar la mejor estrategia basándose en algún criterio estático
([Beck04] por ordenación de variables, [Filipic93], [Flener01] por la mejor heurística, [Gebruers04] por el mejor
solver). Sin embargo, ya que sus efectos son bastante impredecibles, decidir a priori sobre una buena estrategia de
enumeración es muy difícil (generalmente casi imposible). Para determinar una estrategia se puede utilizar
información acerca del proceso de resolución [Monfroy07] (ver [Canzi93], [Carchrae04] para un algoritmo de
control).
1.2 Motivación
En la literatura existen numerosas propuestas que consideran la utilización de técnicas incompletas (también
denominadas técnicas de búsqueda local) para “guiar” el proceso de solución de problemas combinatorios difíciles
modelados como CSP (ver [Monfroy06] para un ejemplo). Considerando el éxito de estos acercamientos, se esta
interesado en utilizar este tipo de modelado como alternativa para la modelación y resolución del problema de
BACP.
Con el fin de mejorar la eficiencia de los algoritmos, actualmente se ha concentrado gran interés en la colaboración
entre la Programación con Restricciones y la Búsqueda Local [Francois03]. La idea principal es beneficiarse de la
eficiencia de la Búsqueda Local y la flexibilidad de la Programación con Restricciones, ambos aspectos tan
necesarios para resolver los problemas que demanda el mundo real.
Las técnicas de resolución completas realizan primero una búsqueda en profundidad buscando mediante la
alternación entre propagación de restricciones y enumeración. La propagación de restricciones poda el árbol de
búsqueda eliminando valores que no pueden estar en ninguna solución. La enumeración crea una rama por
instanciación de una variable (ejemplo, x = v) y otra distinta (ejemplo, x ≠ v) por backtracking cuando se prueba que
la primera rama no satisface. Todas las estrategias de enumeración que conservan soluciones son válidas, pero esto
tiene un tremendo impacto sobre la eficiencia. Además, ninguna estrategia es la mejor para todos los problemas.
Existen distintas formas de hacer colaborar ambas técnicas, las cuales se pueden clasificar en dos grandes clases:
� Integración de la Programación con Restricciones en la Búsqueda Local. Por ejemplo: utilizando la
Programación con Restricciones para la búsqueda de vecinos en la Búsqueda Local [Pesant96, Pesant97] o para
buscar solo vecinos factibles (ver figura 1).
� Integrar la búsqueda local dentro de la Programación con Restricciones. En donde la búsqueda local se usa en
6
partes del árbol de búsqueda o dentro de cada nodo.
En esta tesis se propone un esquema de colaboración, para la resolución del problema de diseño de un currículo
académico.
1.3 Estructura de la tesis
La tesis comienza con el análisis de objetivos y una breve descripción de la metodología de desarrollo para
la investigación, luego se plantea la hipótesis. Continúa con el estado del arte donde se definen el origen del
problema a resolver y los principales conceptos utilizados en el desarrollo de la solución propuesta. En el capitulo 4
se presenta el diseño de la solución, aquí se incluye un esquema de colaboración entre programación con
restricciones y búsqueda local estocástica, además se presentan detalles de la implementación del prototipo de
sistema para la solución propuesta. La tesis sigue con la presentación y análisis de los resultados empíricos
obtenidos. Finalmente, en el capitulo 7, se resume y concluye la tesis.
Fig. 1 Función de distribución de soluciones en un espacio completo
7
Capítulo 2
Análisis de Objetivos y Metodología
Durante la última década, la colaboración entre las dos grandes familias de algoritmos de resolución de
problemas combinatorios difíciles; las técnicas completas que recorren todo el espacio de búsqueda, con lo cual se
puede estar interesado en encontrar una solución, todas las soluciones o comprobar que el problema no tiene
solución, y las técnicas incompletas, que recorren ciertos sectores del espacio de búsqueda, intentando pasar por los
sectores más auspiciosos y encontrando sólo algunas soluciones, han despertado el interés de la comunidad científica
debido a su capacidad para explotar y explorar eficientemente grandes espacios de soluciones. En este ámbito, esta
tesis aborda el desarrollo, análisis y puesta a punto de un esquema de colaboración entre técnicas completas e
incompletas, específicamente basadas en Programación con Restricciones y Búsqueda Local.
La implementación y validación del esquema de colaboración se realiza considerando como problema de referencia
la optimización en el diseño de mallas curriculares balanceadas para carreras universitarias.
2.1 Objetivo General
• Diseñar, implementar y evaluar un esquema de colaboración entre técnicas completas e incompletas y un
prototipo de sistema para la generación de mallas curriculares balanceadas.
2.2 Objetivos Específicos
� Investigar y proponer el fundamento teórico para el desarrollo de un modelo de generación de mallas
curriculares basado en satisfacción con restricciones.
� Diseñar e implementar un modelo de generación de mallas curriculares inspirado en heurísticas de búsqueda
local y técnicas de programación con restricciones.
� Evaluar el rendimiento del modelo propuesto según variables, restricciones y dominios, mediante la utilización
de Benchmarks reconocidos por la academia.
� Implementar un prototipo de sistema de generación de mallas curriculares balanceadas para la Escuela de
Ingeniería Informática de la Pontificia Universidad Católica de Valparaíso.
8
2.3 Hipótesis
El desarrollo de la investigación asociada a esta tesis de Magíster se sustenta en la validación de la siguiente
hipótesis: “Si se utiliza un esquema de colaboración entre técnicas completas e incompletas de resolución de
problemas combinatorios difícil se puede resolver el problema de diseño de mallas curriculares balanceadas para
carreras universitarias”.
2.4 Metodología
Para el desarrollo de esta tesis y de la investigación a asociada a la misma se utilizaran básicamente dos
metodologías de trabajo, las cuales son:
� Metodología Bibliográfica: según la cual se obtiene información de búsquedas realizadas en Internet,
encontrando páginas y documentos de índole académico respecto a la temática del proyecto. Proporcionando
una base sólida para crear las referencias bibliográficas respectivas.
� Metodología Descriptiva-Cualitativa: a partir de la metodología anterior se obtiene la información necesaria para
extraer, como el nombre de la metodología lo indica, las descripciones y cualidades de los temas que conciernen
a este proyecto para lograr un trabajo que explicite los aspectos más relevantes relacionados con los conceptos
de interés (CSP, Métodos de Búsqueda Local y el BACP; Balanced Academic Curriculum Problem).
9
Capítulo 3
Estado del Arte
3.1 El Curriculum de Estudios en la Educación Superior.
Tradicionalmente se ha designado al plan de estudios como un conjunto de asignaturas y actividades
graduadas, sistematizadas y armonizadas, de manera que concurran a la obtención de un objetivo o grupo de
objetivos, correspondientes a un nivel educativo.
Dentro de los esquemas de la pedagogía, el plan de estudios es denominado curriculum, y se le define como "El
conjunto de enseñanzas, teorías y prácticas, que han de realizar para ser promovidos los alumnos, como el orden de
ellos dentro de una institución docente" [Canudas72].
Todos los procedimientos modernos para organizar la materia de enseñanza aspiran a que el curriculum sea orgánico
y funcional. Un plan orgánico de enseñanza enlaza de un modo natural y múltiple las asignaturas o temas concretos,
mediante una red de comunicaciones que permite aproximar los contenidos más diversos del saber y de la técnica,
evitando la dispersión mental de los alumnos y logrando un efecto total. Como el verdadero aprender implica una
transformación graduada y valiosa de las aptitudes humanas, el curriculum orgánico concibe de peculiar modo las
materias de enseñanza: Estas dejan de ser meros signos de erudición e información, y se convierten en medios
eficientes para la realización de la vida presente y futura, de los aspirantes a profesionales.
La materia de enseñanza se selecciona y ordena para crear en el alumno la mejor habilidad en las situaciones de la
profesión, y el aprendizaje queda así articulado en función del círculo de experiencias actuales y posibles del alumno.
Los nuevos curriculum de estudio son al mismo tiempo planes de formación y planes de materias, ofrecen cuadros de
experiencias, métodos de trabajo y orientación para evaluar los resultados del aprendizaje. Indican en una unidad
diferenciada que materia puede y debe ser asimilada por el educando y cómo puede ello realizarse.
3.1.1 Información sobre el currículo.
El curriculum flexible es una forma de organización de los estudios universitarios que permite la máxima adecuación
de ellos a las aptitudes y a los intereses de los estudiantes, mediante una selección de matices de especialización
dentro de una pauta general. No es, por cierto, un sistema caótico, sino una mejora ordenada e inteligente de realizar
un propósito educacional concreto y bien definido. Por eso es extremadamente importante que al aplicar un
10
curriculum flexible en la universidad, exista en todos los profesores y alumnos un claro y consciente entendimiento
de su naturaleza, de su justificación y de los medios y procedimientos por los cuales es posible llevarlo a la práctica
con éxito.
La palabra curriculum designa todo el conjunto de esfuerzos que despliega la universidad para la realización de sus
fines. Ellos comprenden: un programa de cursos; un programa de investigaciones; un programa de actividades
culturales, físicas y recreativas; un programa de prácticas; un conjunto de normas escritas o tácitas, que establecen un
sistema de trabajo del que se desprende una atmósfera de dignidad académica y de respeto personal entre los
integrantes de la universidad, y expresa, además, de manera práctica su filosofía y sus objetivos.
Hay muchas maneras posibles de organizar el curriculum de una universidad, y hay numerosos factores que influyen,
en cada caso, en la decisión final sobre cómo debe quedar organizado. Sus rasgos esenciales se van depurando y
estableciendo con el tiempo en forma de tradiciones que determinan una fisonomía propia en la universidad y
tipifican su influencia en la vida del país. Sin embargo, cuando el curriculum se establece en forma rígida alrededor
de ciertos conceptos inmóviles, se corre el riesgo de llegar al estancamiento de la situación y de cerrar las puertas al
progreso científico y a la capacidad individual.
Sobre todo, en una época como la actual en que los conocimientos científicos y tecnológicos se desarrollan tan rápida
y ampliamente, determinando el surgimiento de nuevas disciplinas o la reestructuración interna de ellas, la
universidad, como generadora de este dinámico proceso de creación, debe, por consiguiente, adoptar una estructura y
régimen académico especialmente flexibles que le permita organizar rápidamente los cambios que llevan implícitos
la creación e incorporación de nuevos conocimientos.
El campo de los conocimientos humanos es cada vez más amplio y exige mayor especialización. Pero al mismo
tiempo la especialización no debe hacer perder de vista la perspectiva cultural y social en la cual ha sido posible que
se den esos conocimientos y la condición esencial del hombre que los adquiere y los aplica. Dicho en otras palabras:
la formación como profesional es inseparable de su formación como hombre y como miembro de una cultura, y la
responsabilidad de la universidad es atender a esa formación de manera integral.
La aplicación del curriculum flexible, si bien favorece la acentuación de los estudios de acuerdo con el interés o la
inclinación del alumno, le demanda al mismo tiempo un mayor sentido de responsabilidad, y a los profesores una
más estrecha orientación y consejo.
Todo esto, que es consecuencia del establecimiento de un sistema flexible en el régimen de estudios, representa a la
vez pasos decisivos hacia el fortalecimiento del ambiente universitario y de la relación académica y personal
profesor-alumno, que es otra parte importantísima del curriculum total de la universidad.:
11
3.1.2 Organización del currículo.
Las asignaturas que se dictan en la universidad corresponden en general a los siguientes grupos:
Cursos básicos a nivel general: Se designa así al grupo de cursos seleccionados por la universidad, con el fin de
proporcionar al estudiante una cultura básica universitaria en las ciencias y humanidades, orientación psicológica y
vocacional, que le permita seguir una especialización posterior u orientarse a otra actividad con una formación más
efectiva. Los cursos básicos o de nivel general no se dictan, por lo tanto, en función de ninguna profesión o
especialidad en particular, sino como núcleo y fundamento de toda formación universitaria. Este grupo de cursos es
común a todos los programas. Estos cursos no se dictan necesariamente como un bloque previo a los estudios
profesionales, sino más bien pueden distribuirse a lo largo de los primeros semestres de estudios, constituyendo una
de las partes del curriculum balanceado. De estos cursos, los que corresponden a humanidades son ofrecidos por los
departamentos respectivos y los que corresponden a ciencias básicas, por los departamentos de física, matemáticas y
química, pero se matriculan en ellos todos los alumnos de la universidad, según sus requisitos.
Cursos requisitos del programa académico: Se denomina así al grupo de cursos que debe ser estudiado y aprobado
por todos los estudiantes que siguen un determinado programa académico. El título profesional o grado académico
que otorga la universidad al término de los estudios está avalado por un cierto bagaje de conocimientos y habilidades
que definen básicamente la profesión o especialidad. Estos conocimientos y habilidades se enseñan y desarrollan en
los cursos que constituyen los requisitos del programa académico. Los cursos requisitos del programa académico son
seleccionados, coordinados y evaluados por la dirección del programa académico respectivo, y constituyen el núcleo
básico de cursos de la profesión o de la especialidad. Es necesario observar, sin embargo, que estas dos partes del
curriculum que hemos descrito hasta ahora, formado por los cursos básicos o de nivel general y los cursos requisitos
del programa académico, constituyen un todo indivisible. No se puede ser profesional, u optar un grado académico,
sin antes haber completado los cursos del nivel general y los requisitos del programa académico seleccionado. Sin
embargo, esto no quiere decir en forma absoluta que sea necesario completar primero todos los cursos de nivel
general para empezar a estudiar los cursos requisitos del programa académico o de especialización. Dentro de ciertos
límites, impuestos por la estructura de cada programa académico, es posible llevar cursos del programa de
especialización desde el comienzo de los estudios de nivel general, siempre que no tengan prerrequisitos que hagan
necesario postergarlos.
Los cursos electivos: Deliberadamente se ha dejado los cursos electivos fuera de los dos grupos -cursos de nivel
general y cursos del programa académico profesional- en que se ha considerado dividido el curriculum, porque en
cada uno de estos dos grupos puede haber cursos electivos. Es decir, que los cursos electivos no constituyen una
categoría especial por el hecho de ser electivos. La condición de electivos es adicional y depende de las
circunstancias en que se encuentre cada curso dentro del curriculum. En principio, todos los cursos son electivos.
Esto quiere decir que de un conjunto de cursos que ofrece la universidad, el estudiante sólo está obligado a escoger
12
los equivalentes a cierto número de créditos. Sin embargo, al elegir un determinado programa académico profesional
o de especialización, el estudiante encuentra que para algunos cursos que necesita tomar más tarde se exige como
prerrequisito ciertos cursos que corresponden al presente ciclo. Ello hace que automáticamente estos últimos cursos
se transformen en obligatorios para él. Pero de todas maneras, siempre le quedará un margen para tomar cursos que
no son prerrequisito de ninguno que deba tomar más adelante, y dentro de esos sí juega su libre elección. Estos son
los que se denominan, por esa razón, "cursos electivos". Lo son en tanto que el estudiante puede elegir entre varias
posibilidades sin restricciones, pero siempre debe tomarlos para completar el número total de créditos que le exige el
curriculum de su programa académico.
3.1.3 El sistema de créditos.
La flexibilidad del curriculum requiere un instrumento operativo que permita estimar el trabajo académico de los
estudiantes y traducirlo en cifras que revelen en cualquier instante su situación y su progreso dentro de la
universidad. Este instrumento es el sistema de créditos. El crédito es una unidad de evaluación del trabajo efectuado
para aprobar una asignatura. Para fines prácticos, por ejemplo, se hace equivaler un crédito a una hora semanal de
clase expositiva o a dos horas semanales de trabajos prácticos durante un semestre. Pero en realidad, cuando se dice
que un curso tiene digamos, 3 créditos, no solamente se esta indicando que tiene 3 horas de clase o 2 horas de clase
expositiva y 2 horas de práctica, sino que, para ganar los 3 créditos, el alumno debe cumplir satisfactoriamente con
todos los requisitos de aprobación del curso. Estos comprenden no solamente la asistencia a las clases y a las
prácticas, sino también pasos, exámenes, consultas bibliográficas, trabajos monográficos y cualesquiera otros que
señale el profesor. Expresando en créditos el volumen de trabajo que representa cada curso, se facilita el
establecimiento de pautas que regulan la distribución equilibrada (o balanceada) de asignaturas en el curriculum, el
monto de la carga académica ponderada del rendimiento del estudiante en las diversas materias.
El número total de créditos que un estudiante debe completar para graduarse no es un número indiscriminado. El
total está repartido proporcionalmente entre las áreas en que es importante la formación de los estudiantes: cultura
general y especialización profesional.
La proporción de créditos asignada a cada una de estas áreas refleja la política académica general de la universidad o
del programa respectivo, y se traduce en el carácter final del profesional que egresará de sus aulas. Un mayor número
de créditos en cursos básicos indicará una cultura general más sólida; más créditos en cursos profesionales generales
revelarán mayor amplitud en la formación profesional; mayor acento en cursos electivos podría significar una mayor
profundización en el campo restringido de la especialidad. Al formular el curriculum, el programa establece estas
proporciones, y ellas pueden ser variadas en modificaciones sucesivas. Pero bajo la vigencia de un determinado
curriculum, el estudiante se mantiene dentro de los márgenes establecidos. Esto quiere decir que si un alumno tiene
exceso de créditos en cursos electivos, por ejemplo, no podrá aplicarlos en sustitución de cursos que le faltan en el
área de cursos de especialización profesional o en la de cursos básicos.
13
Como se ve, los créditos representan un procedimiento exacto y racional para dar significado a las calificaciones e
interpretar en cifras la situación académica real de los estudiantes. El sistema permite establecer niveles mínimos de
rendimiento y determinar cuando un alumno está encontrando dificultades en sus estudios y necesita mayor ayuda y
superar sus dificultades. Un índice ponderado demasiado bajo es una señal de alarma sobre la situación académica
del alumno y sus probabilidades de fracasar como estudiante. A veces, un reajuste oportuno en la orientación del
curriculum, una reducción en la carga académica o el consejo amistoso del profesor pueden bastar para mejorar el
rendimiento.
Antes de terminar este análisis, es oportuno señalar que, además de la aplicación del curriculum señalada, puede éste
adoptar diversas modalidades, según sean los objetivos que se pretenda alcanzar.
3.2 Problemas de Satisfacción de Restricciones.
La Satisfacción de Restricciones (Constraint Satisfaction), es un paradigma usado para resolver diversos
tipos de problemas, expresados como, encontrar las soluciones, los valores de un conjunto de variables en dominios
específicos que satisfacen un conjunto de restricciones sobre estas variables. Muchos problemas de optimización
combinatoria se pueden expresar de esta manera. En los últimos años ha tenido un desarrollo importante por la
facilidad para modelar problemas complejos, así como por la flexibilidad en el tratamiento de las restricciones. Fruto
de ello, es la generalización del paradigma en la modelación de problemas y en el tratamiento declarativo de su
implementación, para la resolución de los mismos, denominado Programación con Restricciones (Constraint
Programming) y los avances en entornos de desarrollo estandarizados. Las estrategias generales de solución en este
paradigma pertenecen a dos categorías: las que razonan sobre las propias restricciones, procedimientos de
propagación de restricciones o técnicas de consistencia y otra basada en la exploración del espacio de búsqueda con
métodos de búsqueda constructiva, a partir de la asignación sistemática de valores parciales a las variables hasta
completar la solución, con algoritmos conocidos de vuelta atrás (backtracking) y también algoritmos de ramificación
y acotación (branch and bound) para los problemas de optimización, o también mediante exploraciones del espacio
de soluciones mediante heurísticas de búsqueda local.
3.2.1 Conceptos Básicos de CSP. Asignación. Una asignación de variables, también llamado instanciación, (x, a) es un par variable-valor que
representa la asignación del valor a a la variable x. Una instanciación de un conjunto de variables es una tupla de
pares ordenados, donde cada par ordenado (x, a) asigna el valor a a la variable x. Una tupla ((x1, a1),…, (xi, ai)) es
localmente consistente si satisface todas las restricciones formadas por variables de la tupla. Para simplificar la
notación, sustituiremos la tupla ((x1, a1),…, (xi, ai)) por (a1,…, ai).
Solución. Una solución a un CSP es una asignación de valores a todas las variables de forma que se satisfagan todas
las restricciones. Es decir, una solución es una tupla consistente que contiene todas las variables del problema. Una
14
solución parcial es una tupla consistente que contiene algunas de las variables del problema. Por lo tanto diremos que
un problema es consistente, si existe al menos una solución, es decir una tupla consistente (a1, a2,…, an).
3.2.2 Notación de CSP General: El número de variables de un CSP lo denotaremos por n. La longitud del dominio de una variable xi lo
denotamos por di = |D i|. El número de restricciones totales lo denotaremos por c. La aridad máxima de una
restricción la denotaremos por k. En el caso de problemas disyuntivos, al número máximo de disyunciones que tiene
una restricción disyuntiva lo denotaremos por l.
Variables: Para representar las variables utilizaremos las ultimas letras del alfabeto en cursiva, por ejemplo x, y, z,
así como esas mismas letras con un subíndice, por ejemplo x1, xi, xj. Estos subíndices son letras seleccionadas por
mitad del alfabeto o números enteros. Al conjunto de variables xi,...., xj lo denotaremos por Xi,...,j .
Dominios/Valores: El dominio de una variable xi lo denotamos por Di. A los valores individuales de un dominio los
representaremos mediante las primeras letras del alfabeto, por ejemplo, a, b, c, y al igual que en las variables también
pueden ir seguidas de subíndices. La asignación de un valor a a una variable x la denotaremos mediante el par (x, a).
Como ya mencionamos en la definición una tupla de asignación de variables ((x1, a1),..., (xi, ai)) la denotaremos por
(a1, ..., ai).
Restricciones: Una restricción k-aria entre las variables {x1, ..., xk} la denotaremos por C1..k.. De esta manera, una
restricción binaria entre las variables xi y xj la denotaremos por Cij. Cuando los índices de las variables en una
restricción no son relevantes, lo denotaremos simplemente por C. El conjunto de variables involucrados en una
restricción Ci..k lo representaremos por XCi..k.
3.3 Consistencia en un CSP
Los algoritmos de búsqueda sistemática para la resolución de CSPs tienen como base la búsqueda basada en
backtracking. Sin embargo, esta búsqueda sufre con frecuencia una explosión combinatoria en el espacio de
búsqueda, y por lo tanto no es por si solo un método suficientemente eficiente para resolver CSPs. Una de las
principales dificultades con las que nos encontramos en los algoritmos de búsqueda es la aparición de inconsistencias
locales que van apareciendo continuamente. Las inconsistencias locales son valores individuales o combinación de
valores de las variables que no pueden participar en la solución porque no satisfacen alguna propiedad de
consistencia.
3.3.1 Niveles de Consistencia Local
Consistencia de Nodo: La consistencia local más simple de todas es la consistencia de nodo o nodo-consistencia.
Forzar este nivel de consistencia nos asegura que todos los valores en el dominio de una variable satisfacen todas las
15
restricciones unarias sobre esa variable. Así, un problema es nodo-consistente si y solo si todas sus variables son
nodo-consistentes:
Consistencia de Arco: Un problema binario es arco-consistente si para cualquier par de variables restringidas xi y xj,
para cada valor a en Di hay al menos un valor b en Dj tal que las asignaciones (xi, a) y (xj, b) satisfacen la restricción
entre xi y xj. Cualquier valor en el dominio Di de la variable xi que no es arco-consistente puede ser eliminado de Di
ya que no puede formar parte de ninguna solución. El dominio de una variable es arco-consistente si todos sus
valores son arco-consistentes. Así, un problema es arco-consistente si y solo si todos sus arcos son arco-consistentes:
Consistencia de Caminos: La consistencia de caminos (path-consistencia) es un nivel más alto de consistencia local
que la arco-consistencia. La consistencia de caminos requiere para cada par de valores a y b de dos variables xi y xj,
que la asignación de a a xi y de b a xj satisfaga la restricción entre xi y xj, y que además exista un valor para cada
variable a lo largo del camino entre xi y xj de forma que todas las restricciones a lo largo del camino se satisfagan. Un
CSP satisface la consistencia de caminos si y solo si todos los caminos de longitud dos cumplen la consistencia de
caminos. Así, un problema satisface la consistencia de caminos si y solo si todo par de variables (xi, xj) es path-
consistente
3.3.2 Consistencia Global
A veces es deseable una noción más fuerte que la consistencia local. Decimos que un etiquetado, construido
mediante un algoritmo de consistencia, es globalmente consistente si contiene solamente aquellas combinaciones de
valores que forman parte de al menos una solución.
Un etiquetado globalmente consistente es una representación compacta y conservadora de todas las soluciones
admitidas por un CSP. Es correcto en el sentido de que el etiquetado nunca admite una combinación de valores que
no desemboque en una solución. Es completo en el sentido de que todas las soluciones están representadas en él. En
una red de restricciones globalmente consistente la búsqueda puede llevarse a cabo sin backtracking.
En general, un etiquetado globalmente consistente puede requerir de forma explícita representar restricciones para
todas las variables del problema, es decir, generar etiquetas n-1-dimensionales para un problema de talla n forzando
la n-consistencia. Esta tarea tiene una complejidad exponencial en el peor caso. Para clases especiales de problemas,
niveles bajos de consistencia son equivalentes a la consistencia global [Barták01].
Para mayor información acerca de algoritmos y heurísticas de búsqueda sistemática para resolución de CSPs ver
[Manyá03].
16
3.4 Colaboración de Técnicas
Mientras todos los esquemas propuestos en la literatura comparten el común denominador de integrar
técnicas completas con incompletas, es necesario hacer una separación. Esta separación viene dada por las distintas
características, objetivos y motivaciones que plantea cada esquema. Para ello, se han separado los esquemas
propuestos en dos familias, la primera familia se denomina Ramificación Informada y la segunda familia se
denomina Búsqueda Local Restringida y está compuesta por un esquema de colaboración.
Si bien ambas familias se benefician de la colaboración, se distinguen en sus fundamentos, en su concepción y en la
necesidad que las hizo nacer. A continuación se explican las motivaciones que han llevado a los investigadores a
explorar cada familia.
3.4.1 Ramificación Informada.
En el contexto de la Programación con Restricciones, a pesar de que todas las estrategias de ramificación que
preservan todas las soluciones que son válidas, ellas tienen un gran impacto en la eficiencia del proceso de búsqueda
de una solución. El efecto de estas estrategias es difícil de predecir y en la mayoría de los casos imposible. Además,
no existe una estrategia que sea la mejor para todos los problemas.
Muchos estudios han definido algunos criterios, por ejemplo, elegir la variable con el dominio más pequeño, para el
caso de selección de variable, elegir el valor mínimo, para el caso de selección de valor. Por otro lado, para algunos
problemas se han propuesto estrategias específicas. Algunos han focalizado los esfuerzos en determinar la mejor
estrategia estáticamente sólo una vez, antes de comenzar a buscar la solución. Sin embargo, es bien conocido que
para las decisiones a priori con respecto a la selección de variable y valor es muy difícil obtener buenos resultados
(en la mayoría de los casos imposible), porque los efectos de las estrategias son impredecibles. Esto produce que,
dado un problema, una estrategia puede encontrar una solución en segundos, mientras que otra puede requerir horas.
Con el fin de aminorar ese nivel de incertidumbre, han habido intentos de obtener información del proceso de
búsqueda para ayudar a la estrategia de ramificación, ver por ejemplo [Monfroy07]. La idea es obtener buenos
resultados sin depender del conocimiento de un experto, permitiendo el uso de la Programación con Restricciones a
un rango más amplio de personas.
3.4.2 Búsqueda Local Restringida.
Son muchos los que se han preguntado cual es la diferencia esencial entre la Búsqueda Local y la Programación con
Restricciones, que hace que la Búsqueda Local escale tan bien con respecto a la otra técnica. Prestwich se hizo esa
pregunta [Prestwich01a] y llegó a la conclusión de que la principal diferencia es que la Búsqueda Local nunca se
compromete con alguna asignación de una variable. La Programación con Restricciones en cambio, prácticamente no
modifica las asignaciones que se hacen al inicio de la búsqueda, esto es, las zonas altas del árbol.
17
Específicamente, en la Programación con Restricciones se comienza con un conjunto vacío de asignaciones y
paulatinamente se van agregando asignaciones de valores a variables hasta que se completa el conjunto, con una
asignación por variable, que satisface todas las restricciones del problema, o sea, una solución. El principal problema
es que si las primeras asignaciones son erróneas, estas causan que se exploren ramas completas del árbol de
búsqueda sin éxito alguno, perjudicando enormemente la eficiencia del algoritmo, esto se denominaría como
asignación errónea temprana. Por otra parte, la Búsqueda Local hace una exploración incompleta del espacio de
búsqueda, reparando asignaciones completas, eventualmente infactibles. Para ello se trabaja con un conjunto
compuesto por una asignación por variable y se toleran asignaciones infactibles, iterativamente se repararan las
asignaciones hasta obtener una solución. Esto permite que no se sufra del problema de la asignación errónea
temprana, como en la Programación con Restricciones.
Luego de identificar uno de los principales problemas de la Programación con Restricciones, la asignación errónea
temprana, Prestwich propuso el algoritmo híbrido Búsqueda local restringida (CLS) [Prestwich00, Prestwich01b].
Este algoritmo, básicamente, es un Backtracking que permite hacer el backtrack a cualquier variable, a diferencia del
algoritmo clásico que sólo permite hacer el backtrack a la última variable instanciada. A esto se le agregan fases de
propagación de restricciones en cada nodo del árbol, con el fin de reducir el espacio de búsqueda. El objetivo es
mezclar la principal característica de la Búsqueda Local, no comprometerse con ninguna asignación en particular,
con la reducción del espacio de búsqueda de la Programación con Restricciones. La idea es simple, pero tiene serios
problemas de implementación, porque cuando se usan algoritmos de propagación de restricciones, que filtran valores
de los dominios de las variables, es sumamente complicado hacer un backtrack a una variable aleatoria en forma
eficiente. Para hacer un backtrack en forma eficiente, lo ideal es sólo deshacer los valores filtrados por la asignación
que se desea deshacer, pero es sumamente costoso mantener la información de cuales valores se han filtrado
producto de cual asignación, por lo que en la practica no se hace, y volver a filtrar todo de nuevo tiene un muy alto
costo.
Existe bastante trabajo con respecto a este último punto, cuales asignaciones filtraron cuales valores en la fase de
propagación. Formalmente esta información se conoce como explicaciones [Pesant96, Schiex94], cuya idea es
mantener toda la información necesaria para lograr hacer los backtrack de igual forma que la operación deshacer
(haciendo la analogía con los editores de texto), usando las explicaciones y sin incurrir en recomputación. En la
práctica, esto ha sido sumamente costoso y hasta el momento no se han hecho implementaciones eficientes, salvo
para problemas muy específicos.
En un intento por mejorar este enfoque, en esta tesis, se propone un mecanismo para implementar, en forma
eficiente, la Búsqueda Local Restringida, siguiendo un esquema basado en una heurística constructiva, en conjunto
18
con un sistema de Programación con Restricciones basado en propagación para resolver diversas instancias del
BACP.
3.5 Heurísticas de selección de variables y selección de valores. Un algoritmo de búsqueda para la satisfacción de restricciones requiere el orden en el cual se van a estudiar
las variables, así como el orden en el que se van a instanciar los valores de cada una de las variables. Seleccionar el
orden correcto de las variables y de los valores puede mejorar notablemente la eficiencia de resolución. También
puede resultar importante una ordenación adecuada de las restricciones del problema [Monfroy07]. A continuación
se explica en que consisten estas heurísticas:
� Ordenación de Variables: Experimentos y análisis de muchos investigadores han demostrado que el orden en el
cual las variables son asignadas durante la búsqueda puede tener un impacto significativo en el tamaño del
espacio de búsqueda explorado. Generalmente las heurísticas de ordenación de variables tratan de seleccionar lo
antes posible las variables que más restringen a las demás. La intuición es tratar de asignar lo antes posible las
variables más restringidas y de esa manera identificar las situaciones sin salida lo antes posible y así reducir el
número de vueltas atrás. La ordenación de variables puede ser estática y dinámica.
a) Las heurísticas de ordenación de variables estáticas generan un orden fijo de las variables antes de
iniciar la búsqueda, basado en información global derivada del grafo de restricciones inicial.
b) Las heurísticas de ordenación de variables dinámicas pueden cambiar el orden de las variables
dinámicamente basándose en información local que se genera durante la búsqueda.
El problema de los algoritmos de ordenación estáticos es que ellos no tienen en cuenta los cambios en los
dominios de las variables causados por la propagación de las restricciones durante la búsqueda, o por la densidad de
las restricciones. Esto es porque estas heurísticas generalmente se utilizan en algoritmos de comprobación hacia atrás
donde no se lleva a cabo la propagación de restricciones.
� Ordenación de Valores: En comparación, se ha realizado poco trabajo sobre heurísticas para la ordenación de
valores. La idea básica que hay detrás de las heurísticas de ordenación de valores es seleccionar el valor de la
variable actual que más probabilidad tenga de llevarnos a una solución, es decir identificar la rama del árbol de
búsqueda que sea más probable que obtenga una solución. La mayoría de las heurísticas propuestas tratan de
seleccionar el valor menos restringido de la variable actual, es decir, el valor que menos reduce el número de
valores útiles.
Resulta de suma importancia, entonces, el desarrollo de modelos de resolución “guiados” desde el punto de vista
tanto de estrategias de ordenación de variables como también de valores, que permitan la generalización del modelo
de resolución y su aplicación a diversos problemas del mismo tipo. Tradicionalmente la programación de
restricciones ha tratado el estudio para un problema dado, de un modelo y una estrategia de resolución que generen
19
un árbol de búsqueda computacionalmente factible. Sin embargo, generalmente, estas estrategias aplicadas a
problemas distintos ofrecen resultados muy pobres.
20
Capítulo 4
Colaboración de Técnicas para resolver el Problema de Diseño de Mallas Curriculares
4.1 Formulación del Problema.
El BACP, propuesto inicialmente en [Castro01], consiste en diseñar un currículo académico balanceado
mediante la asignación de periodos a cursos de una manera en que la carga académica de cada periodo sea
balanceada, es decir, lo más similar posible. El currículum debe respetar las siguientes regulaciones administrativas y
académicas:
� Currículo Académico: un currículo académico esta definido por un conjunto de cursos y un conjunto de
prerrequisitos relacionados con estos.
� Número de periodos: los cursos deben ser asignados dentro de un número máximo de periodos académicos.
� Carga Académica: cada curso tiene asociado un número de créditos o unidades que representa el esfuerzo
académico requerido para el éxito de este.
� Prerrequisitos: varios cursos tienen otros cursos como prerrequisitos.
� Carga Académica Mínima: se requiere un número mínimo de créditos por periodo para considerar a un
estudiante de tiempo completo.
� Carga Académica Máxima: un número máximo de créditos por periodo que no debe ser sobrepasado.
El objetivo es asignar un periodo para todos los cursos de modo que se satisfacen las restricciones de número mínimo
y máximo de cursos para cada periodo, y las relaciones de prerrequisitos.
Un currículo balanceado óptimo minimiza la carga académica máxima de todos los periodos. Se pueden considerar
otros tipos de criterio de balanceo como minimizar la suma de la carga académica de todos los periodos. Se asume
que una carga académica balanceada favorece los hábitos académicos y facilita el éxito de los estudiantes.
A continuación, se presenta un modelo de Programación Entera para el problema de balanceo de un currículo
académico [Castro01, Hnich02]:
Parámetros: Sean
i) m: Número de cursos
ii) n: Número de períodos académicos.
iii) αi: Número de créditos del curso i; i = 1,…,m.
iv) β: Carga académica mínima permitida por periodo.
v) γ: Carga académica máxima permitida por periodo.
21
vi) δ: Cantidad mínima de cursos por periodo.
vii) ε: Cantidad máxima de cursos por periodo.
Variables de decisión: Sean
i) =∀=∀
=casootroen
njmijperiodoalasignadoesicursoelsixij 0
,...,1 ,...1 1
ii) cj: la carga académica del periodo j
iii) c: la máxima carga académica para todos los periodos { }nccMaxc ,...,1=
iv) La carga académica del periodo j esta definida por:
∑=
=∀=m
iijij mixc
1
,...,1α
Función Objetivo: cMin
Restricciones:
i) Todos los cursos i deben ser asignados a un periodo j:
∑=
=∀=n
jij mix
1
,...,11
ii) El curso b tiene un curso a como prerrequisito:
∑−
=
=∀≤1
1
,...,2j
rarbj njxx
iii) La carga académica máxima esta definida por:
{ }nccMaxc ,...,1= Esto puede ser representado por el siguiente conjunto de restricciones lineales
njcc j ,...,1=∀≤
iv) La carga académica del periodo j debe ser mayor o igual que el mínimo requerido:
njc j ,...,1=∀≥ β
v) La carga académica del periodo j debe ser menor o igual que el máximo requerido:
njc j ,...,1=∀≤ γ
vi) El número de cursos del periodo j debe ser mayor o igual que el mínimo requerido:
22
∑=
=∀≥m
iij njx
1
,...,1δ
vii) El número de cursos del periodo j debe ser menor o igual que el máximo requerido:
∑=
=∀≤m
iij njx
1
,...,1ε
4.2 Estrategias de Enumeración.
En [Monfroy07] se consideran 12 estrategias estáticas básicas de enumeración (estrategias que generalmente
son utilizadas para todo el proceso de resolución, pero que aquí son parte de la estrategia híbrida) basadas en 3
criterios de selección de variables:
• Min selecciona la variable con el dominio más pequeño (según el orden de declaración de las variables
en el problemas si existen 2 con el mismo tamaño de dominio)
• Mcon es la selección de la más restringida, es decir, selecciona la (primera) variable que aparece en el
mayor número de restricciones.
• Ran selecciona aleatoriamente una variable que no ha sido instanciada.
Los criterios de selección de variables son combinados con criterios de selección de valores (Min, Mid, Max y Ran)
seleccionando respectivamente el valor mínimo, el mediano, el máximo y un valor aleatorio para la variable
seleccionada.
Por combinación de los criterios de selección de variables y valores, se obtienen 12 estrategias de enumeración
llamadas VarseleccionValseleccion . Por ejemplo, MinRan es la estrategia de enumeración que selecciona aleatoriamente
un valor en la variable con el dominio más pequeño.
La propuesta en este trabajo es diferente, basándose en las estrategias de selección de variables mencionadas antes,
se quiere guiar el proceso de resolución mediante una estrategia de selección de valores inspirada en búsqueda local
considerando como referencias los resultados de la investigación en este campo en [Solnon02, Khichane06,
Monfroy06]. En el caso de selección de variables estas se instanciarán según el orden en el que aparecen.
4.2.1 Búsqueda Local.
El término local se emplea con bastante frecuencia en los estudios teóricos y prácticos del campo de las
metaheurísticas de búsqueda. Las estructuras de entorno suelen reflejar algún concepto de proximidad o vecindad
entre las soluciones alternativas del problema. Por tanto, el análisis del entorno de la solución actual en el recorrido
de búsqueda para decidir como continuarla, representa un estudio local del espacio de Búsqueda. Las metaheurísticas
23
de búsqueda local establecen pautas de selección de la solución del entorno a la solución actual, dando lugar a
búsquedas locales heurísticas con alto rendimiento. Las búsquedas locales no informadas sólo tienen en cuenta la
estructura de entornos para guiar la búsqueda. Las búsquedas monótonas utilizan la evaluación de la función objetivo
para admitir sólo cambios en la solución actual que supongan una mejora. Por tanto, las búsquedas locales
monótonas quedan atrapadas al llegar a una solución que no admite mejora dentro de su entorno. Las búsquedas
globales emplean diversos métodos para escapar de esta situación.
Mientras que los métodos completos pueden demostrar que un problema no tiene solución (la exploración exhaustiva
del espacio de búsqueda), los métodos incompletos serán ineficaces en aquel caso. Sin embargo, se adaptan muy bien
a grandes aplicaciones ya que se basan principalmente en aquellas heurísticas que proporcionan una exploración más
eficiente de las áreas interesantes del espacio de búsqueda. Esta clase de métodos (antes mencionados como
metaheurísticas) cubre una amplia gama de algoritmos evolutivos para búsqueda local.
Las técnicas locales de búsqueda, por lo general, apuntan a la solución de problemas de optimización. En el contexto
de satisfacción de restricciones, estos métodos reducen al mínimo el número de restricciones violadas para encontrar
una solución del CSP. Un algoritmo local de búsqueda (ver Figura 2), comenzando de una configuración inicial,
explora el espacio de búsqueda mediante una secuencia de movimientos. En cada iteración, el siguiente movimiento
corresponde a la elección de uno de los supuestos vecinos. Esta vecindad a menudo corresponde a pequeños cambios
en la configuración actual. Los movimientos son dirigidos por una función objetivo (función de fitness, f sobre la
figura) que evalúa sus beneficios desde el punto de vista de optimización, para alcanzar un grado óptimo local. El
algoritmo se detiene cuando se encuentra una solución o cuando se alcanza un número máximo de iteraciones.
Fig. 2 Un algoritmo de búsqueda local genérico.
4.3 Utilizando Métodos de Mejora (Improvement Methods) para guiar el proceso de
resolución.
Un Método de Mejora Iterativa (iterative improvement method1) es un método de búsqueda que comienza
con una solución inicial y trata de mejorar esta solución mediante modificaciones “locales”. Hay muchos tipos de
problemas, principalmente problemas de optimización como el vendedor viajero, la mochila, o problemas de
1 Iterative improvement method aún no es un concepto estandarizado y otros nombres para este concepto en la literatura son: “stochastic technique”, “repair-based approach”, “local search”, o “perturbation technique”.
Selecciona s Є S (una configuración inicial)
opt ← s (registra la mejor configuración)
MIENTRAS no termine HACER
Selecciona s’ un vecindario de s
s ← s’ (mover a s’)
opt ← s si f ( s) > f (opt) (en caso de maximizar)
24
planificación (a esta “familia” pertenece el problema de balanceo de mallas curriculares) que pueden resolverse con
métodos de mejora iterativa.
Para problemas de planificación, la planificación inicial se puede construir al azar o con algún otro método
constructivo simple. También puede ser construido por un humano u otro proceso de planificación. Se ha utilizado
mejora iterativa para reaccionar a los acontecimientos imprevistos en una tienda [Dom93a]. Aquí, el evento provoca
una nueva violación de una restricción que conduce a un deterioro de la evaluación de la planificación. Luego, las
búsquedas locales reparan la planificación. En [Dom94a] se han descrito sistemas de planificación de diferentes
plantas, que tienen que cooperar. En este sentido, un sistema genera una planificación y el segundo sistema aplica el
método de mejora iterativa en esta planificación para la construcción de una nueva planificación que se ajuste mejor
a sus restricciones propias. Además, tal método de mejora iterativa puede ser usado para hacer más flexible la
interacción con el usuario, porque el usuario puede manipular la planificación actual mediante la publicación de
nuevas restricciones [Dom94b].
Para modificar los horarios deben ser definidos los operadores. La aplicación de un operador resulta en una
planificación vecina. Si existen varios operadores, algún procedimiento debe decidir qué operador se aplicará para
lograr una modificación. Esta decisión puede ser por casualidad o con algún método look ahead que permite la
selección de los mejores vecinos. Para decidir si se consigue una mejora mediante una modificación, debe ser posible
la comparación de las planificaciones mediante una función de evaluación.
Un algoritmo simple de hill climbing aceptará sólo las planificaciones que tienen una mejor evaluación.
Lamentablemente, por lo general los problemas de planificación tienen muchas soluciones que difieren en su calidad
y las buenas soluciones no son vecinos directos. Por lo tanto, un método de búsqueda que se basa en mejoras locales
puede quedar fácilmente atrapado en un óptimo local. Una característica importante de todos los métodos de mejora
iterativa es, por lo tanto, la capacidad de escapar de esos óptimos locales. Sin embargo, esta capacidad, con la
probabilidad de búsqueda en ciclos, plantea la necesidad de algún tipo de control para evitar los ciclos.
Los componentes de un método de mejora iterativa son un esquema de representación para el problema dado, una
función de evaluación que asigna un valor a cada solución, un conjunto de los operadores que se pueden aplicar para
modificar una solución y, por último, un algoritmo de control para la búsqueda de mejoras.
El boceto del siguiente algoritmo representa, muy cercanamente la estructura general de un algoritmo para un
método de mejora iterativa2. El algoritmo se compone de dos bucles: El bucle exterior describe la búsqueda de la
mejor solución y el bucle interior la búsqueda para la próxima mejora. Las principales diferencias entre los diferentes
2 Algunas veces los métodos de mejora iterativa se basan en sólo un bucle (interior). Entonces, el algoritmo no entregará siempre la mejor solución encontrada hasta el momento. Además, algunos algoritmos (como los genéticos) mantienen un conjunto de soluciones. Por lo tanto, el esquema dado es muy abstracto.
25
algoritmos, que se presentarán en el próximo capítulo son los procedimientos de modificación y la función de
aceptación de soluciones.
Fig. 3. Un algoritmo general de mejora iterativa.
Una importante decisión de diseño para la eficiencia de un método de mejora iterativa es el equilibrio adecuado entre
la dirección de la búsqueda del óptimo global y la cantidad de trabajo invertido para seleccionar un operador. El
número de pasos (mejoras y también modificaciones) desde la solución inicial a la mejor solución que se puede
encontrar será menor si más información se utiliza para modificar una solución. Esta información debe ser adquirida
por inferencias simples, porque una técnica de look ahead exhaustiva toma demasiado tiempo para los problemas de
tamaño real. Además, la mejor mejora local puede conducir a un óptimo local. En la completa falta de
conocimiento a menudo se aplican técnicas estocásticas. Entonces es necesario poco tiempo para seleccionar un
operador de modificación, pero esto conduce a la desventaja de que la búsqueda puede tomar más tiempo,
porque también se aceptan modificaciones que no conducen directamente a la solución óptima. Con
el aumento de la aleatoriedad se debe tratar de hacer que las partes deterministas como la modificación de las
soluciones y su evaluación sean lo más simple posible para permitir examinar más soluciones.
La segunda cuestión importante es la capacidad para escapar de óptimos locales. Se pueden observar en los métodos
existentes dos estrategias generales. Algunos métodos realizan hill climbing hasta que la búsqueda es atrapada.
Luego, se utilizan los métodos que permiten un escape. La segunda estrategia primero soporta la diversidad para
buscar, más aleatoriamente, en todo el espacio las buenas soluciones y, a continuación, se intensifica la búsqueda
para encontrar una solución óptima. Métodos más elaborados intentan cambiar entre búsqueda intensiva y
diversificada, lo que puede lograrse con algunos modelos probabilísticos o con conocimientos adicionales.
4.3.1 Representación.
Los problemas de planificación simples consideran sólo secuencias de operaciones en una máquina. Estos
se pueden representar mejor como una lista ordenada o, más eficazmente, para las modificaciones como un conjunto
de operaciones. Ambas estructuras de datos también pueden contener horas de inicio, duración, etc. Para problemas
iterative_improvement;
s := initialSolution();
repeat {iterative improvement}
sbest := s;
repeat {improvement}
s' := modify(s);
if acceptable(s', s)
then s := s';
until better(s, sbest);
until stopping_criteria
26
complejos con más máquinas y otros recursos, se han hecho diferentes propuestas para representar la planificación.
En investigación de operaciones a menudo se utilizan Grafos Disyuntivos [Balas69], [Roy64] como un formalismo
para representar la información necesaria temporal de un problema de planificación con diferentes máquinas
diferentes. Un Grafo Disyuntivo D = (N, Z, W) consta de un conjunto de N nodos en representación de las
operaciones que vayan ser realizadas, un conjunto de arcos dirigidos Z para describir las restricciones de precedencia
entre las operaciones y un conjunto de bordes disyuntivo W para restringir las operaciones que no se deben
superponer. Normalmente, los bordes disyuntivos se utilizan para representar los conflictos de recursos, también se
utilizan para describir que entre dos operaciones de un trabajo no existe secuencia. El siguiente grafo es un pequeño
ejemplo. En el ejemplo de tres trabajos J1, J2 y J3 se han planificado en tres máquinas M1, M2, M3 que sólo pueden
procesar una operación a la vez. El grafo contiene dos nodos adicionales un fuente y un sumidero que son requeridos
por el algoritmo para determinar el camino crítico.
Fig. 4. Grafo Disyuntivo representando un problema de asignación de trabajos con 3 trabajos y 3 maquinas.
En enfoques de IA, muchos investigadores siguen las ideas de Fox [Fox87] de utilizar algún tipo de representación
orientada a objetos con la capacidad de heredar propiedades de una superclase a una subclase (por ejemplo, la
representación de todos los recursos puede ser descrita en una superclase y cada subclase describe sólo las
propiedades de las máquinas que las distinguen de otros recursos). Se debe distinguir objetos del dominio como una
máquina y los objetos que se utilizan para resolver el problema de planificación como el programa, es decir, la
asignación de las máquinas en el tiempo. La representación de objetos del dominio mediante la orientación a objetos
parece ser muy natural.
Interesante, pero muy complejo es la realización de la idea de definir una asignación de un recurso como un objeto
que es básicamente una tripleta de recursos, funcionamiento, e intervalo temporal. Por ejemplo, esto fue aplicado en
el proyecto CRONOS [Canzi93]. Para un método de planificación donde muchas modificaciones se realizan en un
programa, esto significa que son necesarias muchas creaciones y eliminaciones de objetos en el tiempo. Si tal
representación es elegida para un método de mejora iterativa, los operadores deben ser sofisticados para reducir el
número de creaciones de objetos.
27
Dado que el objeto jerarquía no suele ser importante para los problemas de asignación y secuenciación, una
representación plana basada en restricciones parece ser más adecuada para los aspectos dinámicos de un problema de
planificación. Básicamente, las restricciones son relaciones entre objetos o atributos de objetos que definen
propiedades deseables o requeridas. A pesar de que las restricciones y los atributos restringidos pueden ser
modelados como objetos en una representación orientada a objetos, la más eficiente representación parece ser un
grafo de restricciones almacenadas en una estructura de memoria dinámica. La herencia y la encapsulación de estos
enlaces dinámicos es una sobrecarga que puede evitarse.
Como fue definido en la sección 3.2, un problema de satisfacción de restricciones (CSP) es generalmente modelado
por un conjunto de variables donde cada variable tiene asignado un dominio de valores posibles. Una variable típica
en un problema de planificación es la hora de inicio y la duración de una operación. Si la operación tiene una fecha
de liberación y de vencimiento, el dominio de esta variable será restringido por dos restricciones unarias. A menudo
restricciones adicionales de precedencia demandan que la hora de término de una operación sea anterior a la hora de
inicio de otra operación. Esto puede ser fácilmente expresado con una restricción binaria. A veces también son
necesarias restricciones n-arias. Por ejemplo, se podría restringir el consumo de energía de n operaciones a ser menor
que algún valor e.
Una solución a un problema de satisfacción de restricciones es una asignación de un valor a cada variable tal que las
restricciones no son violadas. Meseguer [Meseguer89] da una visión de un conjunto de algoritmos para encontrar
solución a un CSP. Prosser [Prosser93] ha examinado varias de estas técnicas para resolver problemas de
planificación. Por lo general, técnicas de pre-procesamiento como ordenación de variables, forward checking o
propagación de restricciones se aplican para mejorar los algoritmos. Sin embargo, en la literatura sólo se proponen
técnicas para restricciones binarias y como se dijo por Prosser, problemas de tamaño real siguen siendo demasiado
complejos para ser resueltos por estos métodos. Algoritmos más específicos se han desarrollado para restricciones
temporales [Dom92], [Dom94b]. Estas técnicas pueden usarse para comprobar la factibilidad de horarios [Dom93b],
pero son todavía demasiado complejas para problemas de secuenciación.
Además, se tiene que ver que la planificación no es usualmente tanto un problema de encontrar un programa factible
(es decir, un programa sin violación de restricciones), sino un problema de optimización de uno o más criterios. A
veces se propone para modelar esta optimización varias llamadas a un solver de problemas de satisfacción de
restricciones con diferentes restricciones para la función de optimización [Nuijten93]. A la luz de la complejidad del
CSP, no parece buena solución y una asunción implícita es el supuesto de que existe sólo una función de
optimización discreta. A menudo, sin embargo, existen objetivos conflictivos de valor real en las aplicaciones
industriales. Otra propuesta fue hecha por Bakker [Bakker93]. Se propone un exceso de restricciones al problema y
luego aplicar técnicas de modelado basadas en diagnosis para encontrar una relajación tal que el problema se puede
resolver. Lamentablemente, encontrar una diagnosis mínima esperada, en este caso, es un problema NP-completo.
28
Como conclusión se puede decir que la representación de problemas industriales complejos de planificación por un
formalismo de restricciones es prometedora debido a su expresividad, pero no se puede esperar una solución al
problema. La secuenciación de las operaciones debería ser objeto de, por ejemplo, un método de mejora iterativa.
Las técnicas de consistencia, como son conocidas en la literatura de CSP, pueden entonces ser de apoyo al método de
mejora iterativa para el control de la factibilidad del nuevo programa.
4.3.2 Función de Evaluación.
Una función de evaluación asigna costo a una planificación determinada. Por lo general, la función se expresa de
manera que el objetivo es reducir al mínimo la misma. Por lo tanto, se trata de encontrar un programa que termina
todas las operaciones tan pronto como sea posible o con el menor monto posible de capital. En teoría, una diferencia
regular e irregular de funciones de evaluación [French82]. La mayoría de las veces se utilizan las funciones regulares
que implican que el retraso de una operación nunca puede disminuir la evaluación. Una típica evaluación regular es
la makespan, es decir, el tiempo necesario para llevar a cabo todas las operaciones. En este caso, el objetivo es
encontrar un programa que tenga el mínimo makespan. Si se modifica la secuencia de las operaciones en el programa
en virtud de este criterio de optimización, cada operación puede ser desplazada a la izquierda en la medida de lo
posible mientras la función de evaluación sea regular. El valor de makespan de la nueva secuencia se puede calcular
localmente.
Una función irregular de evaluación implica que el cambio hacia la izquierda no llevará necesariamente al mejor
programa para la secuencia dada. Por ejemplo, Sadeh y Nakakuki [Sadeh94] minimizan los costos de inventario y la
lentitud. El costo de inventario se define como la diferencia entre la hora de vencimiento y la hora de inicio de la
primera operación de un trabajo. Esta combinación de objetivos es irregular porque los costos a veces se reducen si
la hora de inicio de un trabajo se retrasa. A veces los efectos de una modificación no puede limitarse al entorno local
y la función de evaluación debe ser calculada totalmente de nuevo. Si en una fase de post-procesamiento una nueva
serie de intervalos de configuraciones o de mantenimiento deben ser determinados, la evaluación debe ser calculada
siempre de nuevo [Dom94c].
En algunos proyectos en la industria del acero, se tiene más conciencia de que a menudo los expertos no pueden dar
restricciones exactas. Entregan por lo general muy fuerte límites, porque tienen miedo de que si
entregan estas restricciones relajadas el sistema que se construirá siempre tomará estos límites más bajos. Sin
embargo, con estos fuertes límites, el problema esta sobre restringido. Cuando se relaciona como resuelven el
problema, a menudo se puede ver una fuerte relajación de las restricciones. Normalmente se hace sin importar si la
fecha de vencimiento es violada por algunos minutos. Con frecuencia, la penalización por violar una fecha de
vencimiento es proporcional al tiempo de retraso. Una posibilidad para modelar el grado de violación de estas
restricciones es por conjuntos difusos [Dom94d]. Con este modelo no binario es necesaria la decisión de si una
restricción se cumple.
29
Otros dos objetivos importantes con la planificación reactiva son la robustez y la reducción al mínimo de
modificaciones. La primera es una medida de cómo el programa permanece robusto bajo potenciales perturbaciones
en la base de la planificación. Un programa que no debe ser cambiado si ocurre algún evento inesperado es más
robusto que uno que debe ser cambiado. Una minimización de modificaciones se convierte en importante si la
planificación reactiva se hace necesaria. Si hay otras plantas de relevo en el programa, el programa debe ser reparado
con tan pocas modificaciones como sea posible. En [Dom93a] se muestra cómo estos objetivos se pueden incorporar
en una función de evaluación. La minimización de las modificaciones es también un objetivo en el sistema de
GERRY [Zweben92].
A menudo, la planificación es un proceso dinámico: nuevos trabajos se introducen y algunos trabajos finalizan. A
veces no todos los trabajos son previstos, pero existe una lista de trabajos restantes no planificados. Si un sistema de
planificación no tiene que programar todos los trabajos, esto se traduce muy probablemente en que varios trabajos
difíciles restan en la lista de trabajos no planificados. Para evitar esto, podemos asignar una penalización a los
trabajos que no están programados. Por lo tanto, la evaluación de la planificación no será tan buena si los trabajos
difíciles no son planificados. Del mismo modo se puede modelar la importancia de los trabajos.
Para encontrar una función de evaluación realista para un problema multi-criterio, deben ser introducidos
coeficientes de ponderación para diferentes restricciones y objetivos. Por lo general, restricciones de fecha de
vencimiento son de peso no tan importante como aspectos que conducen a una mala calidad de los productos.
Además, se tiene que decidir si se destacaron grandes violaciones o no. A veces el lugar de la demora de los trabajos
se agrega como una función de costos. Esto significa que se prefiere un programa con muchos pequeños retrasos. A
veces esto puede favorecer un programa que tiene un trabajo muy tarde, pero todos los demás trabajos en el tiempo.
Especialmente para la toma de decisiones difusa, un lote de tales funciones de agregado que también fueron
examinadas para planificación se define en [Slany94].
4.3.3 Modificación del Programa.
Para buscar un programa mejorado se tiene que modificar el programa existente. Dado que el principal problema en
la planificación es el problema de secuenciación, la mayoría de los operadores influyen en la secuencia de los
trabajos o de las operaciones.
Se pueden interpretar todos los programas que pueden ser generados a partir de una planificación S como un
conjunto de vecindarios N(s) que puede ser alcanzado mediante la aplicación de un operador o de un conjunto de
posibles operadores Os:
N(s) = {s' | ∃ o ∈ Os: S' = s ⊕o}
30
Uno de los más sencillos operadores en planificación es el intercambio de trabajos u operaciones adyacentes en un
programa. Si hay n ítems programados, esto significa que se pueden construir n - 1 vecinos. Si se permite el
intercambio de dos elementos existen n * (n - 1) / 2 vecinos. Para problemas de planificación dinámica, es posible
también un intercambio de trabajos, en el programa, que aún no se han planificado. Otro operador muy sencillo es
tomar un ítem desde una posición p1 de la lista y colocarlo entre otros dos ítems en un lugar p2 y el intercambio de
todos los ítems entre P1 y P2. Estos son todos los operadores que se pueden encontrar en la literatura. El dilema en el
diseño de los operadores es que, por un lado, los operadores deben ser tan sofisticados como sea posible y, por otro
lado, no deberían ser tantos los vecinos que pueden ser generados a partir de los operadores, porque de otro modo
existen muchas alternativas. Se deben diseñar operadores tal que se pueda alcanzar una mejora en un paso, pero esto
puede significar que se deben evaluar muchos operadores candidatos.
También se ha experimentado con operadores que mueven varios trabajos al mismo tiempo. Dado que el número de
operadores de tales grupos es exponencial y no se pueden generar todos los vecinos, esto no puede ser un
acercamiento general. Se han logrado buenos resultados al reducir los operadores utilizando la heurística de
reparación del mayor conflicto [Dom94d].
Una modificación de un programa factible por un operador puede resultar en un programa infactible en el caso de
que sean violadas varias restricciones duras. Hay tres posibilidades de reaccionar sobre esta modificación:
� dar una evaluación baja a un programa inviable,
� eliminar este tipo de operadores del conjunto de los posibles operadores, o
� generar a partir de un programa inviable uno factible con una técnica de post-procesamiento.
La primera posibilidad puede ser costosa si se generan muchos programas inviables. Teóricamente, sería posible que
el mejor programa encontrado todavía viole restricciones duras difíciles. La asignación de costos muy elevados a la
violación de restricciones duras puede bloquear el camino a la solución óptima. Por lo tanto, se tiene que diseñar una
función de evaluación muy cuidadosamente a fin de que las violaciones a restricciones duras no permanezcan en la
solución óptima, pero puedan ocurrir en el camino hacia la solución.
El esfuerzo de la segunda posibilidad depende de si se puede decidir la infactibilidad de un vecino sin construirlo
explícitamente. Si se puede decidir sólo mirando el operador los costos serán bajos. Sin embargo, hay instancias de
problemas donde la prohibición de soluciones inviables bloquearía el camino a la solución óptima.
El esfuerzo de la tercera posibilidad depende de la técnica que sea necesaria para la construcción de un programa
factible. Por ejemplo, en un programa “semi-activo”, la hora de inicio de las operaciones puede ser determinada por
un algoritmo del camino crítico [French82]. A menudo, este esfuerzo de post-procesamiento es lineal, pero a veces
también es polinómico. A veces, pueden existir varias posibilidades para construir una solución factible. Si se aplica
31
un algoritmo determinista entonces algunas soluciones nunca se alcanzarán. Sadeh y Nakakuki [Sadeh94], por lo
tanto, utilizan un operador adicional que cambia las operaciones en lugar de cambiar el orden.
La decisión final por una de estas posibilidades dependerá de la aplicación y los operadores que se definan. Si es
probable que sean generados muchos programas inviables, el esfuerzo para evaluar un nuevo programa es alto, y hay
un método para construir un programa factible a partir de uno inviable y, a continuación, entonces parece ser
prometedor ajustar el programa. En [Dom94c] las operaciones de configuración y mantenimiento se añaden
nuevamente después de cada modificación de la secuencia de operaciones. Por otra parte, no siempre es posible
lograr un programa factible sin cambiar el orden de los trabajos. En la aplicación descrita en [Dom94d], donde las
restricciones de compatibilidad desempeñan un papel dominante en muchas secuencias, esto no está permitido.
Cuando hay muchos programas inviables en la aplicación, un método de mejora iterativa debe aceptar también los
programas inviables, porque de otro modo podría ser que no hay camino para la solución óptima.
El número de vecinos de un programa depende del tamaño del problema de planificación y del número de operadores
definido. Para un pequeño número de vecinos es posible evaluar todos los vecinos y continuar entonces con el mejor.
Para problemas más grandes, esto será ineficientes, Zweben [Zweben92] ha evaluado los costos de aplicación de
tales procedimientos look ahead y ha reportado una degradación del rendimiento.
El método usual ahora es seleccionar en forma aleatoria los operadores y entonces decidir si esta modificación es
aceptable. Las técnicas de mejora se consideran ineficiencias en el programa actual para decidir esto. La "reparación"
de tales ineficiencias se puede considerar como una meta-heurística para métodos de mejora iterativa que se
focalizan sólo en subconjuntos de los operadores evaluados.
La heurística min-conflicts [Minton90] es un tipo de estrategia de reparación que reasigna la variable en un problema
de satisfacción de restricciones que está involucrada en la mayoría de las restricciones violadas. La heurística trata
entonces de seleccionar una asignación con menos violaciones que la original. Esta heurística se ha combinado con
un hill-climbing simple para hallar una solución para el problema del Telescopio Espacial Hubble. Zweben
[Zweben90] adopta un enfoque similar, pero aplica con cada reparación un algoritmo de arco-consistencia para las
restricciones temporales. Sadeh y Nakakuki [Sadeh94] inflan los costos asociados con las mayores ineficiencias de
un determinado programa. Por lo tanto, se hace más probable que estos algoritmos modifiquen el programa en estos
lugares.
4.4 Optimizando Programas por Mejoras Iterativas.
Hay varios algoritmos que pueden utilizarse para mejorar iterativamente un programa. Las principales
diferencias entre ellos son la selección de los operadores y los criterios de aceptación. Los algoritmos pueden ser
ordenados por la cantidad de aleatoriedad que está involucrada en estos aspectos. Para el propósito de comparación
32
se plantea la aplicación de un algoritmo que selecciona los operadores puramente aleatorios [Dom94c]. Si bien este
tipo de algoritmo optimiza mucho el programa, otros algoritmos que aplican más conocimiento tienen un mejor
rendimiento. Por el contrario, uno también puede aplicar algoritmos de búsqueda deteterministicos para una mejora.
El primer método que será descrito a continuación es un algoritmo que se limita a clases de problemas muy
específicos. Sin embargo, su ventaja es que garantiza una solución óptima si se agota el tiempo. El segundo
algoritmo busca exhaustivamente una mejora por profundización iterativa. En teoría, este algoritmo también puede
encontrar la solución óptima, pero esto es prácticamente imposible. En 1988, algunos investigadores de la
comunidad de IO habían identificado los siguientes tres métodos de optimización como los más prometedores para
aplicaciones prácticas [Com88]. Tabu Search, el tercer método, aunque principalmente determinista, también puede
ser enriquecido con algunas técnicas estocásticas. El cuarto método que se describe es Simulated Annealing que
selecciona al azar un operador y la posibilidad de aceptar una modificación se decide con un modelo de probabilidad,
también. Por último, se presentan los algoritmos genéticos como un método de optimización. Este método es
ligeramente diferente a los otros métodos porque siempre se mantienen un número de soluciones al mismo tiempo.
4.4.1 Grafos Disyuntivos.
Uno de los primeros algoritmos que pueden clasificarse como método de mejora iterativa, es el que se describe por
Balas [Balas69]. Él usa un grafo disyuntivo para representar el problema de planificación y optimiza el makespan
por inversión de bordes con un algoritmo de enumeración implícita.
Un programa factible contiene sólo los bordes y no tiene ciclos. Es creado un primer programa seleccionando para
cada borde disyuntivo una dirección. El conjunto de todos los bordes elegidos se llama selección. Para obtener un
primer programa factible, todas las operaciones están ordenadas aleatoriamente, y siempre se elige la dirección que
conduce desde la primera operación a la segunda.
Una modificación de dicho programa es la inversión de uno de estos bordes elegidos. El algoritmo se basa en la idea
de que un borde en el camino crítico debe ser invertido para encontrar un programa que tiene un makespan más corto
que un programa dado. Evidentemente, el camino crítico (la más larga cadena de operaciones) es en cierto sentido, el
conjunto de restricciones violadas que causa un largo makespan. Además, si un borde en el camino crítico se invierte
se demuestra que el nuevo grafo no tiene ciclos.
Si se crea un nuevo programa, se debe determinar la nueva ruta crítica. Esta nueva ruta crítica, y también su
duración, puede ser fácilmente calculada a partir de la transformación de Balas; almacena en cada nodo el camino
más largo (crítico) hacia la fuente y al sumidero. Para cada borde en el camino crítico ahora se pueden examinar los
costos de un vecino con un pequeño esfuerzo.
El algoritmo de búsqueda usa un árbol con los programas como nodos. Un nodo es expandido si un mejor programa
33
se puede construir invirtiendo un borde disyuntivo. Se puede elegir el mejor vecindario y Balas ha demostrado
también un criterio para cortar algunas ramas del árbol de búsqueda. La búsqueda puede ser interrumpida en
cualquier momento y siempre ofrecer una solución viable para lograr así las características de un algoritmo en
cualquier momento [Boddy89].
En un artículo posterior [Adams88], en el procedimiento de cambio de cuello de botella se presentan las secuencias
de primeras máquinas que son reconocidas como cuello de botella. Las máquinas son secuenciadas en un momento,
consecutivamente. Para cada máquina, que todavía no se ha secuenciado se resuelve el problema de secuenciación de
una única máquina por consistencia de las restricciones procedentes de las máquinas que ya están programadas y las
operaciones que se han programado en esta máquina. Debido a que este algoritmo tiene muy buen rendimiento sobre
problemas con muchas máquinas, es a menudo utilizado como un estándar de comparación. La ventaja del algoritmo
frente a otros, que se presentarán más tarde, es que finalmente encuentra la solución óptima si hay suficiente tiempo
disponible. Sin embargo, hay que destacar que este algoritmo es sólo aplicable a problemas donde el flujo del tiempo
o makespan se minimizará.
4.4.2 Profundización Iterativa.
El primer intento para un método general de mejora iterativa que no es tan restringido como el enfoque anterior y es
capaz de escapar del óptimo local, podría ser un enfoque que busca en forma exhaustiva, en cada paso, una mejora.
Se ha aplicado la estrategia de profundización iterativa primero en profundidad (depth-first iterative deepening)
[Korf85] en algunos experimentos. La idea de esta estrategia es combinar las ventajas de la búsqueda primero en
amplitud (el camino más corto a una mejora) y vuelta a atrás (backtracking) (no se almacenan en árbol de búsqueda).
En un primer intento se hace una búsqueda hasta profundidad uno y si no se encuentra una mejora, se lleva a cabo
una búsqueda con backtrack de profundidad dos. Este límite de profundidad iterativa se aumenta hasta que se
encuentra una mejora.
Por supuesto, cada estrategia exhaustiva de búsqueda tiene sus límites. Si existen demasiados operadores que se
pueden aplicar, el esfuerzo de búsqueda es intratable. Se ha aplicado este método para compararlo con otros métodos
con tal enfoque determinista y es sorprendente que se hayan obtenido muy buenos resultados. Desde que se ha
combinado el método con heurísticas para reparar siempre la mayor violación de restricción, el número de
operadores no ha sido tan grande y ha superado, por ejemplo, el enfoque de algoritmos genéticos.
Además, parece prometedor combinar esta estrategia de búsqueda más fuerte con la función de evaluación. Con
IDA* [Korf85] también existe un algoritmo que combina las ventajas del algoritmo A* y backtracking. Si se aplica
como combinación se permite primero hacer una búsqueda en una dirección en que parece ser más probable una
mejora.
34
4.4.3 Tabu Search.
Tabu Search es un método de búsqueda inspirado en gran medida en la investigación en ciencia cognitiva [Glover89]
y [Glover90]. Una de las principales ideas es un proceso dinámico de memoria que almacena los atributos de las
anteriores soluciones del proceso de búsqueda. En una memoria de corto plazo son almacenadas las características de
las soluciones recientes a fin de evitar retrocesos o ciclos en la búsqueda. Una memoria de largo plazo se utiliza para
definir las fases de intensificación y diversificación de la búsqueda. Por lo tanto, si una región del espacio de
búsqueda se examinó intensivamente sin encontrar soluciones mejores, la memoria a largo plazo puede cambiar los
parámetros para orientar el proceso de búsqueda a regiones distintas. Se requieren varios conceptos para cumplir con
este comportamiento.
Una amplia gama de problemas de planificación ya se han resuelto con búsqueda Tabú. Barnes [Barnes93] entrega
una visión general de algunas de estas soluciones y [Glover93] contiene una colección de artículos sobre problemas
de planificación que se resolvieron con búsqueda Tabú.
Los primeros acercamientos de búsqueda Tabú han investigado todo el vecindario [Widmer89], sin embargo, en
aplicaciones industriales reales esto no es posible. En consecuencia, más tarde se aconsejó formar primero muestras
de operadores y luego examinar la totalidad de la muestra para seleccionar la mejor modificación [deWerra89].
Laguna [Laguna91], aplica por ejemplo intercambio de operadores y limita la distancia entre dos trabajos que se
intercambian para que sea más pequeña que algún valor d. Se ha utilizado la estrategia para reparar el conflicto más
grande en una planificación para formar una muestra [Dom94c]. Si, por ejemplo, un trabajo es tarde, sólo se intentan
operadores que mueven ese trabajo a otro lugar.
Para escapar del óptimo local es también posible seleccionar un operador que lleve a una planificación con una peor
evaluación. Para evitar los ciclos de búsqueda, se introduce una lista tabú que contiene los atributos de las anteriores
soluciones. Si una nueva planificación se considera que coincide con uno de estos elementos de la lista tabú, este
movimiento es tabú y se busca el siguiente mejor vecino.
Teóricamente, se podría almacenar un conjunto de planificaciones en la lista tabú para que sea tabú. Dado que esto
consumiría demasiado espacio y tiempo, sólo se almacenan algunos atributos de una antigua planificación. Ahora
puede ocurrir que sea generada una nueva planificación de la cual se ha almacenado atributos, pero que además sea
diferente a la antigua. Para permitir en determinadas condiciones, el reescribir el estado tabú de un atributo, se puede
introducir una condición de nivel de aspiración. Una condición típica es que sea encontrada una nueva mejor
solución.
Los atributos almacenados deben caracterizar la solución lo mejor que sea posible. Por lo tanto, parecen ser
adecuados diferentes atributos para aplicaciones específicas. Por otra parte, Glover [Glover90] propone almacenar
35
distintos atributos para lograr una mayor flexibilidad. Atributos prometedores para la aplicación de una planificación
son:
• Si se intercambian dos trabajos en un plan, se almacenan estos trabajos y sus antiguas posiciones en el
plan, para permitir la prohibición de que en un futuro próximo estos trabajos se colocan de nuevo en sus
lugares originales.
• Si dos trabajos no se ajustan cada uno después del otro y uno de ellos se mueve, se puede almacenar la
antigua secuencia de ambos como una constelación tabú.
• Se almacena un tipo de función hash para todo el plan.
La lista tabú simulando una memoria a corto plazo humana tiene una duración limitada y generalmente es
implementada como un espacio de anillo. Glover recomienda limitar este a siete entradas. Con esta restricción de
longitud será posible para el caso de almacenar la posición original de los trabajos que, después de siete
modificaciones, vuelvan a su posición original en el plan. Se pueden definir listas tabú con diferentes longitudes para
los tres atributos: valor de hash, antigua secuencia de trabajos y antigua posición de los trabajos. La lista tabú para
los valores de hash debe ser la más larga para prohibir por un largo tiempo el retorno a una solución antigua. En
contraste, la lista con las antiguas posiciones deben ser relativamente corta, porque esto puede provocar repeticiones
de las mejores soluciones.
Una posibilidad para tener una diversificación de la búsqueda es cambiar la longitud de la lista tabú dinámicamente.
Con una lista más larga más operadores serán tabú y como resultado habrá una búsqueda en diferentes regiones, por
lo tanto, así se logra una diversificación. Si se encuentra alguna otra buena solución que difiere considerablemente de
las antiguas buenas soluciones, la longitud de la lista tabú puede reducirse de nuevo. Otra posibilidad es cambiar
entre los diferentes operadores. Por ejemplo, un operador intercambio intercambiando sólo operaciones adyacentes
conduce a una intensificación de la búsqueda más que los operadores que producen estructuras con grandes
vecindarios que apuntan a una diversificación. Para forzar la diversificación también pueden aplicarse técnicas
probabilísticas. Laguna y Glover [Laguna92] han desarrollado una técnica de análisis objetivo para controlar las dos
fases de diversificación e intensificación y las primeras aplicaciones han aplicado con éxito esta técnica.
4.4.4 Simulated Annealing.
Recocido simulado es un método de optimización basado en las ideas de la física estadística, donde es simulado el
enfriamiento de un sólido a su estado terreno (es decir, el estado con energía mínima). Kirkpatrick [Kirkpatrick83] lo
utilizan como un método de optimización para el diseño VLSI.
En el recocido simulado se selecciona al azar un operador de modificación y se decide si el plan resultante puede ser
aceptado como un nuevo candidato para continuar la búsqueda. Para escapar del óptimo local se permite una
disminución de la evaluación por una probabilidad que baja durante la búsqueda. Si la evaluación de un plan si es ci
y, a continuación, entonces el algoritmo acepta un vecino sj con una evaluación de cj, con una probabilidad de:
36
=
−−
t
cc ji
eP ,1min
donde t (la temperatura) es un parámetro de control positivo que disminuye durante la ejecución del algoritmo. La
probabilidad de aceptar un nuevo plan es baja si la diferencia entre ambas evaluaciones es grande. En el comienzo
cuando la temperatura es alta, es más probable que una gran diferencia sea aceptada. La estrategia global es buscar
primero al azar sobre todo el espacio de búsqueda de planes. Luego la búsqueda se limita más fuerte para encontrar
una solución cercana al óptimo.
La decisión de la rapidez con que la "temperatura" disminuye influye en el tiempo que el algoritmo necesita para
resolver un problema y también en que tan buena será la solución. Las diferentes temperaturas de recocido se pueden
dar explícitamente por un conjunto fijo de constantes o por una función implícita. Asimismo, la duración el tiempo
que la búsqueda utiliza una cierta temperatura se puede ajustar. A menudo, estos ajustes se conocen como el “plan
de recocido”.
Van Laarhoven [vanLaarhoven92] ha aplicado recocido simulado sobre grafos disyuntivos y ha definido el
vecindario de la misma manera que en [Balas69]. Comparaciones experimentales con el "procedimiento de cambio
cuello de botella” [Adams88] han demostrado que puede competir con este enfoque. Zweben [Zweben90],
[Zweben92] ha combinado recocido simulado con una representación basada en restricciones. Aquí se “reparan”
violaciones a las restricciones con algunas heurísticas, aplicando un algoritmo de consistencia temporal en el nuevo
programa y, por último, evaluando con el modelo de recocido simulado si este nuevo programa puede ser aceptado.
Dado que los operadores no son seleccionados al azar, se podría hablar de una versión de recocido simulado basado
en conocimiento. Sadeh y Nakakuki [Sadeh94] han aplicado recocido simulado a un problema de planificación y
mejorado el algoritmo haciendo hincapié en la eficiencia de la planificación. Su heurística "focalizada en recocido
simulado" incrementa los costos de los subproblemas por lo tanto, guía la búsqueda más fuertemente. Esta parece ser
la misma motivación de la heurística min-conflicts [Minton90] o la heurística de “reparación” [Dom94d] o
[Zweben90].
El problema de Recocido Simulado es que las soluciones difieren considerablemente entre ejecuciones distintas. Por
esto, Nakakuki y Sadeh [Nakakuki94], proponen técnicas para detener ejecuciones poco promisorias y reiniciar el
Recocido Simulado según algunos criterios que pueden ser adquiridos a través de múltiples ejecuciones. Otra
posibilidad de reducir esta diferencia es hacer más “determinista” el Recocido Simulado. En Threshold Accepting
[Dueck90], el modelo probabilístico se omite y sólo se utiliza un valor umbral durante la búsqueda para reducir la
temperatura como en Recocido Simulado. En [Dueck90] y [Dueck93] se hicieron varios experimentos con el
problema del vendedor viajero para comparar su rendimiento con Recocido Simulado. Los autores afirman que sus
algoritmos tienen un rendimiento más rápido que Recocido Simulado y ofrecen resultados similares. Aunque la idea
detrás de Threshold Accepting es evidente, en [List94] se reportan diferentes resultados. Para problemas de
37
planificación montados en aplicaciones, Recocido Simulado ha encontrado soluciones con un menor tiempo de flujo
que Threshold Acceptingr. Lamentablemente, sólo se reportan las modificaciones requeridas y no el tiempo
requerido.
4.4.5 Algoritmos Genéticos.
Los Algoritmos Genéticos fueron propuestos por primera vez por Holland [Holland75], son una clase de algoritmos
que imitan la selección natural y la genética. Los algoritmos genéticos difieren de los otros métodos de búsqueda
descritos en el sentido de que mantienen siempre un conjunto de soluciones llamadas población. Los miembros de la
población son los cromosomas que están representados originalmente por cadenas de bits. La primera población se
inicializa al azar y evoluciona en generaciones. En cada generación la población es afectada por los operadores
genéticos y mecanismos de selección. Los operadores genéticos, tales como los operadores de cruzamiento y
mutación proporcionan el flujo de información entre los cromosomas, mientras que la selección promueve la
supervivencia de los cromosomas más aptos. Una función de calidad evalúa los cromosomas individuales. El
mecanismo de selección suele ser una combinación de la función de calidad con cierta probabilidad
A partir de Davis [Davis85] se hicieron muchas propuestas para la aplicación de algoritmos genéticos en
planificación. Normalmente, es dirigido hacia el problema de secuenciación de un conjunto de puestos de trabajo
debido a que este es un problema difícil en la planificación y este tipo de problema puede ser fácilmente representado
con algoritmos genéticos. Sin embargo, hay acercamientos para hacer frente también al problema de asignación.
Bagchi [Bagchi91] clasifica la representación de las planificaciones con los cromosomas en acercamientos directos e
indirectos. En una representación directa todos los conocimientos necesarios para evaluar una planificación existen
en un cromosoma. La representación directa tiene por supuesto ventajas, pero entonces el algoritmo genético debe
ser muy especializado y no puede ser reutilizado en otro problema. Por lo tanto, a menudo la representación indirecta
es favorable donde un constructor de planificaciones construye una planificación valida desde un cromosoma. En
este caso, sólo tiene que ser modificado el constructor de planificaciones para una nueva aplicación. Los algoritmos
genéticos no siempre pertenecen a uno de estos extremos, también hay planteamientos que toman conocimientos más
dependientes del dominio en un cromosoma, pero que aún requieren un constructor de planificaciones, porque no
todo el conocimiento está representado en el cromosoma. Bruns [Bruns93] llama a estos acercamientos problem-
specific indirect representation.
La mayoría de los enfoques para planificación usan la representación indirecta y codifican una planificación en un
cromosoma. Dado que los algoritmos genéticos no trabajan sobre una planificación, se realiza una transición de un
cromosoma a una planificación valida cada vez que un nuevo cromosoma tiene que ser evaluado.
La planificación puede ser representada por cadenas de bits donde cada bit determina cual de las dos órdenes se
ejecuta primero [Fox91], [Nakano91]. Más a menudo los trabajos de un problema de planificación son representados
38
como una lista de números enteros [Cleveland89], [Filipic93], [Kanet], [Syswerda91]. Los operadores genéticos
aplicados en estos acercamientos deben estar diseñados de tal manera que las órdenes o trabajos no existan dos veces
en un nuevo cromosoma. Aunque el problema de planificación se reduce en un problema de secuenciación, para
algunas aplicaciones, este enfoque parece suficiente sin constructor de planificación porque sólo la secuencia es
importante. Sistemas más complejos de cromosomas representan también un proceso para un plan de trabajo o los
recursos que se utilizarán para una operación, [Bagchi91] y [Bruns93].
Varios operadores genéticos específicos para planificación son propuestos en la literatura. Fox y McMahon [Fox91]
han examinado varios de ellos para planificación. Dos clases de operadores se distinguen usualmente: los operadores
de mutación que operan en un único cromosoma y los operadores de cruzamiento que combinan dos cromosomas
para generar uno, dos, o incluso más hijos. El problema en planificación es el diseño de estos operadores a fin de que
puedan ser producidas planificaciones validas. Si la planificación se representa como una lista de números enteros se
debe verificar que el nuevo cromosoma no contiene dos veces un trabajo.
Los operadores de mutación se pueden diseñar fácilmente porque es más sencillo establecer que el nuevo cromosoma
forme otra vez una planificación valida. El más primitivo es un operador de cambio de dos trabajos adyacentes. Por
lo tanto, se selecciona una posición en la lista aleatoriamente y el trabajo en esta posición y su sucesor se
intercambian. Por supuesto se puede realizar más de un intercambio también. La mutación basada en la posición
selecciona aleatoriamente dos posiciones e intercambia los trabajos en estas posiciones. La mutación basada en el
orden selecciona dos posiciones y pone el trabajo de la segunda posición en el lugar del trabajo de la primera
posición. Se puede diseñar un gran número de estos operadores de mutación. Se han hecho también experimentos
exitosos con el intercambio de grupos de trabajos en una planificación. Además, se ha diseñado un operador de
mutación que selecciona las posiciones con alguna probabilidad donde la probabilidad de seleccionar una posición en
la que existe una violación a alguna restricción es mayor que el de otras posiciones [Dom94e].
Los operadores de cruzamiento son más sofisticados y deben ajustarse más aspectos a un determinado problema. Por
lo tanto, para planificación, se debe poner en el diseño de estos operadores algún esfuerzo para generar
planificaciones sólo validas. Fox y McMahon por ejemplo, usan matrices adyacentes booleanas para comprobar con
un simple algoritmo la validez. Diferentes operadores son propuestos para planificación. Por ejemplo, el cruzamiento
basado en orden toma algunos genes de uno de los padres y los pone en las mismas posiciones en la descendencia y
llena los puestos restantes con los genes del segundo padre, mientras que preservan el orden del segundo padre. El
operador de intersección de Fox y McMahon encuentra predecesores / sucesores comunes en ambos padres y estos
hereda en el hijo. Luego, el hijo será completado. Una vez más, son posibles un montón de diferentes operadores.
Parece ser que para cada tipo de problema se tienen que diseñar nuevos operadores para tener modificadores de
planificación eficientes.
39
Un algoritmo genético puede ser controlado por diferentes parámetros. Por lo tanto, el tamaño de la población tiene
una gran influencia sobre el desempeño del algoritmo. Una población demasiado grande
requiere más esfuerzo computacional y una población demasiado pequeña no garantiza diversidad para encontrar
buenas soluciones. Elitismo es un principio que garantiza que el mejor cromosoma de una población siempre debe
sobrevivir. Asimismo, el con qué frecuencia las tasas en que se aplicaran los operadores de mutación y cruzamiento
influyen en el comportamiento del algoritmo. Syswerda [Syswerda91] ha reconocido, para su problema de
planificación, que el rendimiento fue mejor cuando la tasa de la mutación basada en orden poco a poco fue
aumentada, mientras que la tasa de mutación basada en la posición se redujo.
En algunas comparaciones realizadas en [Dom94c] de diferentes métodos de mejora iterativa, algoritmos genéticos
se ha comportado peor que búsqueda tabú y profundización iterativa. Esta no debe ser la última palabra al respecto:
pero, el problema con algoritmos genéticos, parece ser que hay muchas decisiones de diseño que tienen influencia en
el rendimiento. Aunque los algoritmos genéticos son, en principio, un muy buen acercamiento para optimización
general, se requiere de mucho trabajo para adaptarlos a una aplicación específica, especialmente si se refiere a
problemas de planificación.
4.5 Propiedades deseables de la Metaheurística de resolución.
En esta sección analizamos un conjunto de propiedades deseables de las metaheurísticas. Son propiedades
deseables todas aquellas que favorezcan el interés práctico y teórico de las metaheurísticas. Indicaran direcciones a
las que dirigir los esfuerzos para la contribución al desarrollo científico e ingenieril de este proyecto, pero no será
posible mejorar todas las propiedades a la vez, dado que algunas son parcialmente contrapuestas. Una relación de
tales propiedades debe incluir las siguientes:
− Simple. La metaheurística debe estar basada en un principio sencillo y claro; fácil de comprender.
− Precisa. Los pasos y fases de la metaheurística deben estar formulados en términos concretos.
− Coherente. Los elementos de la metaheurística deben deducirse naturalmente de sus principios.
− Efectiva. Los algoritmos derivados de la metaheurística deben proporcionar soluciones de muy alta calidad;
optimas o muy cercanas a las óptimas.
− Eficaz. La probabilidad de alcanzar soluciones optimas de casos realistas con la metaheurística debe ser alta.
− Eficiente. La metaheurística debe realizar un buen aprovechamiento de recursos computacionales; tiempo de
ejecución y espacio de memoria.
− General. La metaheurística debe ser utilizable con buen rendimiento en una amplia variedad de problemas.
− Adaptable. La metaheurística debe ser capaz de adaptarse a diferentes contextos de aplicación o modificaciones
importantes del modelo.
− Robusta. El comportamiento de la metaheurística debe ser poco sensible a pequeñas alteraciones del modelo o
contexto de aplicación.
40
− Interactiva. La metaheurística debe permitir que el usuario pueda aplicar sus conocimientos para mejorar el
rendimiento del procedimiento.
− Múltiple. La metaheurística debe suministrar diferentes soluciones alternativas de alta calidad entre las que el
usuario pueda elegir.
− Autónoma. La metaheurística debe permitir un funcionamiento autónomo, libre de parámetros o que se puedan
establecer automáticamente.
− Flexible. La metaheurística debe permitir el ajuste flexible de sus parámetros y criterios, así como el manejo
flexible de las restricciones del problema.
− Equilibrada. La metaheurística debe mantener un equilibrio permanente entre la búsqueda de soluciones de
calidad y el uso de recursos computacionales.
− Modelable. La metaheurística debe permitir con el menor esfuerzo su modelización, diseño e implementación a
la hora de resolver problemas reales y concretos como para facilitar su aplicación e integración en entornos de
desarrollo mas generales.
Varias de estas propiedades están muy relacionadas y apuntan en la misma dirección, como la simplicidad, la
precisión y la coherencia. La simplicidad de la metaheurística facilita su uso y contribuye a dotarla de amplia
aplicabilidad. La descripción formal de las operaciones debe liberarse de la analogía física o biológica que haya sido
la fuente inicial de inspiración para permitir mejoras que no respeten la analogía. La precisión en la descripción de
los elementos que componen la metaheurística es crucial para concretar un procedimiento de alta calidad; fácil de
implementar. Los pasos de los procedimientos básicos de los algoritmos deben traducirse coherentemente de los
principios en que se inspira. Debe huirse de sentencias sin sentido o vagas. Frecuentemente se presentan como
extensiones de una metaheurística la incorporación de herramientas o recursos computacionales estándares, o de
pautas de otras metaheurísticas cuando en realidad deben calificarse como hibridaciones de las mismas.
La evaluación del rendimiento de una metaheurística debe atender tanto a la eficiencia como a la efectividad y
eficacia de los procedimientos heurísticos obtenidos. Para validar la efectividad y eficacia de una metaheurística,
estas deben afrontar con éxito problemas de un banco de casos reales para los que se conozcan las soluciones. Si no
se dispone de estos casos, se deben construir recurriendo a procesos de simulación que se aproximen a tales
circunstancias. La eficiencia del método se contrasta experimentalmente en el empleo de un tiempo computacional
moderado (o al menos razonable) para alcanzar éxito en los problemas considerados. El tamaño de los problemas
considerados en las aplicaciones prácticas de los métodos de optimización se limita por las herramientas disponibles
para resolverlos más que por la necesidad de los potenciales usuarios. Cuando las metaheurísticas se aplican a
instancias realmente grandes, sus fortalezas y debilidades aparecen más claramente. Las metaheurísticas pueden
mejorar su rendimiento extendiéndose en varias direcciones y, posiblemente, hibridizandose. Los procedimientos
heurísticos resultantes se complican y usan muchos parámetros. Con ello se puede mejorar su eficiencia, pero
41
enmascaran las razones de su éxito. En algunas ocasiones la alta especialización de una metaheurística lleva a un
ajuste fino de parámetros sobre algún conjunto de entrenamiento concreto.
La aplicabilidad de una metaheurística debe estar sustentada en la generalidad, pero también en su adaptabilidad y
robustez. La robustez tiene que ser contrastada experimentalmente analizando el rendimiento frente a fluctuaciones
de las características de los problemas. La robustez se refleja en que el número de parámetros que hay que fijar en las
distintas aplicaciones se mantiene bajo. La generalidad de una metaheurística se refleja en la diversidad de los
campos de aplicación para los que se han utilizado con éxito. La adaptabilidad permite que las conclusiones
obtenidas al afrontar un tipo de problemas particular puedan ser aprovechadas en otros contextos. Las pautas
proporcionadas por una metaheurística de búsqueda se aplican a descripciones asociadas a un problema, referidas
simplemente a los movimientos posibles para transformar una solución en otra y la forma de evaluarlas.
Para favorecer la utilidad de la metaheurística en la resolución de problemas reales, por ejemplo incorporándolo a
Sistemas de Apoyo a la Toma de Decisiones, son importantes las propiedades que propicien una interfase amigable.
La interactividad de los sistemas basados en las metaheurísticas favorece la colaboración con otros campos que
proporcionan conocimientos especificos de los problemas para mejorar el rendimiento de la metaheurística. La
posibilidad de ofrecer diversas soluciones de alta calidad, realmente diferentes, entre las que los decidores puedan
optar contribuye a diseminar su uso. La relativa autónoma de implementaciones de la metaheurística permite ganarse
la confianza de usuarios poco expertos en optimización o en los campos de aplicación.
Una característica que contribuye a divulgar una metaheurística es la novedad a la que va asociada, en cuanto a la
originalidad de los principios que la inspiran y a los campos de repercusión social a los que se aplica. Este aspecto se
revela, por ejemplo, en la inspiración en fenómenos naturales de los algoritmos genéticos y otras metaheurísticas, en
la aplicación a la demostración matemática de la metaheurística de entorno variable, y en la aplicación a la ingeniera
genética de algunas técnicas. Sin embargo, en los entornos científicos, tecnológicos, ingenieril o empresarial, el
aspecto mas relevante es el éxito asociado a la eficiencia y efectividad de los algoritmos derivados de cada
metaheurística en la resolución de problemas de gran tamaño o surgidos en aplicaciones reales.
42
Capítulo 5
Un Algoritmo de Mejora Iterativa Estocástica para resolver el Problema de
Diseño de Mallas Curriculares
5.1 Solución Inicial.
La solución inicial se produce utilizando una heurística constructiva que parte de una malla curricular
(planificación) vacía. Esta solución factible se obtiene mediante la adición o eliminación adecuada de cursos
(trabajos) de la malla, basada en la disponibilidad de semestres (se trata de programar primero durante el proceso los
cursos sin prerrequisitos), sin tener en cuenta ninguna de las restricciones suaves, hasta que las restricciones duras se
cumplan (restricciones de precedencia). Esta heurística constructiva se comporta como un grado de saturación
heurístico (ver [Carter96]). La planificación se hace factible antes de iniciar los algoritmos.
5.2 Estructura del Vecindario.
Se implementaran las siguientes estructuras de vecindario para ser utilizadas en el algoritmo propuesto. Se
presentan en primer lugar, N1-N8 que ya han sido publicadas en [Abdullah05] (donde fueron aplicados con éxito al
UCTP), pero que se muestran nuevamente aquí (junto con tres estructuras extras para integridad y claridad):
− N1: Seleccione un curso al azar y encuentra otro curso al azar, que pueden intercambiar períodos.
− N2: Elije al azar sólo un curso y se desplaza a otro periodo posible de asignar.
− N3: Selecciona dos periodos al azar y simplemente intercambia todos los cursos de un periodo con todos los
demás cursos en el otro periodo.
− N4: Mover un periodo. Toma 2 periodos (seleccionados al azar), por ejemplo ti y tj (donde j > i) y los periodos
están ordenados t1, t2,...., tn. Toma todos los cursos en ti y los asigna a tj. Luego, tomar los cursos que se
encontraban en tj y los asigna a tj-1. A continuación, asigna los cursos en tj-1 a tj-2 y así sucesivamente hasta que
se asigne los cursos de ti-1 a ti y termine el proceso.
− N5: Mover el curso con la penalidad más alta, luego de una selección aleatoria del 10% de los cursos, a un
periodo factible de forma aleatoria.
− N6: Mover el curso con la penalidad más alta, luego de una selección aleatoria del 20% de los cursos, a un
periodo factible de forma aleatoria.
43
− N7: Mover el curso con la penalidad más alta (es decir, el curso con el mayor número de violaciones a
restricciones suaves. Tomar el 10% de los cursos al azar. A continuación, seleccionar el curso con el más alto
costo de penalidad y asignarlo al periodo que genere la menor penalidad y que no crea infactibilidad.
− N8: Mover el curso con la penalidad más alta luego de una selección aleatoria del 20% de los cursos (como en
(N7)).
− N9: Seleccionar un curso al azar, elegir un periodo al azar (distinto al que esta asignado el curso seleccionado) y
luego aplicar la cadena de Kempe (descrita en [Thompson96]).
− N10: Este es el mismo que N9, pero aquí se selecciona el curso con la penalidad más alta luego de una selección
del 5% de los cursos al azar.
− N11: Como N10, pero con el 20% de los cursos.
A fin de mantener la factibilidad de la solución, la asignación de cursos en cada periodo de la malla
curricular (después de una operación de cadena de Kempe) no puede exceder el espacio (número de periodos)
disponible y, por supuesto, cada uno de los cursos debe ser programado en diferentes periodos.
5.3 El Algoritmo.
Para el acercamiento presentado en esta tesis, se aplica un conjunto de estructuras de vecindario como en la
subsección 5.2. Las restricciones duras nunca son violadas durante el proceso de asignación de cursos a la malla
curricular. La figura 5 muestra una vista esquemática general de esta propuesta. El algoritmo comienza con una
solución factible inicial generada por una heurística constructiva. Siendo K el número total de estructuras de
vecindario que se utilizarán en la búsqueda y f(Sol) es la medida de calidad de la solución Sol. Al principio, la mejor
solución, Solbest y la solución anterior, Solprev pueden ser Sol. En un bucle do-while cada vecindario i donde i ∈ (1,...,
K) se aplica a Sol para obtener TempSoli. Se identifica la mejor solución en TempSoli, y se establece como la nueva
solución de Sol*. Si Sol* es mejor que la mejor solución actual Solbest, entonces Sol* es aceptada. De lo contrario, se
aplica el criterio de aceptación de la exponencial de Monte Carlo (véase [Ayob03]). La Exponencial de Monte Carlo
se basa sólo en la calidad de la solución. Se acepta una peor solución con una cierta probabilidad. Por ejemplo, dadas
una solución antigua y una nueva denotadas por Sol y Sol*, respectivamente. La nueva solución Sol* será aceptada si
genera un número aleatorio entre [0,1] es inferior a expδ donde δ = f(Sol*)-f(Sol). El aumento del valor de
δ disminuirá la probabilidad de aceptar peores soluciones. Los detalles sobre la exponencial de Monte Carlo se
pueden encontrar en [Ayob03].
44
Fig. 5. Seudo-código dfor the randomised iterative improvement algorithm for course timetabling
5.4 La Heurística Constructiva.
Se propone un enfoque inspirado en la programación con restricciones. Sin embargo, como se menciono en
la sección 3.5, cuando se construye una asignación el orden en que las variables son asignadas por la heurística de
ordenamiento es bastante importante, estas heurísticas han sido estudiadas extensamente.
Cada vez que se asigna un valor a una variable, se debe invocar algún algoritmo de propagación. Este algoritmo
acota los dominios de las variables que aún no son asignadas. Si el tamaño del dominio de una variable se hace 1,
entonces se completa la asignación parcial de la variable de decisión Xij (según el modelo descrito en la sección 4.1)
por la asignación de un valor a esta variable y el proceso de propagación continua. Al final del proceso de
propagación, si el dominio de una variable se hace vacío o si se descubre alguna inconsistencia, entonces el
algoritmo falla.
Como se señalo en la sección 3.3, se pueden considerar algoritmos de propagación diferentes, que aseguran niveles
de consistencia diferentes, por ejemplo, consistencia de nodo, consistencia de arco, o consistencia de caminos. En
Set the initial solution Sol by employing a constru ctive heuristic;
Calculate initial cost function f(Sol);
Set best solution Sol best ← Sol;
do while (not termination criteria)
for i = 1 to i= K where K is the total number of n eighbourhood structures
Apply neighbourhood structure on Sol, TempSoli;
Calculate cost function f(TempSoli);
Find the best solution among TempSoli where i ∈ {1,…,K} call new solution
Sol*;
if (f(Sol*) < f(Sol best ))
Sol ← Sol*;
Sol best ← Sol*;
else
δ = f(Sol*) ← f(Sol));
Generate RandNum, a random number in [0,1];
if (RandNum < e � ) then Sol ← Sol*;
end for
end do
45
este proyecto se pretenden utilizar algoritmos de propagación de consistencias integrados en algún solver3.
5.5 Esquema de Solución Propuesto para BACP.
Para la resolución de la problemática que da origen a esta tesis de grado, se ha recurrido a un conjunto de
elementos computacionales que ayudan en el proceso de creación de soluciones para el BACP, algunos de estos
elementos se han diseñado siguiendo la idea original para el problema de Timetabling presentada en [Johnson06]. De
esta forma se tienen los módulos que se presentan a continuación.
• Un algoritmo de satisfacción de restricciones: Este algoritmo proporciona una correcta asignación de
cursos a eventos asignados a un determinado timeslot (semestre).
• Una búsqueda local estocástica: esta búsqueda local permite mejorar la calidad de las soluciones generadas
a lo largo del algoritmo, y ha sido descrita en la sección 5.3.
El esquema de la figura 6, presenta los módulos utilizados para generar una solución optimizada, haciendo uso de la
heurística constructiva para asignar eventos a determinados timeslot, el algoritmo de emparejamiento toma esta
asociación evento-timeslot y realiza una asignación de asignatura para cada semestre. Esto genera una solución
completa pero de baja calidad. Entonces pasa por un proceso de optimización a través de una búsqueda local, para
generar una solución factible de mejor calidad (óptima).
Fig. 6. Esquema de Solución Propuesto
3 Aquí se considera GECODEJ, interfaz Java para el desarrollo de soluciones basadas en GECODE (GEneric COnstraint Development Environment): conjunto de librerías C++ que provee un conjunto de algoritmos de propagación y estrategias de búsqueda para la resolución de problemas de satisfacción de restricciones.
Satisfacción de Restricciones Verifica restricciones duras
Búsqueda Local basada en Mejora Iterativa Estocástica
Mejora la calidad de las soluciones
Emparejamiento eventos-timeslot
Solución sin optimizar
Instancia
Heurística Constructiva Asociación de cada evento con un
determinado timeslot.
Solución
46
5.5.1 Representación.
Uno de los elementos principales del esquema de resolución propuesto es la representación matricial de cada una de
las posibles soluciones al problema, de modo que una asignación de valores binarios en cada posición represente una
solución al problema. En el problema del BACP se requieren asignar cada uno de los │E│ eventos (cursos) a un
│T│ timeslots (períodos). En la mayoría de las representaciones directa la matriz de construcción tiene dimensiones
de E × T; dada esta matriz podemos entonces decidir si un curso será asignado a un período, colocando un 1, en caso
de que sea asignado, en la fila correspondiente al curso y la columna correspondiente al periodo, o un 0 en caso
contrario, la solución termina de ser construida cuando la matriz esta completa. La figura 7 y la figura 8 representan
esta matriz de construcción.
Fig. 7. Cada evento (curso) es asignado según una lista de timeslots (períodos), y para cada timeslot t’ ∈ T’, se elige un conjunto de eventos e ∈ E que se colocará en este timeslot.
Fig. 8. Matriz binaria, donde cada evento tiene que ser puesto exactamente una vez en un timeslot; ∑=
=n
jijx
1
1.
47
La representación es bastante simple (la presentada en la figura 6), en donde se construye la solución “caminando” a
lo largo de una lista de eventos, eligiendo un timeslot para cada uno, no requiere la complicación adicional de
utilización de grafos y no parece tener ninguna desventajas obvia. De hecho, no se prohíbe la oportunidad de usar
una lista ordenada de eventos heuristicamente (asignar primero los cursos sin prerrequisitos). Realizando un cierto se
podría colocar en orden los eventos para poner los eventos de mayor dificultad primero en la malla, cuando todavía
hay muchos timeslots con pocos o ningún curso asignado. Por estas razones se considera que esta forma de
representar el problema es mejor para desarrollar una adecuada implementación del enfoque de solución propuesto.
48
Capítulo 6
Diseño de Prototipo
6.1 Descripción del Prototipo.
La Pontificia Universidad Católica de Valparaíso, y en general cualquier institución de educación superior,
considera como parte importante de su reglamento una serie de artículos con el fin de mantener cierto nivel de
exigencia académica para sus estudiantes. Existe uno en particular que hace mención a la cantidad de créditos
promedio por semestre que un estudiante debe tener aprobados a partir de cierto periodo, esta exigencia esta descrita
en el artículo 28 del Reglamento General de Estudios. A continuación se presenta un extracto:
“El promedio acumulativo mínimo de créditos aprobados por semestre, exigible a contar del período
académico lectivo indicado en la letra e. del artículo 22º, corresponderá al cuociente entre el total de créditos del
Plan de Estudios y el número máximo de períodos académicos a que se refiere la letra d. del artículo 22º.”
Cuando un estudiante no cumple con la exigencia antes descrita incurre en causal de eliminación, sin embargo, el
estudiante puede solicitar eximición de dicho artículo. Una vez aprobada esta solicitud debe acudir al Jefe de
Docencia respectivo para que este “reprograme” su carga académica. Esta reprogramación consiste en reformular la
malla curricular considerando los cursos reprobados, además de los aún no cursados, de tal forma que se mantenga el
equilibrio de la malla, es decir, se mantenga el balanceo de la malla curricular propuesta según las restricciones
definidas en el capitulo 4.
A continuación se muestra un ejemplo de aplicación:
− Carrera: Ingeniería Ejecución en Informática
− Número de períodos que componen el currículo: 8
− Número máximo de períodos académicos: 13
− Total de créditos del plan de estudios: 145
En este caso el artículo 28 regirá a partir del quinto semestre (8/2 + 1), por lo tanto la cantidad de créditos exigidos a
esa fecha se calcula como:
1113
145
cos
Pr ===
AcadémiPeriodosMáximoNúmero
CreditosTotalexigiblescreditosdeomedio (6.1)
Esto implica que al quinto semestre el alumno tendrá que contar con 44 (11 × 4) créditos aprobados.
49
6.1.1 Modificaciones al modelo clásico.
Para adecuar el modelo clásico a esta situación se deben incorporar ciertas modificaciones adicionales, que satisfacen
el objetivo de reformular una malla curricular y que potencian la utilidad del sistema final, sin embargo quedan fuera
del alcance de esta tesis:
Parámetros adicionales: Sean
i) s: Semestre que el estudiante actualmente cursa.
ii) =∀=∀
=casootroen
njmiaprobadosidohaicursoelsixij 0
,...,1 ,...1 1
Nueva Función Objetivo: { }ns ccMaxcMin ,..., =
6.2 Análisis Funcional.
El prototipo desarrollado utilizando tecnología Java (NetBeans IDE 6.01 y JDK 1.6) considera las siguientes
funcionalidades:
1. Crear Malla: en esta opción el usuario define las características de la malla curricular: (definidas en la
sección 2.1) número de cursos, número de períodos académicos, número de créditos de cada curso, carga
académica mínima y máxima permitida por periodo y cantidad mínima y máxima de cursos por periodo
(Ver Figura 8).
2. Visualizar Malla: esta opción permite visualizar la malla curricular a partir de un archivo plano (que puede
haber sido previamente generado mediante el Prototipo), durante este proceso de visualización se crea una
propuesta inicial de malla no balanceada, pero que satisface las restricciones descritas en la sección 2.1 (Ver
Figura 9).
6.2.1 Formato de Archivos de Entrada.
Los archivos planos utilizados para la implementación y evaluación de este primer prototipo corresponden a
benchmarks disponibles en la literatura4 [Gent99]. Estos consisten en archivos de texto con la siguiente información:
− Carga mínima permitida por periodo.
− Carga máxima permitida por periodo.
− Cantidad mínima de cursos por periodo
− Cantidad máxima de cursos por periodo
− Lista (arreglo) de cursos y sus siglas.
− Lista (arreglo) con la cantidad de créditos correspondientes a cada curso.
− Lista de prerrequisitos.
4 Ver www.csplib.org, Problema 30.
50
Fig. 8. Interfaz de usuario opción “Crear Malla”
Por otra parte el Prototipo esta configurado para, mediante la opción Crear Malla, generar archivos de texto plano
con los antecedentes de las mallas curriculares creadas siguiendo el formato ya aceptado por la academia para este
tipo de experimentos. Así se pretende contribuir de alguna manera a la generación y distribución de conocimiento
respecto a la problemática que da origen a esta tesis de grado.
51
Fig. 9. Visualización de malla curricular mediante la opción “Visualizar Malla”.
6.2.2 Arquitectura del Prototipo.
A continuación se describe cada uno de los paquetes y componentes que forman parte del prototipo de Sistema de
Balanceo de Mallas Curriculares:
� Java Swing: Librería Java para el desarrollo de interfaces gráficas de usuario, es una extensión de la
antigua AWT.
� VO (Visual Objects): Contiene la definición de los objetos visuales Malla, Semestre y Ramo utilizados
para construir una malla curricular.
� Interfaz: Contiene la definición de las clases que permiten la generación de las distintas interfaces
gráficas de usuario que posee el prototipo, entre ellas se encuentra el objeto VisualizadorMalla que
permite generar una imagen de la malla curricular generada por el prototipo.
� Util: Contiene la definición de las clases que permite la carga de datos de los archivos benchmark para
la validación del prototipo y la generación de nuevos archivos (en el mismo formato) a partir del
ingreso de datos por parte de usuarios reales.
� Gecode Nativo: GEneric COnstraint Development Environment, conjunto de librerías C++ que permite
el desarrollo de algoritmos para la resolución de problemas de satisfacción de restricciones.
� GecodeJ: Interfaz Java para el desarrollo de soluciones basadas en Gecode.
52
� Logica: Conjunto de clases Java que permite la resolución del problema central de este proyecto, entre
ellas se encuentra la clase Options que permite la inicialización y parametrización del espacio inicial de
búsqueda.
� Clase SolverBACP: Clase Java, que se define a partir de la clase Space, sobre la cual se definen los
propagadores para la satisfacción de las restricciones asociadas al programa en cuestión.
Fig. 10. Modelo Conceptual del Prototipo.
6.3 Definición de propagadores y estrategia de enumeración en GecodeJ.
A continuación se muestra la especificación GecodeJ de los propagadores asociados a cada una de las
restricciones del BACP:
� Todos los cursos i deben ser asignados a un periodo j:
for(int i = 0; i < m; i++)
linear(this, X.row(i), IRT_EQ, 1);
53
� El curso b tiene un curso a como prerrequisito:
for (int i = 0; i < m; ++i)
{
for (int r = 1; r < n; j++)
{
int Xar = Xij.get(prq[i][0],j).val();
rel(this, Xij.get(i, r), IRT_LQ, Xar);
}
}
� La carga académica del periodo j debe ser mayor o igual que el mínimo requerido:
for (int j = 0; j < n; j++)
linear(this, alfa, X.col(j), IRT_GQ, this.b eta);
� La carga académica del periodo j debe ser menor o igual que el máximo requerido:
for (int j = 0; j < n; j++)
linear(this, alfa, X.col(j), IRT_LQ, this.g ama);
� El número de cursos del periodo j debe ser mayor o igual que el mínimo requerido:
for (int j = 0; j < n; j++) {
linear(this, X.col(j), IRT_GQ, this.g);
� El número de cursos del periodo j debe ser menor o igual que el máximo requerido:
for (int j = 0; j < n; j++) {
linear(this, X.col(j), IRT_LQ, this.e);
� Estrategia de enumeración: Un Branching en Gecode determina la heurística utilizada para la exploración
del espacio durante la busqueda.
branch(this, X, INT_VAR_NONE, INT_VAL_MAX);
INT_VAR_NONE: Selecciona la variable a asignar según el orden en la cuál fueron definidas.
INT_VAL_MAX: Selecciona el valor máximo del dominio para asignar a la variable.
Fig. 11. Espacio (Gecode Space).
54
6.4 Resultados Computacionales.
La figura 12, muestra una tabla resumen con los resultados obtenidos durante la evaluación del prototipo.
INDICADOR bacp8 bacp10 bacp12
m/n 46/8 42/10 66/12
Propagaciones 914 976 1365
Fallas 0 0 0
Soluciones (antes de encontrar la mejor) 7 2 1
Nº de backtracks 45 48 74
Fig. 12. Resumen de Resultados Computaciones.
Aquí se puede observar la efectividad del esquema propuesto en todas las instancias benchmark evaluadas. A medida
que el espacio de búsqueda crece también lo hace el número de propagaciones de resultantes de la aplicación de
cada restricción del problema de balanceo, lo mismo sucede con el número de vueltas atrás (backtraks) del
algoritmo. Un aspecto positivo del proceso es que durante la búsqueda nunca se generan fallas y el número de
soluciones visitadas antes de encontrar la mejor disminuye de acuerdo a mayor complejidad del problema.
6.4.1 Restricciones Suaves versus Restricciones Duras.
Se sabe que, en general, los problemas de planificación son NP-completo [Burke99], lo que significa que no se
conoce un método para hallar con garantías una solución óptima en un tiempo razonable. En un problema así, hay
restricciones duras (en este caso no puede asignarse el mismo curso a dos periodos a la vez) y restricciones suaves (si
es posible, no deben asignarse cursos a un mismo periodo si superan la cantidad máxima de créditos permitidos).
Luego en el caso del BACP, podemos clasificar las restricciones que modelan el problema en alguno de estos 2 tipos:
− Restricciones Duras (hard constraints): Son aquellas restricciones cuya satisfacción imprescindible, por ende no
puede ser violadas.
� Todos los cursos i deben ser asignados a un periodo j:
� El curso b tiene un curso a como prerrequisito:
− Restricciones Suaves (soft constraints): Son aquellas restricciones cuya satisfacción no es imprescindible, pero
afectan la calidad de una solución, por ende pueden ser violadas a cierto costo.
� El número de cursos del periodo j debe ser mayor o igual que el mínimo requerido:
� El número de cursos del periodo j debe ser menor o igual que el máximo requerido:
� La carga académica del periodo j debe ser mayor o igual que el mínimo requerido:
� La carga académica del periodo j debe ser menor o igual que el máximo requerido:
55
A continuación se muestra un análisis del comportamiento del modelo propuesto para resolver el BACP respecto al
número de restricciones suaves a satisfacer durante la resolución del problema:
Primera Solución
0
200
400
600
800
1000
1200
0 1 2 3 4
n° de restricciones suaves
tiem
po (
seg.
)
bacp8 bacp10 bacp12
Fig. 13. Resultados Computaciones Primera Solución
En la figura 13, se puede observar como el esfuerzo computacional del esquema propuesto aumenta
exponencialmente a medida que se aumenta la cantidad de restricciones suaves que no se relajan (se exige su
satisfacción para considerar una asignación de valores como solución del problema). También se puede observar el
aumento del esfuerzo computacional a medida que se aumenta la complejidad del problema. Sin embargo se logra
encontrar una primera solución en todas las instancias benchmark evaluadas.
A continuación, en la figura 14, se muestra el comportamiento del esquema propuesto al explorar hasta encontrar la
mejor solución. Aquí el esquema no es capaz de encontrar soluciones satisfactorias en un tiempo computacional
razonable en las instancias bacp10, cuando se exige la satisfacción de todas las restricciones suaves (no hay
relajación), y bacp12 sólo se resuelve exigiendo la satisfacción de las 2 primeras restricciones suaves.
Finalmente en la figura 15, se aprecia como los rendimientos del esquema propuestos difieren notablemente si se
considera el esfuerzo computacional empleado para encontrar la primera solución a las instancias del problema
evaluadas en comparación a encontrar la mejor solución según los criterios de búsqueda definidos en el esquema.
56
Mejor Solución
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
0 1 2 3 4
n° de restricciones suaves
tiem
po (
seg.
)
bacp8 bacp10 bacp12
Fig. 14. Resultados Computaciones Mejor Solución
Primera v/s Mejor
0
500
1000
1500
2000
2500
3000
3500
4000
4500
1 2 3 4 5
n° de restricciones suaves
tiem
po (
seg.
)
prom. primera prom. mejor
Fig. 15. Comparación Resultados Computacionales de la búsqueda de la primera v/s la mejor Solución
57
Capítulo 7
Conclusiones y Trabajo Futuro
Al concluir este proyecto se ha presentado una propuesta y un prototipo hacia la resolución del problema de
diseño de mallas curriculares balanceadas basado en técnicas de programación con restricciones y un algoritmo
inspirado en búsqueda local estocástica. Además se han introducido los conceptos más importantes respecto a los
problemas de satisfacción de restricciones, y al problema de diseño de un currículo académico balanceado que da
origen al desarrollo de esta tesis de magíster, y técnicas de mejora iterativa estocástica. Aquí, se ha hecho especial
hincapié en el modelado y resolución mediante estrategias basadas en búsqueda local y propagación de restricciones
de tal manera de explotar rápidamente las zonas más prometedoras de los árboles de búsqueda de solución a este tipo
de problemas y por consiguiente optimizar los requisitos de memoria. También se ha presentado una descripción
general de los algoritmos basados en mejora iterativa estocástica cuyas características probabilistas se utilizan como
parte del esquema de resolución asociado al problema especificado.
Además, se ha definido el algoritmo de optimización basado en mejora iterativa estocástica para la resolución de
CSP’s y la función de evaluación de la calidad de las soluciones para utilizar esta como estrategia de salida ante la
presencia de óptimos locales, incluyendo el paso de actualización del espacio de búsqueda mediante propagación de
restricciones.
Los resultados computacionales obtenidos confirman la hipótesis sostenida en la formulación de esta tesis de
magíster, es decir, la utilización de un esquema de colaboración entre técnicas completas e incompletas de resolución
de problemas combinatorios difíciles puede resolver el problema de diseño de mallas curriculares balanceadas para
carreras universitarias. Sin embargo, también el análisis de resultados permite visualizar que el esquema de
resolución propuesto es susceptible a mejoras tanto en su diseño como quizás en su implementación final.
Se puede destacar aquí que como producto de software del trabajo realizado también se tiene un prototipo funcional
del sistema (tal como de describió en el capitulo 6) que permite el diseño de mallas curriculares balanceadas
mediante la utilización del esquema de resolución del problema de BACP propuesto.
Finalmente, como posibilidades de trabajo futuro, es clara la necesidad de probar la utilización de otras técnicas de
búsqueda local en el esquema de colaboración propuesto y evaluar su efectividad y eficiencia en la resolución del
problema original de BACP y su inclusión en el prototipo propuesto.
58
REFERENCIAS
[Abdullah05] Abdullah S, Burke EK and McCollum B (2005) An investigation of variable neighbourhood
search for university course timetabling. Accepted for publication in The 2nd Multidisciplinary International
Conference on Scheduling: Theory and Applications (MISTA 2005).
[Adams88] Adams, J., Balas, E. and Zawack, D. The Shifting Bottleneck Procedure for Job Shop Scheduling,
Management Science 34 (3), pp. 391-401, 1988.
[Ayob03] Ayob M and Kendall G (2003) A monte carlo hyper-heuristic to optimise component placement
sequencing for multi head placement machine. Proc. Of the International Conference on Intelligent Technologies,
InTech’03, pp 132-141.
[Bagchi91] Bagchi, S., Uckum, S. Miyabe, Y. and Kawamura, K. Exploring Problem-Specific Recombination
Operators for Job Shop Scheduling, Proceedings of the 4 th International Conference on Genetic Algorithms , 1991.
[Bakker93] Bakker, R. R., Dikker, F., Tempelman, F. and Wognum, P. M. Diagnosing and Solving Over-
determined Constraint Satisfaction Problems, Proceedings of the 13th International Joint Conference on Artificial
Intelligence , pp. 276-281, 1993.
[Balas69] Balas, E. Machine Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm, Operations
Research 17 (6), pp. 941-957, 1969.
[Barnes93] Barnes, J. W. and Laguna, M. A Tabu Search Experience in Production Scheduling, in Annals of
Operations Research 41, pp. 141-156, 1993.
[Barták01] R. Barták, Constraint Programming: In Pursuit of the Holy Grail, 2001.
[Beck04] J. C. Beck, P. Prosser, and R.Wallace, Variable Ordering Heuristics Show Promise, In Proc. of CP’2004,
volume 3258 of LNCS, pages 711–715, 2004.
[Boddy89] Boddy , M. and Dean, T. Solving Time Dependent Planning Problems, Proceedings of the 11 th
International Joint Conference on Artificial Intelligence , pp. 979-984, (989.
[Bruns93] Bruns, R. Direct Chromosome Representation and Advanced Genetic Operators for Production
Scheduling, Proceedings of the 5 th International Conference on Genetic Algorithms, 1993.
59
[Burke99] Burke, E.K. y J.P. Newall. ``A multistage evolutionary algorithm for the timetable problem.'' IEEE
Transactions on Evolutionary Computation, vol.3, no.1, p.63-74 (abril de 1999).
[Canudas72] L.F. Canudas, Revista de la Educación Superior, Nº 2, 1972, Págs. 13-21.
[Canzi93] Canzi, U. and Guida, G. The Temporal Model of CRONOS -III: A Knowledge-based System for
Production Scheduling, in J. Dorn and K. A. Froeschl (eds.), Scheduling of Production Processes , Chichester: Ellis
Horwood, pp. 113-129, 1993.
[Carchrae04] T. Carchrae and J. C. Beck, Low-Knowledge Algorithm Control, In Proc. of AAAI 2004, pages 49–54,
2004.
[Carter96] Carter, M.W. and Laporte, G. (1996) Recent developments in practical examination timetabling. In
[3], pp 3-21.
[Castro01] C. Castro, S. Manzano, “Variable and Value Ordering When Solving Balanced Academic Curriculum
Problems”, Proceedings ERCIM WG on constraints, 2001.
[Cleveland89] Cleveland, G. A. and Smith, S. F. Using Genetic Algorithms to Schedule Flow Shop Releases,
Proceedings of the 3 rd International Conference on Genetic Algorithms, Morgan Kaufmann, pp. 160-169, 1989.
[Com88] Committee on the Next Decade of Operations Research (Condor). Operations Research: The Next Decade.
Operations Research 36, 1988.
[Davis85] Davis, L. Job Shop Scheduling with Genetic Algorithms, Proceedings of the 1 st International Conference
on Genetic Algorithms, Lawrence Erlbaum, 1985.
[deWerra89] de Werra, D. and Hertz, A. Tabu Search Techniques: A Tutorial and an Application to Neural
Networks, OR Spektrum 11, pp. 131-141, 1989.
[Dom92] Dorn, J. Temporal Reasoning in Sequence Graphs, Proceedings of the 10 th National Conference on
Artificial Intelligence (AAAI 92), pp. 735-740, 1992.
[Dom93b] Dorn, J. Supporting Scheduling with Temporal Logic, Proceedings of the IJCAI’93 Workshop on
Production Planning, Scheduling and Control, Chambéry, France.
60
[Dom93a] Dorn, J, Kerr, R. M. and Thalhammer, G. Reactive Scheduling in a Fuzzy-Temporal Framework, in E.
Szelke and R. M. Kerr Knowledge-based Reactive Scheduling , IFIP Transactions B-15, North Holland, pp. 39-55,
1993.
[Dom94b] Dorn, J. Hybrid Temporal Reasoning, Proceedings of the 11 th International Conference on Artificial
Intelligence , Amsterdam, pp. 619-623, 1994
[Dom94d] Dorn, J. and Slany, W. A Flow Shop with Compatibility Constraints in a Steelmaking Plant, in Zweben
and Fox (eds.) Intelligent Scheduling, Morgan Kaufmann, 1994.
[Dom94c] Dorn, J., Girsch, M. Skele, G. and Slany, W. Comparison of Iterative Improvement Techniques for
Schedule Optimization, Proceedings of the 13th UK Planning Special Interest Group , Glasgow (also available as
CD-TR 94-61), 1994.
[Dom94a] Dorn, J. and Kerr, R. M. Co-operating Scheduling Systems Communicating Through Fuzzy Sets,
Preprints of the 2 nd IFAC/IFIP/IFORS-Workshop on Intelligent Manufacturing Systems (IMS’94), Vienna, pp. 367-
373, 1994.
[Dom94e] Dorn, J. and Girsch, M. Genetic Operators Based on Constraint Repair, Proceedings of the ECAI’94
Workshop on Applied Genetic and other Evolutionary Algorithms, 1994.
[Dom94b] Dorn, J. Interaction with a Scheduling System by Soft Constraints, AAAI SIGMAN Workshop , New
Orleans, 1994.
[Dueck90] Dueck, G. and Scheuer, T. Threshold Accepting: A General Purpose Optimization Algorithm Appearing
Superior to Simulated Annealing, Journal of Computational Physics 90, pp. 161-175, 1990.
[Dueck93] Dueck, G. New Optimization Heuristics, Journal of Computational Physics 104, pp. 86-92, 1993.
[Filipic93] Filipic, B. Enhancing Genetic Search to Schedule a Production Unit, in J. Dorn and K. A. Froeschl (eds.),
Scheduling of Production Processes , Chichester: Ellis Horwood, pp. 61-69, 1993.
[Flener01] P. Flener, B. Hnich, and Z. Kiziltan, A meta-heuristic for subset problems, In Proc. of PADL’2001,
volume 1990 of LNCS, pages 274–287. Springer, 2001.
61
[Flener02] P. Flener, A.M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel y T. Walsh, “Matrix Modelling: Exploiting
Common Patterns in Constraint Programming”, Proceedings of the International Workshop on Reformulating
Constraint Satisfaction Problems, 2002.
[Francois03] Francois Laburthe Filippo Focacci and Andrea Lodi. Local Search and Constraint Programming. 2003.
[French82] French, S. Sequencing and Scheduling - An Introduction to the Mathematics of the Job-Shop, Chichester:
Ellis Horwood, 1982.
[Fox87] Fox, M. S. Constraint-directed search: a case study of job-shop scheduling , Ph.D. Computer Science Dept.,
Carnegie-Mellon University, also published by Pitman, 1987.
[Fox91] Fox, B. R. and McMahon, M. B. Genetic Operators for Sequencing Problem, in G. J. E. Rawlings (ed.)
Foundations of Genetic Algorithms, pp. 284-300, 1991.
[Gebruers04] C. Gebruers, A. Guerri, B. Hnich, and M. Milano, Making choices using structure at the instance level
within a case based reasoning framework, In Proc. Of CPAIOR’2004, volume 3011 of LNCS, pages 380–386.
Springer, 2004.
[Gent99] I.P. Gent and T. Walsh. Csplib: a benchmark library for constraints. Technical report, Technical report
APES-09-1999, 1999. Available from http://csplib.cs.strath.ac.uk/. A shorter version appears in the Proceedings of
the 5th International Conference on Principles and Practices of Constraint Programming (CP-99).
[Glover89] Glover, F. Tabu Search-Part I, ORSA Journal on Computing 1 (3), pp. 190-206, 1989.
[Glover90] Glover, F. Tabu Search-Part II, ORSA Journal on Computing 2 (1), pp. 4-32, 1990.
[Glover93] Glover, F., Laguna, M., Taillard, E. and de Werra, D. (eds.) Tabu Search, Annals of Operations Research
41 (1), pp. 4-32, 1993.
[Hnich02] B. Hnich, Z. Kiziltan y T. Walsh, “Modelling a Balanced Academic Curriculum Problem”, Proceedings
CPAIOR 2002.
[Holland75] Holland, J. H. Adaptation in Natural and Artificial Systems, Ann Arbor: University of Michigan Press,
1975.
62
[Johnson06] Johnson, F., Crawford, B. y Palma, W.: Hypercube FrameWork for ACO applied to timetabling. IFIP
AI 2006: pp. 237-246.
[Kanet] Kanet, J. J. and Sridharan, V. PROGENITOR: A Genetic Algorithm for Production Scheduling,
Wirtschaftsinformatik, pp. 332-336
[Khichane06] M. Khichane, P. Albert, C. Solnon, “Using ACO to guide a CP search”, 2006.
[Kirkpatrick83] Kirkpatrick, S. Gelatt, C.D. and Vecchi, M. P. Optimization by Simulated Annealing, Science 220,
pp. 671-680, 1983.
[Korf85] Korf, R.E. Depth-First Iterative-Deepening, Artificial Intelligence 27 (1), pp. 97-109, 1985.
[Laguna91] Laguna, M., Barnes, J. W. and Glover, F. Tabu Search Methods for a Single Machine Scheduling
Problem, Journal of International Manufacturing 2, pp. 63-73, 1991.
[Laguna92] Laguna, M. and Glover, F. Integrating Target Analysis and Tabu Search for Improved Scheduling
Systems, Expert Systems Applications , 1992.
[Lambert06] T. Lambert, C. Castro, E. Monfroy y F. Saubion, Solving the Balanced Academic Curriculum Problem
with an Hybridization of Genetic Algorithm and Constraint Propagation, volume 4029 of LNCS, pages 410–419,
Springer, 2006.
[List94] List, G. Heuristic Methods in a Flexible Assembly System, Preprints of the 2nd IFAC/IFIP/IFORS
Workshop on Intelligent Manufacturing Systems, Vienna, pp. 273 -276, 1994.
[Manyá03] F. Manyá y C. Gomes, “Solution Techniques for Constraint Satisfaction Problems”, 2003
[Meseguer89] Meseguer, P. Constraint Satisfaction Problems: An Overview, AICOM 2 (1) pp. 3-17, 1989.
[Minton90] Minton, S. Johnston, M. Philips, A. and Laird, P. Solving Large-Scale Constraint Satisfaction and
Scheduling Problems Using a Heuristic Repair Method, Proceedings of the 8 th National Conference on Artificial
Intelligence, pp. 17-24, 1990.
[Monfroy06] E. Monfroy, C. Castro y B. Crawford, “Using Local Search for Guiding Enumeration in Constraint
Solving”, 2006.
63
[Monfroy07] E. Monfroy, C. Castro y B. Crawford, Adaptive Enumeration Strategies and Metabacktracks for
Constraint Solving, 2007.
[Nakakuki94] Nakakuki, Y. and Sadeh, N. Increasing the Efficiency of Simulated Annealing Search by Learning to
Recognize (Un)Promising Runs, Proceedings of the 12 th National Conference on Artificial Intelligence (AAAI’94),
1994.
[Nakano91] Nakano, R. Conventional Genetic Algorithm for Job Shop Problems, Proceedings of the 4th
International Conference on Genetic Algorithms, pp. 474-479, 1991.
[Nuijten93] Nuijten, W.P.M., Aarts, E. H. L., van Erp Taalman Kip, D. A. A. and van Hee, K. M. Randomized
Constraint Satisfaction for Job Shop Scheduling, Proceedings of the IJCAI’93 Workshop on Production Planning,
Scheduling and Control , pp. 251-262, 1993.
[Pesant96] Gilles Pesant and Michel Gendreau. A view of local search in constraint programming. In Principles and
Practice of Constraint Programming, pages 353-366, 1996.
[Pesant97] Gilles Pesant, Michel Gendreau, and Jean-Marc Rousseau. GENIUS-CP: a generic single-vehicle routing
algorithm. In Principles and Practice of Constraint Programming, pages 420-434, 1997.
[Prestwich00] S. Prestwich. A hybrid search architecture applied to hard random 3-sat and low-autocorrelation
binary sequences. In Proceedings of the Sixth International Conference on Principles and Practice of Constraint
Programming, Lecture Notes in Computer Science, volume 1894, pages 337-352. Springer-Verlag, 2000.
[Prestwich01b] Steve Prestwich. Trading completeness for scalability: Hybrid search for cliques and rulers. pages
159{174, 2001.
[Prestwich01a] Steven Prestwich. Local search and backtracking versus non-systematic backtracking. In Papers from
the AAAI 2001 Fall Symposium on Using Uncertainty Within Computation, pages 109{115, North Falmouth, Cape
Cod, MA, November 2-4 2001. The American Association for Articial Intelligence, The AAAI Press.
[Prosser93] Prosser, P. Scheduling as a Constraint Satisfaction Problem: Theory and Practice, in Scheduling of
Production Processes , J. Dorn and K. A. Froeschl (eds.), Chichester: Ellis Horwood, pp. 22-30, 1993.
[Roy64] Roy, S. and Sussman, B. Les problèmes d’ordonnancement avec contraintes disjonctives , Note DS No. 9
bis, SEMA, Paris, 1964.
64
[Schiex94] Thomas Schiex and Gerard Verfaillie. Nogood Recording fot Static and Dynamic Constraint Satisfaction
Problems. International Journal of Articial Intelligence Tools, 3(2):187{207, 1994.
[Solar06] M. Solar, “Balanceo de Carga Académica en el Diseño de un Currículum basado en Competencias”,
Revista Latinoamericana de Ciencias e Ingeniería, Nº 3 - Vol. II, 2006.
[Sadeh94] Sadeh, N. and Nakakuki, Y. Focused Simulated Annealing Search: An Application to Job Shop
Scheduling, Annals of Operations Research , 1994.
[Slany94] Slany, W. Scheduling as a fuzzy multiple criteria optimization problem, CD-TR 94/62, 1994.
[Solnon02] C. Solnon, “Ants can solve Constraint Satisfaction Problem”, 2002
[Syswerda91] Syswerda, G. Schedule Optimization Using Genetic Algorithms, in Davis (ed.) Handbook of Genetic
Algorithms , New York: Van Nostrand Reinhold, pp. 332-349, 1991.
[Thompson96] Thompson J and Dowsland K (1996) Various of simulated annealing for the examination timetabling
problem. Annals of Operational Research 63, pp 105-128.
[vanLaarhoven92] van Laarhoven, P. L. M., Aarts, and Lenstra, L. K. Job Shop Scheduling by Simulated Annealing,
Operations Research 40, pp. 113-125, 1992.
[Widmer89] Widmer, M. and Hertz, A. A New Heuristic Method for the Flow Shop Sequencing Problem, European
Journal on Operations Research 41, 1989.
[Zweben90] Zweben, M., Deale, M. and Gargan, R. Anytime Rescheduling, Proceedings of the Workshop on
Innovative Approaches to Planning, Scheduling and Control , Katia P. Sycara (ed.), pp. 251-262, 1990.
[Zweben92] Zweben, M., Davis, E., Daun, B. and Deale, M. J. Scheduling and Rescheduling with Iterative Repair,
IEEE Transactions on Systems, Man, and Cybernetics 23 (6) , pp. 1588-1596, 1992.