tarea

1

Área de la Energía, las Industrias y los Recursos Naturales no Renovables

CARRERA DE

INGENIERÍA EN SISTEMAS

TEMA:

Aplicaciones Informáticas

Algoritmos Genéticos

JGAP

Autor:

Iliana Vargas Aguilar

LOJA – ECUADOR

2011

2

INTRODUCCIÓN JGAP es un framework libre basado en la tecnología JAVA. El mismo provee mecanismos para aplicar principios evolutivos en la resolución de problemas. Al momento de escribir este documento la última versión estable de este framework es la 3.4.3 El trabajo se focaliza en probar este framework y realizar un manual detallado con ejemplos didácticos que permitan aprender a utilizarlo haciendo más leve su aprendizaje. Incluimos “srceen shots” para hacer esta tarea más simple.

3

INSTALACIÓN Y CONFIGURACIÓN DEL ENTORNO En primer lugar debe disponerse de una herramienta de desarrollo de aplicaciones java. Luego es necesario descargar las librerías JGAP y agregarlas a una aplicación.

Descarga e instalación de la máquina virtual de java Antes de descargar NetBeans para Linux es necesario disponer de la máquina virtual de java para poder compilar las aplicaciones. Esto lo hace automáticamente Netbeans pero debe tenerse instalada previamente. Se lo puede realizar instalándolo desde el Gestor de Paquetes Synaptic, como se indica a continuación:

E instalar el JDK, como se indica en la siguiente imagen:

4

Aplicar los cambios respectivos de instalación del JDK:

5

Descarga e instalación de NetBeans para desarrollo en java Junto con este manual se adjunta la última versión de NetBeans para poder utilizar el framework. De todas formas se puede bajar de Internet del sitio http://netbeans.org/downloads/ Como se indica en las siguientes imágenes:

1. Seleccionar el idioma deseado

http://netbeans.org/downloads/

6

2. Seleccionar el sistema operativo, donde se lo va a instalar.

7

3. Procedemos a descargar:

8

Dirigirse a la carpeta donde se guardó la descarga, y seleccionar “propiedades” para poder

ejecutar:

Seleccionar: “es ejecutable” para proceder a instalar:

9

A continuación, se muestra la forma de instalar NetBeans, para ello hacemos clic en “Next”, en

todas las ventanas subsiguientes.

10

Agregar la librería JGAP a la aplicación

Creamos un proyecto en NetBeans para utilizar el framework:

Elegimos que el proyecto será de tipo Java:

11

Escribimos el nombre del proyecto:

A continuación, cargamos la librería, para ello hacemos clic derecho en Librerías y clic en Add

JAR/Folder.

12

Buscamos la librería y la seleccionamos:

Finalmente observaremos que se ha cargador correctamente:

13

INTRODUCCIÓN A LOS ALGORITMOS GENÉTICOS Los algoritmos genéticos buscan imitar los procesos evolutivos de la naturaleza para resolver problemas. En la naturaleza los individuos de una población se reproducen entre si y de esta forma nacen nuevos individuos. Todos se someten a una selección natural durante sus vidas en la que los más aptos tienen más probabilidades de sobrevivir, de esta forma las poblaciones evolucionan, mejoran constantemente y se adaptan a los nuevos medios. Para los algoritmos genéticos los individuos se denominan cromosomas. Cada cromosoma es una solución a un problema específico. Las características de un cromosoma se denominan genes. También existe una función de aptitud, la cual aplicada a cada cromosoma devuelve un valor que indica cuan apto es y permite compararlos entre ellos. Antes de comenzar, es necesario tener una población inicial. Lo que suele hacerse es crear una población de cromosomas al azar. Una vez que se tiene una población se reproducen los individuos para obtener mayor variedad, tal como en la naturaleza. Luego, es necesario seleccionar los mejores, para ir evolucionando. Hay varios métodos de selección pero en general lo que se busca es que los mejores pasen a la próxima generación y algunos no tan aptos también, ya que la variedad ayuda a que en la reproducción se generen cromosomas más aptos aun que sus padres. Puede que de la cruza de un cromosoma muy apto y otro no tanto resulte uno mucho mejor a sus padres. En la naturaleza algunas veces sucede un fenómeno llamado mutación. Este es un pequeño cambio en la información genética producido esporádicamente, que provoca un cambio en un individuo. Este cambio asegura más variedad y provoca cambios positivos o negativos. Los cambios negativos deberían quedar en el olvido gracias a la selección natural y los positivos perdurar haciendo evolucionar a la población. Para los algoritmos también se puede utilizar mutación para agregar variedad y obtener mejores soluciones. Para llegar a buenos resultados es necesario recorrer varias generaciones. Es decir, reproducir varias veces los individuos y hacer varias selecciones y algunas pocas mutaciones. También es necesario determinar cuándo una solución es suficientemente apta como para aceptarla. Para esto puede medirse cuanto aumenta la aptitud del mejor cromosoma y si después de varias generaciones no mejora aun introduciendo mutaciones o aumentando el número de cromosomas podemos decidir dejar de evolucionar y utilizar esa solución. Otra técnica consiste establecer de ante mano cuantas generaciones se van a considerar.

