Área de Energía, Industrias y Recursos Naturales No
Renovables
INGENIERÍA EN SISTEMAS
Algoritmos Genéticos
JGAP
POR:
Angel Alberto Valdez Masache
DOCENTE:
Luis Antonio Chamba Eras
LOJA - ECUADOR
2012
Índice
Introducción ............................................................................................................................... …3
Instalación y configuración del entorno ......................................................................................... 4
Descarga e instalación de la maquina virtual de java ...................................................... 4
Descarga e instalación de Netbeans desarrollo en java .................................................. 4
Descarga e instalación de JGAP ..................................................................................... 5
Agregar las librerías a una aplicación .............................................................................. 5
Métodos de Selección ................................................................................................................. 10
Rueda de ruleta ............................................................................................................. 10
Selección por torneo ...................................................................................................... 11
Basado en el rango ........................................................................................................ 11
Método Estocástico ....................................................................................................... 11
Métodos de Reproducción .......................................................................................................... 12
Cruza Simple ................................................................................................................. 12
Cruza de dos puntos ...................................................................................................... 12
Cruza Multipunto ............................................................................................................ 12
Cruza binomial ............................................................................................................... 12
Mutación ........................................................................................................................ 13
Ejemplo de aplicación: ................................................................................................................ 15
Implementación de ejemplo ........................................................................................................ 16
Función Aptitud .............................................................................................................. 19
ANEXO I: Código fuente Cambio Mínimo ................................................................................... 20
ANEXO II: Ejemplo de Ejecuciones y Resultados ...................................................................... 29
Para 90 centavos ........................................................................................................... 29
Para 125 Centavos ........................................................................................................ 29
Para 87 Centavos .......................................................................................................... 29
ANEXO III: Licencia .................................................................................................................... 30
Bibliografía………………………………………………………………………………………………31
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.5
Nuestro 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
curva de aprendizaje. Incluiremos "srceen shots" para hacer esta tarea mas simple.
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 el Eclipse es necesario disponer de la máquina virtual de java para
poder compilar las aplicaciones. Esto lo hace automáticamente el eclipse pero debe
tenerse instalada previamente. Se puede obtener en este sitio o en el cd.
http://java.sun.com/javase/downloads/index.jsp
Descarga e instalación de Netbeans para desarrollo en java
Se puede bajar la última versión de Netbeans de Internet del sitio:
http://www.oracle.com/technetwork/java/javase/downloads/jdk-netbeans-jsp-142931.html
Como se muestra en la siguiente imagen.
Una vez descargado el instalador, se ejecuta e instala con normalidad.
Descarga e instalación de JGAP
Se deben descargar las librerías de JGAP desde el sitio oficial hay un link a la última
versión. Hasta el día de hoy es la 3.5.
http://sourceforge.net/projects/jgap/files/jgap/
En este archivo se encuentran las librerías y algunos ejemplos de aplicación compilados,
el archivo jgap_3.5_full.zip contiene todos los códigos fuentes. Descomprimir el archivo
jgap_3.5_full.zip en c:\jgap\jgapfull
Agregar las librerías a una aplicación
Una vez instalado netbeans y descomprimido el framework en c:\jgap\jgapfull debemos
crear un proyecto en el netbeans.
Entramos al netbeans y creamos un nuevo proyecto java:
Para esto hacemos click derecho como se muestra en la imagen.
Escribimos el nombre del proyecto y hacemos clic en Finish y crea automáticamente un proyecto nuevo.
Una vez creado el proyecto se debe configurar el Build Path para incluir las librerías de jgap. Haciendo clic derecho en el proyecto y seleccionando Set Configuratión -> Customize
Luego se debe seleccionar el item Libraries y hacer clic en Add JAR/Folder
Buscar en c:\jgap\jgap_3.5_full el jgap.jar y hacer click en Abrir
Una vez realizado esto ya se puede utilizar las librerías desde una clase java de ese
proyecto.
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
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.
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.
XYX | XYYYX YYX|YYXXY
XYX | YYXXY YYX | XYYYX
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
X | YXX | Y | YY | X Y | YXY | Y | XX | Y
X | YXY | Y | XX | X Y | YXX | Y | YY | Y
Cruza binomial
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:
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.
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 dólares (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
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:
Cantidad de Monedas de 1 dólar 2
Cantidad de Monedas de 50 centavos 1
Cantidad de Monedas de 25 centavos 1
Cantidad de Monedas de 10 centavos 0
Cantidad de Monedas de 5 centavos 0
Cantidad de Monedas de 1 centavo 0
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 configuración 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 configuración que el elemento más apto siempre pase // a
// la próxima generación //
conf.setPreservFittestIndividual(true);
Se crea la función de aptitud que más adelante se explicará y se setea en la configuración
// Se Crea la función de aptitud y se setea en la configuración //
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 6 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_M0WT0/100)); // Moneda 1 dolar
sampleGenes[1] = new IntegerGene(conf, 0, 10); // Moneda 50 centavos
sampleGenes[2] = new IntegerGene(conf, 0, 10); // Moneda 25 centavos
sampleGenes[3] = new IntegerGene(conf, 0, 10); // Moneda 10 centavos
sampleGenes[4] = new IntegerGene(conf, 0, 10); // Moneda 5 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 tal vez sean las mejores o si son muy amplios
costara más tiempo de procesamiento llegar a soluciones óptimas.
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.
Pobl acion,evolve();
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 como
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.
ANEXO I: CÓDIGO FUENTE CAMBIO MÍNIMO
package practica1;
import java.io.File;
import org.jgap.Chromosome;
import org.jgap.Configuration;
import org.jgap.FitnessFunction;
import org.jgap.Gene;
import org.jgap.Genotype;
import org.jgap.IChromosome;
import org.jgap.data.DataTreeBuilder;
import org.jgap.data.IDataCreators;
import org.jgap.impl.DefaultConfiguration;
import org.jgap.impl.IntegerGene;
import org.jgap.xml.XMLDocumentBuilder;
import org.jgap.xml.XMLManager;
import org.w3c.dom.Document;
/**
* En este ejemplo se muestra como resolver un problema clasico de algoritmos
* genéticos utilizando el framework JGAP. El problema consiste en lograr juntar
* el monto de dinero ingresado a la aplicacion por parametro con la menor
* cantidad de monedas posibles. Para resolver el problema nos basamos en la
* moneda de la Republica Argentina(Se adapto para trabajarlo en Euros aumentando)
* la moneda de 2 euros, cambiando la de 25 por 20 y agregando la de 2 centimos
* Moneda de 1 euro ( equivale a 100 centimos) Moneda de 50 Centimos Moneda de 20 Centimos
* Moneda de 10 Centimos Moneda de 5 Centimos Moneda de 2 Centimos Moneda de 1 Centimo
*
* @author Gabriel Veloso
* @author Ruben Arce
* @since 1.0
*/
public class CambioMinimo {
/**
* The total number of times we'll let the population evolve.
*/
private static final int MAX_EVOLUCIONES_PERMITIDAS = 2200;
/**
* Calcula utilizando algoritmos geneticos la solución al problema y la
* imprime por pantalla
*
* @param Monto
* Monto que se desea descomponer en la menor cantidad de monedas
* posibles
* @throws Exception
*
* @author Gabriel Veloso
* @author Ruben Arce
* @since 1.0
*/
public static void calcularCambioMinimo(int Monto)throws Exception {
// Se crea una configuracion con valores predeterminados.
// -------------------------------------------------------------
Configuration conf = new DefaultConfiguration();
// Se indica en la configuracion que el elemento mas apto siempre pase a
// la proxima generacion
// -------------------------------------------------------------
conf.setPreservFittestIndividual(true);
// Se Crea la funcion de aptitud y se setea en la configuracion
// ---------------------------------------------------------
FitnessFunction myFunc = new CambioMinimoFuncionAptitud(Monto);
conf.setFitnessFunction(myFunc);
// Ahora se debe indicar a la configuracion como seran los cromosomas: en
// este caso tendran 8 genes (uno para cada tipo de moneda) con un valor
// entero (cantidad 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[2] = new IntegerGene(conf, 0, 10); // Moneda 25 centavos
sampleGenes[3] = new IntegerGene(conf, 0, 10); // Moneda 10 centavos
sampleGenes[4] = new IntegerGene(conf, 0, 10); // Moneda 5 centavos
sampleGenes[5] = new IntegerGene(conf, 0, 10); // Moneda 1 centavo
IChromosome sampleChromosome = new Chromosome(conf, sampleGenes);
conf.setSampleChromosome(sampleChromosome);
// Por ultimo se debe indicar el tamaño de la poblacion en la
// configuracion
// ------------------------------------------------------------
conf.setPopulationSize(200);
Genotype Poblacion;
// El framework permite obtener la poblacion inicial de archivos xml
// pero para este caso particular resulta mejor crear una poblacion
// aleatoria, para ello se utiliza el metodo randomInitialGenotype que
// devuelve la poblacion random creada
Poblacion = Genotype.randomInitialGenotype(conf);
// La Poblacion debe evolucionar para obtener resultados mas aptos
// ---------------------------------------------------------------
long TiempoComienzo = System.currentTimeMillis();
for (int i = 0; i < MAX_EVOLUCIONES_PERMITIDAS; i++) {
Poblacion.evolve();
}
long TiempoFin = System.currentTimeMillis();
System.out.println("Tiempo total de evolucion: " + (TiempoFin - TiempoComienzo) + "
ms");
guardarPoblacion(Poblacion);
// Una vez que la poblacion evoluciono es necesario obtener el cromosoma
// mas apto para mostrarlo como solucion al problema planteado para ello
// se utiliza el metodo getFittestChromosome
IChromosome cromosomaMasApto = Poblacion.getFittestChromosome();
System.out.println("El cromosoma mas apto encontrado tiene un valor de aptitud de: "
+ cromosomaMasApto.getFitnessValue());
System.out.println("Y esta formado por la siguiente distribucion de monedas: ");
System.out.println("\t" +
CambioMinimoFuncionAptitud.getNumeroDeComendasDeGen(cromosomaMasApto, 0) + " Moneda 1
dolar");
System.out.println("\t" +
CambioMinimoFuncionAptitud.getNumeroDeComendasDeGen(cromosomaMasApto, 1) + " Moneda
50 centavos");
System.out.println("\t" +
CambioMinimoFuncionAptitud.getNumeroDeComendasDeGen(cromosomaMasApto, 2) + " Moneda
25 centavos");
System.out.println("\t" +
CambioMinimoFuncionAptitud.getNumeroDeComendasDeGen(cromosomaMasApto, 3) + " Moneda
10 centavos");
System.out.println("\t" +
CambioMinimoFuncionAptitud.getNumeroDeComendasDeGen(cromosomaMasApto, 4) + " Moneda 5
centavos");
System.out.println("\t" +
CambioMinimoFuncionAptitud.getNumeroDeComendasDeGen(cromosomaMasApto, 5) + " Moneda 1
centavo");
System.out.println("Para un total de "+
CambioMinimoFuncionAptitud.montoCambioMoneda(cromosomaMasApto) + " centimos en " +
CambioMinimoFuncionAptitud.getNumeroTotalMonedas(cromosomaMasApto) + " monedas.");
}
/**
* Método principal: Recibe el monto en dinero por parámetro para determinar
* la cantidad minima de monedas necesarias para formarlo
*
* @param args
* Monto de dinero
* @throws Exception
*
* @author Gabriel Veloso
* @author Ruben Arce
* @since 1.0
*/
public static void main(String[] args) throws Exception {
int amount = 353;
try {
//amount = Integer.parseInt(args[0]);
} catch (NumberFormatException e) {
System.out.println("El (Monto de dinero) debe ser un numero entero
valido");
System.exit(1);
}
if (amount < 1 || amount >= CambioMinimoFuncionAptitud.MAX_MONTO) {
System.out.println("El monto de dinero debe estar entre 1 y "+
(CambioMinimoFuncionAptitud.MAX_MONTO - 1)+ ".");
} else {
calcularCambioMinimo(amount);
}
}
// ---------------------------------------------------------------------
// Este metodo permite guardar en un xml la ultima poblacion calculada
// ---------------------------------------------------------------------
public static void guardarPoblacion(Genotype Poblacion) throws Exception {
DataTreeBuilder builder = DataTreeBuilder.getInstance();
IDataCreators doc2 = builder.representGenotypeAsDocument(Poblacion);
// create XML document from generated tree
XMLDocumentBuilder docbuilder = new XMLDocumentBuilder();
Document xmlDoc = (Document) docbuilder.buildDocument(doc2);
XMLManager.writeFile(xmlDoc, new File("PoblacionCambioMinimo.xml"));
}
}
package practica1;
import org.jgap.*;
public class CambioMinimoFuncionAptitud extends FitnessFunction{
private final int montoObjetivo;
// Maximo monto posible 1000 Centimos = 10 Euros
public static final int MAX_MONTO = 1000;
// Maxima cantidad de monedas posibles. Es igual al Monto maximo en
// centimos, ya que si se utilizan monedas de un centimo se llegaria al
// monton con la mayor cantidad posible de monedas
public static final int MAX_CANT_MONEDAS = MAX_MONTO;
// El constructor de la funcion de aptitud debe recibir el monto objetivo
// del problema y almacenarlo en un atributo. Si el monto es invalido arroja
// una excepcion
public CambioMinimoFuncionAptitud(int monto) {
if (monto < 1 || monto >= MAX_MONTO) {
throw new IllegalArgumentException("El monto debe ser un numero entre 1 y
" + MAX_MONTO + " centimos");
}
montoObjetivo = monto;
}
/**
* El metodo evaluate es el metodo que se debe sobrecargar para que devuelva
* el valor de aptitud asociado al cromosoma que se recibe por parametro.
*
*
* @param cromosoma
* El cromosoma a evaluar
*
* @return El valor de aptitud de ese cromosoma
* @author Gabriel Veloso, Ruben Arce
*/
public double evaluate(IChromosome cromosoma) {
// Se debe tener en cuenta el evaluador que se esta usando. El evaluador
// estandar le asigna un valor mas apto a los valores mas altos de
// aptitud. Tambien hay otros evaluadores que asignan mejor aptitud a
// los valores mas bajos.
// Es por esto que se chequea si 2 es mas apto que 1. Si esto es asi
// entonces el valor mas apto sera el mayor y el menos apto el 0
boolean evaluadorEstandard =
cromosoma.getConfiguration().getFitnessEvaluator().isFitter(2, 1);
int montoCambioMonedas = montoCambioMoneda(cromosoma);
int totalMonedas = getNumeroTotalMonedas(cromosoma);
int diferenciaMonto = Math.abs(montoObjetivo - montoCambioMonedas);
// El primer paso es asignar la menor aptitud a aquellos cromosomas cuyo
// monto no sea el monto objetivo. Es decir una descomposicion en
// monedas que no sea del monto ingresado
if (evaluadorEstandard) {
if (diferenciaMonto != 0)
return 0.0d;
} else {
if (diferenciaMonto != 0)
return MAX_CANT_MONEDAS;
}
// luego se debe asignar mas aptitud a aquellos cromosomas que posean
// menor cantidad de monedas.
if (evaluadorEstandard) {
// Se debe asegurar devolver un valor de aptitud positivo siempre.
// Si el valor es negativo se devuelve MAX_CANT_MONEDAS ( elemento
// menos apto )
return Math.max(0.0d, MAX_CANT_MONEDAS - totalMonedas);
} else {
// Se debe asgurar devolver un valor de aptitud positivo siempre.
// Si el valor es negativo se devuelve 0 ( elemento menos apto )
return Math.max(0.0d, totalMonedas);
}
}
/**
* Calcula el monto total que suman todas las monedas de un cromosoma
*
*
* @param cromosoma
* El cromosoma a evaluar
* @return Retorna el monto en centimos compuesto por la suma de las monedas
* de ese cromosoma
*
* @author Gabriel Veloso, Ruben Arce
*
*/
public static int montoCambioMoneda(IChromosome cromosoma) {
int Moneda1Dolar = getNumeroDeComendasDeGen(cromosoma, 0);
int Moneda50Centimos = getNumeroDeComendasDeGen(cromosoma, 1);
int Moneda25Centimos = getNumeroDeComendasDeGen(cromosoma, 2);
int Moneda10Centimos = getNumeroDeComendasDeGen(cromosoma, 3);
int Moneda5Centimos = getNumeroDeComendasDeGen(cromosoma, 4);
int Moneda1Centimo = getNumeroDeComendasDeGen(cromosoma, 5);
return (Moneda1Dolar * 100) + (Moneda50Centimos * 50) + (Moneda25Centimos *
25) + (Moneda10Centimos * 10) + (Moneda5Centimos * 5) + Moneda1Centimo;
}
/**
* Calcula la cantidad de monedas de determinado tipo (gen) de un cromosoma
* Ejemplo. Cantidad de monedas de 20 centimos de es cromosoma
*
* @param cromosoma
* El cromosoma a evaluar
* @param numeroGen
* El numero gen (tipo de moneda) de que se desea averiguar la
* cantidad
* @return Devuelve la cantidad de monedas de ese tipo de ese cromosoma
*
*
* @author Gabriel Veloso, Ruben Arce
*/
public static int getNumeroDeComendasDeGen(IChromosome cromosoma,int numeroGen) {
Integer numMonedas = (Integer)
cromosoma.getGene(numeroGen).getAllele();
return numMonedas.intValue();
}
/**
* Calcula el total de monedas que tiene esa solucion. Este valor se utiliza
* para calcular la aptitud del cromosoma ya que el objetivo es minimizar la
* cantidad de monedas de la solucion
*
*
* @param cromosoma
* El cromosoma a evaluar
* @return El total de monedas que tiene esa solucion
*
* @author Gabriel Veloso, Ruben Arce
*/
public static int getNumeroTotalMonedas(IChromosome cromosoma) {
int totalMonedas = 0;
int numberOfGenes = cromosoma.size();
for (int i = 0; i < numberOfGenes; i++) {
totalMonedas += getNumeroDeComendasDeGen(cromosoma, i);
}
return totalMonedas;
}
}
ANEXO II: EJEMPLO DE EJECUCIONES Y RESULTADOS
Para 353 centavos
Tiempo total de evolución: 12265 ms
El cromosoma más apto encontrado tiene un valor de aptitud de: 993.0
Y está formado por la siguiente distribución de monedas:
3 Moneda 1 dólar
1 Moneda 50 centavos
0 Moneda 25 centavos
0 Moneda 10 centavos
0 Moneda 5 centavos
3 Moneda 1 centavo
Para un total de 353 centavos en 7 monedas.
Para 155 Centavos
Tiempo total de evolución: 13591 ms
El cromosoma más apto encontrado tiene un valor de aptitud de: 997.0
Y está formado por la siguiente distribución de monedas:
1 Moneda 1 dólar
1 Moneda 50 centavos
0 Moneda 25 centavos
0 Moneda 10 centavos
1 Moneda 5 centavos
0 Moneda 1 centavo
Para un total de 155 centavos en 3 monedas.
Para 263 Centavos
Tiempo total de evolución: 12540 ms
El cromosoma más apto encontrado tiene un valor de aptitud de: 990.0
Y está formado por la siguiente distribución de monedas:
2 Moneda 1 dólar
0 Moneda 50 centavos
1 Moneda 25 centavos
3 Moneda 10 centavos
1 Moneda 5 centavos
3 Moneda 1 centavo
Para un total de 263 centavos en 10 monedas.
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. Inste|ad, 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!
Bibliografía:
VELOSO, Gabriel Alejandro. ARCE, Rubén, Algoritmos Genéticos JGAP. 2009.
http://eqaula.org/eva/mod/resource/view.php?inpopup=true&id=9541 [disponible en
línea].
Top Related