CHAC, the Military Ants in the press around the world

Last Friday, 6th of November some news related to the mini-simulator which we have developed for the implementation and test of the algorithms based in the ants’ behaviour to search for the best path (attending to the speed and safety) in a military battlefield, were published. :)

This new appeared firstly (in May some days after my PhD Tesis lecture) at the Press  site of the University of Granada.

But last Friday, the new was published by some other webs, as AlphaGalileo, EurekAlert and RedOrbit. Then it appeared in many other scientific news webs (AECC, SoftPedia, ScienceDaily, Physorg, LabSpaces, TMCnet, First Science or Science Centric).

In addition it has appeared in some general news online sites (mainly in Asia): Sindh Today, New Kerala, TopNews.in, South Asia News, CBNews and Breaking News among others.

Finally, the new has been also introduced in some blogs, forums and social nets (Blog.Taragana, BizFace, Defense Forum India, Twitter).

Thanks a lot for the interest in our work and let us know if you need some documentation or other stuff concerning to it. ;)

The application can be downloaded from our group’s project site in forja.rediris (is the project hCHAC), and it has been developed under a GPL license, so it is free to download, use and even modify, but following this license restrictions. :)

Best regards.

[IDC'09] Studying the Cache Size in a gossip-based evolutionary algorithm

Last week we were presenting the work Studying the Cache Size in a Gossip-Based Evolutionary Algorithm [BibTex] in the 3rd International Symposium on Intelligent Distributed Computing hold in Ayia Napa (Cyprus).

Gossiping is a self-organized and decentralized approach to distribute algorithms through Peer-to-Peer (P2P) networks.
Based on such an approach, the Evolvable Agent model is a P2P Evolutionary Algorithm (EA) whose
population structure is defined by the gossiping protocol newscast, a protocol that behaves asymptotically as a small-world graph. This paper explores the impact of different cache sizes on the algorithm performance given that cache size is the only tunable parameter in newscast. To this aim, the problem generator wP-PEAKS and the multimodal deceptive problem MMDP have been used as benchmarks.
Results show that the quality of the solutions and the run-time of the algorithm are not altered when changing the settings of the cache size. This fact points out that newscast is a robust gossiping protocol for tackling distributed evolutionary computation.

Ants and Estimation of Distribution Algorithms (ECAL 2009)

Last week I went to Budapest to present the paper “An Ant-Based Rule for UMDA’s Update Strategy” in the 10th European Conference on Artificial Life (ECAL 2009). ECAL is one of the leading congresses in the area and some of the most relevant work in the Artificial Life research field is presented there in first hand. It is held every two years and this time the capital of Hungary was chosen to host the event. The Academy of Sciences, in Roosevelt tér (square), on the banks of the Danube and with a perfect view on the Castle and the hills of Buda was ECAL’s headquarters for 4 days.

Only 30% of the accepted papers were selected for oral presentation. The remaining was scheduled for poster sessions (although all the accepted papers were published in full-length in two LNCS volumes) that lasted…the whole day! I cannot understand why not all the congresses follow a line similar to PPSN (a poster-only congress, with 90 minutes sessions) when it comes to poster sessions, but ECAL’s strategy is, my opinion, particularly ineffective and exhausting.

ECAL 2009, Budapest, Academy of Sciences

As for our paper, it presents a study on an alternative update strategy for the Univariate Marginal Distribution Algorithm based on the ACO computational paradigm and first presented here. The aim is to control the balance between exploration and exploitation in order to avoid diversity loss, reduce the optimal population size and improve the scalability of the algorithm on hard problems. The results confirmed the hypothesis. This is the abstract:

This paper investigates an update strategy for the Univariate Marginal Distribution Algorithm (UMDA) probabilistic model inspired by the equations of the Ant Colony Optimization (ACO) computational paradigm. By adapting ACO’s transition probability equations to the univariate probabilistic model, it is possible to control the balance between exploration and exploitation by tuning a single parameter. It is expected that a proper balance can improve the scalability of the algorithm on hard problems with bounded difficulties and experiments conducted on such problems with increasing difficulty and size confirmed these assumptions. These are important results because the performance is improved without increasing the complexity of the model, which is known to have a considerable computational effort.

Autonomic computing at the Friday paper seminar

Autonomic computing is one of those things that involves a certain amount of hand-waving but that corresponds to a really simple idea: tell a computing system what’s expected of it, instead of a step-by-step account of what we want it to do. We can tell a network we expect 99% uptime, or a database system to improve its performance by 5%, or a webserver to try and serve ten thousand simultaneous connections. Most systems will look back at you slack-jawed, but, well, that’s why the paper we’re dealing with today is called Research challenges of autonomic computing, which is written by Jeffrey O. Kephart, an IBM researcher which has produced lots of fine papers on the topic.
What are, then, the challenges and how does all that relates to our own research? The idea is to achieve what are collectively called self-star properties: self configuration, self-management, self-protection and self-healing. That is, let the system itself handle as a body, with each component being like an organ that performs its own function but is also aware that must work for the collective good and obtain an emergent property like body temperature or oxygen supply. That double function leads to architectural challenges, but also to algorithmic problems like how to be aware of what the system at large is doing and how it is behaving, how to learn new responses to changes in environment, and, eventually, how to optimize the system configuration and behaviour to attain desired targets set by the user.
And that’s where our own research comes in: the evolvable-agent architecture, to a point, configures an overlay network to take advantage of all its resources but it’s not there yet: it would be necessary to include more self-star properties such as self-management and self-configuration, so that the user should have to include just performance targets (obtain solution in a certain amount of time), and the system would set its parameters itself to attain it. A step in the right direction, anyways.

[GECCO'09] Improving Genetic Algorithms Performance via Deterministic Population Shrinkage

This year the Genetic and Evolutionary Computation Conference (GECCO) took place in Montréal (Québec-Canada) where we were presenting our last work in collaboration with the Laboratoire de Vision et Systèmes Numériques de l’Université Laval in Quebec City:

• Improving Genetic Algorithms Performance via Deterministic Population Shrinkage

Despite the intuition that the same population size is not needed throughout the run of an Evolutionary Algorithm (EA), most EAs use a fixed population size.
This paper presents an empirical study on the possible benefits of a Simple Variable Population Sizing (SVPS) scheme on the performance of Genetic Algorithms (GAs). It consists in decreasing the population for a GA run following a predetermined schedule, configured by a speed and a severity parameter. The method uses as initial population size an estimation of the minimum size needed to supply enough building blocks, using a fixed-size selectorecombinative GA converging within some confidence interval toward good solutions for a particular problem. Following this methodology, a scalability analysis is conducted on deceptive, quasi-deceptive, and non-deceptive trap functions in order to assess whether SVPS-GA improves performances compared to a fixed-size GA under different problem instances and difficulty levels. Results show several combinations of speed-severity where SVPS-GA preserves the solution quality while improving performances, by reducing the number of evaluations needed for success.

Conferencias en el Máster en Tecnologías Informáticas Avanzadas de la UHU

El pasado viernes asistí a tres charlas que impartó el profesor Francisco Herrera del departamento de CCIA de la Universidad de Granada. En la primera de ellas, “Data Mining: From the Top 10 Algorithms to the New Challenges”, el profesor Herrera habló de los 10 mejores algorimos que se aplican a la minería de datos según (ICDM ‘06), así como de los 10 mayores retos de la minería de datos actual. La siguente charla, titulada “Data Complexity” estaba dedicada a los intentos de dar fundamento teórico a la minería de datos. Se habló de los modos de caracterizar los conjuntos de datos con el fin de recomendar que algoritmo funciona mejor con un determinado conjunto de datos. La última de las tres conferencias “How must I do my Experimental Study?” trataba los test estadísticos que deben aplicarse a los experimentos en un trabajo de investigación con el fin de justificar, por ejemplo, la calidad de un nuevo algoritmo. Se trató el uso de métodos estadísticos no-paramétricos que funcionan bien en conjuntos de datos que no siguen una distribución normal, cosa que sucede en la mayoría de los problemas reales. Este tipo de test, en palabras del profesor Herrera, empiezan a ser indispensables cuando se quiere publicar en revistas científicas de primer nivel. A continuación aportaré alguna información adicional sobre estas conferencias.

“Data Mining: From the Top 10 Algorithms to the New Challenges”

Lo candidatos al Top 10 debían cumplir algunos requisitos, como por ejemplo que tuviesen como mínimo 50 citas recientes.  De los inicialmente propuestos quedaron sólo 18 algoritmos finalistas. Los resultados del estudio fueron publicados en el artículo “Top 10 algorithm in data mining” y posteriormente en un libro con el mismo título. La siguiente tabla muestra a los finalistas clasificados en categorías.

Categoría	Finalistas
Classification	1. C4.5, 2. CART, 3. K Nearest Neighbours (kNN), 4. Naive Bayes
Statistical Learning	5. SVM,  6. EM
Association Analysis	7. Apriori,  8. FP-Tree
Link Mining	9. PageRank, 10. HITS
Clustering	11. K-Means,  12. BIRCH
Bagging and Boosting	13.  AdaBoost
Sequential Patterns	14. GSP,  15. PrefixSpan
Integrated Mining	16. CBA
Rough Sets	17. Finding reduct
Graph Mining	18. gSpan

En la segunda parte de esta primera charla, se presentaron los 10 grandes retos en minería de datos según (ICDM 2005). No he conseguido más información sobre la fuente del estudio. Ampliaré esta información cuando consiga las transparencias utilizadas en la charla. Los principales desafíos se engloban en las siguientes áreas:

1. Teoría. Definición de una teoría unificada ¿por qué funcionan los algoritmos? ¿cuales son los fundamentos del Data Mining?
2. Escalabilidad. Algoritmos que manejen gran cantidad de datos a gran velocidad.
3. Secuencialidad y series temporales. Técnicas para predecir acontecimientos a partir de datos históricos.
4. Datos complejos. Obtención conocimiento complejo a partir de datos complejos.
5. Minería de datos en redes sociales.
6. Minería de datos en bases de datos distribuidas.
7. Minería de datos para problemas biológicos y ambientales
8. Procesos de la minería de datos. Automatización, caracterización de los problemas, etc.
9. Seguridad, privacidad e integridad.
10. Minería de datos sobre datos no estáticos y datos cuya observación sea costosa.

Buscando más información sobre estos desafíos futuros he encontrado un artículo reciente sobre este tema titulado “Future tends in data mining“.

“Data Complexity”

Pretende dar respuesta a la pregunta “dado un problema de clasificación, ¿qué clasificador es mejor para el?”.  El libro de referencia es Data Complexity in Pattern Recognition. Para poder responder a esa pregunta se necesitan medidas de complejidad de los conjuntos de datos. Podemos encontrar diferentes medida de la complejidad de los datos en el trabajo de Tin Kam Ho, titulado “Measures of Geometrical Complexity in Classification Problems“.  Os dejo un enlace a las transparencias de la charla.

“How must I do my Experimental Study?”

Cuando nuestro trabajo de investigación consiste en el desarrollo de un nuevo algoritmo, es muy importante compararlo con con algoritmos de calidad. Muchos artículos son rechazados en revistas de prestigio, cuando se compara un nuevo algoritmo con versiones antiguas de nuestros competidores y no se incluyen comparativas con las últimas versiones más eficientes y precisas.  Justificar convenientemente la bondad del nuevo algoritmo utilizando  conjuntos de datos conocidos y métodos estadísticos es igualmente importante. En la dirección del grupo de investigación “Soft Computing and Intelligent Information Systems” que dirige el profesor Herrera, podemos encontrar información sobre estos métodos estadísticos y un software desarrollado por el profesor Salvador García, que genera los gráficos para incluir en documentos Latex utilizando a la entrada un fichero en formato CVS.

Data Mining: From the Top 10 Algorithms to the New Challenges

Descargar el Simulador de estrategias militares basado en el comportamiento de las hormigas

JJ ha subido hoy los fuentes y el ejecutable del simulador de estrategias militares basado en el comportamiento de las hormigas, como se ha denominado en la prensa (ver post Hormiguitas Militares en la prensa).

O mini-simulador SIMAUTAVA (mSS-HEXA, que lo llamamos nosotros). :-)

Éste se puede descargar en el sitio de geneura en la Forja de Rediris:

https://forja.rediris.es/projects/geneura/

(mini-simulador hCHAC)

El software ha sido implementado bajo una licencia GPL. ;)

