El problema de la mochila (II)

Aplicamos un algoritmo genético para introducir en la mochila el mayor número de objetos que maximicen el beneficio pero sin superar la restricción de peso de la misma. En la tabla se muestra el problema a resolver: 4 objetos con diferentes utilidades y pesos.

La función objetivo Z no puede contener los 4 objetos pues rebasaría la restricción del peso que no puede superar el valor 15.

$$Z=4x_1+5x_2+6x_3+3x_4$$

$$P=7x_1+6x_2+8x_3+2x_4 \leq 15$$

Un cromosoma está formado por genes que son variables binarias. Cada cromosoma estará formado por una cadena de 4 bits. Si la suma de pesos de un cromosoma rebasa el peso máximo permitido 15, no se considera.

En la Tabla se muestran 4 cromosomas aleatorios de los cuales se tienen que obtener dos padres. La penúltima columna de probabilidad se obtiene dividiendo cada peso entre el total, y en la última columna la probabilidad acumulada.

• Selección:
Para obtener un padre debemos seleccionar uno de los 4 cromosomas. Se genera un número aleatorio (0.477) que supera a la probabilidad acumulada 0.2973; así el Padre 1 será el cromosoma 2: 1 0 1 0.
Se genera otro número aleatorio (0.934) que supera a la probabilidad acumulada 0.7027; así el Padre 2 será el cromosoma 4: 0 1 1 0.
.
• Cruzamiento:
Se asigna una probabilidad de cruzamiento entre dos genes de 0.98.  Se genera un número aleatorio 0.735<0.98 y entonces hay cruzamiento. Como hay 4 genes hay tres puntos de corte entre genes. Se genera otro número aleatorio (0.492). Como 1/3<0.492<2/3, el punto de corte está entre el gen 2 y el gen 3 (línea discontinua). Entonces se intercambian los genes 3 y 4.

• Mutación:
Se genera un número aleatorio para cada gen para ver si hay o no mutación. La habrá si es menor que el valor asignado 0.1. Los genes en rojo se han cambiado. Como el segundo cromosoma rebasa la restricción se elimina. Por tanto, hasta el momento, sólo hemos obtenido un hijo.

Repetimos el proceso, manteniendo la tabla inicial, para obtener nuevos hijos.

• Selección:
Para obtener un padre debemos seleccionar uno de los 4 cromosomas. Se genera un número aleatorio (0.802) que supera a la probabilidad acumulada 0.7027; así el Padre 1 será el cromosoma 4: 0 1 1 0.
Se genera otro número aleatorio (0.266) que no supera a la probabilidad acumulada 0.2973; así el Padre 2 será el cromosoma 1: 0 1 1 0.
.
• Cruzamiento:
Se asigna una probabilidad de cruzamiento entre dos genes de 0.98. Se genera un número aleatorio 0.174<0.98 y entonces hay cruzamiento. Como hay 4 genes hay tres puntos de corte entre genes. Se genera otro número aleatorio (0.740). Como 2/3<0.7401, el punto de corte está entre el gen 3 y el gen 4 (línea discontinua). Entonces se intercambia el gen 4.

• Mutación:
Se genera un número aleatorio para cada gen para ver si hay o no mutación. La habrá si es menor que el valor asignado 0.1. Los genes en rojo se han cambiado. Como el primer cromosoma rebasa la restricción se elimina. Por tanto sólo hemos obtenido un segundo hijo.

Volvemos a repetir el proceso para conseguir los dos hijos que faltan.

• Selección:
Para obtener un padre debemos seleccionar uno de los 4 cromosomas. Se genera un número aleatorio (0.658) que supera a la probabilidad acumulada 0.5676; así el Padre 1 será el cromosoma 3: 0 1 0 0.
Se genera otro número aleatorio (0.258) que no supera a la probabilidad acumulada 0.2973; así el Padre 2 será el cromosoma 1: 0 1 1 0.
.
• Cruzamiento:
Se asigna una probabilidad de cruzamiento entre dos genes de 0.98. Se genera un número aleatorio 0.989>0.98 y entonces no hay cruzamiento. 

