Libertonia
Portada · Todo · Software Libre · Desarrolladores · Comunidad · Internet · Tecnología · Meta · Diarios
Algoritmos genéticos: un caso práctico

Programación
Por jamarier
departamento prometo no soltar más rollos en una temporada , Sección Tecnología
Puesto a las Mon Jan 12th, 2004 at 08:17:38 AM CET

Como segunda parte a esta introducción a los algoritmos genéticos, vamos a desarrollar un programa que nos resuelva un problema de empaquetamiento (que como han indicado por ahí se llama «el problema de la mochila»). Para el que no lo conozca, relato brevemente aquél que vamos a resolver:

Tenemos un directorios lleno de ficheros y subdirectorios y queremos grabarlos en CDs de forma que el espacio que sobre en cada CD sea mínimo y que ni los ficheros ni los directorios se tengan que dividir entre varios CD.

Para ello, tenemos ya un programa llamado «empaca.pl» que implementa dicho algoritmo y que podemos encontrar en empaca con la única pega de no tener más instrucciones de uso que las que vienen en las primeras lineas del programa (less empaca.pl).

Ah, no está escrito en arameo antiguo, es Perl. B-)

 


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!

< ¿Está KDE en decadencia? (29 comments) | Una nueva vida con Mandrake (!y sin salir de Linux!) (62 comments) >
Enlaces Relacionados
· empaca
· More on Programación
· Also by jamarier

Encuesta
empaca.pl me parece:
· La mejor utilidad del 2004. Premio nobel 7%
· Una buena utilidad, que usaré regularmente a partir de ahora 7%
· Curioso, he jugado un poco con ella y ya está 7%
· No me es útil 5%
· No funciona 2%
· Dedicate a la magia. 10%
· Un ejemplo de mala programación 0%
· No soy capaz de hacerlo funcionar 5%
· ¿y la rubia? ¿No aparece en esta encuesta? 53%

Votos: 39
Resultados | Otras Encuestas

Menu
· crear cuenta
· FAQ
· búsqueda
· Fuentes de Noticias

Login
Nueva cuenta
Usuario:
Contraseña:

Ver: Modo: Orden:
Algoritmos genéticos: un caso práctico | 14 comentarios (10 temáticos, 4 editoriales, 0 ocultos)
¿Azar en el paso entre generaciones? (4.00 / 2) (#5)
por nya a las Sun Jan 11th, 2004 at 08:51:49 PM CET
(Información Usuario)

El tema me parece muy interesante, aunque mis conocimientos son pocos :). Pero si no voy errado, el hecho de que la reproducción sea asexual hace que la evolución sea más lenta (en número de generaciones, en tiempo de ejecución supongo que dependerá de la implementación) que si fuera sexual. Además, intuyo (aunque no afirmo con rotundidad, si alguien le ve problemas que lo diga) que la reproducción sexual podría minimizar el riesgo de caer en máximos/mínimos locales.

Una duda que tengo (no del empaca.pl, sino de los algoritmos genéticos en general) es si los individuos que pasan a la siguiente generación son los más aptos, elegidos siempre de forma determinista, o por el contrario interviene el azar, aunque la probabilidad de pasar a la siguiente generación venga determinada por la función de evaluación. Lo digo porque en la evolución biológica interviene siempre el azar, y se tiene que considerar el efecto de la deriva genética. Esto hace que en según qué circunstancias (por ejemplo en poblaciones pequeñas) se pueda llegar a la fijación de un alelo que tenía una fitness menor que otro (y esto no es lo mismo que los máximos/mínimos locales) simplemente por azar. Como esto no es deseable si lo que quieres es encontrar una solución suficientemente buena, supongo que la mayoría de bibliotecas para programación genética o programas en sí lo harán de forma totalmente determinista, pero me interesaría saber si existe la posibilidad de incorporar el azar al paso entre generaciones. ¿Alguien sabe si hay alguna herramienta que permita esta opción?