Se ha incluido , aparte del ejecutable (para Windows) un manual de funcionamiento y varios mapas de ejemplo.

Además se han subido los fuentes del mismo, escritos en Borland Delphi 7.

Esperamos que sea útil para la gente interesada en el mismo.

Saludos a todos y gracias por el interés puesto en esta aplicación y los algoritmos.

Hormiguitas Militares en la prensa

Hoy (o más bien ayer) fue publicada una noticia sobre el simulador y los algoritmos implementados para el desarrollo de la Tesis Doctoral que leí hace dos semanas (ver post El fin del trabajo… la tesis!!!).

La noticia se incluyó inicialmente entre las notas de prensa de la UGR y posteriormente se hicieron eco de ella en Europa Press. A partir de ese momento, se incluyó un artículo o post al respecto en diversas publicaciones electrónicas.

Entre ellas se incluyen varios periódicos:

El Mundo, ABC, Ideal de Granada, La Opinión de Granada, 20 Minutos, El Periódico de Cataluña, e incluso El Economista. ;-)

Algunos portales:

Yahoo, Ya.com, Terra

Y también algunos blogs:

cienciaaldia, geeko, elsenderodelguerrero, thebluebulb

En general lo comentado en los artículos es bastante correcto desde el punto de vista ‘científico’, si bien en aquellos en los que se incluyen comentarios de lectores, se puede ver que la información no es todo lo completa o ‘estricta’ que quizá debiera ser.