• Mutación:
Se genera un número aleatorio para cada gen para ver si hay o no mutación. La habrá si es menor que el valor asignado 0.1. El gen en rojo se ha cambiado. Como los dos cromosoma cumplen la restricción se aceptan. Por tanto ya tenemos los 4 hijos.

Termina la primera iteración y vamos a iniciar la segunda iteración con estos 4 hijos. Para ello tomamos estos 4 hijos como cromosomas iniciales y construimos una nueva tabla.

Si suponemos que esta tabla es la obtenida después de varias iteraciones podemos considerar que representa los resultados finales donde los objetos a considerar para la mochila son el 2 y el 3 con una utilidad máxima de 11 y un peso de 14.

El problema de la mochila (I)

El problema de la mochila (knapsack problem) es el siguiente problema de optimización combinatoria:

  Dado un conjunto de elementos, cada uno con un peso y un valor, determinar qué elementos incluir en la colección para que el peso total sea menor o igual a un límite dado y el valor total sea el mayor posible.

El problema más sencillo (0-1 knapsack problem) es aquel en el que se restringe el número de copias de cada item a cero o uno.

Si n es el número de items numerados de 1 a n, cada uno con un peso wi y un valor vi, con una capacidad máxima de peso W, se trata de maximizar:

$$\sum_{i=1}^n v_ix_i$$

con la restricción:

$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in \{ 0,1 \}$$

El problema de la mochila acotada (BKP) elimina la restricción de que solo exista un ejemplar de cada artículo, pero restringe el número xi de copias de cada tipo de artículo a un valor entero máximo no negativo c. Por tanto la restricción es:

$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in \{ 0,1 \dots c\}$$

El problema de la mochila ilimitada (UKP) no impone un límite superior al número de copias de cada tipo de artículo y  la única restricción de xi es que sea un número entero no negativo:

$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in N$$

Vamos a resolver un ejemplo mediante programación dinámica:

Sean 5 objetos con los valores vi y pesos wi que se muestran en la Figura. Los pesos posibles en la mochila van desde 0 al máximo permitido de W=8 .

 Se establece una matriz M[i,j] donde cada elemento indica el beneficio máximo de llevar una mochila de peso j con objetos desde x1 hasta xi.

La primera fila de ceros corresponde  a no meter ningún objeto en la mochila y la primera columna de ceros indica mochila de tamaño cero que no admite ningún objeto.

Analicemos el funcionamiento observando las celdas coloreadas.  La matriz se va completando de izquierda a derecha y de arriba a abajo. Si estamos en la celda M[3,5]=7, retrocedemos 4 posiciones hasta la celda M[2,0]=0 ya que w3=4; ahora hacemos el cálculo siguiente:

$$M[3,1]+v_3=0+10=10>M[3,5]=7 \rightarrow M[4,5]=10$$

La celda M[5,5] también  vale 10 porque una mochila de peso máximo 4 no admite un objeto de peso 5.

La celda M[6,8] repite el valor 16 pues el valor que se obtiene (15) es menor que el de su celda superior.

El valor más alto de la última columna (19) indica el valor máximo.

Vamos a obtener los objetos con los que se consigue el valor máximo:

Al ser M[6,9]=M[5,9] el objeto W5=7 no se pone en la mochila. Como M[5,9]>M[4,9] el objeto w4=5 se pone en la mochila.

Retrocedemos 5 posiciones a  M[4,4] y siguiendo el mismo razonamiento no ponemos el objeto w3=4 y si ponemos el objeto w2=3. Continuando el proceso se llega a M[2,1]=0 y finaliza rl proceso.

Se han colocado en la mochila el objeto w2=3, v2=5 y el objeto w4=5, v4=14.

Problema del cambio de moneda (II)

Se trata de, dada una serie de monedas, devolver una cantidad determinada usando el menor número posible. Vamos a aplicar la Programación Dinámica para evitar los errores que se pueden producir utilizando un Algoritmo Voraz.

