Empacando

Hace ya casi un siglo que publiqué en Libertonia una serie de artículos sobre algoritmos genéticos. De ellos ya me había olvidado si no fuese porque alguien ha rescatado dichos artículos y ha pedido que le pase los programas que comentaba.

Voy a modo de índice a incluir toda la información aquí. (Para darle una unidad al conjunto).

Buscando soluciones de Empaquetamiento

Algoritmos genéticos: un caso práctico

Estos artículos hacían referencia a un programa llamado empaca.pl que resolvía el problema de la mochila usando algoritmos genéticos. Y, cuyo planteamiento en este caso era el siguiente:

Tenemos una serie de mp3 clasificados en directorios, queremos grabarlos en CDs de forma que el espacio sobrante en cada CD sea mínimo.(Y que los mp3 del mismo disco o artista queden juntos).

Al final, se desarrollaron 3 programas que resolvían dicho problema con enfoques ligeramente distintos:

empaca.pl
Este es el original y el que se comenta en libertonia. El motor del algoritmo genético es mio.
empacinco.pl
Aquí tenemos una reimplementación del algoritmo, en este caso utilizando el módulo AI:GA que da más posibilidades que mis propias rutinas.

Como era un módulo que no estaba incluido en debian, lo he incluido dentro de los scripts para que no sea necesario descargarselo.

empacuatro.pl
Y en esta última variante, hay un pequeño cambio de concepto. Los otros dos sistemas, son de optimización global. Intentan que el sobrante sea mínimo en todos los CDs simultaneamente. Este proceso es lento.

Así que el sistema empleado aquí es el de optimización local. En este caso se intenta optimizar un solo CD para que esté lo más lleno posible. Una vez que esto se consigue se eliminan de la lista los ubicados y se procede con el segundo CD, así hasta completar todos los CDs.

Aunque este sistema debería de dar resultados menos óptimos, lo cierto es que se comporta muy bien. Y es significativamente más rápido.

Al igual que empacinco.pl, usa AI:GA para implementar el algoritmo genético y está incluido dentro del código.

Notas que han surgido a partir del uso de estos programas:

  • Estos programas tienen la documentación en forma de comentario en las primeras lineas de cada documento. Con un less se leera como usarlos y las opciones disponibles (tamaño de los Soportes, y otros parámetros referentes al Algoritmo Genético)
  • Este método de optimización es estocástico (guiado por el azar). Si se ejecutan los script con los mismos datos de entrada no suelen dar nunca las mismas soluciones, así que suelo ejecutar un par de veces el script y me quedo con la opción que más de gusta.
  • Podemos hacer agrupaciones lógicas. Todo lo que queremos que vaya junto lo incluimos en un directorio. Así los «empaca» reservan espacio para que vayan juntos. En el momento de grabar, podemos sacarlos de ese directorio y ordenarlos como queramos.
  • El fichero lista.txt mencionado en la documentación se puede editar para borrar archivos o directorios que no queremos que sean considerados para el reparto.
  • Por supuesto, aunque aquí se ha hablado de mp3, y CD no hay limitaciones de uso en este sentido. Sirve para cualquier soporte y cualquier tipo de ficheros.