1

Prediccion de posibles equipos ganadores delmundial 2014 con algoritmos geneticos

J. Saraguro1 R. Leon2 H. Paz3

Resumen—En este artıculo se da una explicion de losalgoritmos geneticos, y de los distintos metodos que existen paragenerar nuevas poblaciones asi como tambien los mecanismos deevalucion(Fitness) para evaluar el funcionmiento del algoritmogenetico y en base a la recopilacion bibliografica poder realizaruna aplicacion para determinar cuales son los cuatro equiposcon mayor probabilidad de ganar el mundial de futbol Brasil2014 con la ayuda de algoritmos geneticos.

Index Terms—Fitness, Algoritmos Geneticos, Cruce, Mutacion,Poblacion.

I. INTRODUCCION

EN el presente articulo con la ayuda de algoritmosgeneticos se pretende determinar las cuatro equipos del

mundial 2014 con mayor posibilidad de convertirse en elganador. Para obtener este objetivo se describira conceptosbasicos acerca de los algoritmos geneticos como tambien sufuncionamiento y utilizacion en la rama de la inteligenciaartificial. Esta prediccion se la realizara mediante el uso deuna aplicacion practica la cual sera desarrollada en el lenguajede programacion Java con la ayuda de la librerıa JGAP.

II. ALGORITMOS GENETICOS

Una de las capacidades de los seres humanos es tener laposibilidad de predecir el comportamiento del entorno que lorodea, tal como lo pretende realizar la inteligencia artificial.Como parte de la inteligencia artificial estan presentes losalgoritmos geneticos, que hoy en dıa son muy utilizados pararesolver multiples problemas del mundo real. Son algoritmosde busqueda basados en la mecanica de la seleccion naturaly de la genetica.[2]

Para obtener la solucion estos algoritmos utilizan lainformacion historica para encontrar nuevos puntos de vistade una solucion optima del problema planteado, o la mejorade los resultados.

El funcionamiento de un algoritmo genetico trata queen cada generacion se crea un conjunto nuevo de cadenas

1J. Saraguro, Universidad Nacional de Loja, Loja, Ecuador jlsaragu-rop@unl.edu.ec

2R. Leon, Universidad Nacional de Loja, Loja, Ecuadormrleonr@unl.edu.ec

3Tutor. H. Paz, Universidad Nacional de Loja, Loja, Ecuadorhpaz@unl.edu.ec

utilizando bits y partes mas adecuadas del progenitor. Esteproceso aleatorio no resulta nada facil o simple.

Entonces estos algoritmos estan basados en conocimientosde la evolucion biologica, ya que en esta evolucion se llevan acabo a base de interacciones locales entre individuos, y entreestos y lo que les rodea, ya sea por conseguir recursos como:comida, agua y refugio y la persona que atraiga mas personasa perseguir su meta sera el que tenga mas probabilidad desupervivencia.

Por tanto, cuando Holland se enfrento a los algoritmosgeneticos, los objetivos de su investigacion fueron dos:

1. Imitar los procesos adaptativos de los sistemas naturales.2. Disenar sistemas artificiales (normalmente programas)

que retengan los mecanismos importantes de lossistemas naturales.

Podemos considerar que los algoritmos geneticos tienen, almenos, estos elementos en comun:

Poblaciones de cromosomasSeleccion en base a su capacidadCruces para producir descendencia nuevaMutacion aleatoria de la nueva descendencia.

II-A. Algoritmos geneticos simples

El Algoritmo Genetico Simple, tambien denominadoCanonico, se representa en la figura 1, se necesita una codi-ficacion o representacion del problema, que resulte adecuadaal mismo.

Figura 1. Pseudocodigo de un Algoritmo Genetico Simple

Ademas se requiere una funcion de ajuste o adaptacional problema, la cual asigna un numero real a cada posible

2

solucion codificada. Durante la ejecucion del algoritmo,los padres deben ser seleccionados para la reproduccion,a continuacion dichos padres seleccionados se cruzarangenerando dos hijos, sobre cada uno de los cuales actuara unoperador de mutacion.[3]

Aplicar el algoritmo genetico al campo de la resolucionde problemas habra que seguir una serie de pasos, como esconseguir que el tamano de la poblacion sea lo suficientementegrande para garantizar la diversidad de soluciones. Se aconsejaque la poblacion sea generada de forma aleatoria para obtenerdicha diversidad. [1]

