REPORTE ALGORITMOS GENETICOS

 En esta entrada explicaremos que son los algoritmos genéticos y haremos dos ejemplos del problema de la Mochila, uno con 5 objetos y el otro con 10 objetos, de cada uno realizaremos el método de fuerza bruta para saber cual es la configuración optima y también lo realizaremos mediante algoritmos genéticos con 4 iteraciones y 10 generaciones cada iteración. Reportaremos cuales fueron los resultados, mostraremos gráficas para tener un mejor panorama y mostraremos las conclusiones de cada Instancia.

• Introducción

   El problema de la mochila es un problema de optimización el cual consiste en imaginar que llevamos una mochila en la cual le caben un numero indefinido de objetos los cuales tienen un valor de peso y ganancia, la mochila tiene una limite de peso y conforme a un estudio realizado debemos de obtener la combinación de objetos que nos dejen una mayor ganancia sin sobrepasar el limite del peso de la mochila. Es importante ya que encuentra la respuesta optima ya sea por alguna de sus formas de resolverlo con ayuda de algunos de los algoritmos o mediante fuerza bruta. En la vida real podemos ver aplicado este problema cuando un ladrón entra a una casa a robar, por lo general, estos roban joyas, celulares, cosas pequeñas pero de gran valor monetario. Este problema es difícil porque tienes que evaluar todas las opciones posibles y podemos cometer errores al evaluarlos. Este es un algoritmo basado en la teoría de charles Darwin con respecto a la evolución humana.

• Marco teórico

     El problema de la mochila trata de resolver un problema en el que tienes que llevar objetos, que tienen un peso y valor, debes tratar de conseguir sumar el valor más grande, pero que no exceda el peso limite.

Este problema puede resolverse con algoritmos genéticos (AG). Un AG es  un método que se utiliza para optimización de algún problema, además, este trata de imitar a la naturaleza en cuanto a la evolución donde solo sobreviven quienes tienen las mejores características, lo que funciona muy bien para el problema de la mochila, en el que solo las mejores opciones son tomadas en cuenta.

El problema de la mochila se considera un problema NP-completo, que es un problema difícil pero tiene una solución.

    Para entender mejor de que trata el problema de la mochila, les presentamos 2 ejemplos.

Primero si alguna vez has jugado el videojuego Resident Evil 4, seguro recordaras que durante el juego, vas recogiendo objetos que te ayudan para resolver acertijos o pequeños problemas que se te presentan, estos objetos tienen un cierto tamaño y ocupan una cantidad de cuadros, claro que no puedes encimar un objeto con otro, por lo que tienes una cantidad limitada de espacio en tu mochila para cargar armas u objetos útiles, aquí está claramente el problema de la mochila, uno tiene que decidir que objetos le son más útiles para el siguiente acertijo o jefe que tengas que vencer, claro haciendo que todo quepa en tu mochila.

Si tal vez nunca jugaste este videojuego y no te resulta fácil imaginarte esta situación, tal vez te sea mas fácil imaginarte a ti mismo que ganas un concurso y tu premio es que de una tienda puedes llevarte todo lo que puedas cargar en una mochila (sin arrastrar), entonces seguro pensaras en llevarte los objetos mas caros, pero como tienes un límite de peso que puedes llevar, entonces tienes que conseguir hacer la combinación mas optima en el que te lleves la mayor ganancia sin sobrepasar el máximo de peso.

Los algoritmos genéticos son una técnica de búsqueda que se le atribuye a John Henry Holland, estos se basan en la teoría de la evolución que propuso Charles Darwin (como ya se mencionó anteriormente).

La información de un algoritmo genético se representa con los siguientes términos:

• Población: se refiere a los objetos o individuos.
• Cromosomas: es la estructura de las características que tiene un individuo.
• Gen: es una sola característica que puede tener.

El siguiente es un diagrama de flujo de un algoritmo genético

• Experimentos y resultados

INSTANCIA #1

Esta instancia nos dice que la capacidad de la mochila es de 35u. Consta de 5 objetos y cada uno tiene diferentes pesos y ganancias

               

El Óptimo

Buscamos la configuración optima en la cual podíamos tener mayor ganancia y un menor peso, por medio del método de Fuerza Bruta la tabla generada se encuentra en este documento:

https://docs.google.com/file/d/0B13-QqK-5Op-V0Y4X0RXenJCdGM/edit?usp=sharing

y obtuvimos que la configuración:
[0 1 1 1 0] nos da una ganancia de 75 con un peso de 32 es este el optimo.