Sobre seleccion de individuos (3.00 / 1) (#6)
por sunblade1000 a las Mon Jan 12th, 2004 at 09:51:07 AM CET
(Información Usuario)

Sobre la seleccion de individuos fundamentalmente existen dos criterios de seleccion de individuos ( aunque despues cada uno se puede inventar los que le de la gana ) y uno de ellos se basa en la funcion objetivo y a partir de la funcion objetivo se obtienen unas tablas de probabilidad y se "tiran los dados" pero este metodo peca de beneficiar demasiado a los individuos mejor dotados cosa que inicialmente no es interesante ya que podemos caer en minimos/maximos locales. El segundo de los metodos consiste en ordenar por el score o funcion de valoracion pero no utilizar el valor de este sino el orden del mismo y se obtienen siempre tablas de probabilidad mas racionales. Tambien hay que indicar que la obtencion de parametros ideales es en si un problema de optimizacion por lo algunos investigadores empezaron a trabajar en nuevos paradigmas que eviten estos problemas de los propios metodos como los Algoritmos de Estimacion de Distribuciones, o Estimation of Distribution Algorithms (EDAs). Para jamarier ( todavia no he completado los apuntes que te envie, ando todavia liado ...) P.D.: En mis clases mande una practica de "diseñar" un algoritmo genetico para entrenar redes neuronales multicapa ... y funciona muy bien incluso a veces con un error menor que el algoritmo ad-hoc

[ Padre ]


A/A sunblade1000 (2.00 / 1) (#9)
por jamarier a las Tue Jan 13th, 2004 at 08:37:39 PM CET
(Información Usuario) http://barbacana.net/blog/

O gran maestro, espero no haber mancillado su nombre y sus enseñanzas al permitirme haber escrito un par de articulillos sobre algoritmos genéticos.

No se preocupe por los artículos, que aun no terminé de leer los otros.

Saludos

Estoy empezando a plantearme el Proyecto de fin de Carrera. Si se te ocurre algo interesante... B-)

-----
- Porque mañana será un gran día.
[ Padre ]



 
Reproduccion sexual (none / 0) (#8)
por Envite a las Tue Jan 13th, 2004 at 04:42:28 PM CET
(Información Usuario)

Esta es una manera de nombrar las cosas procedente de la genetica de carbono. En la de silicio puedes utilizar no solo uno o dos progenitores, sino tambien tres o cuantro o los que quieras para generar cada nuevo individuo. Lo importante es que, ademas, haya mutaciones. Teniendo en cuenta que es posible que tus poblaciones se estanquen en un conjunto de minimos locales, la reproduccion entre ellos puede hacer que consigas el mejor de esos minimos locales, pero que sigas sin saltar del pozo hacia fuera, para buscar el minimo real. Ahi esta la importancia de las mutaciones.
No estoy de acuerdo con lo que dices, pero defenderé con mi vida tu derecho a decirlo.
Voltaire

[ Padre ]


 
Mi (poca) experiencia (3.00 / 1) (#7)
por Walden (waldenmail at gmx dot net) a las Tue Jan 13th, 2004 at 02:44:44 AM CET
(Información Usuario)

Yo apliqué una vez los algoritmos genéticos en el diseño de antenas inteligentes. Una antena inteligente, o array de antenas, es un conjunto de antenas sobre las que se aplica una ganancia en amplitud y fase de manera que se pueda controlar electrónicamente el haz de emisión/recepción de todo el conjunto, permitiendo por ejemplo "apuntar y seguir" a un emisor movil.

Los algoritmos de diseño de estos controles de ganancia, denominados algoritmos de beamforming, aplicados a cada antena son continuo objeto de investigación, y los hay de todos los sabores. Normalmente, se basan en métodos de gradiente para encontrar el mínimo de una función de coste. Para impedir caer en un mínimo local pueden crease perturbaciones en la elección de ganancias y evaluar el error cometido. Los algoritmos genéticos demostraron un buen comportamiento ante errores no lineales (acoples entre antenas, fallos eléctricos, etc), incluso mejor que algoritmos tan conocidos como el LMS. La convergencia es sorprendentemente rápida. Eso sí, el suelo del error tras muchas iteraciones suele ser más alto que el RLS. Parece una buena opción para disparar el sistema, y luego saltar a otro algoritmo más refinado o ad-hoc.



 
Curiosidades de los algoritmos genéticos (3.00 / 1) (#12)
por svampa a las Sun Jan 18th, 2004 at 07:15:37 PM CET
(Información Usuario)

Durante mucho tiempo me encantó hacer simulaciones genéticas en el sentido más clásico: Simular una población de individuos en unos condiciones y llegar al mejor. Quizá algún día busque las pruebas que hice y las ponga en la red.

Más tarde descubrí que era un método para buscar soluciones a problemas diversos, incluso matemáticos.

Si no tenemos ningún técnica matemática para calcular los parámetros óptimos de un proceso, un algoritmo genetico proporciona siempre una solución buena, quizá no la mejor, pero si buena y muy rápidamente. Siempre se pueden hacer varias pruebas partiendo distintos "indivíduos inciales" para intentar evitar caer en un óptimo local.

Entre los más curiosos intentos que encontré hace tiempo están estos:

Un algorítmo genético para optimizar las colas de porcesos en Unix/Linux.

Este me fascinó. Analizar las tareas que realiza un usuario desde que se conecta para intentar carga anticipadamente las librerías que utiliza y disminuir la latencia. Tiene que conjugar dos factores, si la carga demasiado pronto, usa memoria inecesariamente, si tarda demasiado con el usuario arrancará el programa antes de haber cargado nada, y tendrá que esperar como siempre. Como buen algoritmo genético, se adapta a cada individuo.

Si alguien encuentra los enlaces de esto, que me lo diga, los perdía hace mucho. Bueno la verdad es que hace mucho que no trabajo on esto.



 
Explicar la funcion de ajuste o evaluacion (2.00 / 1) (#10)
por tecnocrata a las Tue Jan 13th, 2004 at 09:45:43 PM CET
(Información Usuario)

Aun no me quedo claro lo de la funcion de ajuste, si yo hubiese hecho el algoritmo hubiese utilizado la primera que planteas y que dices que es erronea, de sumar todos los espacios restantes y buscar el minimo de ellos. Pero tu dices que ese espacio sera constante, podrias explicar un poco mas la funcion de ajuste por favor?

Muchas Gracias



Marchando una de aclaraciones (4.00 / 1) (#11)
por jamarier a las Wed Jan 14th, 2004 at 10:35:43 AM CET
(Información Usuario) http://barbacana.net/blog/

Si te pones a pensarlo un poco verás la razón. Piensa en un ejemplo muy reducido. Sean 2 CDs de 700 MiB y ficheros por valor de 1000 MiB. Un posible reparto sería 500 MiB y 500 MiB (a partir de ahora obviaré las unidades), ¿Cuanto sobra? 1400-1000 = 400. Si el reparto hubiera sido 700 + 300 sobraría igualmente 400. Es decir lo que sobra totalmente siempre es igual a el espacio total disponible: 1400 (constante) menos lo que ocupan realmente los ficheros: 1000 constante. Luego este siempre será constante.

La segunda aproximación es sumar todos los espacios sobrantes menos el de un CD. Veamoslo: Imagina que tenemos 10 CD y que se llenan 9 casi totalmente y el décimo está medio lleno. Ya sabemos que el espacio sobrante total es constante. Si eliminamos de un CD de los primeros algo de espacio, ese espacio tendrá que irse a otro CD (porque el total no puede variar). ¿A donde va? pues va al último que es medio lleno. Luego si tenemos un valor constante y queremos minimizar una parte, es necesario que exista otra parte que se maximice (para contrarestar). El último CD es el que se máximiza en espacio sobrante. (Y este criterio si es bueno).

La evaluación de los espacios sobrantes no discrimina entre grados de ocupación de cada CD. Es decir, si tenemos unos CDs llenos con 600+600+300 su función de ajuste sería: 200 (espacio sobrante de todos salvo el último). Igualmente la distribución 700+500+300 tendria función de ajuste 200. yo considero que la segunda opción los CD están «más llenos» (porque hay un CD completamente lleno) por lo que hay que tocar la función de ajuste para que la segunda opción tenga mejor puntuación. Lo cual significa complicar la función de evaluación. Formas de tocar existen muchas, pero yo exprese la suma de cuadrados (era un ejemplo, pero no merece la pena centrarse en ello).

¿De dónde viene entonces la fórmula tan extraña que al final propuse? Un gráfico aquí sería estupendo, pero yo te lo voy a dictar y tu lo haces B-)
  1. Dibuja una linea horizontal y dividelo en 4 segmentos iguales.
  2. Sobre el punto intermedio del segmento levanta una linea vertical de longitud 4 segmentos. Son cuatro segmentos de alto, porque es igual al producto de los segmentos que tienes a la derecha del punto medio por número de segmentos que tienes a la izquierda del mismo punto.
  3. Si te desplazas un segmento a la derecha, podrás levantar otra linea vertical de longitud 3 (producto de los segmentos de la derecha del punto con los de la izquierda.
  4. Por no alargar el proceso diré que hay 5 puntos y que los valores de los productos son: 0,3,4,3,0. Si en vez de dividir en 4 segmentos iguales hubiera sido en 5 segmento iguales, las alturas correspondientes serían: 0,4,6,6,4,0
  5. ¿qué forma nos da estas curvas? Son todas parábolas. Donde los mínimos aparecen cuando uno de los dos factores es mínimo y el máximo se dá cuando los dos factores son iguales (en el punto medio del segmento horizontal).
  6. Si repites toda la gráfica pero sumando 1 a cada factor, tendrás una gráfica distinta pero seguirá siendo una parabola que cumple con nuestro objetivo.


Fíjate que la longitud del segmento es constante (igual que el espacio sobrante total de los CDs) y que la suma de los factores es igual a la longitud total de los segmentos (salvo cuando le sumamos uno a cada factor, en cuyo caso la suma total de los factores es: long segmento + 2)

Hasta ahora hemos hablado de solo 2 factores (dos CDs) ¿que ocurre si tenemos 3? pues en vez de una parabola tendríamos un paraboloide de revolución. Cuyo comportamiento es similar. ¿Si tenemos 4? obtendriamos algo no representable en gráfica pero su comportamiento seguiría siendo igual

Esa es la justificación de la función de ajuste escogido.

-----
- Porque mañana será un gran día.
[ Padre ]



ACTUALIZACION: CAMBIO DE POSICIÓN DE EMPACA (none / 0) (#14)
por jamarier a las Thu Jun 8th, 2006 at 12:51:02 AM CET
(Información Usuario) http://barbacana.net/blog/

Lamentablemente una reorganización del servidor ha cambiado de sitio los ficheros.

Y no tengo capacidad para corregir el enlace en el cuerpo de la noticia. Ni siquiera de hacer un comentario independiente.

Este es el enlace actual para obtener una copia de empaca o una de sus variantes.

-----
Opinión expresada por alguien que puede que no sea yo.
[ Padre ]



 
Matemáticas de segundo de bachillerato (2.00 / 1) (#13)
por Corellian a las Tue Jan 20th, 2004 at 12:02:04 AM CET
(Información Usuario)

Esto me recuerda a los problemas que hace unos días hacíamos en Matemáticas, en Segundo de Bachillerato: Los famosos "problemas de Optimización". Claro que, por lo que aquí se refiere, con un grado de complicación más, añadido ;-)

Saludos.



 
Algoritmos genéticos: un caso práctico | 14 comentarios (10 temáticos, 4 editoriales, 0 ocultos)
Ver: Modo: Orden:

ecol Logo Powered by Scoop
Todas las Marcas Registradas y copyrights de esta página son propiedad de sus respectivos dueños.
Los comentarios son propiedad del que los escribe.
Los iconos de las noticias y el logotipo son propiedad de Javier Malonda.
El Resto © 2002 Escomposlinux.org y aledaños.

Puedes sindicar los contenidos de libertonia en formato RSS 1.0 y RDF 0.9. También se puede sindicar la cola de envíos pendientes de moderación.

El proyecto escomposlinux.org está dedicado a la memoria de tas

crear cuenta | faq | búsqueda