Sistemas Adaptativos: Práctica 2 - Algoritmos Genéticos

Introducción

Los algoritmos genéticos son llamados así porque se inspiran en la evolución biológica y su base genético-molecular. Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica, así como también a una selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.

Nuestro programa lo que busca es encontrar la forma en la cual podamos invertir nuestro dinero para comprar determinados objetos, después venderlos y así incrementar nuestro capital.

Objetivo y Justificación

Decidimos realizar este programa ya que notamos que la mayoría de nuestros compañeros iban a desarrollar el programa de autómatas celulares. Queríamos realizar algo diferente. El objetivo principal es aprender, ya que cada proyecto tiene un grado de dificultad diferente, y en este caso, el tiempo no estuvo a nuestro favor.

Al realizar este programa tuvimos ciertos problemas. El más importante fue el de manejar diferentes tipos de datos, llámese strings, chars, ints, etcétera. Se tuvo que tener mucha precaución con la conversión de cada uno de estos tipos.

Desarrollo

Lo que se hizo fue tratar de dividir el programa en varios modulos de acuerdo a su función, primero se generaron aleatoriamente los datos de costo y venta de cada articulo así como el capital inicial. Despues se genero la interfaz y luego se implemento el algoritmo genetico, el cual se analizará en esta sección. Por último, se usó un librería para crear el histograma.

Lo anterior muestra los pasos usados en la clase que se encarga de implementar el algoritmo genético.
- Primero se calculan las ganancias de cada objeto
- Despues se creá una poblacion inicial aleatoria de combinaciones de objetos

Luego el programa entra en un ciclo para repetir los siguientes pasos y crear varias generaciones de individuos, buscando siempre una solución óptima para nuestro problema. Estos pasos son:

- Evaluar a cada uno de los individuos de la poblacion para saber si es rentable esa combinación de objetos
- Crear un arreglo, el cual representará a una ruleta que contendrá a los individuos mas aptos de la población actual y nos servirá a la hora de elegir a los mejores para cruzarlos
- Eligir 2 individuos y los cruza (combina) para tratar de generar una mejor combinación de objetos
- Cambiar algunos genes en el individuo (mutar)
- Muestra la nueva generacion de individuos

Otras partes importantes de la clase:

Método para la evaluación de los individuos

Método para la cruza de los individuos

Para ver el código completo, visitar el siguiente enlace:

http://pastebin.com/8XLFhVuD

Entrando un poco más en el código, utilizamos 6 clases, las cuales se describen brevemente a continuación.

Datos. Contiene los datos con los que vamos a trabajar, los cuales se comparten entre las diferentes clases.

GenerarDatos. Clase cuya única función es generar datos aleatorios a los precios de compra y venta de cada artículo, así como el capital inicial.

Mochila. En esta clase se implementa el algoritmo genético para la resolución del problema.

Ventana. Esta es la parte gráfica de la aplicación, la interfaz.

Graficos. Esta clase crea un histograma con los datos de las generaciones que se fueron creando durante la ejecución del programa.

Main. Clase principal.

Simulación

Aquí una muestra de nuestro programa en ejecución en tiempo real.

Conclusiones

El uso de los algoritmos genéticos es ideal cuando se requiere encontrar un valor máximo o un valor mínimo en donde se tiene un mundo de soluciones muy grande. Consiste en un método iterativo donde la intención es ir encontrando, en cada iteración, soluciones mas óptimas que las que encontramos en iteraciones anteriores. Este método no garantiza encontrar la solución mas óptima, pero si puede encontrar una solución muy cercana a esta.

Se podría mejorar implementando una función que revise las aptitudes de los mejores individuos de las ultimas generaciones para conocer si se ha encontrado un progreso en la búsqueda de una respuesta óptima en las ultimas generaciones, ya que asi conoceremos cuando parar o terminar nuestro programa.