Download Elaboración de Herramientas para la Programación de Algoritmos

25
Elaboración de Herramientas para la
Programación de Algoritmos Genéticos en Java
Sergio Enrique Morel Peralta
Facultad Politécnica, Universidad Nacional del Este
Ciudad del Este, Paraguay
[email protected]
Resumen. Este trabajo consiste en un proyecto que busca crear herramientas que sirvan para la elaboración de
programas utilizando Algoritmos Genéticos en JAVA. Estas herramientas consisten en clases genéricas que
implementan correctamente los métodos de la clase Object y permiten la utilización de la herencia para crear las
clases que contendrán los códigos específicos para cada utilización particular de los Algoritmos Genéticos. Se
pretende que estas herramientas además de contener el código para la creación de Algoritmos Genéticos, también
contengan clases que ayuden a encontrar el valor óptimo de los parámetros que influyen en la forma en que se
realizan las técnicas evolutivas para cada caso individual.
Palabras Claves: Algoritmos genéticos, inteligencia artificial, JAVA.
Abstract. This project aims to create tools that would help developing programs using Genetic Algorithms in
JAVA. These tools consist of generic classes that implement the methods of the class Object correctly; therefore
they can be inherited to create more specific classes that would contain codes for using in particular Genetic
Algorithms implementations. It’s intended that these tools would also contain classes to help find the ideal values of
the parameters that have influence in the way evolutionary techniques are performed for each individual case.
Keywords: Genetic algorithms, Artificial Intelligence, JAVA.
1. Introducción
Los Algoritmos Genéticos son técnicas utilizadas en la
computación para encontrar soluciones exactas o
aproximadas para los problemas de optimización y
búsqueda [1]. Una de las grandes ventajas de este
algoritmo es que la solución encontrada no se limita a
un solo resultado, sino que podemos obtener un
conjunto de resultados según el problema lo permita.
Para comenzar a programar utilizando los Algoritmos
Genéticos debemos primero definir la forma de
representar las posibles soluciones del problema, y
luego definir una función de evaluación que califique
esas soluciones [1]. Esto es necesario realizar para cada
problema que se quiera resolver.
Una vez que esto esté definido, se procede a aplicar las
técnicas evolutivas que nos ayuden a encontrar la
mejor solución.
El objetivo de este proyecto es crear herramientas que
apliquen las técnicas evolutivas sin necesidad de estar
programándolas, pero que nos permita controlar el
valor de los parámetros que se utilizan para realizar
estas operaciones si fuese necesario.
Debido a que gran parte del código se queda aislado
dentro de las clases más generales, los que utilicen las
herramientas podrán concentrarse mejor en el código
del problema específico que se quiera resolver.
2. Objetivos
2.1. General
Crear clases genéricas que sirvan como base y guía
para la programación en JAVA de Algoritmos
Genéticos.
2.2. Específicos
-
Definir y crear las clases que serán necesarias para
los algoritmos evolutivos.
-
Crear clases que contengan métodos de utilización
frecuente para simplificar la programación.
-
Crear un programa simple de prueba para
comprobar el funcionamiento de la herramienta.
-
Definir y crear las clases necesarias para encontrar
los mejores valores de los parámetros que influyen
en los algoritmos evolutivos para cada problema
en forma individual.
-
Comparar la velocidad de convergencia de los
algoritmos.
INFORMÁTICA – Nº 5 – AÑO 2009
26
3. Materiales
El lenguaje de programación que se decidió utilizar es
JAVA debido a su gran portabilidad y por las ventajas
que ofrece la programación orientada a objetos. Para
programar en JAVA se necesita tener instalado el JDK
(Java Development Kit) para el sistema operativo a
utilizar. El JDK es la herramienta que permitirá
compilar el programa a “bytecodes”. Los “bytecodes”
después pueden ser ejecutados en cualquier máquina
que disponga de una máquina virtual java JVM (Java
Virtual Machine). El software necesario se puede
conseguir en la página http://www.java.com/.
Como ayuda para la programación se decidió utilizar el
entorno de desarrollo integrado Eclipse. El entorno de
desarrollo integrado (IDE por sus siglas en inglés)
permite acelerar la programación gracias a la ayuda
que proporciona en el momento de detectar errores, en
el seguimiento de variables, etc. El IDE Eclipse se
puede conseguir en la página http://www.eclipse.org/.
4. Métodos
Para realizar la programación de los Algoritmos
Genéticos, se debe crear 3 clases, las cuales deben
heredar de las clases generales que contiene la
herramienta. El nombre de estas clases generales son:
Población, Individuo y Gen. Estas clases no pueden
ser instanciadas.
La clase que herede de Población es la que se
encargará de manejar al conjunto de soluciones del
problema, contendrá un array de soluciones del tipo
Individuo. En esta clase se definirán los parámetros
tales como: el tamaño de la población, la cantidad de
resultados que se obtendrán, la probabilidad de que
ocurran las mutaciones y cruces. Además se encargará
de seleccionar los individuos que participarán de las
operaciones evolutivas de acuerdo a su calificación
relativa (calificación con respecto a los demás
individuos de la población). La clase hija solo
necesitará definir que subclase de Individuo se utilizará
para el programa; el resto del código se encuentra en la
clase padre.
La clase que herede de Individuo es la que se utilizará
para representar a una solución. Esta clase contendrá el
genotipo de la solución, el cual consiste en un array del
tipo Gen. En esta clase se definirá la forma de
representar la solución, la forma en que se realizarán
las operaciones de cruce y mutación, y la función de
calificación de las soluciones. La clase hija necesitará
definir que subclase de Gen se utilizará para la
representación y también deberá implementar la
función de calificación.
Estrictamente hablando Gen es una interfase en el
lenguaje de programación JAVA, por lo tanto no
contiene ninguna codificación. La clase que
implemente la interfaz Gen será la más específica de
las 3. Su contenido será diferente para cada problema
en particular. Esta clase definirá el tipo de dato con el
que se trabajará, como también el dominio o
restricciones de los valores válidos, etc.
En caso de que se quiera realizar cualquier función de
forma diferente a lo codificado en estas clases, se
puede realizar un override de los métodos
correspondientes.
Esta herramienta realiza las operaciones de cruce y
mutación; pero como la forma de realizar la
representación de datos, la generación de datos
iniciales y la calificación de resultados es específica de
cada problema en particular, estas tareas quedan en
manos de quién utilice las herramientas.
4.1. Cruce
La operación de cruce consiste en combinar los genes
de dos individuos para generar un nuevo individuo. La
herramienta realiza el cruce de forma que el tamaño de
la población se mantenga constante, y que la totalidad
de los individuos de la nueva generación sea resultado
de los cruces con los individuos de la generación
anterior [2].
Para la selección de los individuos que participarán en
el cruce, antes es necesario determinar la calificación
relativa de cada individuo. Esta se calcula según la
siguiente formula.
En donde N es la cantidad de individuos de la
población. La Tabla 1, nos muestra un ejemplo de los
resultados obtenidos con una población de 5
individuos.
Individuo
Cal. Absoluta
Cal. Relativa
A
300
25,00
B
100
8,33
C
250
20,83
D
50
4,17
E
500
41,67
Tabla 1. Población de 5 Individuos
Luego, la clase Poblacion selecciona los individuos
que participarán del cruce, para ello se crea una tabla
de cruce de N filas y 2 columnas [2].
Los individuos son cargados en la tabla de tal forma
que los individuos con mayor calificación relativa
tengan mayores probabilidades de ser sorteados. Para
realizar el sorteo, se asigna un área de una ruleta a cada
individuo de acuerdo con su calificación relativa, y
luego se procede a generar en forma aleatoria números
del 0 al 100. Luego, el individuo cuya área salió
sorteada es agregado a la tabla de cruce [2].
INFORMÁTICA – Nº 5 – AÑO 2009
27
Una vez creada la tabla de cruces, se realiza el cruce
entre los individuos de la misma fila. La clase
Individuo es la que se encarga de realizar el cruce.
La clase Individuo puede realizar el cruce de varias
formas dependiendo de los puntos de cruce. Estos
puntos se pueden definir en forma manual, o dejar que
la clase Individuo los genere en forma aleatoria.
4.2. Mutación
La clase Población utiliza el valor de un parámetro
denominado porcentaje de mutación, el cual
determinará con que probabilidad un individuo será
modificado. Para la selección se procede a recorrer los
individuos de la población; para cada individuo se
genera un valor aleatorio desde 1 hasta 100, si el valor
generado es menor o igual que el porcentaje de
mutación, entonces ese individuo será seleccionado
para la mutación [2].
Una vez un individuo haya seleccionado, la clase
Individuo se encarga de realizar la mutación. La clase
Individuo utiliza el valor de un parámetro denominado
intensidad de mutación. Para realizar la mutación se
procede a recorrer cada gen; se vuelve a generar un
valor aleatorio entre 1 y 100, y en caso de que el valor
generado sea menor o igual a la intensidad de mutación
la clase Gen generará un nuevo valor para dicho gen
[2].
6. Trabajos Anteriores
Este trabajo está basado en un trabajo titulado
Optimización de horarios de Examen Utilizando
algoritmos genéticos; el cual consiste en la creación de
un algoritmo que permita optimizar el horario de
exámenes de la facultad Politécnica.
El trabajo tiene en cuenta el horario en el que se puede
rendir cada examen, y aplica estas restricciones en el
momento de generar los horarios iniciales.
La función de calificación utilizada está basada en la
Ley de Coulomb, que fue utilizada para separar los
exámenes (como si hubiera una fuerza de repulsión
entre cargas del mismo signo).
Los algoritmos de mutación y cruce son similares a los
utilizados en esta herramienta, con la diferencia que los
puntos de cruce son siempre aleatorios, o sea, no se
pueden elegir los puntos de cruce.
7. Conclusión
Utilizando esta herramienta se puede agilizar mucho la
programación de algoritmos genéticos, debido a que
contiene gran parte del código, que es constante para la
mayoría de los problemas. También se puede destacar
el hecho de que sirve como guía de programación, por
que define cuales son los métodos generales que serán
necesarios para la realización del código; lo que
permite su utilización para fines didácticos.
3. Discusión
Actualmente la herramienta cuenta con las 3 clases
discutidas anteriormente y también con una clase
funciones que contiene funciones varias, como generar
números aleatorios entre 2 números, funciones para
desordenar el orden de elementos de un vector, y otras
más que se utilizan dentro de la programación. Estas
funciones también pueden ser aprovechadas por quién
utilice las herramientas.
Un objetivo adicional, es el de agregar clases que
permitan hallar el mejor valor para los parámetros que
influyen en las operaciones arriba mencionadas; puesto
que estos valores pueden ser distintos para cada
problema en particular. Encontrar los valores óptimos
ayudará a aumentar la velocidad de convergencia a un
resultado óptimo.
Referencias
[1] Wikipedia, the free enciclopedia. Genetic
algorithm [en linea]
<http://en.wikipedia.org/wiki/Genetic_algorithm>
[16 – 06 – 2009].
[2]
Morel, S. Optimización de Horarios de Examen
Utilizando Algoritmos Genéticos. XVI Jornadas
de Jóvenes Investigadores AUGM, página 188.
[3] Roulo, M. How to avoid traps and correctly
override methods from java.lang.Object
[en linea] <http://www.javaworld.com/javaworld/
jw-01-1999/jw-01-object.html> [05 – 03 – 2009].
Estos valores pueden ser diferentes para cada etapa de
la resolución de un problema, por ejemplo, durante la
etapa inicial es probable que sea mejor tener un
porcentaje de cruce alto, y uno de mutación bajo,
mientras que en la etapa final es probable que sea
mejor tener un mayor porcentaje de mutación para salir
de estancamientos.
INFORMÁTICA – Nº 5 – AÑO 2009