Como comenté en el otro artículo, para usar un algoritmo genético
hacen falta 3 elementos, La descripción del individuo, la función de
evaluación (llamada función de ajuste) y los mecanismos de
reproducción. Voy a describir a continuación los tres aspectos. Dado
que el espacio es reducido, voy a hacer una descripción general y en
función de los comentarios me centro en aquellas partes que no hayan
quedado muy claras.
Descripción del individuo.
Supongamos que tenemos 10 ficheros a repartir en 3 CDs. Necesitamos
indicar de una forma clara como se reparten (o podrían) esos ficheros
en los CDs. Un sistema sería poner una lista de ceros y unos de la
siguiente forma: como hay 10 ficheros ponemos 3 ristras (número de CDs)
de 10 dígitos cada una (número de ficheros/directorios) donde un 0
indica no inclusión y un 1 indica inclusión. ejemplo:
1100000000 0011100000 0000011111
Que significa que los dos primeros archivos entran en el primer CD,
los tres siguientes en el segundo y los restantes en el tercero. Este
conjunto de datos que definen el estado completo del problema lo
llamaremos cromosoma o individuo según nos interese en cada
momento. Fijaos que no cualquier ristra de 30 bits representa a un
individuo viable (pueden darse casos en los que un archivo esté en
varios CD o en ninguno). Por lo que habría que implementar sistemas de
control que nos asegurara cuando es realmente una solución y cuando
no. Por eso no hemos usado este sistema de codificación.
El sistema que hemos empleado en empaca.pl es
definir cada individuo como una única ristra de números (tantos
como ficheros a repartir) y cuyo valor representa el CD donde se
incluye el fichero. La misma solución anterior se representaría como:
0011122222
La ventaja es obvia, siempre que la longitud del cromosoma sea
constante y que las cifras en cada posición sea inferior al
número de soportes de grabación, este representará un posible
reparto. Por cierto cada trozo del cromosoma con significado se le
llama gen (en este caso cada cifra es un gen).
Función de ajuste
La segunda parte interesante es la de encontrar una expresión
matemática que puntúe a cada individuo de forma que nuestro ideal sea
un máximo o un mínimo.
Un primer intento sería sumar lo que sobra de cada CD e intentar
que esta función sea un mínimo. OJO, esto es erróneo porque el espacio
sobrante siempre será constante. Una segunda aproximación sería que la
suma de todos los espacios sobrantes de los CDs salvo un CD sea
mínimo. Esta función si sería válida (dejo como ejercicio la
demostración de esto último, o si no lo añado como comentario más
tarde); pero tiene un problema: Caso de 3 CDs, dos de ellos casi
llenos. Si en esos 2 CDs casi llenos sobran 4 megas, la función de
ajuste valorará igual como se repartan estos megas sobrantes: 2+2 o
0+4 o 1+3. Desde mi punto de vista lo ideal sería 0+4, es decir un CD
lleno y el otro menos lleno. Osea que sería necesario una función cuya
suma de espacios sobrantes menos 1 CD sea mínima pero cuya suma de
cuadrados de los mismos espacios fuera máximo. Vamos un lío.
Al final la función escogida a minimizar es la siguiente: es un
producto donde cada factor depende del espacio sobrante (tanto por
uno) en cada CD según la siguiente relación.
CD_n sobrante ->
factor_n=(1+(EspacioTot-EspacioUsad_n)/EspacioTot)
El uno está incluido para evitar la siguiente situación: un CD
completamente lleno tendría un factor de valor 0. Sería óptimo. Al
multiplicar dicho factor por los factores de los otros soportes, la
función de evaluación sería 0, mínimo y por tanto la solución óptima
independientemente de los estados de los otros soportes. El 1 no
altera el comportamiento del factor pero elimina el problema del 0
(siendo ahora el óptimo el valor de la función de evaluación=1)
El que sobre espacio en un CD es una situación poco deseable (por
eso la evaluación de ese espacio no es óptima y el factor de ajuste es
superior a 1), pero que exista un desbordamiento en un CDs se
convierte en una situación intolerable. Modificamos el factor de un CD
desbordado para que el valor de función global sea superior en el caso
de desbordamiento que en el caso de espacios no aprovechados. La
expresión del factor del soporte desbordado es:
CD_n desbordado ->
factor_n=(2+(EspacioUsad_n-EspacioTot)/EspacioTot)
Fijaos que ante dos situaciones de desbordamiento, el valor factor
de la función de ajuste menor se da en el que presente un desbordamiento menor, que es lo deseable.
Mecanismo de reproducción
He de confesar que en este apartado he sido un poco perro. La
definición purista de Algoritmo genético implica que los cromosomas de
2 padres se mezclen para obtener una descendencia. Podría haber
escogido dos individuos y copiar un trozo de su cromosoma y mezclarlo
con el trozo del cromosoma de otro y obtener un descendiente de
estos. Luego aportaríamos un poco de azar mutando el cromosoma de
algún descendiente (para evitar el empobrecimiento genético de la
población) y por último eliminaríamos a los menos aptos de la
especie.
En empaca.pl hemos simplificado el proceso
reproductivo. Hacemos reproducción asexuada. Los más adaptados de la
generación anterior tienen 2 descendientes uno idéntico a si mismo y
el otro un hijo mutado (alteramos el valor de algún gen del cromosoma
del padre). El resto de la población tiene un solo descendiente que es
un hijo mutado. Como la población total sufre un crecimiento igual al
número de los considerados más aptos, hacemos una criba de los peor
clasificados según la función de ajuste. Y así mantenemos la población constante
Y eso es todo
Para facilitar la posibilidad de jugar con el
software de empaquetamiento, se han habilitado una serie de opciones
en la línea de comandos que permiten variar las variables del
algoritmo tales como la población, el número de generaciones, grado de
la mutación y otros.
¡Que lo disfrutéis!
