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.