Práctica 1 de Inteligencia Artificial Planificación de horarios %! Target: html %! Options: --toc %! Style: basic.css - Daniel Clemente Laboreo, 45786256-H - Felix Marquardt, 1094094148 - Noviembre 2005. ------------------------- %%toc ------------------------- =Introducción= El objetivo de esta práctica es implementar un programa en JAVA que simula la asignación del uso de recursos de un supercomputador. El supercomputador tiene 168 horas para ejecutar varios trabajos. Un trabajo tiene un tamaño entre una y cinco horas y además una tolerancia con que la hora de inicio real puede apartarse de la hora de inicio. El rango para cada trabajo puede ser diferente y no tiene por que ser simétrico, por eso el trabajo puede empezar en cualquier hora entre la tolerancia. Además los trabajos tienen que terminar en una hora válida. El programa tiene que intentar asignar el máximo número de trabajos posible dentro del horario. Para esto se usan los algoritmos Hill-Climbing y Simulated Annealing, que ya están implementados en el paquete AIMA. El ejercicio es crear formas de representación del estado, operadores junto con sus restricciones, la manera en que se generarán sucesores y las funciones heurísticas. Para comparar los posibles métodos hay varios experimentos, que combinan los diferentes operadores, estados inciales, funciones heurísticas y parámetros de cada algoritmo. Cada parte se explica con más detalles en las siguientes secciones. =Implementación= ==Representación== ===Trabajo=== Cada trabajo guarda 4 datos: - hora de inicio propuesta - tamaño del trabajo - tolerancia a desplazarse hacia la izquierda - tolerancia a desplazarse hacia la derecha - Además, hemos ampliado esta clase con dos datos extra: - identificador de trabajo: un número positivo que permite diferenciar a cada trabajo (ya que dos trabajos distintos pueden tener los 4 datos iguales). - hora real a la que hemos decidido que empiece el trabajo. Siempre está dentro de la tolerancia permitida. - ===Horario=== En cada horario grabamos la lista de trabajos que contiene. Es un //ArrayList// de objetos de tipo Trabajo, y puede tener de 0 a 168 elementos. Para simplificar las búsquedas, mantenemos el array ordenado por hora de inicio real. Además, para que sea más eficiente comprobar si un trabajo está o no en el horario, mantenemos un array de horas libres, que contiene, para cada hora (de 0 a 167): - el identificador del trabajo que la ocupa, si es que hay alguno - -1 si esa hora está libre - Todos los horarios son válidos y contienen trabajos que no se solapan. ===Lista de trabajos disponibles=== En la clase ``HorarioTrabajo`` (programa principal) guardamos la lista de todos los trabajos a poner, que es la entrada del programa. Usamos un //ArrayList// llamado ``todosTrabajos``, que contendrá probablemente más de 168. Nosotros llenamos esta lista con trabajos aleatorios mediante la función ``llenarLista()``, que escoge datos al azar y les asigna un identificador distinto a cada uno. Para saber si un trabajo ya está puesto o no dentro de un horario determinado, la información la guardamos dentro de cada horario (pero no en esta clase). Por tanto, esta lista no se modifica durante la ejecución del algoritmo. ==Estado inicial== Hemos usado básicamente, dos tipos de estado inicial: + Horario vacío + Horario lleno con trabajos al azar + Un horario vacío da más libertad para poner buenos trabajos, y es apropiado si los operadores usados no permiten corregir los trabajos ya puestos (por ejemplo, si sólo podemos poner y quitar trabajos). Lo malo es que tarda más en llenarse. Un horario ya lleno está más cerca de la solución, pero puede pasar que para llegar al óptimo haya que deshacerlo un poco (quitando trabajos), y algunos algoritmos se negarán a hacer esto porque les llevaría a situaciones peores (ej. Hill Climbing). Esto se evita usando otros operadores más sofisticados. Para llenar el horario, lo que hacemos es intentar colocar cada trabajo de la lista de trabajos disponibles. Si alguno no se puede colocar a la hora propuesta, lo dejamos y pasamos al siguiente. Así queda un horario bastante lleno (ej: 51 trabajos cuando hay 200 disponibles). ==Estado final== En este problema no queda claro cuál es el estado final al que se quiere llegar. Al principio consideramos que una solución era un //horario con algún trabajo//, pero eso haría que casi cualquier horario fuera aceptado. Al final hemos usado como definición de estado final el //horario que tiene 168 trabajos//, ya que si conseguimos eso, no hay ningún otro horario mejor. Es muy poco probable que lleguemos a esta solución, pero al menos el algoritmo intentará acercarse. ==Operadores== Para moverse de un estado a otro hace falta aplicar un operador. Pero como un operador no se puede usar siempre en cualquier situación, junto con cada uno decidimos sus restricciones especiales. ===poner=== El operador ``poner`` añade un trabajo nuevo al horario, en una posición fija. Sólo se puede poner un trabajo nuevo si su sitio está dentro del horario y libre. Por eso se tiene que comprobar que la hora de inicio es mayor que 0 y la hora de fin menor o igual que 168, que el desplazamiento (la diferencia entre la hora de inicio y la hora de inicio real) está permitido, que el trabajo no está ya en el horario, y que las horas a ocupar están libres. Si todo esto es cierto, el trabajo nuevo puede ponerse en el horario. Se pone el trabajo en el horario en la posición correcta (manteniendo la lista ordenada según la hora de inicio real), y se cambian las horas libres, que pasan a estar ocupadas. ===quitar=== El operador ``quitar`` quita un trabajo puesto del horario. Pero antes se tiene que comprobar que el trabajo está puesto en el trabajo. Después de haber quitado el trabajo se tienen que marcar las horas ocupadas como horas libres. ===ajustar=== El operador ``ajustar`` cambia la posición de un trabajo puesto en el horario. Por eso las restricciones son casi las mismas que las de poner. El trabajo tiene que estar puesto y la posición nueva tiene que está dentro del horario y el desplazamiento tiene que estar permitido. Además las horas antes o después el trabajo puesto tienen que estar libres para ajustar. Después del cambio se cambia la información en el trabajo y las horas en la lista de horas libres. ===intercambiar=== El operador ``intercambiar`` es una combinación de los operadores ``quitar`` y ``poner``. El primero quita el trabajo del horario, y el segundo pone otro posiblemente distinto, quizás en otro sitio. Las acciones y las restricciones de este operador son las mismas que en los operadores ``poner`` y ``quitar``, por supuesto. El operador es sólo para simplificar el proceso: se puede mejorar el horario con sólo un sucesor en vez de dos (uno para ``quitar`` y otro para ``poner``). ==Heurísticas== En el programa hay funciones heurísticas diferentes para comparar los sucesores. El objetivo es optimizar la cantidad de trabajos en el horario de 168 horas. Para este objetivo hay tres parámetros en el horario que influyen en la calidad: El número de trabajos, los tamaños de los trabajos y la posición en el horario. El número de trabajos es lo más importante, por eso la heurística más fácil es la uno: 1. ``f(n) = - n`` (``n`` = el número de trabajos) Normalmente es un valor bajo mejor que un valor alto. Por eso la función heurística es ``-n``. Los tamaños de los trabajos son importantes, también. Una posibilidad para compararlos es usando el número de horas libres. Un horario de ``x`` trabajos con ``y`` horas libres es mejor que un horario con ``x`` trabajos y ``z