Libertonia
Portada · Todo · Software Libre · Desarrolladores · Comunidad · Internet · Tecnología · Meta · Diarios
Ver: Modo: Orden:
Algoritmos genéticos: un caso práctico | 14 comentarios (10 temáticos, 4 editoriales, 0 ocultos)
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 ]



 

Algoritmos genéticos: un caso práctico | 14 comentarios (10 temáticos, 4 editoriales, 0 ocultos)
Ver: Modo: Orden:
Menu
· crear cuenta
· FAQ
· búsqueda
· Fuentes de Noticias

Login
Nueva cuenta
Usuario:
Contraseña:

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