MÉTODOS DE SELECCIÓN A continuación se muestran algunas de las técnicas de selección más conocidas

14

Rueda de ruleta

Este método consiste en construir una ruleta particionada en ranuras de igual tamaño, las cuales se numeran. A cada individuo de la población se le asigna una cantidad de ranuras proporcional a su aptitud. El proceso se repite hasta completar la cantidad de individuos deseados. Este método de selección otorga mayor probabilidad de contribuir a la siguiente generación a los individuos con mayor aptitud. Hay algunas otras variantes como por ejemplo, incluir en la nueva generación el mejor representante de la generación actual. En este caso, se denomina método elitista.

Selección por torneo En este caso dos individuos son elegidos al azar de la población actual y el mejor o más apto de los dos se coloca en la generación siguiente. Esto continúa hasta que se complete la nueva población.

Basado en el rango En este esquema se mantiene un porcentaje de la población, generalmente la mayoría, para la siguiente generación. Se coloca toda la población por orden de aptitud, y los M menos dignos son eliminados y sustituidos por la descendencia de alguno de los M mejores con algún otro individuo de la población.

Método Estocástico

Por cada individuo se calcula la aptitud relativa al promedio de aptitudes de la población, y en

función de esto se asignan las copias. Por ejemplo, si la aptitud promedio de la población es

15 y la aptitud del individuo es 10; entonces su aptitud relativa es 1.5. Esto significa que se

colocará una copia en la próxima generación y que se tiene el 0.5 (50 %) de chance de colocar

una segunda copia.

15

MÉTODOS DE REPRODUCCIÓN A continuación se muestran algunas técnicas para reproducir individuos (o cromosomas).

Cruza Simple Los dos cromosomas padres se cortan por un punto, y el material genético situado entre ellos se intercambia. Dada las siguientes estructuras de longitud 1 = 8, y eligiendo 3 como el punto de cruza se intercambian los segmentos de cromosoma separados por este punto.

Cruza de dos puntos En este método de cruza de dos puntos, se seleccionan dos puntos aleatoriamente a lo largo de la longitud de los cromosomas y los dos padres intercambian los segmentos entre estos puntos.

Cruza Multipunto El cromosoma es considerado un anillo, y se eligen n puntos de cruza en forma aleatoria. Si la cantidad de puntos de cruza es par, se intercambian las porciones de cromosomas definidas entre cada par de puntos consecutivos, si es impar se asume un punto de cruza adicional en la posición cero y se procede de igual modo. Dadas dos estructuras de longitud 1 = 8, con n = 4 puntos de cruza. Intercambiando los segmentos de la posición 2 a 4 y 6 a 7, se tiene:

16

Cruza binomial

Para generar un cromosoma hijo por cruza binomial, se define la probabilidad P0 como la probabilidad de que el Alelo de cualquier posición del descendiente se herede del padre, y 1 – P0 como la probabilidad de que lo herede de la madre. En este caso se puede construir un único hijo por cada aplicación del operador, o bien generar un segundo hijo como complemento del primero. Cuando existe igual probabilidad de heredar del padre como de la madre, P0 = 0,5 la cruza se denomina uniforme. Para estructuras de longitud l la cruza uniforme implica un promedio de l/2 puntos de cruza.