Los pasos basicos de un algoritmo genetico son:Evaluar la puntuacion de cada uno de los cromosomasgenerados.Permitir la reproduccion de los cromosomas siendo losmas aptos los que tengan mas probabilidad de reprodu-cirse.Con cierta probabilidad de mutacion, mutar un gen delnuevo individuo generado.Organizar la nueva poblacion.

Estos pasos se repetiran hasta que se de una condicion determinacion. Se puede fijar un numero maximo de iteracionesantes de finalizar el algoritmo genetico o detenerlo cuando nose produzcan mas cambios en la poblacion.[1]

Figura 2. Estructura de un Algoritmo Genetico Simple

III. OPERADORES GENETICOS

Para el paso de una generacion a la siguiente se aplicanoperadores geneticos. Los mas usados son los operadores deseleccion, cruce, copia y mutacion.

1. Seleccion.- Los algoritmos de seleccion seran los en-cargados de escoger que individuos van a disponer deoportunidades de reproducirse.En este tipo de algoritmos se pretende imitar loque ocurre en la naturaleza, se ha de otorgar unmayor numero de oportunidades de reproduccion a losindividuos mas aptos.[5]

Este operador escoge cromosomas entre la poblacionpara efectuar la reproduccion. Cuanto mas capaz

sea el cromosoma, mas veces sera seleccionado parareproducirse.[6]

Existen dos formas de emplear este algoritmo las cualesson:

a) Seleccion por Ruleta: Propuesto por DeJong, esposiblemente el metodo mas utilizado. A cadaindividuo de la poblacion se le asigna una parteproporcional a su ajuste de una ruleta, de talforma que la suma de todos los porcentajes es launidad.

En este tipo de seleccion los mejores individuosreciben una porcion de la ruleta mayor quela recibida por los peores. Para seleccionar unindividuo basta con generar un numero aleatoriodel intervalo [0..1] y devolver el individuo situadoen esa posicion de la ruleta.[5]

Es un metodo muy sencillo, pero ineficiente amedida que aumenta el tamano de la poblacion(su complejidad es O(n2)). Presenta ademas elinconveniente de que el peor individuo puede serseleccionado mas de una vez.[5]

b) Seleccion por Torneo: La idea principal de estemetodo consiste en realizar la seleccion en basea comparaciones directas entre individuos. Existendos versiones:

Determinıstica: en esta version se selecciona alazar un numero p de individuos (generalmentese escoge p = 2). De entre los individuosseleccionados se selecciona el mas apto parapasarlo a la siguiente generacion. [5]

Probabilıstica: se diferencia en que en vez deescoger siempre el mejor, se genera un numeroaleatorio del intervalo [0.,1], si es mayor queun parametro p (fijado para todo el procesoevolutivo) se escoge el individuo mas alto y encaso contrario el menos apto. Generalmente ptoma valores en el rango 0,5 < p <= 1.

2. Cruce.- Una ves seleccionados los individuos, estosson combinados para producir la descendencia quese formara la nueva generacion. la idea principal delcruce se basa en que, si se toman dos individuoscorrectamente adaptados al medios y se obtiene unadescendencia que comparta genes de ambos, existela posibilidad de que los genes heredados sean loscausantes de la bondad de los padres.[5]

Basicamente la labor de este operador es elegir unlugar, y cambiar las secuencias antes y despues deesa posicion entre dos cromosomas, para crear nuevadescendencia.[6]

3

Al compartir las caracterısticas buenas de dos indivi-duos, las descendencia o al menos parte de ella, deberıatener una bondad mayor de cada unos de los padres porseparado.Existen multitud de algoritmos de cruce, perolos mas utilizados son:

a) Cruce de 1 punto: Es la mas sencilla de las tecnicasde cruce. Una ves seleccionados dos individuos secortan sus cromosomas por un punto seleccionadoaleatoriamente para generar dos segmentos diferen-ciados en cada uno de ellos: la cabeza y la cola.Se intercambian las colas entre los dos individuospara generar los nuevos descendientes.

Figura 3. Cruce de 1 Punto

b) Cruce de 2 puntos: Se trata de una modificaciondel cruce de 1 punto. En vez de cortar por ununico punto los cromosomas de los padres comoen el caso caso anterior se realizan dos cortes.Se debera tener en cuenta que ninguno de estospuntos de corte coincida con el extremo de loscromosomas para garantizar que se originen tressegmentos. Para generar la descendencia se escogeel segmento central de uno de los padres y lossegmentos laterales del otro padre.[5]

Figura 4. Cruce de 2 Puntos

