Durante la presentación tuvimos muchos curiosos haciendo toda clase de preguntas relacionadas tanto con los resultados como con la metodología. Respecto a la metodología, se trata de aplicar la estadística a la selección de parámetros y así no elegir los parámetros según dicen otros autores o simplemente probando varias veces. Respecto a los resultados, nos muestran que para un Algoritmo Evolutivo y para los parámetros y problemas que hemos testeado, lo que más influencia puede tener en el resultado final es la combinación de operadores que elijamos y el tipo de selector. También se concluye que no siempre se consiguen buenos resultados aplicando más generaciones, ni utilizando una población de un tamaño mayor.
O al menos no todo el tiempo, también podemos hacer cosas ‘de provecho’ con ellas… :D
Como expuse en la reunión del pasado Viernes 24, ultimamente se estan adaptando y desarrollando muchos de los algoritmos que todos conocemos (AGs, GPs, RNs, PSOs, etc), para el aprovechamiento de estas unidades de procesamiento, optimizadas para la computación en paralelo (de forma masiva, ya que cuentan con decenas o cientos de procesadores dedicados al cálculo en coma flotante).
En la siguiente presentación, se exponen sus ventajas e inconvenientes, así como se muestran algunas de las herramientas y APIs utilizadas para realizar dichas implementaciones, como por ejemplo CUDA.
Last week in conjunction with PPSN XI, the Self* 2010 and PARCO 2010 workshops were held in Kraków (Poland) where we were presenting some of our most recent works. Specifically, you can find the respective presentations below.
A Self-Organized Critically Online Adjustment of Genetic Algorithms’ Mutation Rate
This paper describes an alternative mutation control scheme for Genetic Algorithms (GAs) inspired by the Self-Organized Criticality (SOC) theory. The strategy, which mimics a SOC system known as sand pile, is able to generate mutation rates that, unlike those generated by other methods of adaptive parameter control, oscillate between very low values and cataclysmic mutations. In order to attain the desired behaviour, the sandpile is not just attached to a GA; it is also modified in order for its conduct to reflect the stage of the search, i.e., the fitness distribution of the population. Due to its characteristics, the sandpile mutation arises as a promising candidate for efficient and yet simple and context-independent approach to dynamic optimization. An experimental study confirms this assumption: a GA with sandpile mutation outperforms a recently proposed SOC-based GA for dynamic optimization. Furthermore, the proposed method does not increase traditional GAs’ parameter set.
Influence of the Population Structure on the Performance of an Agent-based Evolutionary Algorithm
The Evolvable Agent model is a Peer-to-Peer Evolutionary Algorithm which focuses on distributed optimization over Peer-to-Peer infrastructures. The key idea of the model is that every agent-individual is designated as a peer and adopts a decentralised population structure defined by the Peer-to-Peer protocol newscast. In that context, this work aims to compare performances of the approach
when using two additional population structures other than newscast: a ring and a Watts-Strogatz topology.
La Universidad de Waterloo Computer Science Club con la colaboración de Google organizan un año más el Google AI Challenge. Este año, el objetivo es crear un algoritmo que juegue a Planet Wars de la forma más inteligente posible.
Problema:
Planet Wars es un juego de estrategia en el espacio exterior. El objetivo es conquistar todos los planetas del mapa o eliminar todas las naves enemigas. Podemos ver un ejemplo de juego en el siguiente vídeo.
Planet Wars está inspirado en Galcon, un popular juego de Iphone, Android y PC. Puedes jugar a Galcon aquí para hacerte una idea del juego y sus estrategias. Es un juego basado en turnos. El bot a implementar es una función que recibe la lista de planetas y flotas y devuelve una lista de órdenes.
Cada planeta, tiene los siguientes campos o propiedades:
Coordenadas (x,y)
ID del propietario
Número de naves alojadas
Tasa de crecimiento
Los planetas neutrales tienen un ID de cero, mientras que los de tu bot tiene el ID de 1 y los enemigos el ID de 2. Tras cada turno, el número de naves en los planetas no neutrales aumenta de acuerdo a la Tasa de crecimiento de dicho planeta.
Las flotas son los números de colores que vuelan entre los planetas. Cuando una flota llega a su planeta de destino, pueden suceder dos cosas. Si el planeta del destino pertenece al bot, las naves se añaden como refuerzos al planeta. En caso contrario, las naves de la flota se restan a las naves que ocupan en ese momento el planeta. Si el resultado es menor que cero, entonces el bot gana el control del planeta. Si el resultado es exactamente 0, entonces el control del planeta no cambia.
Las flotas tienen los siguientes campos o propiedades:
ID del propietario
Número de náves
ID Planeta de origen
ID Planeta de destino
Longitud total del viaje
Número de turnos hasta la llegada
El bot puede emitir tantas órdenes como quiera durante el turno. Cada orden especifica un planeta de origen, un planeta de destino y un número de naves. Una vez que la orden se ejecuta, el número determinado de naves abandona el planeta para ir hacia su destino.
El juego termina cuando solo queda un solo jugador o se excede un determinado número de turnos.
Timeline:
1 Septiembre 2010: publicación del material oficial.
10 Septiembre 2010: Fecha de inicio oficial.
27 Noviembre 2010: Fecha límite de entrega.
1 Diciembre 2010: Los resultados finales y la clasificación final se darán a conocer.
Reglas:
La clasificación final se determinará mediante un torneo computerizado diseñado por la organización. El ranking actual en la clasificación no son los oficiales y pueden no ser representativos de los resultados finales.
Solo se puede poseer una cuenta. Si usted mantiene el control efectivo sobre más de una cuenta incluso si las cuentas son nominalmente propiedad de otra persona, las cuentas serán descalificadas.
Su programa no puede tomar más de un segundo en hacer cualquier jugada personal. Si se quieren hacer cálculos intensivos, asegúrese de agregar código que compruebe el tiempo a intervalos regulares para que no sobrepase la cuota de un segundo. Si el programa viola la cuota de tiempo, será suspendido.
Los mecanismos que se consideren que violan el espíritu de la competencia leal y deportiva será descalificado sin ninguna posibilidad de apelación. En particular, la exploración de memoria, perder juegos de forma intencionada y la conducta condicionada al ID del oponente están prohibidos.
El código no puede escribir en archivos. Sin embargo, puede leer archivos en el directorio de representación, que será el directorio actual.
El uso de múltiples procesos o hilos está prohibido.
Cualquier intento de perturbar el funcionamiento normal del software de los servidores del concurso dará lugar a la intervención de los agentes del orden.
Queda reservado el derecho a modificar estas reglas en cualquier momento y sin previo aviso.
Paquetes iniciales de software:
La organización proporciona unos paquetes de software inciales. Cada paquete es un archivo ZIP que contiene:
Una entrada sencilla y funcional para ser usada como punto incial.
Las herramientas que permiten ejecutar el bot y un entorno gráfico de ejecución.
Algunos oponentes para testear nuestros bots.
Un centenar de mapas generados al azar para testeo.
Los paquetes iniciales se encuentran disponibles para C++, Java, Python y C#.
En la web de la organización pueden encontrarse la especificación funcional de las herramientas así como guías de estrategias y decisiones sobre el problema.
Llevamos programando algoritmos evolutivos desde que casi echamos los dientes en la universidad, y sin embargo la preocupación y la investigación va más por el camino de cambiar el algoritmo, y no cambiar la implementación, y eso que tanto los lenguajes como las librerías como las prácticas de programación han cambiado enormemente en estos años. En este artículo, que se va a presentar en el congreso de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados que se integra dentro del CEDI que se está celebrando en Valencia, tratamos de hacer precisamente eso: abordar un algoritmo evolutivo (hecho en Perl desde el punto de vista de la programación, y demostrar que las mejoras en tiempo de ejecución que se pueden obtener alcanzan, en ocasiones, varios órdenes de magnitud.
El trabajo se titula
Optimizando la implementación de algoritmos evolutivos. JJ Merelo, Pedro Castillo, Juan Luís Jiménez Laredo and María Isabel García Arenas
Tenéis la presentación
Y también el código cuyas mejoras podéis visualizar a través de las diferencias entre las versiones de fichero que te permite hacer Launchpad
GeNeura Team 