Mutación En la Evolución, una mutación es un suceso bastante poco común (sucede aproximadamente una de cada mil replicaciones), en la mayoría de los casos las mutaciones son letales, pero en promedio, contribuyen a la diversidad genética de la especie. En un algoritmo genético tendrán el mismo papel, y la misma frecuencia (es decir, muy baja). Una vez establecida la frecuencia de mutación, por ejemplo, uno por mil, se examina cada bit de cada cadena. Si un número generado aleatoriamente está por debajo de esa probabilidad, se cambiará el bit (es decir, de 0 a 1 o de 1 a 0). Si no, se dejará como está. Dependiendo del número de individuos que haya y del número de bits por individuo, puede resultar que las mutaciones sean extremadamente raras en una sola generación. No hace falta decir que no conviene abusar de la mutación. Es cierto que es un mecanismo generador de diversidad, y, por tanto, la solución cuando un algoritmo genético está estancado, pero también es cierto que reduce el algoritmo genético a una búsqueda aleatoria. Siempre es más conveniente usar otros mecanismos de generación de diversidad, como aumentar el tamaño de la población, o garantizar la aleatoriedad de la población inicial.

17

EJEMPLO DE APLICACIÓN: Para poder entender cómo funciona el framework y poder manejarlo, un ejemplo de aplicación simple es lo indicado. Supongamos que es necesario descomponer un cierto monto de dinero en la menor cantidad posible de monedas. Por ejemplo si se tienen 1,35 pesos (135 centavos) puede descomponerse de la siguiente forma:

1 Moneda de un dólar 1 Moneda de 25 centavos 1 Moneda de 10 centavos 3 monedas en total

Pero también puede descomponerse de la siguiente forma:

27 Monedas de 5 centavos. 27 monedas en total.

Hay muchas formas de descomponer este monto en monedas cada una de ellas es una solución posible al problema (cromosoma) y tiene un valor de aptitud asociado, que deberá depender de la cantidad de monedas totales de ese cromosoma. Cuantas menos monedas se necesiten más apta será la solución ya que lo que se busca es lograr la menor cantidad de monedas posibles. Cada cromosoma tendrá 6 genes. Los genes en este problema son números enteros que representan la cantidad de monedas de cada tipo.

Moneda de un dólar (100 centavos) Moneda de 50 centavos Moneda de 25 centavos Moneda de 10 centavos Moneda de 5 centavos Moneda de 1 centavo

18

IMPLEMENTACIÓN DE EJEMPLO Para poder implementar una solución a este problema utilizando JGAP es necesario indicarle al framework una serie de parámetros y codificar la función de aptitud. Para este caso la clase principal se llamará CambioMinimo y la función aptitud se codificará en la clase CambioMinimoFuncionAptitud En primer lugar se debe modelar el problema, es decir definir como se compone cada gen de los cromosomas (soluciones posibles). Para este problema puntual cada gen será un número entero y representará la cantidad de un tipo de moneda de ese cromosoma. Por lo tanto cada cromosoma tendrá 6 genes. Ejemplo:

Este cromosoma sumaría 275 centavos en 4 monedas. Una vez definido el modelo se puede comenzar a codificar la solución. A continuación se explica a grandes rasgos como se implementó el ejemplo de aplicación y que clases y funciones principales se utilizaron. Pero para más detalle se encuentra el anexo con el código fuete explicado instrucción por instrucción. Primero se debe crear una configuración con valores predeterminados que luego se irán modificando: // Se crea una configuracion con valores predeterminados.

// -------------------------------------------------------------

Configuration conf = new DefaultConfiguration();

Luego se le indica que el mejor elemento siempre pase a la próxima generación // Se indica en la configuracion que el elemento más apto siempre pase //

a

// la proxima generacion

// -------------------------------------------------------------

conf.setPreservFittestIndividual(true);

Se crea la función de aptitud que más adelante se explicará y se setea en la configuración

19

// Se Crea la funcion de aptitud y se setea en la configuracion

// ---------------------------------------------------------

FitnessFunction myFunc = new CambioMinimoFuncionAptitud(Monto);

conf.setFitnessFunction(myFunc);

También se debe crear un cromosoma de ejemplo para que el framework conozca su estructura: // Ahora se debe indicar a la configuracion como seran los cromosoma: //

en