c) Cruce Uniforme: Esta tecnica implica lageneracion de una mascara de cruce de valoresbinarios. Si en una de las posiciones de lasmascara hay un 1, el gen situado en esa posicionen uno de los descendientes se copia del primerpadre. Si por lo contrario hay un 0 el gen secopia del segundo padre. Para producir el segundodescendiente se intercambian los papeles de lospadres, o bien se intercambia la interpretacion delos unos y los ceros de la mascara de cruce.[5]

La descendencia contiene una mezcla de genes decada uno de los padres. El numero efectivo depuntos de cruce es fijo pero sera por termino medioL/2, siendo L la longitud del cromosoma (numerode alelos en representaciones binarias o de genesen otro tipo de representaciones).

3. Copia.- Es otra estrategia reproductiva para la obtencionde una nueva generacion a partir de la anterior. Adiferencia del cruce, se trata de una estrategia de

Figura 5. Cruce Uniforme

reproduccion asexual. Consiste simplemente en la copiade un individuo en la nueva generacion.

El porcentaje de copias de una generacion a la siguientees relativamente reducido, pues en caso contrario secorre el riesgo de una convergencia prematura de lapoblacion hacia ese individuo.

4. Mutacion.- la mutacion de un individuo provoca quealguno de sus genes, generalmente uno solo, varıe suvalor de forma aleatoria.

Aunque se pueden seleccionar los individuosdirectamente de la poblacion actual y mutarlos antes deintroducirlos en la nueva poblacion, la mutacion se lapuede utilizar de manera conjunta con el operador decruce, es decir primero se seleccionan dos individuos dela poblacion para realizar el cruce. Si el cruce tiene exitoentonces uno de los descendientes, o ambos se muta. [5]

IV. FUNCION DE EVALUACION DE LOS ALGORITMOSGENETICOS

Para el correcto funcionamiento de un algoritmo geneticose debe poseer un metodo que indique si los individuos dela poblacion representa o no buenas soluciones al problemaplanteado. De esto se encarga la funcion de evaluacion, queestablece una medida numerica d la bondad de una solucionla cual recibe el nombre de ajuste.[5]

Se pueden diferencias cuatro tipos de ajuste o fitness[4]:

Fitness Puro: r(i,t)

Es la medida de ajuste establecida en la terminologıanatural del propio problema. La ecuacion 1 establece elcalculo del valor de bondad de un individuo i en uninstante t (o generacion).

r(i, t) =

Nc∑j=1

|s(i, j)− c(i, j)| (1)

Siendo:

s(i, j) = valor deseado para el individuo i en el caso j.c(i, j) = valor obtenido por el individuo i en el caso j.

4

Nc = numero de casos.

En problemas de maximizacion los individuos con unfitness puro elevado seran los mas interesantes, por elcontrario en los problemas de minimizacion interesaranlos individuos con un fitness puro reducido.

Fitness Estandarizado: s(i, t)

Para solucionar esta dualidad ante problemas de mini-mizacion o maximizacion se modifica el ajuste puro deacuerdo a la ecuacion 2.

s(i, t) =