Por ello quisiera hacer un par de apuntes sobre la noticia a fin de aclarar un poco más su contenido, al menos para aquellos que lean este post. ;)

- La primera anotación creo que es completamente necesaria y es que los algoritmos de optimización basada en colonias de hormigas fueron presentados en el año 1991 por Dorigo et al., si bien incluso sus estudios estaban basados por otros realizados varios años antes por Pierre-Paul Grassé y confirmados por Deneubourg sobre el comportamiento de las hormigas naturales.

- En segundo lugar y entrando en cuestiones ‘etico/políticas’, el software ha sido diseñado en colaboración con personal del ejército, pero no va a ser utilizado al menos a corto plazo. En cualquier caso su utilidad hasta el momento sería completamente ‘pacífica’, dado que la unidad solo se mueve, no dispara.

Del mismo modo su uso para aplicaciones ‘civiles’, como planificación de rutas de transporte, sería posible realizando una adaptación del simulador al nuevo problema.

- Es libre por ser un proyecto desarrollado como investigación dentro de la UGR, aunque bajo demanda en principio.

- Del mismo modo, el objetivo de la aplicación diseñada sería la automatización de avatares dentro de un simulador más complejo que el utilizado, los cuales deberían buscar y elegir el mejor camino de forma autónoma.

Si bien, también podría ser útil para que el capitán de una compañía planificase por adelantado la ruta a seguir en un campo de batalla conocido.