// este caso tendran 5 genes (uno para cada tipo de moneda) con un

// valor

// entero (candiad de monedas de ese tipo).

// Se debe crear un cromosoma de ejemplo y cargarlo en la

// configuracion

// Cada gen tendra un valor maximo y minimo que debe setearse.

// --------------------------------------------------------------

Gene[] sampleGenes = new Gene[6];

sampleGenes[0] = new IntegerGene(conf, 0,

Math.round(CambioMinimoFuncionAptitud.MAX_MONTO / 100)); // Moneda 1

Dolar

sampleGenes[1] = new IntegerGene(conf, 0, 10); // Moneda 50 centavos




sampleGenes[5] = new IntegerGene(conf, 0, 10); // Moneda 1 centavo

IChromosome sampleChromosome = new Chromosome(conf, sampleGenes);

conf.setSampleChromosome(sampleChromosome);

Es importante tener en cuenta los valores máximos y mínimos ya que si se cargan mal, podría eliminar muchas soluciones que talvez sean las mejores o si son muy amplios costara mas tiempo de procesamiento llegar a soluciones optimas Se puede configurar el tamaño que tendrá la población (Cantidad de cromosomas de una generación)

conf.setPopulationSize(200);

Para poder evolucionar se necesita una población inicial. El framework permite cargarla de un xml pero lo mejor en este caso es indicarle que genere una población inicial aleatoria.

Poblacion = Genotype.randomInitialGenotype(conf);

El método envolve evoluciona una generación. Se lo llama una cierta cantidad de veces con un loop para que realice cierta cantidad de evoluciones.

Poblacion.evolve();

20

El método guardar población creado para este manual guarda todos los datos de la población en un xml llamado PoblacionCaminoMinimo.xml para demostrar cómo trabaja el Framework con las poblaciones y los xml. Para más detalle ver el código fuente del anexo.

guardarPoblacion(Poblacion);

De esta forma se obtiene el cromosoma más apto de la población

IChromosome cromosomaMasApto = Poblacion.getFittestChromosome();

Función Aptitud La clase que implementará la función aptitud debe heredar de FitnessFunction y redefinir el método public double evaluate(IChromosome cromosoma)

Este método le permite al framework determinar que cromosoma es más apto que otro. El valor devuelto debe ser un double positivo. Por defecto, se entiende que un valor más alto devuelto corresponde a un cromosoma más apto pero esto puede no ser así, depende del evaluador que se haya utilizado. En el ejemplo se tiene en cuenta esto antes de devolver el valor de aptitud.

21

ANEXO I: CÓDIGO FUENTE CAMBIO MÍNIMO

29

NEXO II: EJEMPLO DE EJECUCIONES Y RESULTADOS Para 90 centavos Tiempo total de evolución: 18375 ms

El cromosoma más apto encontrado tiene un valor de aptitud de:

996.0

Y está formado por la siguiente distribución de monedas:

0 Moneda 1 dólar

1 Moneda 50 centavos



1 Moneda 5 centavos

0 Moneda 1 centavo

Para un total de 90 centavos en 4 monedas.

Para 125 Centavos

Tiempo total de evolución: 15735 ms

El cromosoma más apto encontrado tiene un valor de aptitud de:

998.0

Y está formado por la siguiente distribución de monedas:

1 Moneda 1 dólar




0 Moneda 5 centavos

0 Moneda 1 centavo


Para 87 Centavos Y está formado por la siguiente distribución de monedas:

0 Moneda 1 dólar




0 Moneda 5 centavos

2 Moneda 1 centavo


30

ANEXO III: LICENCIA Este fragmento esta publicado en la página principal de JGAP donde explica que es un software libre. Pero si se quiere utilizar de forma comercial es necesario donar al menos 20 euros a JGAP. JGAP is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. Instead, you could choose to use the Mozilla Public License to use JGAP in commercial applications without the need of publishing your source code or make it reverse engineerable (as is required with the GNU License). For using the MPL you have to donate at least 20 Euros to JGAP. Maybe you would like to browser further information about using JGAP commercially. JGAP is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the above mentioned GNU Lesser Public License and the Mozilla Public License for more details. But we offer really a lot of unit tests which help assure a very high probability for a correct piece of software!

tarea

Technology