{r(i, t) minimizacionrmax − r(i, t) maximizacion (2)

En el caso de minimizacion se emplea directamentela medida de fitness puro, si el problema es demaximizacion se resta de una cota superior rmax delerror de fitness puro. Empleando esta metrica la bondadde un individuo sera mayor cuanto mas cercano este acero el valor del ajuste.

Por lo tanto, dentro de la generacion t, un individuoi siempre sera mejor que uno j si se verifica ques(i, t) < s(j, t).

Fitness Ajustado: a(i, t)

Se obtiene aplicando la transformacion reflejada en laecuacion 3 al fitness estandarizado.

a(i, t) =1

1 + s(i, t)(3)

De esta manera, el fitness ajustado tomara siemprevalores del intervalo [0..1]. Cuando mas se aproximeal fitness ajustado de un individuo a 1 mayor sera subondad.

Fitness Normalizado: n(i, t)

Los diferentes tipos de fitness vistos hasta ahora hacenreferencia unicamente a la bondad del individuo en cues-tion. El fitness normalizado introduce un nuevo aspecto:indica la bondad de una solucion con respecto al resto desoluciones representadas en la poblacion. Considerandouna poblacion de tamano N, se obtiene segun la ecuacion4

n(i, t) =a(i, t)∑N

k=1 a(k, t)(4)

Al igual que el fitness ajustado, siempre tomara valoresdel intervalo [0.,1], con mejores individuos cuanto masproximo este a la unidad. Pero a diferencia de antes,un valor cercano a 1 no solo indica que ese individuo

represente una buena solucion al problema, sino queademas es una solucion destacadamente mejor que lasproporcionadas por el resto de la poblacion.

La suma de los valores del fitness normalizado de todoslos individuos de una poblacion dara siempre 1. Este tipode ajuste es empleado en la mayorıa de los metodos deseleccion proporcionales al fitness.

V. EJEMPLO EN JAVA

La aplicacion esta desarrollada en le lenguje deprogramacion JAVA utilizando la librerıa JGAP la cualnos permite el desarrollo de Algoritmos Geneticos.

Como se explico en la introduccion esta aplicacion nospermite predecir los cuatro equipos con mayor probabilidadde ganar el mundial Brasil 2014 con la ayuda de algoritmosgeneticos.

En la figura 6 se presenta la pantalla principal de laaplicacion.

Figura 6. Pantalla Principal

En la figura 7 observamos los equipos que se encuentranclasificdos al mundial 2014 los cuales van ha ser nuestrapoblacion.

Figura 7. Listado de Equipos

En la figura 8 observamos la informcion de cada unode los paises que se encuentran en listado, dentro de lainformacion contamos con: datos de los tres ultimos partidos,grupo al cual pertenecen en el mundial, el numero de copasde mundiales que ha ganado y el puesto en el rankig de laFIFA; en base ha esta informacion se dara un puntaje a cadaequipo para su evaluacion.

5

El boton actulizar nos permtira editar la informacion de cadauno de los equipos.

Figura 8. Datos de los Equipos

Al presionar el boton predecir el resultado de esta accionse presenta en la figura 9, en la cual se observa el resultado dela ejecucion de la aplicacion, es decir nos presenta los cuatroequipos con mayor probabilidad de ganar el mundial Brasil2014.

Figura 9. Datos de los Equipos

En la figura 10 se observa la evolucion segun se como seejecuta la aplicacion hasta que encuentra el resultado deseado.

Figura 10. Datos de los Equipos

Con lo respecta al codigo de la aplicacion lo esencialse centra en la clase EFitness la cual contiene los metodosnecesarios para que la poblacion evolucione y ası llegar alresultdo deseado.

En la figura 11 observamos el metodo evalute el cual nospermite determinar cual es la mejor opcion para el resultadodeseado.

En la figura 12 observamos el metodo getGenreScore, nospermite obtener el puntje de acuerdo a la evaluacion .

VI. CONCLUSIONES

Los algoritmo geneticos son de gran ayuda para resolverproblemas de optimizacion cuando su espcio de busquedesta dentro de un rango.

La calidad de evalucion del algoritmo geneticodependara de la logica que se codifique en el fitness.

La seleccion de buenos padres para la generacion de unnueva poblacion dependera del tamano de la poblacionoriginal.

Figura 11. Metodo Evluate de la Clase Fitness

Figura 12. Metodo getGenreScore de la Clase Fitness

VII. RECOMENDACIONES

Relizar un buena logica de comparacion entre losparametros del algoritmo genetico para obtener un buenresultdo.

El uso de la librerıa JGAP para el desarrollo dealgoritmos geneticos en el lenguaje de programacionJAVA

El uso de la librerıa JAVACSV para el manejo dearchivos CSV.

El codigo de la aplicacion se encuentra disponible en:https://github.com/mricharleon/PrediccionMundialAlgoritmosGeneticos.git

REFERENCIAS

[1] P. Antonio A. Jorge. Algoritmos geneticos, 2005.[2] Universidad de paıs vasco. Algoritmos geneticos, 2014.[3] Intelligent Systems Group. Algoritmos geneticos, 2001.[4] J. R. Koza. Genetic Programming: On the Programming

of Computers by Means of Natural Selection. 1992.[5] G. Marcos. Introduccion a los algoritmos geneticos, 2012.

6

[6] R. Piedad. Introduccion a los algoritmos geneticos y susaplicaciones, 2011.

BIOGRAFIA

Jenny Liliana Saraguro Pacheco Estudiante de laCarrera de Ingierıa en Sistemas, Decimo Modulo.Loja, Ciudad Loja - Ecuador, 2014.

Mario Richar Leon Ramon , estudiante de laCarrera de Ingierıa en Sistemas, Decimo Modulo.Loja, Ciudad Loja - Ecuador, 2014.