Existen n monedas diferentes y con una cantidad ilimitada de cada tipo: $$X_1 < X_2 < X_3 \cdots < X_n$$

Se trata de devolver una cantidad c, donde cambio(n,c) indica las mínimas monedas necesarias para devolver c usando X1, X2, X3,...Xn monedas.

• Si Xn>c no usamos esa moneda y cambio(n,c)=cambio(n-1,c).
• Si Xn<=c podemos usar esa moneda o no.
• Si usamos Xn entonces cambio(n,c-Xn)+1.
• Si no usamos Xn entonces cambio(n-1,c).
• De las dos opciones cogemos la menor cantidad.

Vamos a establecer una tabla con una matriz M((i,j)=cambio(i,j) donde i indica el número total de monedas <=Xi para devolver la cantidad j. Entonces cambio(i,j) es: $$cambio(i-1,j) \hspace{0.1 cm}si \hspace{0.1 cm} X_i>j$$ $$min(cambio(i-1,j),cambio(i,j-X_k)+1) \hspace{0.2 cm} si X_i\leq j$$

En la tabla la primera fila está numerada de 0 a c y la primera columna con los valores de las monedas incluida la posibilidad de no tener monedas. La primera columna de ceros indica que no se necesita ninguna moneda para devolver cero. La fila de infinitos indica que sin monedas no podemos devolver ninguna cantidad. La columna de infinitos indica que no podemos devolver 1 con monedas de valor superior. 

Vamos a explicar como se obtiene el elemento M(3,7) (verde) de la matriz. Para ello utilizamos los elementos M(2,7) M(3,4) (rojos) $$cambio(3-1,7)=M(2,7)=3 \hspace{0.2 cm} cambio(3,7-3)+1=M(3,4)+1=2$$ Al ser M(2,7)=3 se retroceden 3 posiciones desde la columna 7. De los dos valores obtenidos el menor es el que se asigna al elemento M(3,7). El razonamiento seguido, para todos los demás elementos de la matriz, es el mismo. El último elemento M(4,9) indica el número de monedas necesaria. 

  ¡Por tanto la solución óptima utiliza 3 monedas!

Vamos a ver el reparto de esas tres monedas. Para ello aplicamos el algoritmo siguiente: $$ si \hspace{0.2 cm} i>2 \land M(i,j)=M(i-1,j) \rightarrow i=i-1$$ $$ si \hspace{0.2 cm} no \rightarrow N(i)=N(i)+1 \land j=j-X_i$$

Empezamos en el último elemento M(4,8). Como M(4,8)=M(3,8)=3 subimos una fila y ahora M(3,8)=3<>M(2,8)=4 entonces el contador de monedas de valor 3 es N(3)=1 y retrocedemos 8-3 columnas y se repite el proceso a partir del elemento M(3,5) (verde) consiguiendo una segunda moneda de 3 y finalmente una moneda de 2.

¡Por tanto con 2 monedas de 3 y una de 2 se devuelve la cantidad 8 !

Problema del cambio de moneda (I)

Dado un monto M de monedas y un conjunto de denominaciones D (billetes o monedas) se busca la mínima cantidad de denominaciones cuya suma sea M.

No existen restricciones sobre el número de billetes o monedas de una denominación y sobre el uso repetido de billetes o monedas.

Vamos aplicar un algoritmo voraz: se elige la opción óptima en cada paso con la esperanza de llegar a una solución general óptima.

Sea un monto de M=36 monedas y denominaciones D={1,2,5,10,20}. Se elige en cada paso la mayor moneda posible y así sucesivamente:

• paso 1: 36-20=16
• paso 2: 16-10=6
• paso 3: 6-5=1
• paso 4: 1-1=0

Por tanto la solución general es: S={20,10,5,1} que suman 36. Además es óptima porque no existen otra solución con menos monedas. 

No siempre la suma de las soluciones óptimas de cada paso dan una solución óptima general. Si ahora las denominaciones son D={1,2,5,10,18,20} también se tiene:

• paso 1: 36-20=16
• paso 2: 16-10=6
• paso 3: 6-5=1
• paso 4: 1-1=0

Sin embargo la solución óptima es: S={18,18} que también suman 36. Aunque a veces puede no fallar, por ejemplo, si el monto es M=39:

• paso 1: 39-20=19
• paso 2: 19-18=1
• paso 3: 1-1=0

Por tanto la solución general es: S={20,18,1} que suman 39. 

Para que el algoritmo no falle nunca es necesario que cada clase de moneda sea igual o mayor que una sucesión de potencias. No puede haber dos clases de monedas que cumplan la misma condición. $$k^0,k^1,k^2,\cdots k^n$$ En nuestro ejemplo válido: $$2^0\leq1, 2^1\leq2,2^2\leq5,2^3\leq10,2^4\leq20$$ En las monedas del euro se cumple este criterio: $$2^0\leq1, 2^1\leq2,2^2\leq5,2^3\leq10,2^4\leq20,2^5\leq50,2^6\leq100$$ 

 Para que no falle nunca se utiliza la Programación Dinámica.

Conjetura de Kakeya

Durante más de un siglo, uno de los problemas más intrigantes de las matemáticas ha sido la conjetura de Kakeya. Esta cuestión, planteada en 1917 por el matemático japonés Sōichi Kakeya, pregunta cuál es la región de menor área donde puede girarse una aguja de manera completa. Aunque su enunciado es sencillo, su resolución ha desafiado a generaciones de expertos en análisis matemático y geometría.

El problema original de Kakeya se plantea en dos dimensiones: ¿Cuál es la región más pequeña en la que una aguja de longitud unitaria puede girar 180 grados? Se demostró que estos conjuntos pueden tener área arbitrariamente pequeña, lo que llevó a conjeturar que en espacios de mayor dimensión podrían también ser "demasiado pequeños".

 Sin embargo, la versión tridimensional de esta conjetura, ahora resuelta, establece que, aunque estos conjuntos puedan tener volumen cero, su dimensión geométrica debe ser 3. Esto significa que, aunque ocupen poco espacio, siguen teniendo una estructura compleja en el espacio tridimensional.

Este resultado no solo resuelve una cuestión matemática teórica, sino que también tiene aplicaciones en áreas como la física y la informática. Los conjuntos de Kakeya están relacionados con la propagación de ondas y la estructura de los datos en espacios de alta dimensión, lo que los hace relevantes para la criptografía y el análisis de señales.

Ahora, un equipo de matemáticos ha logrado un avance clave en esta conjetura, resolviendo su versión tridimensional. Investigadores de la Universidad de Nueva York y la Universidad de Columbia Británica han demostrado que los conjuntos de Kakeya en tres dimensiones, aunque puedan tener volumen cero, siempre deben ser tridimensionales. Este resultado, publicado en preprint en arXiv, ha sido calificado como un hito en la teoría geométrica y tiene implicaciones en análisis armónico, teoría de números e incluso criptografía.

El nuevo estudio, liderado por Hong Wang y Joshua Zahl, utiliza herramientas avanzadas de análisis geométrico para demostrar la estructura tridimensional de estos conjuntos. Una de las claves del avance ha sido el análisis de la disposición de "tubos" en el espacio tridimensional. En términos matemáticos, el equipo mostró que "la unión de tubos en 3D debe tener un volumen casi máximo", lo que implica que un conjunto de Kakeya no puede ser demasiado pequeño. Para ello, aplicaron un método conocido como inducción en escalas, que les permitió descomponer el problema en estructuras más manejables y demostrar la propiedad tridimensional de los conjuntos de Kakeya. El propio matemático Terence Tao, ganador de la Medalla Fields en 2006, destacó la importancia del hallazgo al afirmar que se trata de "un espectacular avance en la teoría de la medida geométrica". Este comentario subraya el impacto del descubrimiento dentro de la comunidad matemática.