Tabla de valores para los parámetros del AG






Usando Algoritmo Genético
La dra Sara E. Garza nos proporciono un codigo para nosotros practicar y hacerle mejoras, 
adaptándolo a esta instancia nos dio los siguientes resultados:

Gráficas de resultados

Generación Inicial

   
       
      

Generación 1

  Generación 2

Generación 3

Generación 4

        

Aquí se muestra que el programa dio como resultado del mejor individuo a [01110] con una aptitud de 75.0.
Este resultado es el optimo que fue encontrado por fuerza bruta.

Al principio en las gráficas se muestra que la aptitud variaba mucho y conforme fueron avanzando las iteraciones se muestra que hay mejor aptitud entre los individuos. 


INSTANCIA #2

En esta instancia se cuenta con 10 objetos y el peso máximo es de 150

El Óptimo
Resuelto por fuerza bruta 
https://docs.google.com/file/d/0B13-QqK-5Op-UWZtR1JnWHJlVnc/edit?usp=sharing

Tabla de valores para los parámetros del AG
En esta tabla se muestran los valores que arrojo el código a continuación explicaremos como fueron dados:

Las condiciones para realizar el algoritmo fue que tenían que ser por lo menos 10  generaciones en en cada una de las 4 iteraciones.

Parámetro	Iteración 1	Iteración 2	Iteración 3	Iteración 4
Tamaño de las generaciones	10	10	10	10
Probabilidad de mutación.	.1	.1	.1	.1

El código nos fue facilitado por la Dra Sara E. Garza lo único que hicimos nosotros fue acoplar el código para la instancia que se nos solicitó. (Si desea ver el código completo haz Click Aqui) 

En la función generar_poblacion_inical lo único que se hizo fue modificar para que tomara números de un rango de 0 a 1024 (que en la instancia 2 ese era el caso) e imprimiera únicamente 10 elementos al azar.

La función lo que hace es generar es tomar 10 numeros de 0 a 1024, ya que selecciona los pasa a un for donde se convierten en binario (cromosoma = bin(individuo)[2:] ya que los convierte los imprime.

En la función de mutar no modificamos nada lo único que hicimos fue imprimir el valor de r el cual es un valor random que se compara con la probabilidad de mutacion y asi empezar con la mutacion de los genes a mutar. 

Aquí lo único que hicimos fue modificar la instancia del problema cambiamos las ganancias y los pesos, para que al momento de la evaluación si se marca en llegado caso a pasar del peso la ganancia automáticamente se hace 0, también modificamos el número de iteraciones para que sea 4

En la línea ag= AGMOCHILA(cantidad_objetos,ganancias,pesos, 150,.1,10) es una línea muy importante ya que en ella el 150 determina el peso limite, el .1 es la probabilidad de cruza y el 10 es el número de objetos.

Gráficas de resultados




 

Al final nos muestra que el individuo [0011110000] es el mejor con una aptitud de 233.0

• Conclusiones

     Al resolver un problema con fuerza bruta requiere mucho mas tiempo y esfuerzo que resolverlo por mediante de un algoritmo AG. Por ejemplo resolver una instancia por fuerza bruta de 11 objetos tendría que hacerse el doble de  combinaciones que en la actividad anterior en la cual habían 10 objetos, si son 11 entonces tendrían que ser 2048 combinaciones, y si fueran 20 serian 1,048,576, y peor aún si fueran 30 serian 1,073,741,824 combinaciones, lo que es demasiado trabajo. En cambio un algoritmo genético sirve para simplificar ese trabajo y no desperdiciar tanto tiempo haciendo combinaciones, con este algoritmo solo necesita unas cuantas pruebas.

La ventaja de estos algoritmos es que puedes elegir las opciones que parecen ser las mejores y no tienes que revisar todas las combinaciones. Lo malo de este algoritmo es que puede escoger una combinación que parece ser la mejor y sin embargo puede no ser la mejor opción y detenerse ahí mismo.

• Referencias

Garza, D. S. (s.f.). Sistemas Adaptativos. Obtenido de elisa.dyndns: http://elisa.dyndns-web.com/~saraelena/codigo/sistadap/ag_mochila.py

_______________________________________________________________________________

INTEGRANTES DE EQUIPO:

Evelyn Yazmin Acosta Rodriguez             1476096

Pamela Olga Consuelo Olivares Martinez  1523779
Kattia alexandra puga Vázquez               1495155
Diana Anaid Loza Cerda                         1521190
Elsy Noemi Medellin Souto                     1457560