Me alegro de que esto haya trascendido, pero me gustaría que quedase todo lo más claro posible. ;)

Saludos.

El fin del trabajo… la tesis!!!

Bueno, bueno, este post es meramente informativo y me complace sobremanera escribirlo puesto que lo hago para comunicar a los lectores

¡¡¡ que ya he leido mi tesis!!! :D :D

La lectura fue el 5 de Mayo y he tardado tanto en escribir esto porque me prometí no tocar un teclado en dos semanas. ;) XD

El título de la misma es:

Resolución del Problema Militar de Búsqueda de Camino Óptimo Multiobjetivo mediante el uso de algoritmos de optimización Basados en Colonias de Hormigas.
(un poco largo si, pero como todos :D)

La presentación la podeis ver aquí mismo:

Y el PDF está disponible -> aquí <-

Espero que os interese. ;)

Saludos.

————————————————————————————–

English version:

I finished my PhD Thesis  last 5th of May… :D

(I have written this post today because I didn’t want to use a keyboard in two weeks XD).

It is titled Solving the Multiobjetive Military Pathfinding Problem Using Ant Colony Optimization Algorithms.

The presentation and the pdf of the Thesis are available (in spanish) at:

http://geneura.ugr.es/~amorag/tesis/

I wish it will be interesting for you. ;)

Bye bye. :D

Using Dissortative Mating Genetic Algorithms to Track the Extrema of Dynamic Deceptive Functions

Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behaviour is known as random mating. However, non-random schemes − in which individuals mate according to their kinship or likeness − are more common in natural systems. Previous studies indicate that, when applied to GAs, negative assortative mating (a specific type of non-random mating, also known as dissortative mating) may improve their performance (on both speed and reliability) in a wide range of problems. Dissortative mating maintains the genetic diversity at a higher level during the run, and that fact is frequently observed as an explanation for dissortative GAs ability to escape local optima traps. Dynamic problems, due to their specificities, demand special care when tuning a GA, because diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behaviour of dissortative mating GAs, namely the recently proposed Adaptive Dissortative Mating GA (ADMGA), on dynamic trap functions. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with deceptive and nearly deceptive trap functions indicate that ADMGA is able to outperform other GAs, some specifically designed for tracking moving extrema, on a wide range of tests, being particularly effective when speed of change is not very fast. When comparing the algorithm to a previously proposed dissortative GA, results show that performance is equivalent on the majority of the experiments, but ADMGA performs better when solving the hardest instances of the test set.

Full paper here.