Noviembre 2005.
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.
Cada trabajo guarda 4 datos:
Además, hemos ampliado esta clase con dos datos extra:
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):
Todos los horarios son válidos y contienen trabajos que no se solapan.
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.
Hemos usado básicamente, dos tipos de estado inicial:
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).
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.
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.
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.
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.
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.
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).
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<y horas libres porque en
el primer horario se pueden poner más trabajos nuevos.
Pero no sólo el número de horas libres influye en la calidad del horario: las posiciones de los trabajos puestos, también. Un espacio grande es mejor que muchos descansos cortos. La longitud media de los períodos de horas libres es una posibilidad para comprobar esto, pero hay otras mejores. La media no es unívoca, hay situaciones con la misma media pero con diferentes longitudes. Sin embargo la media es muy fácil y rápida de calcular. La función heurística número dos es una combinación de las tres cosas:
2. f(n,s,hl) = - ( 168^2 * n + 168 * s + hl )
(s = longitud media de los períodos de horas libres,
hl = número de horas libres)
El factor 168 es el resultado de la dependencia de las variables. El valor de n es entre 0 y 168,
y el de s y hl también.
Un horario con sólo un trabajo y 167 horas libres es mejor que un horario sin trabajos.
Por eso la importancia de un trabajo tiene que ser más grande que la de un horario libre.
Paralelo a eso, la importancia de la longitud de los períodos tiene que ser más grande que
el número de horas libres.
Pero hay una dependencia muy grande entre la longitud media de los períodos de horas libres y el número de horas libres: una longitud media más grande implica más horas libres. Por eso el número de horas libres es sólo una información más concreta; la longitud es sólo otra versión para representar el número de horas libres. Para simplificar la función heurística número dos hay una función tres:
3. f(n,s) = - ( 168 * n + hl )
Y una función cuatro:
4. f(n,hl) = - ( 168 * n + s )
El factor 168 es el resultado de la misma dependencia de los variables.
poner, etc.)
| est. ini. | ops. | trab. disp. | algo. | heu. | suc. p. | suc. máx. | suc. f. | trab. | nodos | tmp. | comentarios |
|---|---|---|---|---|---|---|---|---|---|---|---|
| vacío | {pq} | 200 | sa | 2 | 1163 | 1163 | 72 | 72 | 73 | 1,4s | sólo se aplica {p}, núm. trabajos creciente siempre |
| vacío | {pqai} | 200 | sa | 2 | 1163 | ~2500 | ~250 | 82 | 308 | 25s | trabajos creciente poco a poco; se aplica sólo {pia} pero 'a' demasiado (le lleva al mismo estado} |
| vacío | {pqai} | 200 | h | 2 | 1163 | 5148 | 192 | 89 | 90 | 10,5s | sólo se aplica {p} |
| vacío | {pq} | 200 | h | 2 | 1163 | 1163 | 89 | 89 | 90 | 2s | |
| lleno | {pq} | 200 | sa | 2 | 96 | 96 | 70 | 70 | 20 | 0,8s | empieza con 51 trabajos, trabajos siempre creciente |
| lleno | {pq} | 200 | h | 2 | 96 | 96 | 70 | 70 | 20 | 0,7s | trabajos siempre creciente |
| lleno | {pqai} | 200 | h | 2 | 299 | 309 | 229 | 79 | 44 | 4s | no se aplica {q}; cantidad de sucesores es siempre casi lo mismo |
| lleno | {pqai} | 200 | sa | 2 | 299 | 939 | 217 | 84 | 332 | 29s | no se aplica {q}, muchas veces no hay un cambio en el número de trabajos |
| lleno | {pqa} | 200 | sa | 2 | 216 | 216 | 159 | 72 | 277 | 2s | no se aplica {q}, muchas veces se aplica {a} y no hay un cambio en el número de trabajo |
| lleno | {pa} | 200 | sa | 2 | 165 | 165 | 81 | 74 | 495 | 2,5s | |
| lleno | {pai} | 200 | sa | 2 | 248 | 640 | 115 | 85 | 458 | 39s | |
| lleno | {pqa} | 200 | h | 2 | 216 | 216 | 157 | 71 | 23 | 1s | |
| lleno | {pa} | 200 | h | 2 | 165 | 165 | 86 | 71 | 23 | 1s | |
| lleno | {pai} | 200 | h | 2 | 248 | 248 | 150 | 79 | 44 | 4s | |
| lleno | {pqai} | 200 | h | 1 | 299 | 299 | 202 | 71 | 21 | 2,3s | sólo se aplica {p}, trabajos siempre creciente |
| lleno | {pqai} | 200 | h | 3 | 299 | 320 | 245 | 77 | 38 | 4s | trabajos siempre creciente, no se aplica {q} |
| lleno | {pqai} | 200 | h | 4 | 299 | 299 | 202 | 71 | 21 | 2,3s | sólo se aplica {p}, trabajos siempre creciente |
| lleno | {pqai} | 200 | sa | 1 | 299 | 1218 | 215 | 78 | 496 | 37s | se aplica {q} alguna vez |
| lleno | {pqai} | 200 | sa | 3 | 299 | 740 | 249 | 81 | 366 | 32s | no se aplica {q} |
| lleno | {pqai} | 200 | sa | 4 | 299 | 648 | 217 | 80 | 369 | 33s | no se aplica {q} |
| lleno | {pqai} | 100 | sa | 2 | 220 | 447 | 158 | 58 | 264 | 7s | no se aplica {q}, empieza con 41 trabajos |
| lleno | {pqai} | 500 | sa | 2 | 418 | 3492 | 440 | 111 | 281 | 1,3m | no se aplica {q}, empieza con 65 trabajos |
| lleno | {pqai} | 1000 | sa | 2 | 634 | 8179 | 969 | 120 | 277 | 4m | no se aplica {q}, empieza con 70 trabajos |
| lleno | {pqai} | 100 | h | 2 | 220 | 237 | 159 | 56 | 27 | 1,3s | no se aplica {q}, empieza con 41 trabajos |
| lleno | {pqai} | 500 | h | 2 | 418 | 991 | 299 | 124 | 92 | 34s | no se aplica {q}, empieza con 65 trabajos |
| lleno | {pqai} | 1000 | h | 2 | 634 | 1900 | 386 | 152 | 117 | 2m | no se aplica {q}, se empieza con 70 trabajos |
| lleno | {pai} | 200 | sa | 2 | 299 | 1030 | 352 | 88 | 2555 | 4m | (10000, 100, 20, 0.005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 1064 | 197 | 86 | 583 | 55s | (2000, 100, 20, 0.005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 1120 | 215 | 82 | 336 | 28s | (1000, 100, 20, 0.005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 1024 | 910 | 57 | 51 | 4,3s | (100, 100, 20, 0.005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 973 | 206 | 83 | 562 | 50s | (2000, 50, 20, 0.005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 1447 | 196 | 87 | 593 | 53s | (2000, 200, 20, 0.005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 994 | 206 | 87 | 552 | 49s | (2000, 300, 20, 0.005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 1360 | 209 | 86 | 556 | 52s | (2000, 100, 10, 0.005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 1013 | 209 | 85 | 613 | 55s | (2000, 100, 50, 0.005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 1296 | 196 | 85 | 665 | 1m | (2000, 100, 500, 0.005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 612 | 204 | 86 | 677 | 1m | (2000, 100, 20, 0.00005) |
| lleno | {pai} | 200 | sa | 2 | 299 | 769 | 206 | 86 | 526 | 47s | (2000, 100, 20, 0.05) |
| lleno | {pai} | 200 | sa | 2 | 299 | 968 | 198 | 85 | 432 | 38s | (2000, 100, 20, 0.5) |
| lleno | {pai} | 200 | sa | 2 | 299 | 1287 | 1083 | 65 | 84 | 7s | (2000, 100, 20, 5), el número de sucesores creciente |
| lleno | {pai} | 200 | sa | 2 | 299 | 776 | 569 | 59 | 55 | 5s | (2000, 100, 20, 50) |
En general, empezar con un horario ya lleno (con trabajos al azar) funciona mejor que
empezar con uno vacío, porque ya tenemos mucha parte del trabajo hecha.
Si los operadores permiten corregir un horario (ajustar e intercambiar), entonces quizás
se puede encontrar una solución mejor.
En cambio, sólo con poner y quitar no se puede mejorar mucho un horario aleatorio;
hace falta un horario vacío para tener más libertad al colocar los trabajos en el sitio más apropiado.
Un horario aleatorio tiene tendencia a no poderse deshacer fácilmente, ya que el operador quitar,
necesario para hacer rectificaciones, siempre lleva a un estado mucho peor.
Considerando n como el número de trabajos ya puestos, y N como el número de trabajos disponibles por poner, cada operador genera el siguiente número de sucesores:
poner (p): N*11
quitar (q): n
ajustar (a): n*11
intercambiar (i): n*N
Esto es porque, por ejemplo para poner, hay que decidir dos cosas:
qué trabajo coger de la lista de trabajos disponibles,
y con qué desplazamiento ponerlo (de -5 a +5).
intercambiar necesita saber el trabajo antiguo (uno de entre los n), y el sustituto (N posibilidades).
En realidad, no todos estos sucesores son válidos, ya que no siempre son aplicables.
Se usan funciones como sePuedePoner() para saber cuándo lo son.
De aquí se deduce que intercambiar es el operador más costoso,
seguido por poner, y luego por ajustar y quitar.
Pero en nuestras pruebas hemos visto que quitar (el menos costoso) casi no se aplica,
por varios motivos:
quitar, se puede usar intercambiar,
que también quita el trabajo pero nos deja
en un estado que no es peor (ya que añade otro trabajo).
Hemos probado los soguientes conjuntos de los operadores:
{poner, quitar}
{poner, quitar, ajustar, intercambiar}
{poner, quitar, ajustar}
{poner, ajustar}
{poner, ajustar, intercambiar}
El último conjunto es el mejor porque con los operadores ajustar e intercambiar se puede mejorar
el horario lleno. El operador quitar se aplica casi nunca, por eso el conjunto con todos los
operadores es peor que el último. Con el segundo conjunto el algoritmo hace más sucesores pero no
usa los sucesores adicionales.
El cuarto conjunto no es tan bueno como el último porque falta la posibilidad de coregir
trabajos ya puestos en el horario.
El tercer conjunto tiene el mismo problema.
Por cierto tiene el operador quitar pero se aplica casi nunca.
El primer conjunto es el peor.
En realidad es como si hubiera sólo el operador poner.
Pero con un horario vacío el conjunto es bastante bueno en combinación con una función heurística buena.
En esto caso el algoritmo puede elegir los trabajos mejores de la lista de trabajos disponibles
y no necesita corregir el horario.
Los operadores ajustar e intercambiar importan más con un horario lleno que con uno vacío.
Todas las funciones heurísticas dan prioridad al número de trabajos, ya que es lo que hay que maximizar en este problema.
Las heurísticas (ya explicadas en la parte de representación) son:
f(n) = - n
f(n,s,hl) = - ( 168^2 * n + 168 * s + hl )
f(n,s) = - ( 168 * n + hl )
f(n,hl) = - ( 168 * n + s )
Donde n es el número de trabajos,
s la longitud media de los períodos de horas libres,
y hl el número de horas libres (información que complementa a s).
En todas interviene n como factor principal.
La heurística 1 es la más sencilla pero la que peor funciona,
ya que hace que sólo se elijan horarios que tienen más trabajos que el actual;
por tanto, sólo se aplica el operador poner
(porque es el único que puede añadir un trabajo a un horario).
El resultado es bastante malo, sobre todo en Hill Climbing, que no permite empeorar.
Se comprueba cómo se aplica continuamente poner con cada uno de los trabajos disponibles
(sin fijarse en otros criterios), y no se aplica ningún otro operador.
Hace algo parecido a nuestra función horarioAleatorio(),
que intenta poner todos los trabajos,
sólo que esta vez se prueba con todos los posibles valores de desplazamiento.
La función 2 es la más sofisticada, y la que da mejores resultados (ver tabla). También es la que tiene en cuenta más magnitudes. Las heurísticas 3 y 4 no son tan buenas como la 2, ya que sólo incorporan uno de los valores mientras que la 2 tiene los dos.
Elegir bien la heurística es importante en todos los casos.
Incluso si sólo estamos trabajando con un operador, poner,
hay diferencia entre poner un trabajo en cualquier sitio libre
y ponerlo en el sitio más apropiado, donde aproveche bien el espacio.
La heurística también importa en los dos algoritmos.
El resultado de los experimentos es muy claro: Más trabajos disponibles es mejor para la solución, pero hacen que cueste más de obtener. Esto pasa siempre, tanto con un estado inicial de un horario vacío o lleno y con cada función heurística y cada algoritmo. Naturalmente con más trabajos disponibles el algoritmo tiene más posibilidades para elegir el trabajo más apropriado.
Hay cuatro parámetros para ajustar el algoritmo Simulated Annealing:
steps, stiter, k y lambda.
Sus valores por defecto son 10000, 100, 20, 0.005 respectivamente.
Los más importantes son el primero, el tercero y el último.
El primer parámetro sirve para poner un límite a la ejecución, y para que sea útil tiene que depender del número de trabajos disponibles. Con muy pocos trabajos, el límite puede ser bajo y por eso la ejecución será muy rápida. Con muchos trabajos, hay que aumentar el límite para que se encuentre una solución buena.
El tercero (k) hace que se generen muchos sucesores cuando éste se aumenta,
y por eso la ejecución es más lenta, y entonces el límite establecido
puede hacer que se pare antes de encontrar una solución buena.
Hemos dejado el valor por defecto porque ya da buenos resultados.
La lambda se comporta de forma inversa:
al aumentarla excesivamente, el programa acaba muy pronto,
pero con un resultado bastante malo.
En cambio, cuando la reducimos mucho (casi 0),
el programa encuentra una solución buena, pero tarda demasiado.
Un valor intermedio, como 0.005, también consigue la solución buena, pero más rápido.
El segundo parámetro (stiter, número de iteraciones por paso de temperatura) no influye mucho,
pero con valores pequeños no da buenos resultados.
El algoritmo Simulated Annealing es mejor con pocos trabajos disponibles. La ejecución es larga, pero el número de trabajos puestos en el horario es más alto. Con más trabajos disponibles el algoritmo Simulated Annealing es peor que el otro pero depende mucho de los parámetros del algoritmo: con un límite bajo de pasos en general la solución es peor, porque se para demasiado pronto (cuando supera el límite de pasos). Con límites más altos la solución es mejor que Hill-Climbing, pero el número de sucesores y el número de nodos expandidos es grande.
Además, el tiempo de ejecución depende mucho del número de trabajos disponibles, con una relación exponencial. Cuando hay muchos, a Simulated Annealing cada vez le cuesta más encontrar una solución mejor que la que ya tiene, y al final sólo se mueve entre horarios que tienen el mismo número de trabajos (a veces aumenta, pero al final este crecimiento es muy lento).
Por eso los resultados de nuestros experimentos con una cantidad de trabajos disponibles de 500 ó 1000 no son muy buenos, porque los límites de Simulated Annealing son demasiado pequeños. Pero para demostrar las diferencias entre las soluciones con pocos trabajos disponibles y muchos, el resultado es suficiente.
Hemos visto que:
{poner, ajustar, intercambiar}.
quitar no hace falta, ya que se puede hacer con intercambiar.